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.

Notes:

  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.

Constant

Name Value
INTERVALS_PER_SLOT uint64(3)

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.

Configuration

Name Value
PROPOSER_SCORE_BOOST uint64(40)
  • 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

Helpers

LatestMessage

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.

Store

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.

is_previous_epoch_justified

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()

get_forkchoice_store

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),
        genesis_time=anchor_state.genesis_time,
        justified_checkpoint=justified_checkpoint,
        finalized_checkpoint=finalized_checkpoint,
        unrealized_justified_checkpoint=justified_checkpoint,
        unrealized_finalized_checkpoint=finalized_checkpoint,
        proposer_boost_root=proposer_boost_root,
        equivocating_indices=set(),
        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.

get_slots_since_genesis

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()

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()

compute_slots_since_epoch_start

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()

get_ancestor

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)

get_weight

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 Ethresear.ch 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

get_voting_source

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]
    else:
        # 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()

filter_block_tree

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.

Viability

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.

When validators that followed branch 1 apply filter_block_tree(), branch 2 is pruned out (as indicated by the dashed lines). This is because their Store has BB as the best justified checkpoint, while branch 2's leaf block has a state with AA as the justified checkpoint. For these validators h2h_2 is no longer a candidate head block.

With this fix, the chain will recover the ability to finalise when the validators on the second branch eventually become aware of the first branch. On seeing h1h_1 and its ancestors, they will update their Stores' justified checkpoints to BB and mark the h2h_2 branch unviable.

Unrealised justification

A major feature of the Capella update to the fork choice specification is the logic for handling "unrealised justification" when filtering the block tree.

Several issues had arisen in the former fork choice spec. First, an unrealised justification reorg attack that allowed the proposer of the first block of an epoch to easily fork out up to nine blocks from the end of the previous epoch. A variant of that attack was also found to be able to cause validators to make slashable attestations - the very issue the filter is intended to prevent. Second, a justification withholding attack that an adversary could use to reorg arbitrary numbers of blocks at the start of an epoch.

The root issue is that, within the consensus layer's state transition, the calculations that update justification and finality are done only at epoch boundaries. An adversary had a couple of ways they could use this to filter out competing branches within filter_block_tree(). Essentially, in not accounting for unrealised justifications, the filtering was being applied too aggressively.

To be clear, both of the attacks described here apply to the old version of filter_block_tree() and have been remedied in the current release. This is the old, much simpler, code for evaluating correct_justified and correct_finalized,

    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
    )

This meant that the tip of a branch was included for consideration if (a) the justified checkpoint in its post-state matched that in the store, and (b) the finalised checkpoint in its post-state matched that in the store. These nice simple criteria have been changed to the mess we have today, which we'll look at in a moment. But first, let's see what was wrong with the old criteria.

Unrealised justification reorg

The unrealised justification reorg allowed an adversary assigned to propose a block in the first slot of an epoch to reorg out a chain of up to nine blocks at the end of the previous epoch.

The key to this is the idea of unrealised justification. Towards the end of an epoch (within the last third of an epoch, that is, the last nine slots), the beacon chain might have gathered enough Casper FFG votes to justify the checkpoint at the start of that epoch. However, justification and finalisation calculations take place only at epoch boundaries, so the achieved justification is "unrealised": until the end of the epoch, all the blocks will continue have a post-state justification that points to an earlier checkpoint.

A diagram showing the setup for an unrealised justification reorg scenario.

The solid vertical lines are epoch boundaries, and the squares C1C_1 and C2C_2 are their checkpoints. A block's JJ value shows the justified checkpoint in its post-state. Its UU value is the hypothetical unrealised justification. During an epoch, the chain may gather enough Casper FFG votes to justify a new checkpoint, but justification in the beacon state happens only at epoch boundaries, so it is unrealised in the interim. Block YY is clearly the head block.

When the adversary is the proposer in the first slot of an epoch, it could have used the unrealised justification in the previous epoch to fork out the last blocks of that epoch - up to around nine of them, depending on the FFG votes the adversary's block contains. By building a competing head block the adversary could trick filter_block_tree() into filtering out the previous head branch from consideration.

A diagram showing how the adversary executes the unrealised justification reorg.

The adversary adds a block ZZ in the first slot of the next epoch. It builds on WW, which has unrealised justification. At the epoch boundary, the state's justified checkpoint is calculated, so WW's post-state has C2C_2. In the former fork choice, only branches with tips that agreed with the Store about the justified checkpoint could be considered. On that basis, the branch ending in YY would have been excluded by the filter, making ZZ the head, even though it might have zero LMD GHOST support. Blocks XX and YY would be orphaned (reorged out).

Unrealised justification deadlock

It also became apparent that the pre-Capella formulation of filter_block_tree() did not fully prevent the possibility of deadlock - the very thing that filtering the block tree is intended to prevent. Deadlock is a situation in which honest validators are forced to choose between making a slashable attestation or not voting at all.

The setup and attack is described in Aditya Asgaonkar's document, and is a variant of the reorg above. The original deadlock attack relied on the network being partitioned, so that validators had split views. This newer deadlock attack did not need a network partition, but under some fairly specific unrealised justification conditions, the adversary could make the justified checkpoint go backwards. Doing this after some honest validators had already used the higher checkpoint as their Casper FFG source vote forced them subsequently to either make a surround vote, or not to vote.

Justification withholding attack

The justification withholding attack was similar to the unrealised justification reorg in that it involved using unrealised justification to get filter_block_tree() to exclude other branches besides the adversary's.

In this attack, the adversary needs to have several proposals in a row at the end of an epoch - enough that, if the adversary does not publish the blocks, the epoch does not get justified by the time it finishes. That is, without the adversary's blocks, there is no unrealised justification, with the adversary's blocks there would be unrealised justification.

A diagram showing how an adversary sets up a justification withholding attack.

The adversary has a string of proposals at the end of an epoch. These blocks contain enough FFG votes to justify the epoch's checkpoint C2C_2, but the adversary withholds them for now.

The remainder of the chain is unaware of the adversary's blocks, so continues to build as if they were skipped slots.

A diagram showing the chain progressing after the setup of the justification withholding attack, but before its execution.

The remainder of the validators continue to build blocks AA and BB at the start of the next epoch. Without the adversary's blocks, checkpoint 2 is not justified, so AA and BB have C1C_1 as justified in their post-states (their unrealised justification is irrelevant here). Block BB is the chain's head.

The adversary has a block proposal at some point in epoch 3 - it does not matter when.

A diagram showing the execution of the justification withholding attack.

When the adversary publishes block ZZ in epoch 3, it releases its withheld blocks at the same time. Block ZZ has a post-state justified checkpoint of C2C_2 (updated at the epoch boundary). Under the old filter_block_tree() that would have excluded BB from consideration as head, and the adversary's block ZZ would have become head, even with no LMD support.

Viable and unviable branches

The block tree filtering is done by checking that blocks at the tip of branches have the "correct" justification and finalisation in some sense. Both the correct_justified and correct_finalised flags must be true for the branch to be considered viable.

correct_justified

The newer, more complex, correct_justified evaluation from the Capella update is as follows.

    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 # A
    )

    # 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): # B
        correct_justified = (
            store.unrealized_justifications[block_root].epoch >= store.justified_checkpoint.epoch and # C
            voting_source.epoch + 2 >= current_epoch # D
        )

I'm not going to pretend that I understand this fully - it seems very far from intuitive, and its correctness far from obvious8. For now I will quote some explanation that Aditya shared with me directly.

The correct_justified condition ensures that: (a) we pick a head block that has a "good" justification in its chain, and (b) that validators can vote for the chosen head block without the risk of creating slashable messages.

I describe (a) here informally, but you can think of the fork choice as a heuristic to choose where to vote so that we advance our finalized checkpoint as fast as possible. Generally, this means we vote on the highest justified checkpoint we know of, but the "that we know of" part is tricky because of the nuances of unrealized justifications and the associated reorg attacks.

Now, if you ignore unrealized justification and the reorg attacks, this first appearance of correct_justified [Line A] is sufficient to address (a) & (b). Then, to fix the reorg attacks, we add an additional version of correct_justified for pulled-up blocks, where the first line [line C] addresses (a) and the second line [line D] addresses (b).

Recall that the chief goal of filtering the block tree is to avoid honest validators being forced to make surround votes in Casper FFG, as these are slashable. However, earlier remedies for this were too eager in filtering out candidate heads, and an adversary could use unrealised justification to force reorgs, and even the kind of self-slashing we want to avoid.

The current fork choice apparatus preserves two key properties9.

  1. The voting_source.epoch of a candidate head block is always less than or equal to the store.justified_checkpoint.epoch.
    • This is because on_block() always calls update_checkpoints(), and the way that the get_voting_source() function is constructed.
    • The voting_source.epoch is the Casper FFG source vote that validators with that block as head will use when making a Casper FFG vote in the current epoch.
  2. store.justified_checkpoint.epoch never decreases (it is monotonically increasing).
    • It is only ever written to in update_checkpoints(), and it is easy to see from there that this is true.

With respect to the line I've marked A in the source code, if the voting source matches the Store's justified checkpoint, then all is good, we have no reason not to consider the block as head, and we can short-circuit the rest of the logic. By property 2, the Store's justified checkpoint never decreases, so a validator's Casper FFG vote based on this cannot ever be a surround vote. (Since the target vote strictly increases, it cannot be a surrounded vote either.)

A diagram showing that it is always safe to vote when the voting source is the same as the store's justified checkpoint.

When the voting source is the same as the store's justified checkpoint, it is always safe to vote. The store's justified checkpoint never decreases, so we cannot commit a surround vote.

If the block is not a viable head by the first criterion, it might still be a viable head by the second (line D). Recall that the reorg attacks above rely on the adversary taking advantage of unrealised justification to update the Store's justified checkpoint, leaving the previous head of the chain "stale" with respect to its realised justification, although based on its unrealised justification it would still be viable. To avoid this, we wish to safely include as many viable heads as possible.

We know that any Casper FFG vote we make at this point will have voting_source.epoch strictly less than store.justified_checkpoint.epoch, by property 1, and since we already dealt with the equality case.

Line D in the source code says that it is safe to allow votes where voting_source.epoch == current_epoch - 2 and voting_source.epoch == current_epoch - 1. Any honest vote's target epoch will be current_epoch, so the gap between source and target is at most two epochs, which is not enough to surround a previous vote. That is, a vote [s2t2][s_2 \rightarrow t_2] that surrounds a previous vote [s1t1][s_1 \rightarrow t_1] requires that s2<s1<t1<t2s_2 < s_1 < t_1 < t_2. This is not possible if t2s22t_2 - s_2 \le 2. This exception is required for the analysis of the safe block confirmation rule, and is discussed in section 3.3 of the Confirmation Rule paper.

A diagram showing that it is safe to vote from two epochs ago.

When the voting source is within two epochs of the current epoch then it is safe to vote as a surround vote must encompass at least two intervening checkpoints.

Both line B (the condition on justification of the previous epoch) and line C seem to be unnecessary, and may be removed in future. See sections 3.3 and 3.4 of the (draft) A Confirmation Rule for the Ethereum Consensus Protocol paper for discussion of this. Note, though, that the proof of the honest viable head property described below relies on the weaker condition that store.justified_checkpoint.epoch >= current_epoch - 2 (that either the previous or previous but one epoch is justified).

correct_finalized

The Capella update's change to correct_finalized is more limited, and more intuitive.

    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)
    )

This simply ensures that a viable block is descended from the Store's finalised checkpoint

The previous version made use the post-state of the block being considered for viability, which caused it to suffer from similar complications to correct_justified with respect to unrealised finality. We don't actually care about the block's post-state view of finalisation, since finality is a global property: as long as the block is descended from the finalised checkpoint it should be eligible for consideration to become viable.

The correct_finalized check might appear redundant at first sight since we are always filtering based on a tree rooted at the last justified checkpoint, which (in the absence of a mass slashing) must be descended from the last finalised checkpoint. The check, however, guarantees the further condition that a node's own view of the finalised checkpoint is irreversible, even if there were to be a mass slashing - this is the irreversible local finality formal property in the next section. Maintaining this invariant is a huge help in building efficient clients - we are free to forget about everything prior to the last finalised checkpoint.

Formal proofs

As referenced in the Ethereum Foundation's disclosure on the Capella fork choice spec updates, some properties of the new fork choice have been formally verified by Roberto Saltini and his team at Consensys.

This formal verification process involves selecting some properties that we wish to be true for the fork choice, and manually constructing proofs that they are always preserved by the specification. It is a much more robust and rigorous process than manual testing, fuzz testing, or general hand-waving that have hitherto been the main approaches.

Four properties were proved in the documents.

  • Non-Self-Slashability
  • Honest Viable Head
    • Assuming a synchronous network, current_epoch - 2 being justified, and honest nodes having received enough attestations to justify the highest possible justified checkpoint, any block proposed by an honest node during the current epoch that is a descendent of the highest possible justified checkpoint is included in the output of get_filtered_block_tree().
  • Deadlock Freedom
    • A distributed system running the Ethereum protocol can never end up in a state in which it is impossible to finalise a new epoch.
  • Irreversible Local Finality
    • A block, once finalized in the local view of an honest validator, is never reverted from the canonical chain in the local view.

Given the complexity of reasoning about the fork choice, and it's rather chequered history, it is hugely reassuring now to have these proofs of correctness10.

Conclusion

This has been a long section on a short function. As I said at the start of the section, filter_block_tree() is at the heart of how LMD GHOST and Casper FFG are bolted together, and I think it has surprised everybody how many complexities lurk here.

As an exercise for the reader, we can imagine life without having to filter the block tree. Potuz has documented some thoughts on this in, Fork choice without on-state FFG filtering.

Ultimately, as with proposer boost, the complexities around the Gasper fork choice largely arise from our slot-based voting, with votes accumulated gradually through an epoch. This results in unrealised justification and the rest of it. The long-term fix is also probably the same: moving to single slot finality.

Used by get_filtered_block_tree(), filter_block_tree() (recursively)
Uses filter_block_tree() (recursively), compute_epoch_at_slot(), get_voting_source(), is_previous_epoch_justified(), compute_start_slot_at_epoch(), get_ancestor()

get_filtered_block_tree

def get_filtered_block_tree(store: Store) -> Dict[Root, BeaconBlock]:
    """
    Retrieve a filtered block tree from ``store``, only returning branches
    whose leaf state's justified/finalized info agrees with that in ``store``.
    """
    base = store.justified_checkpoint.root
    blocks: Dict[Root, BeaconBlock] = {}
    filter_block_tree(store, base, blocks)
    return blocks

A convenience wrapper that passes the Store's justified checkpoint to filter_block_tree(). On returning, the blocks dictionary structure will contain the blocks from all viable branches rooted at that checkpoint, and nothing that does not descend from that checkpoint. For the meaning of "viable", see above.

Used by get_head()
Uses filter_block_tree()

get_head

def get_head(store: Store) -> Root:
    # Get filtered block tree that only includes viable branches
    blocks = get_filtered_block_tree(store)
    # Execute the LMD-GHOST fork choice
    head = store.justified_checkpoint.root
    while True:
        children = [
            root for root in blocks.keys()
            if blocks[root].parent_root == head
        ]
        if len(children) == 0:
            return head
        # Sort by latest attesting balance with ties broken lexicographically
        # Ties broken by favoring block with lexicographically higher root
        head = max(children, key=lambda root: (get_weight(store, root), root))

get_head() encapsulates the fork choice rule: given a Store it returns a head block.

The fork choice rule is objective in that, given the same Store, it will always return the same head block. But the overall process is subjective in that each node on the network will tend to have a different view, that is, a different Store, due to delays in receiving attestations or blocks, or having seen different sets of attestations or blocks because of network asynchrony or an attack.

Looking first at the while True loop, this implements LMD GHOST in its purest form. Starting from a given block (which would be the genesis block in unmodified LMD GHOST), we find the weights of the children of that block. We choose the child block with the largest weight and repeat the process until we end up at a leaf block (the tip of a branch). That is, we Greedily take the Heaviest Observed Sub-Tree, GHOST. Any tie between two child blocks with the same weight is broken by comparing their block hashes, so we end up at a unique leaf block - the head that we return.

Diagram of a block tree showing the weight of each block.

get_head() starts from the root block, AA, of a block tree. The numbers show each block's weight, which is its latest attesting balance - the sum of the effective balances of the validators that cast their latest vote for that block. Proposer boost can temporarily increase the latest block's score (not shown).

Diagram of a block tree showing the weight of each block and the weight of each subtree.

The get_weight() function when applied to a block returns the total weight of the subtree of the block and all its descendants. These weights are shown on the lines between child and parent blocks.

Diagram of a block tree showing the branch chosen by the GHOST rule.

Given a block, the loop in get_head() considers its children and selects the one that roots the subtree with the highest weight. It repeats the process with the heaviest child block11 until it reaches a block with no children. In this example, it would select the branch ACEA \leftarrow C \leftarrow E, returning EE as the head block.

Hybrid LMD GHOST

What we've just described is the pure LMD GHOST algorithm. Starting from the genesis block, it walks the entire block tree, taking the heaviest branch at each fork until it reaches a leaf block.

What is implemented in get_head() however, is a modified form of this that the Gasper paper12 refers to as "hybrid LMD GHOST" (HLMD GHOST). It is not pure LMD GHOST, but LMD GHOST modified by the Casper FFG consensus.

    # Get filtered block tree that only includes viable branches
    blocks = get_filtered_block_tree(store)
    # Execute the LMD-GHOST fork choice
    head = store.justified_checkpoint.root

Specifically, rather than starting to walk the tree from the genesis block, we start from the last justified checkpoint, and rather than considering all blocks that the Store knows about, we first filter out "unviable" branches with get_filtered_block_tree().

This is the point at which the Casper FFG fork choice rule, "follow the chain containing the justified checkpoint of the greatest height", meets the LMD GHOST fork choice rule. The former modifies the latter to give us the HLMD GHOST fork choice rule.

Uses get_filtered_block_tree(), get_weight()

update_checkpoints

def update_checkpoints(store: Store, justified_checkpoint: Checkpoint, finalized_checkpoint: Checkpoint) -> None:
    """
    Update checkpoints in store if necessary
    """
    # Update justified checkpoint
    if justified_checkpoint.epoch > store.justified_checkpoint.epoch:
        store.justified_checkpoint = justified_checkpoint

    # Update finalized checkpoint
    if finalized_checkpoint.epoch > store.finalized_checkpoint.epoch:
        store.finalized_checkpoint = finalized_checkpoint

Update the checkpoints in the store if either of the given justified or finalised checkpoints is newer.

Justification and finalisation are supposed to be "global" properties of the chain, not specific to any one branch, so we keep our Store up to date with the highest checkpoints we've seen.

Note that, by construction, the Store's justified and finalised checkpoints can only increase monotonically. The former is important for the formal proof of non-self-slashability.

Used by compute_pulled_up_tip(), on_tick_per_slot(), on_block()

update_unrealized_checkpoints

def update_unrealized_checkpoints(store: Store, unrealized_justified_checkpoint: Checkpoint,
                                  unrealized_finalized_checkpoint: Checkpoint) -> None:
    """
    Update unrealized checkpoints in store if necessary
    """
    # Update unrealized justified checkpoint
    if unrealized_justified_checkpoint.epoch > store.unrealized_justified_checkpoint.epoch:
        store.unrealized_justified_checkpoint = unrealized_justified_checkpoint

    # Update unrealized finalized checkpoint
    if unrealized_finalized_checkpoint.epoch > store.unrealized_finalized_checkpoint.epoch:
        store.unrealized_finalized_checkpoint = unrealized_finalized_checkpoint

The counterpart to update_checkpoints() for unrealised justified and finalised checkpoints.

Used by compute_pulled_up_tip()

Pull-up tip helpers

compute_pulled_up_tip
def compute_pulled_up_tip(store: Store, block_root: Root) -> None:
    state = store.block_states[block_root].copy()
    # Pull up the post-state of the block to the next epoch boundary
    process_justification_and_finalization(state)

    store.unrealized_justifications[block_root] = state.current_justified_checkpoint
    update_unrealized_checkpoints(store, state.current_justified_checkpoint, state.finalized_checkpoint)

    # If the block is from a prior epoch, apply the realized values
    block_epoch = compute_epoch_at_slot(store.blocks[block_root].slot)
    current_epoch = compute_epoch_at_slot(get_current_slot(store))
    if block_epoch < current_epoch:
        update_checkpoints(store, state.current_justified_checkpoint, state.finalized_checkpoint)

compute_pulled_up_tip() is called for every block processed in order to maintain the update_unrealized_checkpoints map. It was added in the Capella spec update.

The major work in this routine is in the call to process_justification_and_finalization(). In the state transition, this is called once per epoch. Now we are calling it once per block, which would add significant load if implemented naively.

Since the state transition only calls process_justification_and_finalization() at epoch boundaries, the beacon state's justification and finalisation information cannot change mid-epoch. However, Casper FFG votes accumulate throughout the progress of the epoch, and at some point prior to the end of the epoch, enough votes will usually have been included on chain to justify a new checkpoint. When this occurs, we call it "unrealised justification" since it is not yet reflected on chain (in the beacon state). Unrealised justification reflects what the beacon state would be if the end of epoch accounting were to be run immediately on the block - hence the "pulled up tip" naming.

We simulate "pulling up" the block to the next epoch boundary to find out what the justification and finalisation status would be. When the next epoch begins, the unrealised values will become realised.

A diagram showing how unrealised justification becomes realised when a block is "pulled up" to the next epoch.

Each block has a JJ value, which is the justified checkpoint its post-state knows about. JJ is updated only at epoch boundaries. We notionally add a UU value, which is the justified checkpoint that would be in the block's post-state were it to be "pulled up" to the next epoch boundary, where the beacon state's justification and finalisation calculations are done (shown as WW').

As illustrated, the unrealised justification, UU, can differ from the realised justification, JJ, due to unprocessed Casper FFG votes accumulating during an epoch. However, an epoch's own checkpoint cannot gain unrealised justification until at least 2/3 of the way through an epoch (23 slots, since attestations are included one slot after the slot they attest to). That is, the earliest that block WW could occur is in slot 22 of epoch 2 (slot counting is zero-based).

After adding the block and its unrealised justification checkpoint to the store.unrealized_justifications map, the Store's unrealized_justified_checkpoint and unrealized_finalized_checkpoint are updated if the block's values are newer.

If the block is from a previous epoch, then its justification and finalisation are no longer unrealised, since the beacon state has gone through an actual epoch transition since then, so we can update the Store's justified_checkpoint and finalized_checkpoint if the block has newer ones.

Used by on_block()
Uses process_justification_and_finalization(), update_unrealized_checkpoints(), compute_epoch_at_slot(), update_checkpoints()

on_tick helpers

on_tick_per_slot
def on_tick_per_slot(store: Store, time: uint64) -> None:
    previous_slot = get_current_slot(store)

    # Update store time
    store.time = time

    current_slot = get_current_slot(store)

    # If this is a new slot, reset store.proposer_boost_root
    if current_slot > previous_slot:
        store.proposer_boost_root = Root()

    # If a new epoch, pull-up justification and finalization from previous epoch
    if current_slot > previous_slot and compute_slots_since_epoch_start(current_slot) == 0:
        update_checkpoints(store, store.unrealized_justified_checkpoint, store.unrealized_finalized_checkpoint)

The on_tick_per_slot() helper is called at least once every slot. If a tick hasn't been processed for multiple slots, then the on_tick() handler calls it repeatedly to process (synthetic) ticks for the those slots. This ensures that update_checkpoints() is called when there is no tick processed during the first slot of an epoch.

The on_tick_per_slot() helper has three duties,

  • updating the time,
  • resetting proposer boost, and
  • updating checkpoints on epoch boundaries.
Updating the time
    # update store time
    store.time = time

The store has a notion of the current time that is used when calculating the current slot and when applying proposer boost. The time parameter does not need to be very granular. If it weren't for proposer boost, it would be fine to measure time in whole slots, at least within the fork choice13.

Resetting proposer boost
    # Reset store.proposer_boost_root if this is a new slot
    if current_slot > previous_slot:
        store.proposer_boost_root = Root()

Proposer boost is a defence against balancing attacks on LMD GHOST. It rewards timely blocks with extra weight in the fork choice, making it unlikely that an honest proposer's block will become orphaned.

The Store's proposer_boost_root field is set in the on_block() handler when a block is received and processed in a timely manner (within the first four seconds of its slot). For the remainder of the slot this allows extra weight to be added to the block in get_weight().

The logic here resets proposer_boost_root to a default value at the start of the next slot, thereby removing the extra proposer boost weight until the next timely block is processed.

Updating checkpoints
    # If a new epoch, pull-up justification and finalization from previous epoch
    if current_slot > previous_slot and compute_slots_since_epoch_start(current_slot) == 0:
        update_checkpoints(store, store.unrealized_justified_checkpoint, store.unrealized_finalized_checkpoint)

If it's the first slot of an epoch, then we have gone through an epoch boundary since the last tick, and our unrealised justification and finalisation have become realised. They should now be in-sync with the justified and finalised checkpoints in the beacon state.

Used by on_tick()
Uses get_current_slot(), compute_slots_since_epoch_start(), update_checkpoints()

on_attestation helpers

validate_target_epoch_against_current_time
def validate_target_epoch_against_current_time(store: Store, attestation: Attestation) -> None:
    target = attestation.data.target

    # Attestations must be from the current or previous epoch
    current_epoch = compute_epoch_at_slot(get_current_slot(store))
    # Use GENESIS_EPOCH for previous when genesis to avoid underflow
    previous_epoch = current_epoch - 1 if current_epoch > GENESIS_EPOCH else GENESIS_EPOCH
    # If attestation target is from a future epoch, delay consideration until the epoch arrives
    assert target.epoch in [current_epoch, previous_epoch]

This function simply checks that an attestation came from the current or previous epoch, based on its target checkpoint vote. The Store has a notion of the current time, maintained by the on_tick() handler, so it's a straightforward calculation. The timeliness check was introduced to defend against the "decoy flip-flop" attack described below.

Note that there is a small inconsistency here. Attestations may be included in blocks only for 32 slots after the slot in which they were published. However, they are valid for consideration in the fork choice for two epochs, which is up to 64 slots.

Used by validate_on_attestation()
Uses get_current_slot(), compute_epoch_at_slot()
validate_on_attestation
def validate_on_attestation(store: Store, attestation: Attestation, is_from_block: bool) -> None:
    target = attestation.data.target

    # If the given attestation is not from a beacon block message, we have to check the target epoch scope.
    if not is_from_block:
        validate_target_epoch_against_current_time(store, attestation)

    # Check that the epoch number and slot number are matching
    assert target.epoch == compute_epoch_at_slot(attestation.data.slot)

    # Attestation target must be for a known block. If target block is unknown, delay consideration until block is found
    assert target.root in store.blocks

    # Attestations must be for a known block. If block is unknown, delay consideration until the block is found
    assert attestation.data.beacon_block_root in store.blocks
    # Attestations must not be for blocks in the future. If not, the attestation should not be considered
    assert store.blocks[attestation.data.beacon_block_root].slot <= attestation.data.slot

    # LMD vote must be consistent with FFG vote target
    target_slot = compute_start_slot_at_epoch(target.epoch)
    assert target.root == get_ancestor(store, attestation.data.beacon_block_root, target_slot)

    # Attestations can only affect the fork choice of subsequent slots.
    # Delay consideration in the fork choice until their slot is in the past.
    assert get_current_slot(store) >= attestation.data.slot + 1

This is a utility function for the on_attestation() handler that collects together the various validity checks we want to perform on an attestation before we make any changes to the Store. Recall that a failed assertion means that the handler will exit and any changes made to the Store must be rolled back.

Attestation timeliness
    # If the given attestation is not from a beacon block message, we have to check the target epoch scope.
    if not is_from_block:
        validate_target_epoch_against_current_time(store, attestation)

First, we check the attestation's timeliness. Newly received attestations are considered for insertion into the Store only if they came from the current or previous epoch at the time when we heard about them.

This check was introduced to defend against a "decoy flip-flop attack" on LMD GHOST. The attack depends on two competing branches having emerged due to some network failure. An adversary with some fraction of the stake (but less than 33%) can store up votes from earlier epochs and release them at carefully timed moments to switch the winning branch (according to the LMD GHOST fork choice) so that neither branch can gain the necessary 2/3 weight for finalisation. The attack can continue until the adversary runs out of stored votes.

Allowing only attestations from the current and previous epoch to be valid for updates to the Store seems to be an effective defence as it prevents the attacker from storing up attestations from previous epochs. The PR implementing this describes it as "FMD GHOST" (fresh message driven GHOST). However, the fork choice still relies on the latest message ("LMD") from each validator in the Store, no matter how old it is. We seem to have ended up with a kind of hybrid FMD/LMD GHOST in practice14.

As for the if not is_from_block test, this allows the processing of old attestations by the on_attestation handler if they were received in a block. It seems to have been introduced to help with test generation rather than being anything required in normal operation. Here's a comment from the PR that introduced it.

Also good to move ahead with processing old attestations from blocks for now - that's the only way to make atomic updates to the store work in our current testing setup. If that changes in the future, this logic should go through security analysis (esp. for flip-flop attacks).

Attestations are valid for inclusion in a block only if they are less than 32 slots old. These will be a subset of the "fresh" votes made at the time (the "current plus previous epoch" criterion for freshness could encompass as many as 64 slots).

Matching epoch and slot
    # Check that the epoch number and slot number are matching
    assert target.epoch == compute_epoch_at_slot(attestation.data.slot)

This check addresses an edge case in which validators could fabricate votes for a prior or subsequent epoch. It's probably not a big issue for the fork choice, more for the beacon chain state transition accounting. Nevertheless, the check was implemented in both places.

No attestations for unknown blocks
    # Attestations target be for a known block. If target block is unknown, delay consideration until the block is found
    assert target.root in store.blocks
    # Attestations must be for a known block. If block is unknown, delay consideration until the block is found
    assert attestation.data.beacon_block_root in store.blocks

This seems like a natural check - if we don't know about a block (either a target checkpoint or the head block), there's no point processing any votes for it. These conditions were added to the spec without further rationale. As noted in the comments, such attestations may become valid in future and should be reconsidered then. When they receive attestations for blocks that they don't yet know about, clients will typically ask their peers to send the block to them directly.

No attestations for future blocks
    # Attestations must not be for blocks in the future. If not, the attestation should not be considered
    assert store.blocks[attestation.data.beacon_block_root].slot <= attestation.data.slot

This check was introduced alongside the above checks for unknown blocks. Allowing votes for blocks that were published later than the attestation's assigned slot increases the feasibility of the decoy flip-flop attack by removing the need to have had a period of network asynchrony to set it up.

LMD and FFG vote consistency
    # LMD vote must be consistent with FFG vote target
    target_slot = compute_start_slot_at_epoch(target.epoch)
    assert target.root == get_ancestor(store, attestation.data.beacon_block_root, target_slot)

This check ensures that the block in the attestation's head vote descends from the block in its target vote.

The check was introduced to fix three issues that had come to light.

  1. Inconsistencies between the fork choice's validation of attestations and the state transition's validation of attestations. The issue is that, if some attestations are valid with respect to the fork choice but invalid for inclusion in blocks, it is a potential source of differing network views between validators, and could impede fork choice convergence. Validators receive attestations both via attestation gossip and via blocks. Ideally, each of these channels will contain more or less the same information.15

  2. Attestations from incompatible forks. Since committee shufflings are decided only at the start of the previous epoch, it can lead to implementation challenges when processing attestations where the target block is from a different fork. After a while, forks end up with different shufflings. Clients often cache shufflings and it can be a source of bugs having to handle these edge cases. This check removes any ambiguity over the state to be used when validating attestations. It also prevents validators exploiting the ability to influence their own committee assignments in the event of multiple forks.

  3. Faulty or malicious validators shouldn't be able to influence fork choice via exploiting this inconsistency. An attestation that fails this test would not have been produced by a correctly operating, honest validator. Therefore it is safest to ignore it.

Only future slots
    # Attestations can only affect the fork choice of subsequent slots.
    # Delay consideration in the fork choice until their slot is in the past.
    assert get_current_slot(store) >= attestation.data.slot + 1

This criterion is discussed in section 8.4 of the Gasper paper: only attestations from slots up to and including slot N1N-1 may appear in the Store at slot NN.

If attestations were included in the Store as soon as being received, an adversary with a number of dishonest validators could use that to probabilistically split the votes of honest validators. The dishonest validators would attest early in the slot, dividing their votes between competing head blocks. Due to network delays, when honest validators run their own fork choices prior to attesting at the proper time, they are likely to see different weights for each of the candidates, based on the subset of dishonest attestations they have received by then. In which case the vote of the honest validators could end up being split. This might keep the chain from converging on a single head block.

Introducing this one slot lag for considering attestations makes it much more likely that honest validators will all vote for the same head block in slot NN, as they will have all seen a similar set of attestations up to slot N1N-1, and cannot be influenced by an adversary's early attestations in the current slot.

Used by on_attestation()
Uses validate_target_epoch_against_current_time(), compute_epoch_at_slot(), compute_start_slot_at_epoch(), get_ancestor(), get_ancestor()
store_target_checkpoint_state
def store_target_checkpoint_state(store: Store, target: Checkpoint) -> None:
    # Store target checkpoint state if not yet seen
    if target not in store.checkpoint_states:
        base_state = copy(store.block_states[target.root])
        if base_state.slot < compute_start_slot_at_epoch(target.epoch):
            process_slots(base_state, compute_start_slot_at_epoch(target.epoch))
        store.checkpoint_states[target] = base_state

We need checkpoint states both to provide validator balances (used for weighting votes in the fork choice) and for the validator shufflings (used when validating attestations).

A Checkpoint is a reference to the first slot of an epoch and are what the Casper FFG votes in attestations point to. When an attestation targets a checkpoint that has empty slots preceding it, the checkpoint's state will not match the state of the block that it points to. Therefore, we take that block's state (base_state) and run the simple process_slots() state transition for empty slots on it to bring the state up to date with the checkpoint.

A diagram showing the state being updated to the checkpoint by process_slots.

Consider a checkpoint that points to [N,B][N, B], where NN is the checkpoint height (epoch number) and BB is the block root of the most recent block. The shapes with dotted outlines indicate skipped slots. The process_slots() function takes the state SS associated with the block and updates it to the slot of the checkpoint by playing empty slots onto it, resulting in state SS'.

Used by on_attestation()
Uses compute_start_slot_at_epoch(), process_slots(),
update_latest_messages
def update_latest_messages(store: Store, attesting_indices: Sequence[ValidatorIndex], attestation: Attestation) -> None:
    target = attestation.data.target
    beacon_block_root = attestation.data.beacon_block_root
    non_equivocating_attesting_indices = [i for i in attesting_indices if i not in store.equivocating_indices]
    for i in non_equivocating_attesting_indices:
        if i not in store.latest_messages or target.epoch > store.latest_messages[i].epoch:
            store.latest_messages[i] = LatestMessage(epoch=target.epoch, root=beacon_block_root)

A message comprises a timestamp and a block root (head) vote. These are extracted from the containing attestation in the form of the epoch number of the target checkpoint of the attestation, and the LMD GHOST head block vote respectively. By the time we get here, validate_on_attestation() has already checked that the slot for which the head vote was made belongs to the epoch corresponding to the target vote. Validators vote exactly once per epoch, so the epoch number is granular enough for tracking their latest votes.

All the validators in attesting_indices made this same attestation. The attestation will have travelled the world as a single aggregate attestation, but it has been unpacked in on_attestation() before being passed to this function. Validators on our naughty list of equivocaters are filtered out, and any that are left are considered for updates.

If the validator index is not yet in the store.latest_messages set then its vote is inserted; if the vote that we have is newer than the vote already stored then it is updated. Each validator has at most one entry in the latest_messages set.

Used by on_attestation()
See also Attestation, LatestMessage

Handlers

The four handlers below – on_tick(), on_block(), on_attestation(), and on_attester_slashing() – are the fork choice rule's four senses. These are the means by which the fork choice gains its knowledge of the outside world, and the only means by which the Store gets updated.

None of the handlers is explicitly called by any code that appears anywhere in the spec. It is expected that client implementations will call each handler as and when required. As per the introductory material at the top of the fork choice spec, they should be called as follows.

  • on_tick(store, time) whenever time > store.time where time is the current Unix time.
  • on_block(store, block) whenever a block block 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.

on_tick

def on_tick(store: Store, time: uint64) -> None:
    # If the ``store.time`` falls behind, while loop catches up slot by slot
    # to ensure that every previous slot is processed with ``on_tick_per_slot``
    tick_slot = (time - store.genesis_time) // SECONDS_PER_SLOT
    while get_current_slot(store) < tick_slot:
        previous_time = store.genesis_time + (get_current_slot(store) + 1) * SECONDS_PER_SLOT
        on_tick_per_slot(store, previous_time)
    on_tick_per_slot(store, time)

A "tick" is not defined in the specification. Notionally, ticks are used to continually keep the fork choice's internal clock (store.time) updated. In practice, calling on_tick() is only really required at the start of a slot, at SECONDS_PER_SLOT / INTERVALS_PER_SLOT into a slot, and before proposing a block. However, on_tick() processing is light and it can be convenient to call it more often.

The Teku client calls on_tick() regularly twice per second since it is used internally to drive other things beside the fork choice. In addition, Teku uses units of milliseconds rather than seconds for its tick interval, which is strictly speaking off-spec, but is necessary for supporting other chains such as the Gnosis Beacon Chain for which the SECONDS_PER_SLOT is not a multiple of INTERVALS_PER_SLOT.

The while loop was introduced in the Capella specification. It ensures that the processing in on_tick_per_slot() is done every slot. When multiple slots have passed since the last tick was processed, the loop calls on_tick_per_slot() for each of them so as to catch up. The only thing this makes a difference to is updating the checkpoints at epoch boundaries. Previously, if a tick was not processed during the first slot of an epoch, then the checkpoint update could be incorrectly skipped. Note that on_tick_per_slot() updates store.time, which in turn updates the output of get_current_slot(), so the loop will terminate.

I expect that the reason time is provided as a parameter rather than looked up via the machine's clock is that it simplifies testing.

Uses get_current_slot(), on_tick_per_slot()
See also SECONDS_PER_SLOT

on_block

def on_block(store: Store, signed_block: SignedBeaconBlock) -> None:
    block = signed_block.message
    # Parent block must be known
    assert block.parent_root in store.block_states
    # Make a copy of the state to avoid mutability issues
    pre_state = copy(store.block_states[block.parent_root])
    # Blocks cannot be in the future. If they are, their consideration must be delayed until they are in the past.
    assert get_current_slot(store) >= block.slot

    # Check that block is later than the finalized epoch slot (optimization to reduce calls to get_ancestor)
    finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch)
    assert block.slot > finalized_slot
    # Check block is a descendant of the finalized block at the checkpoint finalized slot
    assert get_ancestor(store, block.parent_root, finalized_slot) == store.finalized_checkpoint.root

    # Check the block is valid and compute the post-state
    state = pre_state.copy()
    block_root = hash_tree_root(block)
    state_transition(state, signed_block, True)
    # Add new block to the store
    store.blocks[block_root] = block
    # Add new state for this block to the store
    store.block_states[block_root] = state

    # Add proposer score boost if the block is timely
    time_into_slot = (store.time - store.genesis_time) % SECONDS_PER_SLOT
    is_before_attesting_interval = time_into_slot < SECONDS_PER_SLOT // INTERVALS_PER_SLOT
    if get_current_slot(store) == block.slot and is_before_attesting_interval:
        store.proposer_boost_root = hash_tree_root(block)

    # Update checkpoints in store if necessary
    update_checkpoints(store, state.current_justified_checkpoint, state.finalized_checkpoint)

    # Eagerly compute unrealized justification and finality
    compute_pulled_up_tip(store, block_root)

The on_block() handler should be called whenever a new signed beacon block is received. It does the following.

  • Perform some validity checks:
  • Update the store with the block and its associated beacon state.
  • Handle proposer boost (block timeliness).
  • Update the Store's justified and finalised checkpoints if permitted and required.

The on_block() handler does not call the on_attestation() handler for the attestations it contains, so clients need to do that separately for each attestation.

Validity checks
    # Parent block must be known
    assert block.parent_root in store.block_states
    # Make a copy of the state to avoid mutability issues
    pre_state = copy(store.block_states[block.parent_root])
    # Blocks cannot be in the future. If they are, their consideration must be delayed until they are in the past.
    assert get_current_slot(store) >= block.slot

    # Check that block is later than the finalized epoch slot (optimization to reduce calls to get_ancestor)
    finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch)
    assert block.slot > finalized_slot
    # Check block is a descendant of the finalized block at the checkpoint finalized slot
    assert get_ancestor(store, block.parent_root, finalized_slot) == store.finalized_checkpoint.root

    # Check the block is valid and compute the post-state
    state = pre_state.copy()
    block_root = hash_tree_root(block)
    state_transition(state, signed_block, True)

First we do some fairly self-explanatory checks. In order to be considered in the fork choice, the block must be joined to the block tree that we already have (that is, its parent must be in the Store), it must not be from a future slot according to our Store's clock, and it must be from a branch that descends from our finalised checkpoint. By the definition of finalised, all prior branches from the canonical chain are pruned away.

The final check is to run a full state transition on the block. This has two purposes, (1) it checks that the block is valid with respect to the consensus rules, and (2) it gives us the block's post-state which we need to add to the Store. We got the block's pre-state from its parent, which we know is already in the store. The True parameter to state_transition() ensures that the block's signature is checked, and that the result of applying the block to the state results in the same state root that the block claims it does (the "post-states" must match). Clients will be running this operation elsewhere when performing the state transition, so it is likely that the result of the state_transition() call will be cached somewhere in an optimal implementation.

Update the Store
    # Add new block to the store
    store.blocks[block_root] = block
    # Add new state for this block to the store
    store.block_states[block_root] = state

Once the block has passed the validity checks, it and its post-state can be added to the Store.

Handle proposer boost
    # Add proposer score boost if the block is timely
    time_into_slot = (store.time - store.genesis_time) % SECONDS_PER_SLOT
    is_before_attesting_interval = time_into_slot < SECONDS_PER_SLOT // INTERVALS_PER_SLOT
    if get_current_slot(store) == block.slot and is_before_attesting_interval:
        store.proposer_boost_root = hash_tree_root(block)

Proposer boost is a defence against balancing attacks on LMD GHOST. It rewards timely blocks with extra weight in the fork choice, making it unlikely that an honest proposer's block will become orphaned.

Here, in the on_block() handler, is where the block's timeliness is assessed and recorded. If the Store's time (as set by the on_tick() handler) is within the first third of the slot (1 / INTERVALS_PER_SLOT, that is, 4 seconds) when the block is processed, then we set store.proposer_boost_root to the block's root.

The store.proposer_boost_root field can only be set during the first four seconds of a slot, and it is cleared at the start of the next slot by the on_tick() handler. It is used in the get_weight() function to determine whether to add the extra proposer boost weight or not.

Note that, if there is a proposer equivocation in the slot, this code will apply proposer boost to the second block received rather than to the first block received. This becomes important for the security of third-party block production with MEV-Boost - it can allow a proposer to "steal" the transactions in a block builder's block (at the cost of getting slashed), which is deemed to be a Bad Thing. It would be better to apply the proposer boost only to the first block received, and a small patch to on_block() has been proposed to implement this.

Update justified and finalised
    # Update checkpoints in store if necessary
    update_checkpoints(store, state.current_justified_checkpoint, state.finalized_checkpoint)

    # Eagerly compute unrealized justification and finality
    compute_pulled_up_tip(store, block_root)

update_checkpoints() simply updates the Store's justified and finalised checkpoints if those in the block's post-state are better (that is, higher, more recent). The Store always tracks the best known justified and finalised checkpoints that it is able to validate.

compute_pulled_up_tip() runs the epoch transition Casper FFG accounting on the block – notionally "pulling it up" from its current slot to the first slot of the next epoch – to see if it has achieved unrealised justification. The block's unrealised justification will be stored for later use by filter_block_tree(), and the Store's unrealised justification and unrealised finalisation trackers may be updated. If the block is from a previous epoch, then the unrealised checkpoints become realised, and update_checkpoints() will be called again, potentially over-writing the update we just made in the line above.

Uses get_current_slot(), compute_start_slot_at_epoch(), get_ancestor(), hash_tree_root(), state_transition(), update_checkpoints(), compute_pulled_up_tip()
See also INTERVALS_PER_SLOT

on_attestation

def on_attestation(store: Store, attestation: Attestation, is_from_block: bool=False) -> None:
    """
    Run ``on_attestation`` upon receiving a new ``attestation`` from either within a block or directly on the wire.

    An ``attestation`` that is asserted as invalid may be valid at a later time,
    consider scheduling it for later processing in such case.
    """
    validate_on_attestation(store, attestation, is_from_block)

    store_target_checkpoint_state(store, attestation.data.target)

    # Get state at the `target` to fully validate attestation
    target_state = store.checkpoint_states[attestation.data.target]
    indexed_attestation = get_indexed_attestation(target_state, attestation)
    assert is_valid_indexed_attestation(target_state, indexed_attestation)

    # Update latest messages for attesting indices
    update_latest_messages(store, indexed_attestation.attesting_indices, attestation)

Attestations may be useful no matter how we heard about them: they might have been contained in a block, or been received individually via gossip, or via a carrier pigeon16.

If the attestation was unpacked from a block then the flag is_from_block should be set to True. This causes the timeliness check in validate_on_attestation() to be skipped: attestations not from blocks must be received in the epoch they were produced in, or the next epoch, in order to influence the fork choice. (So, a carrier pigeon would need to be fairly swift.)

The validate_on_attestation() function performs a comprehensive set of validity checks on the attestation to defend against various attacks.

Assuming that the attestation passes the checks, we add its target checkpoint state to the Store for later use, as well as using it immediately. The store_target_checkpoint_state() function is idempotent, so nothing happens if the state is already present.

Having the target checkpoint state, we can use it to look up the correct shuffling for the validators. With the shuffling in hand, calling get_indexed_attestation() turns the Attestation object (containing a bitlist) into an IndexedAttestation object (containing a list of validator indices).

Finally, we can validate the indexed attestation with is_valid_indexed_attestation(), which amounts to checking its aggregate BLS signature against the set of public keys of this indexed validators. Checking the signatures is relatively expensive compared with the other checks, which is one reason for deferring it to last (we also don't want to be checking them against an inconsistent target).

If, and only if, everything has succeeded, we call update_latest_messages() to refresh the Store's list of latest messages for the validators that participated in this vote.

Uses validate_on_attestation(), store_target_checkpoint_state(), get_indexed_attestation(), is_valid_indexed_attestation(), update_latest_messages()

on_attester_slashing

Note: on_attester_slashing should be called while syncing and a client MUST maintain the equivocation set of AttesterSlashings from at least the latest finalized checkpoint.

def on_attester_slashing(store: Store, attester_slashing: AttesterSlashing) -> None:
    """
    Run ``on_attester_slashing`` immediately upon receiving a new ``AttesterSlashing``
    from either within a block or directly on the wire.
    """
    attestation_1 = attester_slashing.attestation_1
    attestation_2 = attester_slashing.attestation_2
    assert is_slashable_attestation_data(attestation_1.data, attestation_2.data)
    state = store.block_states[store.justified_checkpoint.root]
    assert is_valid_indexed_attestation(state, attestation_1)
    assert is_valid_indexed_attestation(state, attestation_2)

    indices = set(attestation_1.attesting_indices).intersection(attestation_2.attesting_indices)
    for index in indices:
        store.equivocating_indices.add(index)

The on_attester_slashing() handler was added to defend against the equivocation balancing attack (described more formally in Two Attacks On Proof-of-Stake GHOST/Ethereum). The attack relies on the adversary's validators equivocating about their attestations – that is, publishing multiple different attestations per epoch – and is not solved by proposer score boosting.

Of course, the equivocating attestations are slashable under the Casper FFG commandments. When the attack finally ends, those validators will be punished and ejected from the validator set. Meanwhile, however, since the fork choice calculations are based on the validator set at the last justified epoch, the adversary's validators could keep the attack going indefinitely.

Rather than add a lot of apparatus within the fork choice to track and detect conflicting attestations, the mechanism relies on third-party slashing claims received via blocks or directly from peers as attester slashing messages. The validity checks are identical to those in the state-transition's process_attester_slashing() method, including the use of is_slashable_attestation_data(). This is broader that we need for our purposes here as it will exclude validators that make surround votes as well as validators that equivocate. But excluding all misbehaving validators is probably a good idea.

Any validators proven to have made conflicting attestations are added to the store.equivocating_indices set17. They will no longer be involved in calculating the weight of branches, and their future attestations will be ignored in the fork choice. We are permitted to clear any equivocating attestation information from before the last finalised checkpoint, but those validators would have been slashed by the state-transition by then, so this ban is permanent.

Uses is_slashable_attestation_data(), is_valid_indexed_attestation()
See also AttesterSlashing, process_attester_slashing()

  1. "Ex-post" reorgs occur when a proposer orphans the block in the previous slot by building on an ancestor. "Ex-ante" reorgs occur when a proposer arranges to orphan the next block by submitting its own proposal late. Caspar Schwarz-Schilling made a nice Twitter thread explainer.
  2. It's interesting to see some explanation finding its way back into the spec documents now, after it was all diligently stripped out a while ago. Turns out that people appreciate explanations, I guess.
  3. "Greedy Heaviest-Observed Sub-Tree", named by Sompolinsky and Zohar.
  4. For example, blocks in slot 4939809 and slot 4939815 had almost no votes and yet became canonical. They were almost certainly published late – apparently by the same operator, Legend – but in time for the next proposer to build on them. The late publishing may have been due to a simple clock misconfiguration, or it may have been a deliberate strategy to gain more transaction income post-merge. In either case, it is undesirable.
  5. View-merge, though not by that name, was first proposed for Ethereum in October 2021 in the Ethresear.ch post, Change fork choice rule to mitigate balancing and reorging attacks. See also this Twitter thread for more explanation of view-merge.
  6. To find the section 6.3 that this quote refers to, you need to see the original v1 version of the Goldfish paper. That section is omitted from the later version of the paper.
  7. This scenario doesn't strictly break Casper FFG's "plausible liveness" property as, in principle, voters can safely ignore the LMD GHOST fork choice and switch back to the original chain in order to advance finality. But it does create a conflict between the LMD GHOST fork choice rule and advancing finality.
  8. Some evidence for how challenging the fork choice is to reason about is provided by the formal proofs of correctness created by Roberto Saltini and team at Consensys. One of the proofs alone is 28 pages long when printed.
  9. I am grateful to Mikhail Kalinin for helping me with his very lucid and careful explanation. My explanation is based on his; any errors and over-simplifications are all my own work.
  10. However, there remain some assumptions in the proofs that are over-simplified, such as, "No bound on the amount of attestations that can be included in a block", and, "Honest nodes do not discard any attestation that they receive regardless of how old it is". There is some history of failed proofs around the fork choice that were based on assumptions that were too broad. Hopefully these will stand; I am not equipped to judge.
  11. The algorithm is recursive, although it is not written recursively here.
  12. See section 4.6 of that paper.
  13. Changing time from seconds to slots in the fork choice has been suggested, but never adopted.
  14. FMD vs LMD GHOST is discussed further in the Ethresear.ch article, Saving strategy and FMD GHOST. Later work, such as the Goldfish protocol and RLMD GHOST, take vote-expiry further.
  15. One such inconsistency remains: attestations are valid in gossip for up to two epochs, but for only 32 slots in blocks.
  16. This would change were we to adopt view-merge. Only attestations that had been processed by specifically designated aggregators would be considered in the fork choice.
  17. store.equivocating_indices is a Python Set. Adding an existing element again is a no-op, so it cannot grow without bounds.

Created by Ben Edgington. Licensed under CC BY-SA 4.0. Published 2023-09-29 14:16 UTC. Commit ebfcf50.