Part 3: Annotated Specification

Fork Choice

Phase 0 Fork Choice

This section covers the Phase 0 Fork Choice document. It is based on the Capella, v1.3.0, spec release version. For an alternative take, I recommend Vitalik's annotated fork choice document.

Block-quoted content below (with a sidebar) has been copied over verbatim from the specs repo, as has all the function code.

The head block root associated with a store is defined as get_head(store). At genesis, let store = get_forkchoice_store(genesis_state, genesis_block) and update store by running:

  • on_tick(store, time) whenever time > store.time where time is the current Unix time
  • on_block(store, block) whenever a block block: SignedBeaconBlock is received
  • on_attestation(store, attestation) whenever an attestation attestation is received
  • on_attester_slashing(store, attester_slashing) whenever an attester slashing attester_slashing is received

Any of the above handlers that trigger an unhandled exception (e.g. a failed assert or an out-of-range list access) are considered invalid. Invalid calls to handlers must not modify store.

Updates to the Store arise only through the four handler functions: on_tick(), on_block(), on_attestation(), and on_attester_slashing(). These are the four senses through which the fork choice gains its knowledge of the world.


  1. Leap seconds: Slots will last SECONDS_PER_SLOT + 1 or SECONDS_PER_SLOT - 1 seconds around leap seconds. This is automatically handled by UNIX time.

Leap seconds will no longer occur after 2035. We can remove this note after that.

  1. Honest clocks: Honest nodes are assumed to have clocks synchronized within SECONDS_PER_SLOT seconds of each other.

In practice, the synchrony assumptions are stronger than this. Any node whose clock is more than SECONDS_PER_SLOT / INTERVALS_PER_SLOT (four seconds) adrift will suffer degraded performance and can be considered Byzantine (faulty), at least for the LMD GHOST fork choice.

  1. Eth1 data: The large ETH1_FOLLOW_DISTANCE specified in the honest validator document should ensure that state.latest_eth1_data of the canonical beacon chain remains consistent with the canonical Ethereum proof-of-work chain. If not, emergency manual intervention will be required.

Post-Merge, consistency between the execution and consensus layers is no longer an issue, although we retain the ETH1_FOLLOW_DISTANCE for now.

  1. Manual forks: Manual forks may arbitrarily change the fork choice rule but are expected to be enacted at epoch transitions, with the fork details reflected in state.fork.

Manual forks are sometimes called hard forks or upgrades, and are planned in advance and coordinated. They are different from the inadvertent forks that the fork choice rule is designed to resolve.

  1. Implementation: The implementation found in this specification is constructed for ease of understanding rather than for optimization in computation, space, or any other resource. A number of optimized alternatives can be found here.

After reading the spec you may be puzzled by the "ease of understanding" claim. However, it is certainly true that several of the algorithms are far from efficient, and a great deal of optimisation is needed for practical implementations.


Name Value

Only blocks that arrive during the first 1 / INTERVALS_PER_SLOT of a slot's duration are eligible to have the proposer score boost added. This moment is the point in the slot at which validators are expected to publish attestations declaring their view of the head of the chain.

In the Ethereum consensus specification INTERVALS_PER_SLOT neatly divides SECONDS_PER_SLOT, and all time quantities are strictly uint64 numbers of seconds. However, other chains that run the same basic protocol as Ethereum might not have this property. For example, the Gnosis Beacon Chain has five-second slots. We changed Teku's internal clock from seconds to milliseconds to support this, which is technically off-spec, but nothing broke.


Name Value
  • The proposer score boost is worth PROPOSER_SCORE_BOOST percentage of the committee's weight, i.e., for slot with committee weight committee_weight the boost weight is equal to (committee_weight * PROPOSER_SCORE_BOOST) // 100.

Proposer boost is a modification to the fork choice rule that defends against a so-called balancing attack. When a timely block proposal is received, proposer boost temporarily adds a huge weight to that block's branch in the fork choice calculation, namely PROPOSER_SCORE_BOOST percent of the total effective balances of all the validators assigned to attest in that slot.

The value of PROPOSER_SCORE_BOOST has changed over time as the balancing attack has been analysed more thoroughly.

The basic trade-off in choosing a value for PROPOSER_SCORE_BOOST is between allowing an adversary to perform "ex-ante" or "ex-post" reorgs. Setting PROPOSER_SCORE_BOOST too high makes it easier for an adversarial proposer to perform ex-post reorgs - it gives the proposer disproportionate power compared with the votes of validators. Setting PROPOSER_SCORE_BOOST too low makes it easier for an adversary to perform ex-ante reorgs. Caspar Schwarz-Schilling covers these trade-offs nicely in his Liscon talk, The game of reorgs in PoS Ethereum.1



class LatestMessage(object):
    epoch: Epoch
    root: Root

This is just a convenience class for tracking the most recent head vote from each validator - the "LM" (latest message) in LMD GHOST. Epoch is a uint64 type, and Root is a Bytes32 type. The Store holds a mapping of validator indices to their latest messages.


The Store is responsible for tracking information required for the fork choice algorithm. The important fields being tracked are described below:

  • justified_checkpoint: the justified checkpoint used as the starting point for the LMD GHOST fork choice algorithm.
  • finalized_checkpoint: the highest known finalized checkpoint. The fork choice only considers blocks that are not conflicting with this checkpoint.
  • unrealized_justified_checkpoint & unrealized_finalized_checkpoint: these track the highest justified & finalized checkpoints resp., without regard to whether on-chain realization has occurred, i.e. FFG processing of new attestations within the state transition function. This is an important distinction from justified_checkpoint & finalized_checkpoint, because they will only track the checkpoints that are realized on-chain. Note that on-chain processing of FFG information only happens at epoch boundaries.
  • unrealized_justifications: stores a map of block root to the unrealized justified checkpoint observed in that block.

These explanatory points were added in the Capella upgrade2. We will expand on them below in the appropriate places.

class Store(object):
    time: uint64
    genesis_time: uint64
    justified_checkpoint: Checkpoint
    finalized_checkpoint: Checkpoint
    unrealized_justified_checkpoint: Checkpoint
    unrealized_finalized_checkpoint: Checkpoint
    proposer_boost_root: Root
    equivocating_indices: Set[ValidatorIndex]
    blocks: Dict[Root, BeaconBlock] = field(default_factory=dict)
    block_states: Dict[Root, BeaconState] = field(default_factory=dict)
    checkpoint_states: Dict[Checkpoint, BeaconState] = field(default_factory=dict)
    latest_messages: Dict[ValidatorIndex, LatestMessage] = field(default_factory=dict)
    unrealized_justifications: Dict[Root, Checkpoint] = field(default_factory=dict)

A node's Store records all the fork choice related information that it has about the outside world. In more classical terms, the Store is the node's view of the network. The Store is updated only by the four handler functions.

The basic fields are as follows.

  • time: The wall-clock time (Unix time) of the last call to the on_tick() handler. In theory this is update continuously; in practice only at least two or three times per slot.
  • justified_checkpoint: Our node's view of the currently justified checkpoint.
  • finalized_checkpoint: Our node's view of the currently finalised checkpoint.
  • blocks: All the blocks that we know about that are descended from the finalized_checkpoint. The fork choice spec does not describe how to prune the Store, so we would end up with all blocks since genesis if we were to follow it precisely. However, only blocks descended from the last finalised checkpoint are ever considered in the fork choice, and the finalised checkpoint only increases in height. So it is safe for client implementations to remove from the Store all blocks (and their associated states) belonging to branches not descending from the last finalised checkpoint.
  • block_states: For every block in the Store, we also keep its corresponding (post-)state. These states are mostly used for information about justification and finalisation.
  • checkpoint_states: If there are empty slots immediately before a checkpoint then the checkpoint state will not correspond to a block state, so we store checkpoint states as well, indexed by Checkpoint rather than block root. The state at the last justified checkpoint is used for validator balances, and for validating attestations in the on_attester_slashing() handler.
  • latest_messages: The set of latest head votes from validators. When the on_attestation() handler processes a new head vote for a validator, it gets added to this set and the old vote is discarded.

The following fields were added at various times as new attacks and defences were found.

  • proposer_boost_root was added when proposer boost was implemented as a defence against the LMD balancing attack. It is set to the root of the current block for the duration of a slot, as long as that block arrived within the first third of a slot.
  • The equivocating_indices set was added to defend against the equivocation balancing attack. It contains the indices of any validators reported as having committed an attester slashing violation. These validators must be removed from consideration in the fork choice rule until the last justified checkpoint state catches up with the fact that the validators have been slashed.
  • The unrealized_justified_checkpoint and unrealized_finalized_checkpointfields were added in the Capella update. They are used to avoid certain problems with unrealised justification that the old version of filter_block_tree() suffered.
  • Also added in the Capella update was unrealized_justifications, which is a map of block roots to unrealised justification checkpoints. It is maintained by compute_pulled_up_tip(). For every block, it stores the justified checkpoint that results from running process_justification_and_finalization() on the block's post-state. In the beacon state, that calculation is done only on epoch boundaries, so, within the fork choice, we call the result "unrealised".

For non-Pythonistas, Set and Dict are Python generic types. A Set is an unordered collection of objects; a Dict provides key–value look-up.


def is_previous_epoch_justified(store: Store) -> bool:
    current_slot = get_current_slot(store)
    current_epoch = compute_epoch_at_slot(current_slot)
    return store.justified_checkpoint.epoch + 1 == current_epoch

Based on the current time in the Store, this function returns True if the checkpoint at the start of the previous epoch has been justified - that is, has received a super-majority Casper FFG vote.

Used by filter_block_tree()


The provided anchor-state will be regarded as a trusted state, to not roll back beyond. This should be the genesis state for a full client.

Note With regards to fork choice, block headers are interchangeable with blocks. The spec is likely to move to headers for reduced overhead in test vectors and better encapsulation. Full implementations store blocks as part of their database and will often use full blocks when dealing with production fork choice.

def get_forkchoice_store(anchor_state: BeaconState, anchor_block: BeaconBlock) -> Store:
    assert anchor_block.state_root == hash_tree_root(anchor_state)
    anchor_root = hash_tree_root(anchor_block)
    anchor_epoch = get_current_epoch(anchor_state)
    justified_checkpoint = Checkpoint(epoch=anchor_epoch, root=anchor_root)
    finalized_checkpoint = Checkpoint(epoch=anchor_epoch, root=anchor_root)
    proposer_boost_root = Root()
    return Store(
        time=uint64(anchor_state.genesis_time + SECONDS_PER_SLOT * anchor_state.slot),
        blocks={anchor_root: copy(anchor_block)},
        block_states={anchor_root: copy(anchor_state)},
        checkpoint_states={justified_checkpoint: copy(anchor_state)},
        unrealized_justifications={anchor_root: justified_checkpoint}

get_forkchoice_store() initialises the fork choice Store object from an anchor state and its corresponding block (header). As noted, the anchor state could be the genesis state. Equally, when using a checkpoint sync, the anchor state will be the finalised checkpoint state provided by the node operator, which will be treated as if it is a genesis state. In either case, the latest_messages store will be empty to begin with.


def get_slots_since_genesis(store: Store) -> int:
    return (store.time - store.genesis_time) // SECONDS_PER_SLOT

Self explanatory. This one of only two places that store.time is used, the other being in the proposer boost logic in the on_block() handler.

Used by get_current_slot()


def get_current_slot(store: Store) -> Slot:
    return Slot(GENESIS_SLOT + get_slots_since_genesis(store))

Self explanatory. GENESIS_SLOT is usually zero.

Used by get_voting_source(), filter_block_tree(), compute_pulled_up_tip(), on_tick_per_slot, validate_target_epoch_against_current_time(), validate_on_attestation(), on_tick(), on_block()
Uses get_slots_since_genesis()


def compute_slots_since_epoch_start(slot: Slot) -> int:
    return slot - compute_start_slot_at_epoch(compute_epoch_at_slot(slot))

Self explanatory.

Used by on_tick_per_slot()
Uses compute_epoch_at_slot(), compute_start_slot_at_epoch()


def get_ancestor(store: Store, root: Root, slot: Slot) -> Root:
    block = store.blocks[root]
    if block.slot > slot:
        return get_ancestor(store, block.parent_root, slot)
    return root

Given a block root root, get_ancestor() returns the ancestor block (on the same branch) that was published at slot slot. If there was no block published at slot, then the ancestor block most recently published prior to slot is returned.

This function is sometimes used just to confirm that the block with root root is descended from a particular block at slot slot, and sometimes used actually to retrieve that ancestor block's root.

Uses get_ancestor() (recursively)
Used by get_weight(), filter_block_tree(), validate_on_attestation(), on_block(), get_ancestor() (recursively)


def get_weight(store: Store, root: Root) -> Gwei:
    state = store.checkpoint_states[store.justified_checkpoint]
    unslashed_and_active_indices = [
        i for i in get_active_validator_indices(state, get_current_epoch(state))
        if not state.validators[i].slashed
    attestation_score = Gwei(sum(
        state.validators[i].effective_balance for i in unslashed_and_active_indices
        if (i in store.latest_messages
            and i not in store.equivocating_indices
            and get_ancestor(store, store.latest_messages[i].root, store.blocks[root].slot) == root)
    if store.proposer_boost_root == Root():
        # Return only attestation score if ``proposer_boost_root`` is not set
        return attestation_score

    # Calculate proposer score if ``proposer_boost_root`` is set
    proposer_score = Gwei(0)
    # Boost is applied if ``root`` is an ancestor of ``proposer_boost_root``
    if get_ancestor(store, store.proposer_boost_root, store.blocks[root].slot) == root:
        committee_weight = get_total_active_balance(state) // SLOTS_PER_EPOCH
        proposer_score = (committee_weight * PROPOSER_SCORE_BOOST) // 100
    return attestation_score + proposer_score

Here we find the essence of the GHOST3 protocol: the weight of a block is the sum of the votes for that block, plus the votes for all of its descendant blocks. We include votes for descendants when calculating a block's weight because a vote for a block is an implicit vote for all of that block's ancestors as well - if a particular block gets included on chain, all its ancestors must also be included. To put it another way, we treat validators as voting for entire branches rather than just their leaves.

Ignoring the proposer boost part for the time being, the main calculation being performed is as follows.

    state = store.checkpoint_states[store.justified_checkpoint]
    unslashed_and_active_indices = [
        i for i in get_active_validator_indices(state, get_current_epoch(state))
        if not state.validators[i].slashed
    attestation_score = Gwei(sum(
        state.validators[i].effective_balance for i in unslashed_and_active_indices
        if (i in store.latest_messages
            and i not in store.equivocating_indices
            and get_ancestor(store, store.latest_messages[i].root, store.blocks[root].slot) == root)

We only consider the votes of active and unslashed validators. (Slashed validators might still be in the exit queue and are technically "active", at least according to is_active_validator().) The exclusion of validators that have been slashed in-protocol at the last justified checkpoint was added in the Capella specification to complement the on_attester_slashing() handler. It will additionally exclude validators slashed via proposer slashings, and validators slashed long ago (when the exit queue is long) and for which we have discarded the attester slashing from the Store.

Given a block root, root, this adds up all the votes for blocks that are descended from that block. More precisely, it calculates the sum of the effective balances of all validators whose latest head vote was for a descendant of root or for root itself. It's the fact that we're basing our weight calculations only on each validator's latest vote that makes this "LMD" (latest message drive) GHOST.

Diagram of a block tree with weights and latest attesting balances shown for each block.

BNB_N is the sum of the effective balances of the validators whose most recent head vote was for block NN, and WNW_N is the weight of the branch starting at block NN.

Some obvious relationships apply between the weights, WxW_x, of blocks, and BxB_x, the latest attesting balances of blocks.

  • For a leaf block NN (a block with no children), WN=BNW_N = B_N.
  • The weight of a block is its own latest attesting balance plus the sum of the weights of its direct children. So, in the diagram, W1=B1+W2+W3W_1 = B_1 + W_2 + W_3.

These relationships can be used to avoid repeating lots of work by memoising the results.

Proposer boost

In September 2020, shortly before mainnet genesis, a theoretical "balancing attack" on the LMD GHOST consensus mechanism was published, with an accompanying post.

The balancing attack allows a very small number of validators controlled by an adversary to perpetually maintain a forked network, with half of all validators following one fork and half the other. This would delay finalisation indefinitely, which is a kind of liveness failure. Since the attack relies on some unrealistic assumptions about the power an adversary has over the network – namely, fine-grained control over who can see what and when – we felt that the potential attack was not a significant threat to the launch of the beacon chain. Later refinements to the attack appear to have made it more practical to execute, however.

A modification to the fork choice to mitigate the balancing attack was first suggested by Vitalik. This became known as proposer boost, and a version of it was adopted into the consensus layer specification in late 2021 with the various client teams releasing versions with mainnet support for proposer boost in April and May 2022.

Changes to the fork choice can be made outside major protocol upgrades; it is not strictly necessary for all client implementations to make the change simultaneously, as they must for hard-fork upgrades. Given this, mainnet client releases supporting proposer boost were made at various times in April and May 2022, and users were not forced to upgrade on a fixed schedule. Unfortunately, having a mix of nodes on the network, around half applying proposer boost and half not, led to a seven block reorganisation of the beacon chain on May 25, 2022. As a result, subsequent updates to the fork choice have tended to be more tightly coordinated between client teams.

Proposer boost details

Proposer boost modifies our nice, intuitive calculation of a branch's weight, based only on latest votes, by adding additional weight to a block that was received on time in the current slot. In this way, it introduces a kind of synchrony weighting. Vitalik calls this "an explicit 'synchronization bottleneck' gadget". In short, it treats a timely block as being a vote with a massive weight that is temporarily added to the branch that it is extending.

The simple intuition behind proposer boost is summarised by Barnabé Monnot as, "a block that is timely shouldn’t expect to be re-orged". In respect of the balancing attack, proposer boost is designed to overwhelm the votes from validators controlled by the adversary and instead allow the proposer of the timely block to choose the fork that will win. Quoting Francesco D'Amato, "the general strategy is to empower honest proposers to impose their view of the fork-choice, but without giving them too much power and making committees irrelevant".

The default setting for store.proposer_boost_root is Root(). That is, the "empty" or "null" default SSZ root value, with all bytes set to zero. Whenever a block is received during the first 1 / INTERVALS_PER_SLOT portion of a slot – that is, when the block is timely – store.proposer_boost_root is set to the hash tree root of that block by the on_block() handler. At the end of each slot it is reset to Root() by the on_tick() handler. Thus, proposer boost has an effect on the fork choice calculation from the point at which a timely block is received until the end of that slot, where "timely" on Ethereum's beacon chain means "within the first four seconds".

Proposer boost causes entire branches to be favoured when the block at their tip is timely. When proposer boost is in effect, and the timely block in the current slot (which has root, store.proposer_boost_root) is descended from the block we are calculating the weight for, then that block's weight is also increased, since the calculation includes the weights of all its descendants. In this way, proposer boost weighting propagates to the boosted block's ancestors in the same way as vote weights do.

The weight that proposer boost adds to the block's branch is a percentage PROPOSER_SCORE_BOOST of the total effective balance of all validators due to attest at that slot. Rather, it is an approximation to the total effective balance for that slot, derived by dividing the total effective balance of all validators by the number of slots per epoch.

The value of PROPOSER_SCORE_BOOST has changed over time before settling at its current 40%. See the description there for the history, and links to how the current value was calculated.

Proposer boost and late blocks

A side-effect of proposer boost is that it enables clients to reliably re-org out (orphan) blocks that were published late. Instead of building on a late block, the proposer can choose to build on the late block's parent.

A block proposer is supposed to publish its block at the start of the slot, so that it has time to be received and attested to by the whole committee within the first four seconds. However, post-merge, it can be profitable to delay block proposals by several seconds in order to collect more transaction income and better extractable value opportunities. Although blocks published five or six seconds into a slot will not gain many votes, they are still likely to remain canonical under the basic consensus spec. As long as the next block proposer receives the late block by the end of the slot, it will usually build on it as the best available head.4 This is undesirable as it punishes the vast majority of honest validators, that (correctly) voted for an empty slot, by depriving them of their reward for correct head votes, and possibly even penalising them for incorrect target votes at the start of an epoch.

Without proposer boost, it is a losing strategy for the next proposer not to build on a block that it received late. Although the late block may have few votes, it has more votes than your block initially, so validators will still attest to the late block as the head of the chain, keeping it canonical and orphaning the alternative block that you built on its parent.

With proposer boost, as long as the late block has fewer votes than the proposer boost percentage, the honest proposer can be confident that its alternative block will win the fork choice for long enough that the next proposer will build on that rather than on the late block it skipped.

Diagram showing a proposer choosing whether to build on a late block or its parent.

Block BB was published late, well after the 4 second attestation cut-off time. However, it still managed to acquire a few attestations (say, 10% of the committee) due to dishonest or misconfigured validators. Should the next proposer build C1C_1 on top of the late block, or C2C_2 on top of its parent?

Diagram showing that without proposer score boosting a proposer should build on the late block.

Without proposer boost, it only makes sense to build C1C_1, on top of the late block BB. Since BB has some weight, albeit small, the top branch will win the fork choice (if the network is behaving synchronously at the time). Block C2C_2 would be orphaned.

Diagram showing that with proposer score boosting a proposer may build on the late block's parent.

With proposer boost, the proposer of CC can safely publish either C1C_1 or C2C_2. Due to the proposer score boost of 40%, it is safe to publish block C2C_2 that orphans BB since the lower branch will have greater weight during the slot.

An implementation of this strategy in the Lighthouse client seems to have been effective in reducing the number of late blocks on the network. Publishing of late blocks is strongly disincentivised when they are likely to be orphaned. It may be adopted as standard behaviour in the consensus specs at some point, but remains optional for the time-being. Several safe-guards are present in order to avoid liveness failures.

Note that Proposer boost does not in general allow validators to re-org out timely blocks (that is, an ex-post reorg). A timely block ought to gain enough votes from the committees that it will always remain canonical.

Alternatives to proposer boost

Proposer boost is not a perfect solution to balancing attacks or ex-ante reorgs. It makes ex-post reorgs easier to accomplish; it does not scale with participation, meaning that if only 40% of validators are online, then proposers can reorg at will; it can fail when an attacker controls several consecutive slots over which to store up votes.

Some changes to, or replacements for, LMD GHOST have been suggested that do not require proposer score boosting.

View-merge5 is a mechanism in which attesters freeze their fork choice some time Δ\Delta before the end of a slot. The next proposer does not freeze its fork choice, however. The assumed maximum network delay is Δ\Delta, so the proposer will see all votes in time, and it will circulate a summary of them to all validators, contained within its block. This allows the whole network to synchronise on a common view. Balancing attacks rely on giving two halves of the network different views, and would be prevented by view-merge.

The Goldfish protocol, described in the paper No More Attacks on Proof-of-Stake Ethereum?, builds on view-merge (called "message buffering" there) and adds vote expiry so that head block votes expire almost immediately (hence the name - rightly or wrongly, goldfish are famed for their short memories). The resulting protocol is provably reorg resilient and supports fast confirmations.

Both view-merge and Goldfish come with nice proofs of their properties under synchronous conditions, which improve on Gasper under the same conditions. However, they may not fare so well under more realistic asynchronous conditions. The original view-merge article says of latency greater than 2 seconds, "This is bad". One of the authors of the Goldfish paper has said that Goldfish "is extremely brittle to asynchrony, allowing for catastrophic failures such as arbitrarily long reorgs"6, and elsewhere, "even a single slot of asynchrony can lead to a catastrophic failure, jeopardizing the safety of any previously confirmed block". At least with proposer boost, we know that it only degrades to normal Gasper under conditions of high latency.

Francesco D'Amato argues in Reorg resilience and security in post-SSF LMD-GHOST that the real origin of the reorg issues with LMD GHOST is our current committee-based voting: "The crux of the issue is that honest majority of the committee of a slot does not equal a majority of the eligible fork-choice weight", since an adversary is able to influence the fork choice with votes from other slots. The ultimate cure for this would be single slot finality (SSF), in which all validators vote at every slot. SSF is a long way from being practical today, but a candidate for its fork choice is RLMD-GHOST (Recent Latest Message Driven GHOST), which expires votes after a configurable time period.

Used by get_head()
Uses get_active_validator_indices(), get_ancestor(), get_total_active_balance()
See also on_tick(), on_block(), PROPOSER_SCORE_BOOST


def get_voting_source(store: Store, block_root: Root) -> Checkpoint:
    Compute the voting source checkpoint in event that block with root ``block_root`` is the head block
    block = store.blocks[block_root]
    current_epoch = compute_epoch_at_slot(get_current_slot(store))
    block_epoch = compute_epoch_at_slot(block.slot)
    if current_epoch > block_epoch:
        # The block is from a prior epoch, the voting source will be pulled-up
        return store.unrealized_justifications[block_root]
        # The block is not from a prior epoch, therefore the voting source is not pulled up
        head_state = store.block_states[block_root]
        return head_state.current_justified_checkpoint

If the given block (which is a leaf block in the Store's block tree) is from a prior epoch, then return its unrealised justification. Otherwise return the justified checkpoint from its post-state (its realised justification).

Returning the unrealised justification is called "pulling up" the block (or "pulling the tip of a branch") as it is equivalent to running the end-of-epoch state transition accounting on the block's post-state: the block is notionally pulled up from its actual slot to the first slot of the next epoch.

The Casper FFG source vote is the checkpoint that a validator believes is the highest justified at the time of the vote. As such, this function returns the source checkpoint that validators with this block as head will use when casting a Casper FFG vote in the current epoch. This has an important role in filter_block_tree() and is used in the formal proof of non-self-slashability.

Used by filter_block_tree()
Uses compute_epoch_at_slot()


Note: External calls to filter_block_tree (i.e., any calls that are not made by the recursive logic in this function) MUST set block_root to store.justified_checkpoint.

The only external call to filter_block_tree() comes from get_filtered_block_tree(), which uses store.justified_checkpoint.root. So we're all good. This is a requirement of Hybrid LMD GHOST - it enforces Casper FFG's fork choice rule.

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

    current_epoch = compute_epoch_at_slot(get_current_slot(store))
    voting_source = get_voting_source(store, block_root)

    # The voting source should be at the same height as the store's justified checkpoint
    correct_justified = (
        store.justified_checkpoint.epoch == GENESIS_EPOCH
        or voting_source.epoch == store.justified_checkpoint.epoch

    # If the previous epoch is justified, the block should be pulled-up. In this case, check that unrealized
    # justification is higher than the store and that the voting source is not more than two epochs ago
    if not correct_justified and is_previous_epoch_justified(store):
        correct_justified = (
            store.unrealized_justifications[block_root].epoch >= store.justified_checkpoint.epoch and
            voting_source.epoch + 2 >= current_epoch

    finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch)
    correct_finalized = (
        store.finalized_checkpoint.epoch == GENESIS_EPOCH
        or store.finalized_checkpoint.root == get_ancestor(store, block_root, finalized_slot)
    # 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

The filter_block_tree() function is at the heart of how LMD GHOST and Casper FFG are bolted together.

The basic structure is fairly simple. Given a block, filter_block_tree() recursively walks the Store's block tree visiting the block's descendants in depth-first fashion. When it arrives at a leaf block (the tip of a branch), if the leaf block is "viable" as head then it and all its ancestors (the whole branch) will be added to the blocks list, otherwise the branch will be ignored.

In other words, the algorithm prunes out branches that terminate in an unviable head block, and keeps branches that terminate in a viable head block.

A diagram showing the pruning of nonviable branches.

Block JJ is the Store's justified checkpoint. There are four candidate head blocks descended from it. Two are viable (VV), and two are nonviable (NVNV). Blocks in branches terminating at viable heads are returned by the filter; blocks in branches terminating at nonviable heads are filtered out.


What dictates whether a leaf block is viable or not?

Pre-Capella, there was a fairly straightforward requirement for a leaf block to be a viable head block: viable head blocks had a post-state that agreed with the Store about the justified and finalised checkpoints. This was encapsulated in the following code from the Bellatrix spec,

    correct_justified = (
        store.justified_checkpoint.epoch == GENESIS_EPOCH
        or head_state.current_justified_checkpoint == store.justified_checkpoint
    correct_finalized = (
        store.finalized_checkpoint.epoch == GENESIS_EPOCH
        or head_state.finalized_checkpoint == store.finalized_checkpoint
    # 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

The code we have in the Capella update is considerably more complex and less intuitive. But before we get to that we need to take a step back and discuss why we should filter the block tree at all.

Why prune unviable branches?

Filtering the block tree like this ensures that the Casper FFG fork choice rule, "follow the chain containing the justified checkpoint of the greatest height", is applied to the block tree before the LMD GHOST fork choice is evaluated.

Very early versions of the spec considered the tip of any branch descended from the Store's justified checkpoint as a potential head block. However, a scenario was identified in which this could result in a deadlock, in which finality would not be able to advance without validators getting themselves slashed - a kind of liveness failure7.

The filter_block_tree() function was added as a fix for this issue. Given a Store and a block root, filter_block_tree() returns the list of all the blocks that we know about in the tree descending from the given block, having pruned out any branches that terminate in a leaf block that is not viable in some sense.

To illustrate the problem, consider the situation shown in the following diagrams, based on the original description of the issue. The context is that there is an adversary controlling 18% of validators that takes advantage of (or causes) a temporary network partition. We will illustrate the issue mostly in terms of checkpoints, and omit the intermediate blocks that carry the attestations - you can mentally insert these as necessary.

We begin with a justified checkpoint AA that all nodes agree on.

Due to the network partition, only 49% of validators, plus the adversary's 18%, see checkpoint BB. They all make Casper FFG votes [AB][A \rightarrow B], thereby justifying BB. A further checkpoint C1C_1 is produced on this branch, and the 49% that are honest validators dutifully make the Casper FFG vote [BC1][B \rightarrow C_1], but the adversary does not, meaning that C1C_1 is not justified. Validators on this branch see h1h_1 as the head block, and have a highest justified checkpoint of BB.

A diagram illustrating the first step in a liveness attack on the unfiltered chain, making the first branch.

The large blocks represent checkpoints. After checkpoint AA there is a network partition: 49% of validators plus the adversary see checkpoints BB and C1C_1. Casper votes are shown by the dashed arrows. The adversary votes for BB, but not for C1C_1.

The remaining 33% of validators do not see checkpoint BB, but see C2C_2 instead and make Casper FFG votes [AC2][A \rightarrow C_2] for it. But this is not enough votes to justify C2C_2. Checkpoint D2D_2 is produced on top of C2C_2, and a further block h2h_2. On this branch, h2h_2 is the head of the chain according to LMD GHOST, and AA remains the highest justified checkpoint.

A diagram illustrating the second step in a liveness attack on the unfiltered chain, making the second branch.

Meanwhile, the remaining 33% of validators do not see the branch starting at BB, but start a new branch containing C2C_2 and its descendants. They do not have enough collective weight to justify any of the checkpoints.

Now for the cunning part. The adversary switches its LMD GHOST vote (and implicitly its Casper FFG vote, although that does not matter for this exercise) from the first branch to the second branch, and lets the validators in the first branch see the blocks and votes on the second branch.

Block h2h_2 now has votes from the majority of validators – 33% plus the adversary's 18% – so all honest validators should make it their head block.

However, the justified checkpoint on the h2h_2 branch remains at AA. This means that the 49% of validators who made Casper FFG vote [BC][B \rightarrow C] cannot switch their chain head from h1h_1 to h2h_2 without committing a Casper FFG surround vote, and thereby getting slashed. Switching branch would cause their highest justified checkpoint to go backwards. Since they have previously voted [BC1][B \rightarrow C_1], they cannot now vote [AX][A \rightarrow X] where XX has a height greater than C1C_1, which they must do if they were to switch to the h2h_2 branch.

A diagram illustrating the third step in a liveness attack on the unfiltered chain, changing the chain head.

The adversary switches to the second branch, giving h2h_2 the majority LMD GHOST vote. This deadlocks finalisation: the 49% who made Casper FFG vote [BC1][B \rightarrow C_1] cannot switch to h2h_2 without being slashed.

In conclusion, the chain can no longer finalise (by creating higher justified checkpoints) without a substantial proportion of validators (at least 16%) being willing to get themselves slashed.

It should never be possible for the chain to get into a situation in which honest validators, following the rules of the protocol, end up in danger of being slashed. The situation here arises due to a conflict between the Casper FFG fork choice (follow the chain containing the justified checkpoint of the greatest height) and the LMD GHOST fork choice (which, in this instance, ignores that rule). It is a symptom of the clunky way in which the two have been bolted together.

The chosen fix for all this is to filter the block tree before applying the LMD GHOST fork choice, so as to remove all "unviable" branches from consideration. That is, all branches whose head block's state does not agree with me about the current state of justification and finalisation.

A diagram showing that filter block tree prunes out the conflicting branch for validators following the first branch.