Gloas Annotated: Forkchoice

This is the third post on the series of annotating the Gloas fork. In this post we will go over the forkchoice changes. Some final details are still missing in forkchoice, particularly dealing with PTC dual deadlines and how to handle the data available boolean in the PTC attestations. Since there seem to be a global agreement on these remaining changes, I take the liberty of indicating them here, even though they may not be accurately what will end up in the final spec. These will be clearly marked in this document and they are anyway very minor modifications to the current specification.

My gratitude goes to Manu Nalepa for continuing to send corrections.

Introduction

In today’s Ethereum, most of the time, for a given slot, there is a maximum of one beacon block that would be valid. Validators need to consider the possibility that this block exists, is part of the canonical chain, or it doesn’t. Most of the time proposers for a slot, say 34, when presented with a reorg scenario like the following:

need to decide between building on top of the latest block they received (in this case block 33) or the previous one (in this case block 32). In the top chain the block 33 will appear as skipped, in the bottom chain the block 32 would be skipped. Block can either be full or skipped.

EIP-7732 brings an entire new type of forkchoice node, that is the fact that for a given slot, say 32, the consensus block of that slot may be canonical, but the corresponding execution payload may be missing. For historical reasons I’ll call these slots empty here and will denote them in orange. There is a new type of reorg now in which a proposer can try to reorg only the execution payload of a past slot, but not necessarily its beacon block. So, in the following situation:

The proposer of 33 has chosen to reorg the payload of 32, the proposer of 34 needs to choose whether to build on top of 33 (in this case with its payload), or on top of 32 with its payload. Of course many other options are there. The proposer of 34 could build on top of 33 without its payload, on top of 32 wihout its payload, etc. But what this situation shows is that there is this new kind of possible reorg in which the chain on top has only a single payload missing (that of 32) while the chain at the bottom has a full block missing (that of 33). On the top chain, the orange node shows the slot 32 is empty, while in the bottom, the missing slot 33 is skipped.

New/Modified structures

We could have rewritten entirely forkchoice from scratch since the existence of an entirely new node structure makes the existing protoarray a little awkward to work with. But this would have been quite invasive for clients which already have a working forkchoice. So instead, we adapted our current forkchoice to this new reality, by adding a new structure and modifying another.

ForkchoiceNode

class ForkChoiceNode(Container):
    root: Root
    payload_status: PayloadStatus

This structure represents a node as above, where the payload_status field can take values PAYLOAD_STATUS_PENDING, used when the payload is still expected to appear, for example in the white nodes like 34 above; PAYLOAD_STATUS_EMPTY meaning an orange node as above; the payload was not included or PAYLOAD_STATUS_FULL, meaning a ligthblue node as above.

Some explanations are in order with regards to the status PAYLOAD_STATUS_PENDING. The Python specs does not track ForkChoiceNode objects in the store. It rather keeps all post-states after syncing blocks and optional payloads. The object ForkChoiceNode is returned on internal helpers when granularity about the payload status of the node is needed. Thus these ForkChoiceNode objects are created in calls to get_ancestor, get_node_children and get_head. The value PAYLOAD_STATUS_PENDING is used internally in these functions while iterating, a little more detail will be added below, but when computing the head, the loop starts at the justified checkpoint with payload status PAYLOAD_STATUS_PENDING and get_node_children always returns at least one child with PAYLOAD_STATUS_EMPTY and the same root. If there are actual beacon blocks that descend from them, get_node_children will return a list, all of which will have PAYLOAD_STATUS_PENDING and the next iteration of the loop returns nodes with actual valid payload statuses (either empty or full). So the current Python implementation overloads the meaning of pending to deal with this loop descending on children. In a sense, the forkchoice node with PAYLOAD_STATUS_PENDING plays the role of being the parent of both the nodes with the same beacon block root but with PAYLOAD_STAUS_EMPTY or PAYLOAD_STATUS_FULL. This plays a role below in is_supporting_vote because both votes for empty or full support the node with status pending.

LatestMessage

@dataclass(eq=True, frozen=True)
class LatestMessage(object):
    slot: Slot
    root: Root
    payload_present: boolean

Attestations in Gloas overloaded the index field so as to signal if they were attesting for a full or emtpy slot, we include this value in the payload_present boolean of the LatestMessage modified structure. Also, we keep track of the slot instead of the epoch, to deal with the case of same slot attestations vs attestations for older blocks, as we already explained in the first post of this series.

Since on forkchoice we only store valid attestations, the slot strictly gives the right epoch, since the epoch is guaranteed to be that of the target checkpoint which is guaranteed to be the epoch corresponding to this slot. Validators cannot attest to different messages on different slots on the same epoch without being slashed.

update_latest_messages

def update_latest_messages(
    store: Store, attesting_indices: Sequence[ValidatorIndex], attestation: Attestation
) -> None:
    slot = attestation.data.slot
    beacon_block_root = attestation.data.beacon_block_root
    payload_present = attestation.data.index == 1
    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 slot > store.latest_messages[i].slot:
            store.latest_messages[i] = LatestMessage(
                slot=slot, root=beacon_block_root, payload_present=payload_present
            )

The only difference in this function is that we use the slot instead of the epoch in the latest message.

Store

@dataclass
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)
    block_timeliness: Dict[Root, Vector[boolean, NUM_BLOCK_TIMELINESS_DEADLINES]] = 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)
    # [New in Gloas:EIP7732]
    execution_payload_states: Dict[Root, BeaconState] = field(default_factory=dict)
    # [New in Gloas:EIP7732]
    ptc_vote: Dict[Root, Vector[boolean, PTC_SIZE]] = field(default_factory=dict)

The two additions are there to be able to track different types of nodes. The existing dictionary block_states used to track the post-state after syncing a block. After Gloas, this post-state does not include the execution payload processing, thus, it corresponds to an empty or orange node as above. We add a new dictionary of states that tracks the post-state after processing the execution payload, which corresponds to full or lightblue nodes as above. The ptc_vote keeps track of the PTC attestations that were cast for the block.

This structure is very likely to change to add minor tweaks. There is currently this open PR to track independently the PTC vote for data availability. It would rename the latest field and add a new one:

    # [New in Gloas:EIP7732]
    payload_timeliness_vote: Dict[Root, Vector[boolean, PTC_SIZE]] = field(default_factory=dict)
    # [New in Gloas:EIP7732]
    payload_data_availability_vote: Dict[Root, Vector[boolean, PTC_SIZE]] = field(default_factory=dict)

The point of this addition is that Data availability votes and Payload timeliness votes from different committee members can be used to achieve independent quorum for either one as we explained in the first post of this series.

Because the Store is modified, we need to modify the corresponding getter:

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)},
        block_timeliness={anchor_root: [True, True]},
        checkpoint_states={justified_checkpoint: copy(anchor_state)},
        unrealized_justifications={anchor_root: justified_checkpoint},
        # [New in Gloas:EIP7732]
        execution_payload_states={anchor_root: copy(anchor_state)},
        # [New in Gloas:EIP7732]
        payload_timeliness_vote={anchor_root: Vector[boolean, PTC_SIZE]()},
        # [New in Gloas:EIP7732]
        payload_data_availability_vote={anchor_root: Vector[boolean, PTC_SIZE]()},
    )

Payload Attestations

When receiving a payload attestation, the following helper is called

on_payload_attestation_message

def on_payload_attestation_message(
    store: Store, ptc_message: PayloadAttestationMessage, is_from_block: bool = False
) -> None:
    """
    Run ``on_payload_attestation_message`` upon receiving a new ``ptc_message`` from
    either within a block or directly on the wire.
    """
    # The beacon block root must be known
    data = ptc_message.data
    # PTC attestation must be for a known block. If block is unknown, delay consideration until the block is found
    state = store.block_states[data.beacon_block_root]
    ptc = get_ptc(state, data.slot)
    # PTC votes can only change the vote for their assigned beacon block, return early otherwise
    if data.slot != state.slot:
        return
    # Check that the attester is from the PTC
    assert ptc_message.validator_index in ptc

    # Verify the signature and check that its for the current slot if it is coming from the wire
    if not is_from_block:
        # Check that the attestation is for the current slot
        assert data.slot == get_current_slot(store)
        # Verify the signature
        assert is_valid_indexed_payload_attestation(
            state,
            IndexedPayloadAttestation(
                attesting_indices=[ptc_message.validator_index],
                data=data,
                signature=ptc_message.signature,
            ),
        )
    # Update the votes for the block
    ptc_index = ptc.index(ptc_message.validator_index)
    payload_timeliness_vote = store.payload_timeliness_vote[data.beacon_block_root]
    payload_timeliness_vote[ptc_index] = data.payload_present
    payload_data_availability_vote = store.payload_data_availability_vote[data.beacon_block_root]
    payload_data_availability_vote[ptc_index] = data.blob_data_available

We only consider attestations for blocks that we already know, so we can get the post-state of processing that beacon block. We only consider attestations for that same slot, then verify the signature and update the two vote dictionaries in the store

notify_ptc_messages

This helper is called from block processing when processing payload attestations

def notify_ptc_messages(
    store: Store, state: BeaconState, payload_attestations: Sequence[PayloadAttestation]
) -> None:
    """
    Extracts a list of ``PayloadAttestationMessage`` from ``payload_attestations`` and updates the store with them
    These Payload attestations are assumed to be in the beacon block hence signature verification is not needed
    """
    if state.slot == 0:
        return
    for payload_attestation in payload_attestations:
        indexed_payload_attestation = get_indexed_payload_attestation(state, payload_attestation)
        for idx in indexed_payload_attestation.attesting_indices:
            on_payload_attestation_message(
                store,
                PayloadAttestationMessage(
                    validator_index=idx,
                    data=payload_attestation.data,
                    signature=BLSSignature(),
                ),
                is_from_block=True,
            )

It just extracts the indexed payload attestations to make the corresponding PayloadAttestationMessage that the helper on_payload_attestation takes. Recall that we decided to have different object for single payload attestations than for aggregated ones. This is the price to pay to avoid having to deal with single bit bitlists.

is_payload_timely

This helper just parses the payload timeliness vote and checks if there was a threshold to consider it timely.

def is_payload_timely(store: Store, root: Root) -> bool:
    """
    Return whether the execution payload for the beacon block with root ``root``
    was voted as present by the PTC, and was locally determined to be available.
    """
    # The beacon block root must be known
    assert root in store.payload_timeliness_vote

    # If the payload is not locally available, the payload
    # is not considered available regardless of the PTC vote
    if root not in store.execution_payload_states:
        return False

    return sum(store.payload_timeliness_vote[root]) > PAYLOAD_TIMELY_THRESHOLD

is_payload_data_available

This helper just parses the payload timeliness vote and checks if there was a threshold to consider its blob data available

def is_payload_data_available(store: Store, root: Root) -> bool:
    """
    Return whether the blob data for the beacon block with root ``root``
    was voted as present by the PTC, and was locally determined to be available.
    Implemnetations MAY return `True` if the node have recovered all the blob data.
    """
    # The beacon block root must be known
    assert root in store.payload_data_availability_vote

    # If the payload is not locally available, the blob data
    # is not considered available regardless of the PTC vote
    if root not in store.execution_payload_states:
        return False

    return sum(store.payload_data_availability_vote[root]) > DATA_AVAILABILITY_TIMELY_THRESHOLD

Notice that these helpers exploit the fact that nodes cannot sync an execution payload envelope whose data was not considered to be available.

Parent status

One of the common themes in implementing block processing is what is the parent of the incoming block?. Before Gloas, one would simply take the store.block_states entry for the parent block root. This is no longer the case as this would point to the empty slot. When receiving a beacon block, we need to decide also its execution layer parent to see if it is building on top of an empty or a full slot. These helpers deal with this.

get_parent_payload_status

def get_parent_payload_status(store: Store, block: BeaconBlock) -> PayloadStatus:
    parent = store.blocks[block.parent_root]
    parent_block_hash = block.body.signed_execution_payload_bid.message.parent_block_hash
    message_block_hash = parent.body.signed_execution_payload_bid.message.block_hash
    return PAYLOAD_STATUS_FULL if parent_block_hash == message_block_hash else PAYLOAD_STATUS_EMPTY

is_parent_node_full

def is_parent_node_full(store: Store, block: BeaconBlock) -> bool:
    return get_parent_payload_status(store, block) == PAYLOAD_STATUS_FULL

Notice that these helpers have nothing to do with the PTC, they just take a node and check if its parent is full or empty. Also notice that here I say “take a node” but these functions take a beacon block. The reason is that both full or empty nodes for a given beacon block root, point to the same parent. The helper exploits the fact that if the parent node is empty, then the CL parent’s block will have in its committed bid the same block hash as the incoming block’s bid parent hash.

get_ancestor

def get_ancestor(store: Store, root: Root, slot: Slot) -> ForkChoiceNode:
    """
    Returns the beacon block root and the payload status of the ancestor of the beacon block
    with ``root`` at ``slot``. If the beacon block with ``root`` is already at ``slot`` or we are
    requesting an ancestor "in the future", it returns ``PAYLOAD_STATUS_PENDING``.
    """
    block = store.blocks[root]
    if block.slot <= slot:
        return ForkChoiceNode(root=root, payload_status=PAYLOAD_STATUS_PENDING)

    parent = store.blocks[block.parent_root]
    while parent.slot > slot:
        block = parent
        parent = store.blocks[block.parent_root]

    return ForkChoiceNode(
        root=block.parent_root,
        payload_status=get_parent_payload_status(store, block),
    )

Recall from above that getting a parent (and therefore an ancestor) to a forkchoice node, is the same as getting the parent/ancestor to the corresponding beacon block root. The parent node however needs to be a full ForkChoiceNode since it has a unique payload status, it is either empty or full. This function however, is some times called with block.slot <= slot. This is because sometimes we want to evaluate head and have advanced the head block to a slot in the future (think for example on missing slots). In these cases, we return simply PAYLOAD_STATUS_PENDING. The Gloas forkchoice spec reduce the number of calls to get_ancestor.

get_checkpoint_block

This function is only modified because get_ancestor now returns a ForkchoiceNode instead of a Root.

def get_checkpoint_block(store: Store, root: Root, epoch: Epoch) -> Root:
    """
    Compute the checkpoint block for epoch ``epoch`` in the chain of block ``root``
    """
    epoch_first_slot = compute_start_slot_at_epoch(epoch)
    return get_ancestor(store, root, epoch_first_slot).root

is_supporting_vote

def is_supporting_vote(store: Store, node: ForkChoiceNode, message: LatestMessage) -> bool:
    """
    Returns whether a vote for ``message.root`` supports the chain containing the beacon block ``node.root`` with the
    payload contents indicated by ``node.payload_status`` as head during slot ``node.slot``.
    """
    block = store.blocks[node.root]
    if node.root == message.root:
        if node.payload_status == PAYLOAD_STATUS_PENDING:
            return True
        assert message.slot >= block.slot
        if message.slot == block.slot:
            return False
        if message.payload_present:
            return node.payload_status == PAYLOAD_STATUS_FULL
        else:
            return node.payload_status == PAYLOAD_STATUS_EMPTY
    else:
        ancestor = get_ancestor(store, message.root, block.slot)
        return node.root == ancestor.root and
            node.payload_status == PAYLOAD_STATUS_PENDING
            or node.payload_status == ancestor.payload_status
        )

This is at the core of the changes in EIP-7732. The docstring describes what this function is meant to do: given an attestation encoded in message, does it support the forkchoice node node? Let us analyze the first branch of the if-else statement.

Attestations directly for the node’s root

Recall our discussion above about the meaning of the pending payload status. Any vote for the beacon block root, either both for empty or full status, do count for the pending state, this is the statement of the first branch. The last two branches are the obvious ones, attestations for full should not count for empty and viceversa.

The assert is enforcing the same rule that is added in validate_on_attestation to deal with blocks from the future. The case when message.slot == block.slot is to deal with same slot attestations, which should support the pending status, but neither empty nor full.

Attestations for a different block root

When the attestation’s block root is not the same as the node’s, we request the ancestor at that slot. The function get_ancestor only returns PAYLOAD_STATUS_PENDING when the message’s block root’s slot is less or equal than block.slot. In this case, the return of get_ancestor will be

ForkChoiceNode(root=message.root, payload_status=PAYLOAD_STATUS_PENDING)

and therefore node.root != ancestor.root because we are in the branch where these two roots are different in fact. Thus, these votes do not support the node. Notice that in this case, the block is in the future of the attestation or in the same slot but in a contending branch, thus these attesttations definitely should not support the block’s root.

Otherwise, get_ancestor returns exactly one node, either full or empty, attestations for both full or empty support the pending status for that root, otherwise the attestation’s ancestor has to have the right payload status.

For example, in the following situation

An attester during slot 33 that did not like the payload reorg, will attest for the root of 32 with the payload present. That attestation supports the beacon block root of 32 as head (it would correspond to PAYLOAD_STATUS_PENDING), it also supports the beacon block root of 32 with the payload present as head (PAYLOAD_STATUS_FULL), but it does not support the orange branch that has PAYLOAD_STATUS_EMPTY.

Conversely, an attestation for the block root of 33, will support the forkchoice node with root 32 and PAYLOAD_STATUS_PENDING, but it does not support the lightblue branch in the bottom because it contains the block root of 32 with PAYLOAD_STATUS_PRESENT which is different than the ancestor’s of the message with root 33: the ancestor will be the root of 32 with PAYLOAD_STATUS_EMPTY.

should_extend_payload

def should_extend_payload(store: Store, root: Root) -> bool:
    proposer_root = store.proposer_boost_root
    if not is_payload_data_available(store, root):
        return False
    return (
        is_payload_timely(store, root)
        or proposer_root == Root()
        or store.blocks[proposer_root].parent_root != root
        or is_parent_node_full(store, store.blocks[proposer_root])
    )

This function is called to decide on a tie breaker between empty or full when head is from the previous slot. If the data is not available for that payload, we should not extend that payload. Notice that the payload will not even be in the store if the data is not deemed locally available. The helper is_payload_data_available takes the PTC vote into account. All the branches that lead to extending the payload are simple to reason about

• If the payload was timely, we extend it to protect the builder from grieving.
• If there is no proposer boost set, which would happen if no block has arrived for the current slot for example, we extend on the payload.
• If there was a timely block but is not built on top of head, then we also extend the payload, this is to prevent the new proposer reorging the payload.
• Finally if the new timely block has arrived and is built on top of our head with its payload, then we extend the payload, that is, follow the branch of the incoming block.

So essentially the only way in which we will return false on this function would be if the incoming timely consensus block, is based on top of our head without a payload, and the payload was late from our perspective, that is, we let the incoming block reorg late payloads.

get_payload_status_tiebreaker

def get_payload_status_tiebreaker(store: Store, node: ForkChoiceNode) -> uint8:
    if node.payload_status == PAYLOAD_STATUS_PENDING or store.blocks[
        node.root
    ].slot + 1 != get_current_slot(store):
        return node.payload_status
    else:
        # To decide on a payload from the previous slot, choose
        # between FULL and EMPTY based on `should_extend_payload`
        if node.payload_status == PAYLOAD_STATUS_EMPTY:
            return 1
        else:
            return 2 if should_extend_payload(store, node.root) else 0

This function is called when running our head loop. It’s used to decide between full or empty branches of a node’s children. The head loop alternates between nodes with PAYLOAD_STATUS_PENDING and children with empty and full payloads. This function overloads the value of the enums of PayloadStatus to use their actual numeric value. Full payloads are by default preferred. If we are trying to decide the tie breaker for any child other than the previous slot, we will prefer the full node over the empty node over the pending node. This function is called to decide between children that all have PAYLOAD_STATUS_PENDING or none have this status. In the former case the root should already decide the tie-breaker so the first check seems superfluous, there is an open PR to remove it.

Let us analyze the main two cases in which this tie breaker plays a role. The head loop has reached a node of the fork root, PAYLOAD_STATUS_PENDING, and the block with this root is from the previous slot. There are two children, the empty and the full ones. And there is a timely incoming block in this slot that is reorging the payload. We haven’t processed any attestations for the current slot, since attestations can only be processed after one slot. Therefore all attestations from the previous slot, towards root cannot count for full or empty, they are same slot attestations and thus they support the pending status. In this situation the tiebreaker has to be invoked as both children have the same root, both have the same weight (no attestation supports them). If the payload wasn’t timely for example and the current slot’s block was timely based on empty, should_extend_payload will return False as explained above and the empty branch will win, making the incoming block the head. If on the other hand the payload was timely, the full branch will win, and that will be the head, ignoring the incoming beacon block root, even it if was timely.

should_apply_proposer_boost

def should_apply_proposer_boost(store: Store) -> bool:
    if store.proposer_boost_root == Root():
        return False

    block = store.blocks[store.proposer_boost_root]
    parent_root = block.parent_root
    parent = store.blocks[parent_root]
    slot = block.slot

    # Apply proposer boost if `parent` is not from the previous slot
    if parent.slot + 1 < slot:
        return True

    # Apply proposer boost if `parent` is not weak
    if not is_head_weak(store, parent_root):
        return True

    # If `parent` is weak and from the previous slot, apply
    # proposer boost if there are no early equivocations
    equivocations = [
        root
        for root, block in store.blocks.items()
        if (
            store.block_timeliness[root][PTC_TIMELINESS_INDEX]
            and block.proposer_index == parent.proposer_index
            and block.slot + 1 == slot
            and root != parent_root
        )
    ]

    return len(equivocations) == 0

This helper is used to check when proposer boost should be applied. The main idea behind this function is to prevent a proposer holding two blocks in a row, to grieve the builder of the first slot by releasing an equivocation and then proposing their second block on top of one of the equivocations, reorging the revealed payload (and one of the equivocations) and unblinding the builder. Proposer boost is always applied if there are no equivocations. Anf if there are equivocations it is not applied to weak, equivocating blocks from the previous slot. This is so that proposers that see these blocks they need to reorg them, and if they don’t we do not apply proposer boost to them.

See the full explanation for these scenarios analyzed here in this PR.

The new addition in the case of equivocations here is the check for block_timeliness that now records both the timeliness of the consensus block and of the payload. The idea is that any equivocation that arrived before the PTC deadline, should have been seen by the next proposer and thus it should have reorged the weak head. Blocks that arrived after the PTC deadline may not have been honestly seen by the proposer so we do not count them here to not penalize unfairly the proposer.

get_attestation_score

def get_attestation_score(
    store: Store,
    # [Modified in Gloas:EIP7732]
    # Removed `root`
    # [New in Gloas:EIP7732]
    node: ForkChoiceNode,
    state: BeaconState,
) -> Gwei:
    unslashed_and_active_indices = [
        i
        for i in get_active_validator_indices(state, get_current_epoch(state))
        if not state.validators[i].slashed
    ]
    return 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
                # [Modified in Gloas:EIP7732]
                and is_supporting_vote(store, node, store.latest_messages[i])
            )
        )
    )

This function is simply modified to use is_supporting_vote as the logic is more complicated than simply checking for the ancestor’s root.

get_weight

def get_weight(
    store: Store,
    # [Modified in Gloas:EIP7732]
    node: ForkChoiceNode,
) -> Gwei:
    if node.payload_status == PAYLOAD_STATUS_PENDING or store.blocks[
        node.root
    ].slot + 1 != get_current_slot(store):
        state = store.checkpoint_states[store.justified_checkpoint]
        attestation_score = get_attestation_score(store, node, state)
        if not should_apply_proposer_boost(store):
            # Return only attestation score if
            # proposer boost should not apply
            return attestation_score

        # Calculate proposer score if `proposer_boost_root` is set
        proposer_score = Gwei(0)

        # `proposer_boost_root` is treated as a vote for the
        # proposer's block in the current slot. Proposer boost
        # is applied accordingly to all ancestors
        message = LatestMessage(
            slot=get_current_slot(store),
            root=store.proposer_boost_root,
            payload_present=False,
        )
        if is_supporting_vote(store, node, message):
            proposer_score = get_proposer_score(store)

        return attestation_score + proposer_score
    else:
        return Gwei(0)

This function returns the main value that is compared when traversing the forkchoice tree, it returns all the attestation weight (and possible proposer boost root) that support the node. We should notice the first check to see if the payload status is PAYLOAD_STATUS_PENDING or if the slot is not the previous slot. Attestations for the beacon block from the previous slot are only considered for the pending status. This is because they could not possibly have attested for either full or empty. For previous slots we do consider the weight that supported either full or empty.

Attestation score is obtained with a call to get_attestation_score described below, the proposer boost is added as if it were an attestation. We create a fake attestation for the current slot and the proposer boost root, with index==0 to signal the pending status. If this attestation supports the given node, then we add the full proposer boost score.

get_node_children

def get_node_children(
    store: Store, blocks: Dict[Root, BeaconBlock], node: ForkChoiceNode
) -> Sequence[ForkChoiceNode]:
    if node.payload_status == PAYLOAD_STATUS_PENDING:
        children = [ForkChoiceNode(root=node.root, payload_status=PAYLOAD_STATUS_EMPTY)]
        if node.root in store.execution_payload_states:
            children.append(ForkChoiceNode(root=node.root, payload_status=PAYLOAD_STATUS_FULL))
        return children
    else:
        return [
            ForkChoiceNode(root=root, payload_status=PAYLOAD_STATUS_PENDING)
            for root in blocks.keys()
            if (
                blocks[root].parent_root == node.root
                and node.payload_status == get_parent_payload_status(store, blocks[root])
)
        ]

This helper is used when iterating over the forkchoice tree. It alternates between pending status and empty/full statuses. The main idea here is the following. A forkchoice node can be thought as two parts. There is a consensus part that is created when importing a beacon block. This consensus part is already enough to pick a unique full parent: the consensus block specifies explcitly the parent consensus block and the parent execution block.

The other part of the forkchoice node has to do with execution. Either the payload was included or not. There are no possible equivocations on payloads because the block hash is specified in the signed bid that is committed in the consensus block. Thus the consensus part of the node is already enough to specify a parent, but only full forkchoice nodes can have children (as each child specifies the payload status).

The approach we take when traversing the forkchice tree is that a forkchoice node with PAYLOAD_STATUS_PENDING corresponds to the consensus side part of the node only. It is already good enough to specify uniquely a parent, but not enough to specify children. A full node (with payload status either empty or full) points uniquely to a pending one since it contains the consensus side.

Hence we alternate as follows. We start from the justified checkpoint with pending status (this is only the consensus part ot the node) and construct full nodes both with empty or full status (if we have seen a payload for this node). Each of these full nodes has a list of children that consist of nodes only with pending status (as the consensus part is enough to specify the parent full node), attestation for either full or empty count towards the pending status, thus we first decide among the pending children and then we go down the winning child and repeat the process.

This is the reason for the two branches in the helper: for pending nodes we always add an empty child and optionally add a full child if we have synced the corresponding payload. On the other hand for either full or empty nodes, we only add children of pending status, one for each beacon block root that descends from the given full node.

get_head

def get_head(store: Store) -> ForkChoiceNode:
    # Get filtered block tree that only includes viable branches
    blocks = get_filtered_block_tree(store)
    # Execute the LMD-GHOST fork-choice
    head = ForkChoiceNode(
        root=store.justified_checkpoint.root,
        payload_status=PAYLOAD_STATUS_PENDING,
    )

    while True:
        children = get_node_children(store, blocks, head)
        if len(children) == 0:
            return head
        # Sort by latest attesting balance with ties broken lexicographically
        head = max(
            children,
            key=lambda child: (
                get_weight(store, child),
                child.root,
                get_payload_status_tiebreaker(store, child),
            ),
        )

This is a minor change, we start the traversing from the justified checkpoint consensus block (we will consider heads that descend from either full or empty) and alternate. For each full node we first decode by checking on the weight of the pending nodes that descend from it, if there is a tie we decide by the root, as we did in previous forks. Once we have chosen a pending node we descend to it and now decide among the full or empty children. Weight can be actually different since attesters do signal payload preference when voting for previous slots. If the weight is equal then the root will be equal anyway because these are all descendents of the same pending node, so tiebreakers are decided by get_payload_status_tiebreaker explained above.

record_block_timeliness

def record_block_timeliness(store: Store, root: Root) -> None:
    block = store.blocks[root]
    seconds_since_genesis = store.time - store.genesis_time
    time_into_slot_ms = seconds_to_milliseconds(seconds_since_genesis) % SLOT_DURATION_MS
    epoch = get_current_store_epoch(store)
    attestation_threshold_ms = get_attestation_due_ms(epoch)
    # [New in Gloas:EIP7732]
    is_current_slot = get_current_slot(store) == block.slot
    ptc_threshold_ms = get_payload_attestation_due_ms(epoch)
    # [Modified in Gloas:EIP7732]
    store.block_timeliness[root] = [
        is_current_slot and time_into_slot_ms < threshold
        for threshold in [attestation_threshold_ms, ptc_threshold_ms]
    ]

This is simply modified track not only when blocks arrive before the attestation threshold but also the payload timeliness committee threshold. The latter is used in case of equivocations to apply proposer boost as described in should_apply_proposer_boost.

update_proposer_boost_root

def update_proposer_boost_root(store: Store, root: Root) -> None:
    is_first_block = store.proposer_boost_root == Root()
    # [Modified in Gloas:EIP7732]
    is_timely = store.block_timeliness[root][ATTESTATION_TIMELINESS_INDEX]

    # Add proposer score boost if the block is the first timely block
    # for this slot, with the same proposer as the canonical chain.
    if is_timely and is_first_block:
        head_state = copy(store.block_states[get_head(store).root])
        slot = get_current_slot(store)
        if head_state.slot < slot:
            process_slots(head_state, slot)
        block = store.blocks[root]
        # Only update if the proposer is the same as on the canonical chain
        if block.proposer_index == get_beacon_proposer_index(head_state):
            store.proposer_boost_root = root

The only change here is with respect to using the block timeliness for the attestation deadline explicitly (and not the PTC deadline).

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.
    block_slot = store.blocks[attestation.data.beacon_block_root].slot
    assert block_slot <= attestation.data.slot

    # [New in Gloas:EIP7732]
    assert attestation.data.index in [0, 1]
    if block_slot == attestation.data.slot:
        assert attestation.data.index == 0

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

    # 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

The only change in this function is that we enforce here that the index field has to be 0 for same-slot attestations, while it can only be 0 or 1 for previous slot ones.

is_head_late

def is_head_late(store: Store, head_root: Root) -> bool:
    return not store.block_timeliness[head_root][ATTESTATION_TIMELINESS_INDEX]

The only change is to explicitly use the ATTESTATION_TIMELINESS_INDEX to recover the previous behavior.

is_head_weak

def is_head_weak(store: Store, head_root: Root) -> bool:
    # Calculate weight threshold for weak head
    justified_state = store.checkpoint_states[store.justified_checkpoint]
    reorg_threshold = calculate_committee_fraction(justified_state, REORG_HEAD_WEIGHT_THRESHOLD)

    # Compute head weight including equivocations
    head_state = store.block_states[head_root]
    head_block = store.blocks[head_root]
    epoch = compute_epoch_at_slot(head_block.slot)
    head_node = ForkChoiceNode(root=head_root, payload_status=PAYLOAD_STATUS_PENDING)
    head_weight = get_attestation_score(store, head_node, justified_state)
    for index in range(get_committee_count_per_slot(head_state, epoch)):
        committee = get_beacon_committee(head_state, head_block.slot, CommitteeIndex(index))
        head_weight += Gwei(
            sum(
                justified_state.validators[i].effective_balance
                for i in committee
                if i in store.equivocating_indices
            )
        )

    return head_weight < reorg_threshold

The addition in this function is to explicitly add the weights of equivocating indices that are in the committee of the head slot. The reason is so that these extra attestations the worst that they can do is make the head not weak and thus not penalize a proposer that builds on top of it as described in should_apply_proposer_boost. Otherwise, equivocating validators could trick the proposer to think that the head is not weak, propose on top of it, and see its block reorged because attesters did not count these equivocating attestations and considered the head weak, and thus try to enforce that the propsoer should reorg it in case of equivocations.

is_parent_strong

def is_parent_strong(store: Store, root: Root) -> bool:
    justified_state = store.checkpoint_states[store.justified_checkpoint]
    parent_threshold = calculate_committee_fraction(justified_state, REORG_PARENT_WEIGHT_THRESHOLD)
    block = store.blocks[root]
    parent_payload_status = get_parent_payload_status(store, block)
    parent_node = ForkChoiceNode(root=block.parent_root, payload_status=parent_payload_status)
    parent_weight = get_attestation_score(store, parent_node, justified_state)
    return parent_weight > parent_threshold

This helper is changed because it uses the function get_attestation_score which requires a node and not just a root, notice that this function no longer counts proposer boost. There is an open issue about this.

Duties due timestamps

The following helpers are changed due to the timings within the slot being changed, with the addition of the new payload attestation deadline.

get_attestation_due_ms

def get_attestation_due_ms(epoch: Epoch) -> uint64:
    # [New in Gloas]
    if epoch >= GLOAS_FORK_EPOCH:
        return get_slot_component_duration_ms(ATTESTATION_DUE_BPS_GLOAS)
    return get_slot_component_duration_ms(ATTESTATION_DUE_BPS)

get_aggregate_due_ms

def get_aggregate_due_ms(epoch: Epoch) -> uint64:
    # [New in Gloas]
    if epoch >= GLOAS_FORK_EPOCH:
        return get_slot_component_duration_ms(AGGREGATE_DUE_BPS_GLOAS)
    return get_slot_component_duration_ms(AGGREGATE_DUE_BPS)

get_sync_message_due_ms

def get_sync_message_due_ms(epoch: Epoch) -> uint64:
    # [New in Gloas]
    if epoch >= GLOAS_FORK_EPOCH:
        return get_slot_component_duration_ms(SYNC_MESSAGE_DUE_BPS_GLOAS)
    return get_slot_component_duration_ms(SYNC_MESSAGE_DUE_BPS)

get_contribution_due_ms

def get_contribution_due_ms(epoch: Epoch) -> uint64:
    # [New in Gloas]
    if epoch >= GLOAS_FORK_EPOCH:
        return get_slot_component_duration_ms(CONTRIBUTION_DUE_BPS_GLOAS)
    return get_slot_component_duration_ms(CONTRIBUTION_DUE_BPS)

get_payload_attestation_due_ms

def get_payload_attestation_due_ms(epoch: Epoch) -> uint64:
    return get_slot_component_duration_ms(PAYLOAD_ATTESTATION_DUE_BPS)

on_block

The main difficulty when processing blocks in Gloas is fetching the right parent state. A beacon block specifies both consensus and execution parent and only the combination of both specifies a unique forkchoice node and therefore a pre-state. This logic is expressed below by a check to is_parent_full, in which case the parent state is taken from store.execution_payload_states. If the block is building on empty, we enforce that the parent hash equals the previous execution layer parent, that is, it ignored the payload of the parent beacon block, but it builds on top of its parent.

def on_block(store: Store, signed_block: SignedBeaconBlock) -> None:
    """
    Run ``on_block`` upon receiving a new block.
    """
    block = signed_block.message
    # Parent block must be known
    assert block.parent_root in store.block_states

    # Check if this blocks builds on empty or full parent block
    parent_block = store.blocks[block.parent_root]
    bid = block.body.signed_execution_payload_bid.message
    parent_bid = parent_block.body.signed_execution_payload_bid.message
    # Make a copy of the state to avoid mutability issues
    if is_parent_node_full(store, block):
        assert block.parent_root in store.execution_payload_states
        state = copy(store.execution_payload_states[block.parent_root])
    else:
        assert bid.parent_block_hash == parent_bid.parent_block_hash
        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.
    current_slot = get_current_slot(store)
    assert current_slot >= 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
    finalized_checkpoint_block = get_checkpoint_block(
        store,
        block.parent_root,
        store.finalized_checkpoint.epoch,
    )
    assert store.finalized_checkpoint.root == finalized_checkpoint_block

    # Check the block is valid and compute the post-state
    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 a new PTC voting for this block to the store
    store.payload_timeliness_vote[block_root] = [False] * PTC_SIZE
    store.payload_data_availability_vote[block_root] = [False] * PTC_SIZE

    # Notify the store about the payload_attestations in the block
    notify_ptc_messages(store, state, block.body.payload_attestations)

    record_block_timeliness(store, block_root)
    update_proposer_boost_root(store, block_root)

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

After picking the right parent state, we initialize the PTC votes for that root and we notify the store about the payload attestations in the block.

on_execution_payload

This is a new handler that is called with the execution payload envelope as its state transition function has been split in two. Data availability check is done at this stage. The parent state is the post-state of importing the beacon block.

def on_execution_payload(store: Store, signed_envelope: SignedExecutionPayloadEnvelope) -> None:
    """
    Run ``on_execution_payload`` upon receiving a new execution payload.
    """
    envelope = signed_envelope.message
    # The corresponding beacon block root needs to be known
    assert envelope.beacon_block_root in store.block_states

    # Check if blob data is available
    # If not, this payload MAY be queued and subsequently considered when blob data becomes available
    assert is_data_available(envelope.beacon_block_root)

    # Make a copy of the state to avoid mutability issues
    state = copy(store.block_states[envelope.beacon_block_root])

    # Process the execution payload
    process_execution_payload(state, signed_envelope, EXECUTION_ENGINE)

    # Add new state for this payload to the store
    store.execution_payload_states[envelope.beacon_block_root] = state

Implementation perks

I will keep this section updated as I personally implement Gloas forkchoice in the Prysm client. The following issues that are not strictly in the spec changes stroke me as difficult design decisions.

Pruning invalid branches

When we are optimistically syncing, we put nodes in forkchoice even though we have not validated their payload content. When the EL catches up, it may realize that a whole branch (or many) that has synced before, are in fact, invalid. What the EL tells us is the last valid payload hash in the branch that is syncing that payload. The way Prysm works now is to search for that last valid payload hash in forkchoice, it corresponds to a unique beacon block and there is a unique beacon block root that is a direct child of this last valid node, and at the same time is an ancestor of the invalid block being synced right now. We delete that unique node and all of its children.

This mechanism would fail in Gloas for a simple reason: the beacon block that committed to the first invalid payload hash is, in fact, valid! The builder that produced that payload is the one at fault, but the proposer is not. Thus we need to remove the full node but not the empty node, and then we need to remove every single node that descends from that full node, be it empty or full.

Keeping information older than finalization.

We need to pass to the engine data like the finalized payload hash. This is the payload hash that was included in the beacon block that has the root of the finalized checkpoint. What happens if the checkpoint block was in fact empty in the above orange sense? We cannot take the payload hash of the committed bid, cause that payload may even be invalid in fact! so we need to keep track of what was the latest payload hash that was included before the finalized checkpoint, so as to inform the engine what is the last payload that actually made it on-chain. This is tricky for Prysm because it forces us to keep track of this information that otherwise would be typically pruned on finalization.

Dependent roots

This was raised before by @dapplion but I wanted to write a quick sentence to it just in case. When designing forkchoice, at least Prysm, does not follow the spec on having pending nodes, and then empty/full ones that are children of it. However, we do have a logically equivalent structure by having all the consensus information in a single node, and then forkchoice nodes keep a pointer to their consensus part. Thus, both empty and full nodes will point to the same consensus part that can be thought of as the pending parent in the current specification. In particular, the consensus node specifies a parent (the full node is irrelevant) and only full nodes can have children (pointing to consensus nodes only). This is equivalent to the alternating nature of get_children in this specs. Now, when getting the dependent roots for beacon APIs or to make sure that we have the right shufflings, we need the latest beacon block root that was imported in an epoch. This is typically obtained by looking at the target for the next epoch and if that target root was at slot zero, take the parent. If it was not at slot zero (for example because slot zero was missed) then the target root and the dependent roots match up.

Now the question is, what should nodes track as their targets? They could be the nodes, either empty/full that are ancestors from the head, or they could be the pending or just the consensus part of these nodes. The point is that all of these have the same root and therefore the same slot so it doesn’t matter for the target. Since the dependent root is either the target or their parent, then the dependent root only depends on the consensus part of the target node. Thus, it does not matter if nodes track for targets their full or empty nodes, both the target roots and the dependent roots will not depend on this choice.

Notice however that by only keeping the root we weaken slightly justification, when attesting for the target checkpoint, nodes are selecting one of the branches for either full or empty, except perhaps those nodes voting during slot 0 that haven’t seen the payload. We however weaken the consistency between LMD and FFG voting since a vote for a blockroot that descends from the full node at slot 0, would also count for justification of the same root in the empty branch!. We could change justification and finalization to account for this but it was deemed minor: we only miss a single payload in the justification process at the max: we are now justifying the pending nodes in the notation of this specification.