History of a buggy bug

This is a full explainer of the DOS experienced by Prysm nodes at the Capella and Fusaka forks.

Checkpoints and Attestations

Before going into the bug details, let’s get a refresher on the technical aspects of attestation validation on Ethereum.

Ethereum has Epochs, consisting of 32 Slots, where blocks are proposed. When a validator, during its assigned slot attests to a block, it also attests to a target checkpoint. This target checkpoint is explicitly sent in the attestation for bookkeeping and accountability reasons, but can be completely derived from the attestation’s slot and block roots. The associated checkpoint is easier to visualize than to define, so let’s draw some cases first before jumping into formal definitions.

Happy case

Here is an attestation during slot 60, a slot in epoch 1, for the block proposed during that slot. The corresponding checkpoint is drawn in orange and corresponds to the block of slot 32.

Missed slot 0

Here is again that attestation during slot 60, for the block proposed during that slot, but the block of slot 32 was missed, so the corresponding checkpoint is drawn in orange and corresponds to the block of slot 31.

If the block at slot 32 was proposed but reorged, the situation will look very similar; the checkpoint will still correspond to the block at slot 31.

Skipped attestation slot

In this case the block of slot 60 was missed or skipped. The attester votes in this case for the block in slot 59, and the checkpoint is the same block in slot 32.

If the block of slot 60 was actually present, but the attester didn’t see it in time, the situation would be similar; it will attest to 59 during its turn:

Forked scenarios

In the event of forks, the same rules above apply; checkpoints are determined by the voted block. Attestations are marked in green and checkpoints in orange. Here’s an attestation at slot 60 for the block in slot 60.

Here is an attestation in slot 60 by a validator that considers the fork with block 58 as its head, in this case its checkpoint is given by the block in slot 31.

Skipped slots across epoch boundary

In this situation there were no blocks between slot 31 and slot 60, the attester of slot 60 votes for its head at slot 31. Here the block for the head attestation and the checkpoint block coincide.

lagging client

The previous situation happens more often for a lagging client. In this case the blocks were present but the client did not receive them or couldn’t process them and is still attesting for old blocks across the epoch boundary. The block and the checkpoint for the attestation coincide with block 31 but the slot of the attestation is still 60.

Forked minorities

In forked scenarios, especially when some minority of nodes is following a fork, the following situation arises. This case, for example, would happen when a minority client declares the canonical chain invalid.

Checkpoint definition

Now armed with many examples, we can give some formal definitions. An attestation consists of a pair (slot, block). The slot component is the slot at which the validator is submitting its attestation. The block component is the Ethereum block that the validator considers the head of the chain.

From this pair one can infer the target checkpoint of the attestation. This is the ancestor of the block component proposed during the highest slot lower than or equal to the very first slot of the same epoch as the slot component of the attestation.

Yes this is a mouthful, but hopefully the above examples help demonstrate this concept well. In all these examples, the attestation slot was 60, which is during epoch 1. The first slot of that epoch is 32.

Attestation’s head state

When a node receives an attestation, it needs to perform a series of validations. The most crucial of which is does the attester belong to the committee for this slot? The problem with this statement is that the committee depends on the reality of the chain. In a forked scenario, the committees of one branch differ from those in the other branch.

Consider the laggy client situation above which is the most prominent for this bug

In the actual chain there is no fork; all blocks are present. But from the point of view of that attester in slot 31, its head state is the state that was obtained after applying block 31, advanced all the way, as if all blocks were missing, to slot 60. If that client were to cast an attestation at slot 1601, then it would need to advance the state of slot 31 all the way up to 1601. The beacon committee of attesters may be very different from that in the canonical chain.

However, honest nodes must validate these attestations nonetheless. There are many reasons for this. These attestations support the chain containing block 31, and therefore support the canonical chain containing the block at slot 60, even though they are voting on a contending fork! If there were to exist yet another fork that started before slot 31, these attestations would support the canonical branch and not the other fork.

Notice that this may also be the case for the forked minorities:

In this case, the attestation for block 31 does not support the branch for 60 directly, but it does with respect to another plausible branch starting before the block at 30. Again, if the attestation were for slot 1601 instead of 60, the committees may be very different from those in the canonical branch. To validate the attestation, the node needs to recreate that head state.

Beacon committee selection

The beacon committee selection is computed in the following helpers from the consensus client specification:

def get_beacon_committee(
    state: BeaconState, slot: Slot, index: CommitteeIndex
) -> Sequence[ValidatorIndex]:
    """
    Return the beacon committee at ``slot`` for ``index``.
    """
    epoch = compute_epoch_at_slot(slot)
    committees_per_slot = get_committee_count_per_slot(state, epoch)
    return compute_committee(
        indices=get_active_validator_indices(state, epoch),
        seed=get_seed(state, epoch, DOMAIN_BEACON_ATTESTER),
        index=(slot % SLOTS_PER_EPOCH) * committees_per_slot + index,
        count=committees_per_slot * SLOTS_PER_EPOCH,
    )

The key ingredients are the seed and the indices that are required. The seed is fixed at the end of the epoch 2 epochs before the attestation, so any state between the beginning of the attestation epoch - 1 and the attestation will have the exact same seed.

To understand the indices entry, we need to know how the validator active status can change. The call in the above snippet follows the following path

def get_active_validator_indices(state: BeaconState, epoch: Epoch) -> Sequence[ValidatorIndex]:
    """
    Return the sequence of active validator indices at ``epoch``.
    """
    return [
        ValidatorIndex(i) for i, v in enumerate(state.validators) if is_active_validator(v, epoch)
    ]

and in turn

def is_active_validator(validator: Validator, epoch: Epoch) -> bool:
    """
    Check if ``validator`` is active.
    """
    return validator.activation_epoch <= epoch < validator.exit_epoch

From this we see the only thing that matters is the validator’s activation_epoch and its exit_epoch. The former only changes at epoch transitions and the latter, while it may change within an epoch because of slashings, can only be set to an epoch in the future. This takes at the very least 5 epochs after the event because of MAX_SEED_LOOKAHEAD:

def compute_activation_exit_epoch(epoch: Epoch) -> Epoch:
    """
    Return the epoch during which validator activations and exits initiated in ``epoch`` take effect.
    """
    return Epoch(epoch + 1 + MAX_SEED_LOOKAHEAD)

So, summarizing:

Attestation’s target state

The above summary shows that the state right after the target checkpoint, advanced to the attestation’s epoch, has exactly the same seed and same active validator indices as the attestation’s sender. This is because it is on the same branch and at the same epoch, and active validator indices can only change at epoch transitions. This is why clients often use these states to validate attestations: since target states happen to be often at epoch boundaries, clients tend to have them cached, or easily recoverable. So often times, instead of trying to reproduce the attester’s view, clients just use the cached target state.

Head state is almost always good

As we saw in the previous section, to validate an attestation, all we need is to have a state with the same seed and active validator indices as the point of view of the attester. When we are finalizing, this is guaranteed to be the head state of the beacon node, which is always quickly and cheaply available. The reason being the composition of the following statements:

• The finalized checkpoint is two epochs ago, therefore the seed is always the same as long as the head being voted does descend from the finalized checkpoint.
• Nodes do not consider attestations for blocks that aren’t descendants of the finalized checkpoint, therefore the seed is guaranteed to be the same as the head state.
• The head state will have the same active validator indices as the attester. The reason is that even if the head block root is on a very long fork as in the forked minorities case, all activations and exits could not change the list of active validator indices in the case we are finalizing the previous epoch consistently. Notice that this works even if the attestation is for a previous epoch and there are actually different active validators in the current epoch from the point of view of the head state.

Thus, nodes typically will just use the head state, which is guaranteed to have the right list of active validator indices, to validate the attesters’ committee. The seed, and the shuffling of indices for the committee, is always cached with the finalized state in this happy case.

The Capella bug

Right after the Capella fork, Prysm (and Teku and perhaps other CL clients) were stressed to the point of not being able to process blocks. The reason was that they kept trying to produce a state that was compatible with the attester’s view. In most cases, head would have been good enough; in some other cases (as we will see below) it makes more sense to just drop the attestation. At that time Prysm introduced the following heuristic to deal with this DOS:

• When an attestation arrives, if it is for a recent state that is compatible with the head view, use the head state to validate it.
• In the remaining cases, we looked for the target checkpoint. If it is a known checkpoint from our forkchoice’s point of view, we would regenerate the state and process the attestation. If it wasn’t, then we would just ignore the attestation.

For example, a lagging client’s attestation is very likely to be ignored, since its checkpoint

is not really a checkpoint in any possible head state in the beacon’s forkchoice: slot 31 has only a child in slot 32 and any branch that we know that descends from 31 will have 32 as a valid checkpoint.

However, forked minorities will still have their attestations processed. In their case, their checkpoints

are known valid checkpoints from our point of view: although the canonical chain has progressed and has 32 as checkpoint for any attestation, we know that there is a chain that will take 31 as a valid checkpoint, thus we do the extra work to process these attestations.

This heuristic worked to get rid of essentially all the spam from lagging clients and we managed to stay resilient afterwards.

When head state is just not good enough

There was a crucial error in our Capella fix. When we rushed to ship that fix, we included a clause that was fundamentally flawed:

This absolutely works if the chain is finalizing, as we have seen already, but if the chain is not, this is a consensus bug!

And this in fact was triggered in testnets for Hoodi when they were not finalizing. We noticed that our nodes kept banning other clients and only peered with Prysm. The reason was lagging peers sending useless attestations again! This time Prysm was too eager to declare the attestation as invalid, using the head state to perform the validation. Let’s look again at the lagging client’s attestation in a non-forked situation but with more realistic numbers:

In this situation, the head state has neither the same seed nor the same active validator indices as the checkpoint from the lagging client using slot 31 to attest.

In this situation, nodes were falling behind several epochs and sending attestations for old canonical blocks. When the active validator set for the epoch changed, Prysm would deem those attestations invalid by using the wrong state (the head state at slot 257 in the above example) to validate them.

Fulu’s bug, Capella v2

In order to fix the above peering issue and the wrong assumption that Prysm was using when validating these old attestations, we included a fix to only use the head state if it was compatible with the target state. That is, if the head state had the same target state as the attestation.

Namely, with this mechanism, an attestation like the happy case, or even with small reorgs or skipped slots:

will be correctly validated by the head state since both the head state (at slot 60 here) and the attestation state (for 59) would have the same target checkpoint at 32.

However, the lagging client problem became again an issue. The targets in the lagging client case are different:

Head at slot 60 has target 32, while the attestation has target 31. In this case, the head state, as we have seen before, is good enough to validate. But Prysm instead opted to regenerate the state of 31.

This ultimately led to the DOS that affected the chain after the Fulu fork.

The flag was originally inverted

When we removed the usage of head state, we also made sure to ignore any attestations from lagging clients as described above as long as they were lagging more than 2 epochs. This made the previous epoch the only DOS vector. We knew this could be a vector, so we added a feature flag to ignore those as well. We tested in Hoodi, a less stable network, for over a month, and these attestations and regenerations were a minor hiccup, so we decided to keep the flag as non-default.