# Witholding attack mitigation

## 1. The attack

Consider the following forkchoice diagram


- At the start of Epoch 12, the previous Epoch 11 has not been justified. The justified checkpoint has Epoch 10 (marked in red).
- The attacker is witholding a chain of valid blocks from Epoch 11, starting from the block marked in yellow. Those blocks have enough votes within them to justify Epoch 11.
- The honest chain in Epoch 12 has advanced, from their perspective the attacker's blocks are missing in Epoch 11.
- The blocks in Epoch 12 have enough votes to justify Epoch 11, these nodes have `unrealized_justified_checkpoint.epoch = 11`. But the realized justification checkpoint is still at Epoch 10.

In this scenario, the attacker releases his blocks:


An honest validator seeing these blocks, since they are from the previous Epoch, will pull tips, realizing the justified checkpoint with Epoch 11. Thus, honest validators will see two valid chains, one with an unrealized justified checkpoint at epoch 11, and the attacker's chain with realized justified checkpoint at epoch 11.

Honest validators are forced, by FFG rules, to switch to the attacker's branch


**Remark** It was noticed by D. Ryan that this attack can happen with relatively the same frequency even without pull-tips.

## 2. Defensive tip pulling

We propose the following defense against the above attack. Let `current_epoch` be the store's current epoch, that is `compute_epoch_at_slot(get_current_slot(store))`. The one rule we add is:

Whenever `store.justified_checkpoint.Epoch + 1 == current_epoch` then pull tips from all Epochs *up to `store.justified_checkpoint.Epoch`*. Explicitly this means the following. Let `n` be a forkchoice node. We consider `n` to be viable for head if it satisfies the following

- It is a descendant of the current justified checkpoint
- Let `state = store.block_states[n.root]`, `future_state = process_justification_and_finalization(state)` and `bits = future_state.justification_bits`. We require `bits[1] = 0b1`, that is after processing justification, the previous epoch would be justified.

**Illustration**:

## 3. Possible specification

We propose the following specification based on A. Asgaonkar's [pulled tips specification](https://github.com/adiasg/consensus-specs/pull/4). It is very poorly optimized so that it changes only one function.

def filter_block_tree(store: Store, block_root: Root, blocks: Dict[Root, BeaconBlock]) -> bool:
    block = store.blocks[block_root]
    children = [
        root for root in store.blocks.keys()
        if store.blocks[root].parent_root == block_root
    ]

    # If any children branches contain expected finalized/justified checkpoints,
    # add to filtered block-tree and signal viability to parent.
    if any(children):
        filter_block_tree_result = [filter_block_tree(store, child, blocks) for child in children]
        if any(filter_block_tree_result):
            blocks[block_root] = block
            return True
        return False

    correct_justified = false
    correct_finalized = false
    if store.justified_checkpoint.epoch == GENESIS_EPOCH: 
        corrent_justified = true
        corret_finalized = true
    if store.realized_justifications[block_root] == store.justified_checkpoint:
        correct_justified = true
    if store.realized_finalizations[block_root] == store.finalized_checkpoint:
        correct_finalized = true
        
    block_epoch = compute_epoch_at_slot(block.slot)    
    current_epoch = compute_epoch_at_slot(get_current_slot(store))    
    
    if !correct_justified and block_epoch == current_epoch:
        if store.justified_checkpoint.epoch + 1 == current_epoch:
            head_state = store.block_states[block_root]
            future_state = process_justification_and_finalization(head_state)
            correct_justified = future_state.justification_bits[1] == 0b1
            if correct_justified:
                correct_finalized = true
                
    # If expected finalized/justified, add to viable block-tree and signal viability to parent.
    if correct_justified and correct_finalized:
        blocks[block_root] = block
        return True

    # Otherwise, branch not viable
    return False

<!--
Earlier version:

correct_justified = false
correct_finalized = false
if store.justified_checkpoint.epoch == GENESIS_EPOCH:
corrent_justified = true
corret_finalized = true
if store.realized_justifications[block_root] == store.justified_checkpoint:
correct_justified = true
if store.realized_finalizations[block_root] == store.finalized_checkpoint:
correct_finalized = true

if !correct_justified:
current_epoch = compute_epoch_at_slot(get_current_slot(store))
if store.justified_checkpoint.epoch + 1 == current_epoch:
head_state = store.block_states[block_root]
future_state = process_justification_and_finalization(head_state)
correct_justified = future_state.justification_bits[1] == 0b1
if correct_justified:
correct_finalized = true -->

**Note**: In the code block `if !correct_justified and block_epoch == current_epoch` we only check if leaf blocks from the current epoch have justified the previous epoch (i.e., `correct_justified = future_state.justification_bits[1] == 0b1`). We do not check leaf blocks from the previous epoch because they are already "pulled-up" by the pull-up tips logic and their justifications are checked in the previous code block using `store.realized_justifications`.

## 4. Proof that the attack is no longer effective
In the situation described in Section 1. After the attacker reveals his blocks and they are imported to forkchoice, an honest validator will have `store.justified_checkpoint.epoch == 11`. The honest chain will still have valid tips as viable as they will satisfy the condition:

...
            correct_justified = (
                future_state.justification_bits[1] = 0b1 and
                get_ancestor(store, block_root, justified_slot) == justified_root
            )
...

The attackers blocks will have to compete with LMD weight vs the honest chain's weight plus proposer boost.

## 5. Voting analysis

### 5.1 Deadlocks
One possible concern is regarding attestations by honest validators. The source vote is taken from the head state `justification_checkpoint`. A validator voting for the attacker's branch will vote with `source.epoch = 11` while a validator voting for the honest branch will vote with `source.epoch = 10`. This represents a deep departure from current specifications, in that honest validators voting in the honest chain will have differing `10 = source.epoch != store.justified_checkpoint.epoch = 11`. Votes for either branch during epoch 12 will have epoch 12 as target.

Epoch 11 will be justified during epoch 13 on either the attackers branch or the honest branch, since this was a requirement for a viable head. Thus, any future vote by honest validators will have `source.epoch >= 11`, and `target.epoch >= 13` without the possibility of deadlocks.

### 5.2 Split views
An earlier iteration of this defensive mechanism suffered from a possible network split, where the attacker would release his blocks to some validators during epoch 11, and others during epoch 12. We show here that both sets of validators will continue voting on the honest branch. Indeed those validators that saw the attackers block during epoch 11, will have `store.justified_checkpoint.epoch = 11` during all of epoch 12 since they would have updated their justification point during `on_tick`. Because of the new rule, all blocks from the honest chain that carry enough FFG information to justify 11 will be viable for head.

On the other hand, those validators that saw the attacker's blocks during epoch 12, will start the epoch with `store.justified_checkpoint.epoch = 10`. They will import the attacker's blocks with `on_block`, at which point the *pull tips* mechanism will update the store's justification checkpoint to epoch 11. The new rule will make any tip from the current epoch 12 viable for head as long as it carries information to justify epoch 11 during the transition to 13.

### 5.3 Split vote

A possible drawback of this approach is that honest validators see an LMD fight between the attacker's blocks and the honest chain. Even though the full network may be participating, and voting for epoch 12 as target, one branch is using epoch 10 as source and the other is using epoch 11 as source, therefore these votes will not count towards the same supermajority link in justifying epoch 12.

An attacker with enough attestation stake may leverage this to cause a split vote and keep the network not justifying. At this stage the attack becomes equivalent to the bouncing attack to which we are susceptible anyway. The current mitigation does not make this attack more or less plausible.

## 6 Non-defensive tip pulling

An alternative to defensive tip pulling is to always *pull up to `store.justification_checkpoint.epoch`*. In the situation of the attack described above the behavior of honest validator is **identical** to defensive tip pulling. This mechanism has the advantage of lower specification complexity. In terms of specification, this amounts to changing `filter_block_tree` according to [Pull #2 in Asgaonkar's specification](https://github.com/adiasg/consensus-specs/pull/2) from

store.u_justified_checkpoints[block_root] == store.justified_checkpoint

to requiring that the block is a descendant of `store.justified_checkpoin` and

store.u_justified_checkpoints[block_root] >= store.justified_checkpoint

A drawback of this implementation is that whenever the previous epoch has not been justified, it allows for a fork. Consider the situation


The chain is following honestly with low participation and we have not justified epoch 11. There exists one block that will be the first block during 12 (this may be modified slightly to work in a future epoch) that has enough FFG votes to justify 11. In this case this is the red block. The attacker can fork off the last honest block (in this case the green block) as long as his block has enough FFG votes to justify epoch 11. These forks are tipically shallow since any attestation toward justifying epoch 11 included in the orphaned block (green) will have to be countered by some attestation in the attacking block (red). Given that attestations for epoch 11 would have been from the previous epoch, these forks would be possible only at the beginning of the epoch.

Note however that these forks will be possible every time that the network fails to justify an epoch by a small drop in participation. Regardless of the percentage stake of the attacker.

Defensive tip pulling as in section 2 does not suffer from this since both the green and the red blocks will be considered valid, given that epoch 11 has not been justified.

## 7. Finality reversal
Care must be taken to avoid a situation where we could revert finality. Consider the following scenario
- During Epoch N-2, it didn't justify. The justified checkpoint is in N-3.
- During Epoch N-1, the proposer of block A has enough votes to justify both N-1 (checkpoint root J) and N-2 (checkpoint root F), thus enough to finalize N-3. But this block is witheld
- During Epoch N, the canonical chain advances, enough attestations to justify N-1 were included in blocks during N, but not enough to justify neither N-2 nor N itself.

In this situation, the canonical chain head, block C has `justified_checkpoint.Epoch = N-3`, and the unrealized ones: `u_justified_checkpoint.Epoch == N-1` and `u_finalized_checkpoint.Epoch < N-3`

- The attacker's block A is revealed, pull tips immediately realize the justifications, so that we have

store.justified_checkpoint.epoch = N-1
store.finalized_checkpoint.epoch = N-3

Now the canonical head block C satifies the check of the current (as of commit `431861f9b3af`) PR #11:

    # If previous epoch is justified, pull up all tips to at least the previous epoch
    if current_epoch > GENESIS_EPOCH and store.justified_checkpoint.epoch == current_epoch - 1:
        correct_justified = (
            store.u_justified_checkpoints[block_root].epoch >= current_epoch - 1
        )
        correct_finalized = correct_justified

Therefore with the proposed fix, the chain C will become canonical.
- The chain advances and crosses the Epoch boundary to N+1. At this point Epoch N-1 becomes justified on state but since Epoch N-2 is not, the finalized checkpoint is still before N-3.

To account for this situation we need to make sure that the canonical chain actually increases finalization

correct_finalized = store.u_finalized_checkpoints[block_root].epoch >= store.finalized_checkpoint.epoch

## 8. Other considerations

### 8.1 finality reversal in Beacon API
Even though the pull tips mechanism already allow for a virtual reversal of finality. The proposed mitigation attack here makes it more evident. Consider a validator that has been temporarily offline and did not see neither the attacker's blocks nor the honest chain in the situation of the attack of section 1. Suppose this validator sees the attacker's blocks before. His head state will have `justification_checkpoint.epoch = 11`. As soon as the honest chain appears, his head state will have `justification_checkpoint.epoch = 10`. This drop will continue throughout the full epoch 12, as opposed to the tipical situation with pull tips in which this drop is only until the node imports a single block which immediately realizes the new justification.

We believe this will impact considerably the UX experience unless some extra care is taken with the endpoints API.

### 8.2 An optimization with a security drawback

On the the drawbacks of pulling tips up to N-1 is that either we need to track this intermediate justified checkpoint, or check that the node is a descendant of the current justified checkpoint as in the specification in section 3 or the filtering in section 6. Relaxing this condition to allow any block with unrealized justification >= current justification, may result in blocks in epoch 12 that would justify epoch 12 on a **different fork**. Perhaps allowing this when epoch 11 (`current_epoch - 1`) is not justified yet, is not so problematic.