ePBS Forkchoice annotated spec

This document deals with the technical specification of forkchoice for ePBS. For a more high level description of it we recommend the reader to look into the design notes.

The main problem with regards to forkchoice is that instead of using a vanilla (block, slot) replacement for LMD, we use a triple (block, slot, payload_present) system where attestations may support a consensus block for a given slot, but not the payload that was revealed for that block for example. This is to prevent situations in which a malicious collusion of a builder and a proposer, agree to reveal the payload late and thus reorg the next proposer.

In the following text I will assume that the reader has already gone through the examples linked in the design notes, and will only comment here as to the specific implementation functions of the forkchoice.md document in this PR.

Modified constants

Name	Value
PAYLOAD_TIMELY_THRESHOLD	PTC_SIZE/2 (=uint64(256))
PROPOSER_SCORE_BOOST	20 (modified in ePBS])
PAYLOAD_WITHHOLD_BOOST	40
PAYLOAD_REVEAL_BOOST	40

These are the values described for PB, WB and RB in the design notes and in this article. The constant PAYLOAD_TIMELY_THRESHOLD is the minimum number of votes from the PTC that a payload status has to receive in order for the PTC to achieve quorum

ChildNode

This is an auxiliary class to consider (block, slot, bool) LMD voting. A forkchoice node is determined by its beacon block root root, whether the block was full or empty (is_payload_present) and the slot in which this node context is being considered: for example when answering the question, is the full block with root root viable for head at slot slot?

class ChildNode(Container):
    root: Root
    slot: Slot
    is_payload_present: bool

Latest Messages

Modified LatestMessage

Note: The class is modified to keep track of the slot instead of the epoch

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

The reason for this modification is so that when receiving an attestation for slot N that points to the block root of N-1 (because N arrived late), then we can assert that this attestation does not support the block N for head at N, but rather supports N-1, advanced to N instead. That, is to allow an attestation to vote for the red node as head:

Modified update_latest_messages

The function update_latest_messages is updated to use the attestation slot instead of target. Since this function is only called on attestations that have been previously validated then the epoch that corresponds to the slot has to indeed be a new epoch for the latest message of this validator unless in the case where the validator has committed a slashable offense.

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

Modified Store

Store adds the following entries:

@dataclass
class Store(object):
    ...
    execution_payload_states: Dict[Root, BeaconState] = field(default_factory=dict) # [New in ePBS]
    inclusion_list_available: Dict[Root, bool] = field(default_factory=dict) # [New in ePBS]
    ptc_vote: Dict[Root, Vector[uint8, PTC_SIZE]] = field(default_factory=dict) # [New in ePBS]
    payload_withhold_boost_root: Root # [New in ePBS]
    payload_withhold_boost_full: bool # [New in ePBS]
    payload_reveal_boost_root: Root # [New in ePBS]

• execution_payload_states are the post-states obtained after performing the state transition function of importing an execution payload, that is process_execution_payload. This is a map keyed by the beacon block root that committed to that payload, rather than by the payload hash.
• inclusion_list_available keeps track if the inclusion list for the given beacon block root has been seen and validated. We could remove this entry if we make this availability a validity condition for the corresponding beacon block.
• ptc_vote keeps track of all the votes from the PTC committee

Clients may chose to only keep track of this full vote for the current slot and instead keep a list of boolean for the payload presence of each block before that.

• payload_withhold_boost_root is the parent block root of a payload that has achieved consensus on PAYLOAD_WITHHELD.
• payload_withhold_boost_full whether the parent block of the withheld payload was full or empty.
• payload_reveal_boost_root is the block root of a payload that has achieved consensus on PAYLOAD_PRESENT.

Inclusion Lists

verify_inclusion_list

This function simply checks the signature of the inclusion list, checks that the proposer index agrees with the corresponding block proposer and then sends the IL to the EL for validation.

def verify_inclusion_list(state: BeaconState, block: BeaconBlock, inclusion_list: InclusionList, execution_engine: ExecutionEngine) -> bool:
    """
    returns true if the inclusion list is valid. 
    """
    # Check that the inclusion list corresponds to the block proposer
    signed_summary = inclusion_list.summary
    proposer_index = signed_summary.message.proposer_index
    assert block.proposer_index == proposer_index

    # Check that the signature is correct
    assert verify_inclusion_list_summary_signature(state, signed_summary)
 
    # TODO: These checks will also be performed by the EL surely so we can probably remove them from here.
    # Check the summary and transaction list lengths
    summary = signed_summary.message.summary
    assert len(summary) <= MAX_TRANSACTIONS_PER_INCLUSION_LIST
    assert len(inclusion_list.transactions) == len(summary)

    # Check that the inclusion list is valid
    return execution_engine.notify_new_inclusion_list(NewInclusionListRequest(
            inclusion_list=inclusion_list.transactions, 
            summary=summary,
            parent_block_hash = state.latest_execution_payload_header.block_hash))

blocks_for_slot

The function blocks_for_slot returns all the beacon blocks found in the store for the given slot. This implementation here is only for specification purposes and clients may choose to optimize this by using an internal map or similar caching structures.

def blocks_for_slot(store: Store, slot: Slot) -> Set[BeaconBlock]:
    return [block for root, block in store.blocks.items() if block.slot == slot]

block_for_inclusion_list

The function block_for_inclusion_list returns a known beacon block in store that is compatible with the given inclusion list. Because of equivocations, we may have different beacon blocks that have compatible data with an inclusion list. This is not really a problem as we make sure that the parent hash is the same, validity of the IL should hold for any block even if equivocating.

def block_for_inclusion_list(store: Store, inclusion_list: InclusionList) -> Optional[BeaconBlock]:
    summary = inclusion_list.signed_summary.message
    parent_hash = inclusion_list.parent_block_hash
    
    blocks = blocks_for_slot(store, summary.slot)
    for block in blocks:
        if block.slot == summary.slot and block.proposer_index == summary.proposer_index and block.signed_execution_payload_header.message.parent_block_hash == parent_hash:
            return block
    return None

on_inclusion_list

This is the main handler for inclusion lists, it is called every time an InclusionList is seen by the node that passes pubsub validation. This specification requires that there is already a beacon block in the store that is compatible with this inclusion list. Client developers may (and should) instead validate the inclusion list against the head state in case it arrives earlier than the beacon block and cache this result. That is, client nodes are encouraged to validate immediately the inclusion list even if they do not have the block, assuming it is for the current slot and the proposer is correct, the client can take the parent block hash and send the IL for validation to the EL immediately. Then they can cache the result in store.inclusion_list_available for usage when the beacon block is validated.

def on_inclusion_list(store: Store, inclusion_list: InclusionList) -> None:
    """
    Validates an incoming inclusion list and records the result in the corresponding forkchoice node.
    """
    # Require we have one block compatible with the inclusion list
    block = block_for_inclusion_list(store, inclusion_list)
    assert block is not None
    root = hash_tree_root(block)
    assert root in store.block_states
    state = store.block_states[root]
    assert block.parent_root in store.blocks
    parent_block = store.blocks[block.parent_root]

    # Ignore the list if the parent consensus block did not contain a payload
    header = block.body.signed_execution_payload_header.message
    parent_header = parent_block.body.signed_execution_payload_header.message
    if header.parent_block_hash != parent_header.block_hash
        assert header.parent_block_hash == parent_header.parent_block_hash
        return

    # verify the inclusion list
    assert verify_inclusion_list(state, block, inclusion_list, EXECUTION_ENGINE)
    store.inclusion_list_available[root]=True

LMD Weights

is_payload_present

This function simply returns whether the given beacon block root has a payload that the PTC vote has achieved quorum for PAYLOAD_PRESENT. If there is no quorum then the payload is considered absent for the point of view of PTC accounting.

def is_payload_present(store: Store, beacon_block_root: Root) -> bool:
    """
    return whether the execution payload for the beacon block with root ``beacon_block_root`` was voted as present 
    by the PTC
    """
    # The beacon block root must be known
    assert beacon_block_root in store.ptc_vote
    return store.ptc_vote[beacon_block_root].count(PAYLOAD_PRESENT) > PAYLOAD_TIMELY_THRESHOLD

This function does not return the payload content of the node in the canonical chain. It may well be that the canonical node disagrees with the PTC vote for the node. This can specially happen if the PTC vote has not reached everywhere on time. Whenever possible, users should use is_parent_node_full

is_parent_node_full

This function checks if the parent block for the passed beacon block was full or empty. This exploits the fact that given a node, its parent has a unique payload content. This is in contrast with the above function is_payload_present which only takes into account a single node.

def is_parent_node_full(store: Store, block: BeaconBlock) -> bool:
    parent = store.blocks[block.parent_root]
    return block.body.signed_execution_payload_header.message.parent_block_hash == parent.body.signed_execution_payload_header.message.block_hash

Modified get_ancestor

This function is modified to account for the different possible statuses of a slot. The slot can be either:

• Full (both blocks are present)
• Empty (only the consensus block is present)
• Skipped (no block is present)

This function takes a root and looks up what is the block root that is the ancestor of the current block at the given slot. It returns a ChildNode object containing the root of the beacon block, the slot at which this block was proposed and the payload status. Notice that for skipped slots, the root will be the last consensus block before the given slot, just as today.

def get_ancestor(store: Store, root: Root, slot: Slot) -> ChildNode:
    """
    Returns the beacon block root, the slot 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`` it returns it's 
    PTC status instead of the actual payload content. 
    """
    block = store.blocks[root]
    if block.slot == slot:
        return ChildNode(root=root, slot=slot, is_payload_present= is_payload_present(store, root))

    assert block.slot > slot
    parent = store.blocks[block.parent_root]
    if parent.slot > slot:
        return get_ancestor(store, block.parent_root, slot)
    return ChildNode(root=block.parent_root, slot=parent.slot, is_payload_present=is_parent_node_full(block))

Let us analyze a few examples for this function. In all cases we call get_ancestor with root=N+1. We abuse notation and by root = N+1 we mean the block root of the block at slot N+1. The ancestor is marked in red. Recall our coloring scheme from the design notes in which lightblue nodes are full, orange ones are empty and white ones are missing.

Same slot

We call get_ancestor with slot = N+1

The first if statement hits:

    if block.slot <= slot:
        return  ChildNode(root=root, slot=slot, is_payload_present= is_payload_present(store, root))

This is a very special case in which the ancestor for a given block root will return the payload status deduced from the PTC vote. That is, as soon as the block is imported and no PTC votes have been counted, the result would be for the absent payload:

The same would happen if requesting the ancestor for a future slot.

This special case needs to be taken into account when analyzing any call to get_ancestor.

Single chain full blocks

We call get_ancestor with slot = N. In this case all blocks are full.

The second if statement does not hit

    if parent.slot > slot:
        return get_ancestor(store, block.parent_root, slot)

since parent.slot == slot = N. The parent's block hash is the current current block's (N+1) parent block hash, hence the return is for N and True indicating that this chain builds on the full node.

Single chain missing payload

In this case the payload for N was revealed late, the proposer of N+1 built on top of the empty block for N. We call get_ancestor with slot = N.

The second if statement does not hit

    if parent.slot > slot:
        return get_ancestor(store, block.parent_root, slot)

since parent.slot == slot = N. The parent's block hash is not the current current block's (N+1) parent block hash. Since the parent's block hash is for the payload revealed in N, but the current block's parent hash is that payload in N-1 (the last full block in this chain is N-1) hence the return is for N and False indicating that this chain builds on the empty node.

Missing slot

In this case the block for N was revealed late, the proposer of N+1 built on top of the missing block for N, that is, it built on top of N-1. We call get_ancestor with slot = N.

The second if statement does not hit

    if parent.slot > slot:
        return get_ancestor(store, block.parent_root, slot)

since parent.slot = N-1 < slot = N.

The parent's block hash is the current current block's (N+1) parent block hash, since the parent's block hash is for the payload revealed in N-1, and the current block's parent hash is that payload in N-1 (the last full block in this chain is N-1) hence the return is for N-1 and True indicating that this chain builds on the missing node.

Longer chain

The situation for longer chains is similar, and can be treated by induction since each block root as a single parent node, no matter if there are many nodes in forkchoice with a given block root. Consider for example the situation when the payload of N was revealed late, thus the builder of N+1 built on top of the empty block N. We call get_ancestor with slot = N-1 this time

This time the parent.slot = N > slot = N-1, thus the second if statement does hit:

    if parent.slot > slot:
        return get_ancestor(store, block.parent_root, slot)

So we call again get_ancestor with root=N and slot = N-1. In this case it will get the parent root N-1 regardless if N+1 was based on empty or full and it will only return True in both cases, since both nodes for N are based on the full N-1 block. Notice that we cannot have a situation where there are valid True and False notions to return unless there was an equivocation; that is, in the following diagram:

There must have been equivocations for the consensus block of N since it has two different parent block hash even though its parent block is the same beacon block.

Modified get_checkpoint_block

This is only modified because of the modification to get_ancestor that now returns a ChildNode object. Notice that we are disregarding the payload content of the beacon block of the checkpoint, that is we would consider both empty or full nodes as valid checkpoints. This does not alter significantly FFG since every ancestor for the two possible blocks is the same and only descendants is that they will not agree upon.

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

This function is a new helper that is used to check if an attestation supports an ancestor. Previously, the notion of ancestor was rather simple. The design landscape here is that we do not want to change the attestation type, attestations only attest to a beacon block root, at a given slot. Before, we would consider that attestation as supporting any ancestor of that beacon block root, we didn't even take into account the slot at which the attestation was cast. In addition to the slot, attestations do not have any information about payload presence, but nodes in forkchoice do! a given blockroot is based on either full or empty for its parent. This makes attestation weight counting rather complicated.

We need to account for many different cases since a vote from the committe a slot N, that votes for N-1 needs to support the N-1 as head during N but need not support N for head at N. It also needs to take into account the payload status of the node we are trying to compute the support. That is, an attestation for N that is based on N-1 full, should not support N-1 empty chains, but should support N-1 full chains.

This function takes a Childnode for the node we want to support, where node.slot is the slot that the given node would be advanced to be computed as head, and the given attestation (sent as the message parameter) would support that head.

def is_supporting_vote(store: Store, node: ChildNode, message: LatestMessage) -> bool:
    if node.root == message.root:
        return node.slot <= message.slot
    message_block = store.blocks[message.root]
    if node.slot >= message_block.slot:
        return False
    ancestor =  get_ancestor(store, message.root, node.slot)
    return (node.root == ancestor.root) and (node.is_payload_present == ancestor.is_payload_present)

Better to consider some concrete examples with the same coloring as above. In all these examples we will call is_supporting_vote for root = N

Direct vote

The easiest example is a vote for the given root N by an attester in a committee after the slot N. That is suppose that message.slot = N or higher, then the following hits

    if node.root == message.root:
        return node.slot <= message.slot

and the attestation supports the node. Notice that this is regardless of the payload content of the node. That is

In both cases a message of the form message.root = N, and message.slot = N+1, will support both branches, that is, both N empty or full, for head at N+1.

This special case needs to be considered when analyzing calls to get_supporting_vote.

If message.slot < node.slot on the other hand, this is an attestation from an older committee, this attestation supported the block N for head only up to that point, but it hasn't attested for N being head during node.slot, therefore it is not a supporting vote.

Higher committee than the block

If the vote is for a slot that is higher or equal than the beacon block root pointed by the message, then the attestation cannot be a supporting vote. This is due to the branch

    if node.slot >= message_block.slot:
        return False

The typical situation would be this

Here we have message.root=N+1 and node.slot = N+2. That is the attestation (which must have been during at least the committee of N+1) is for the root N+1 and it supports it as head, therefore it will not support N as head during slot N+2 (because it supports N+1 already). Notice that the payload status node.is_payload_present of N is completely irrelevant in this situation The fact that the attestation supported N+1 for head means that it won't support N for head at the same slot. Also notice that even if the block was not in N+1 but was earlier (an ancestor of N) or a contending branch from N, then in those cases also this attestation would not support N for head during N+2(or any slot higher than the message block)

This is a big change from the current status, in which the slot is not specified in is_supporting_vote.

Equal slot as the block

We have yet to analyze the situation in which the message.root != node.root and node.slot < message_block.slot. Here the attestation for message.root will support it if and only if the block message.root (with any payload content), is a descendant of N with the payload content defined by node.is_payload_present. This has several subcases:

Not a consensus desendant

An attestation for N+1 does not support N for head at any slot. This is because get_ancestor(N+1, slot) will return never return N as root for any value of slot.

Wrong payload status

Consider the following diagram

An attestation for N+1 will not support N empty for any slot, this is because a call to get_ancestor(N+1, slot) will can only return N, True given that N+1 is based on the full block N. So a call to is_supporting_vote(N, slot, False) will return False always.

Notice that when slot = N a call to is_supporting_vote(N, N, True) does return True, that is a vote for N+1 above did support N as head during slot N.

Wrong slot

Let's consider the situation where there are some missing slots:

Here the proposer of N+1 based his block on the skipped slot N, that is, the parent block is the full N-1 block. Attestations for N+1 do not support N since they are not descendant of the consensus block N, but they will support N-1 full for slots N-1 and slot N as head. It will not support N-1 empty under no circumstances.

New compute_proposer_boost

This is a helper to compute the proposer boost. It applies the proposer boost to any ancestor of the proposer boost root taking into account the payload presence. There is one exception: if the requested node has the same root and slot as the block with the proposer boost root, then the proposer boost is applied to both empty and full versions of the node.

def compute_proposer_boost(store: Store, state: State, node: ChildNode) -> Gwei:
    if store.proposer_boost_root == Root():
        return Gwei(0)
    ancestor = get_ancestor(store, store.proposer_boost_root, node.slot)
    if ancestor.root != node.root:
        return Gwei(0)
    proposer_boost_slot = store.blocks[store.proposer_boost_root].slot
    # Proposer boost is not applied after skipped slots
    if node.slot > proposer_boost_slot:
        return Gwei(0)
    if (node.slot < proposer_boost_slot) and (ancestor.is_payload_present != node.is_payload_present):
        return Gwei(0)
    committee_weight = get_total_active_balance(state) // SLOTS_PER_EPOCH
    return  (committee_weight * PROPOSER_SCORE_BOOST) // 100

The typical application of this would be on a call to get the head of the chain right after importing an early block. In this case we would want to check if the boost applies to the current just synced node. The payload hasn't even been revealed yet so we need the boost to be applied to the consensus block no matter which payload status

Since node.slot == store.blocks[store.proposer_boost_root].slot (and both of them are equal to the current slot), the three if statements do not hit and the proposer boost is applied to the current head. If later when the payload is revealed but still when requesting for node.slot being the current slot, this function would not check for the payload status, and both forkchoice nodes, the current head with and without the payload, will be boosted.

All ancestors however do take into account the right payload status, this is because of the clause ...and (ancestor.is_payload_present != node.is_payload_present). That is, if the current early block is based on the empty parent node, the proposer boost will be applied to the empty parent, but not the full block with the same root as the parent root, as this is a contending block to it.

New compute_withhold_boost `

This is a similar helper that applies for the withhold boost.

def compute_withhold_boost(store: Store, state: State, node: ChildNode) -> Gwei:
    if store.payload_withhold_boost_root == Root():
        return Gwei(0)
    ancestor = get_ancestor(store, store.payload_withold_boost_root, node.slot)
    if ancestor.root != node.root:
        return Gwei(0)
    if node.slot >= store.blocks[store.payload_withhold_boost_root].slot:
        ancestor.is_payload_present = store.payload_withhold_boost_full
    if ancestor.is_payload_present != node.is_payload_present:
        return Gwei(0)

    committee_weight = get_total_active_balance(state) // SLOTS_PER_EPOCH
    return  (committee_weight * PAYLOAD_WITHHOLD_BOOST) // 100

In this case this always takes into account the reveal status. The reason being that the withhold boost is applied to the parent of the beacon block where the payload was withheld. And this parent has an already defined unique payload status.

This is the reason why we record payload_withhold_boost_full in the Store, so that we can recover this unique parent here.

There is a major caveat in this function: we want to apply the withhold boost to skipped slots, that is to consider the parent of the withheld block for head, as if the withheld block did not exist, that is a future slot after the parent's slot.

This is the difference between the lines

    if node.slot > proposer_boost_slot:
        return Gwei(0)

in compute_proposer_boost versus the lines

    if node.slot >= store.blocks[store.payload_withhold_boost_root].slot:
        ancestor.is_payload_present = store.payload_withhold_boost_full

New compute_reveal_boost

This is a similar helper to the last two, the only difference is that the reveal boost is only applied to the full version of the node when querying for the same slot as the revealed payload. Also, differently than the proposer boost, the reveal boost has to be applied on skipped slots while it lasts.

def compute_reveal_boost(store: Store, state: State, node: ChildNode) -> Gwei:
    if store.payload_reveal_boost_root == Root():
        return Gwei(0)
    ancestor = get_ancestor(store, store.payload_reveal_boost_root, node.slot)
    if ancestor.root != node.root:
        return Gwei(0)
    if node.slot >= store.blocks[store.payload_reveal_boost_root].slot:
        ancestor.is_payload_present = True
    if is_ancestor_full != node.is_payload_present:
        return Gwei(0)
    committee_weight = get_total_active_balance(state) // SLOTS_PER_EPOCH
    return  (committee_weight * PAYLOAD_REVEAL_BOOST) // 100

Modified get_weight

This is modified to only count votes for descending chains that support the status of a triple Root, Slot, bool, where the bool indicates if the block was full or not. Slot is needed for a correct implementation of (Block, Slot) voting.

We have seen above the minutiae of is_supporting_vote which is the gist of this function. It simply computes the weight of a node with consensus blockroot root, for consideration as head during slot slot, when the payload was present or not according to is_payload_present, but summing all the effective balances of supporting attestations for that triple. After that it adds to the root the proposer and builder's boosts.

def get_weight(store: Store, node: ChildNode) -> 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 is_slashed_attester(state.validators[i])
    ]
    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 is_supporting_vote(store, node, store.latest_messages[i]))
    ))

    # Compute boosts
    proposer_score = compute_boost(store, state, node)
    builder_reveal_score = compute_reveal_boost(store, state, node)
    builder_withhold_score = compute_withhold_boost(store, state, node)

    return attestation_score + proposer_score + builder_reveal_score + builder_withhold_score

New get_head_no_il

This is a modified version of get_head to use the new get_weight function. It returns the Beacon block root of the head block and whether its payload is considered present or not. It disregards IL availability.

def get_head_no_il(store: Store) -> ChildNode:

    blocks = get_filtered_block_tree(store)
    justified_root = store.justified_checkpoint.root
    justified_block = store.blocks[justified_root]
    justified_slot = justified_block.slot
    justified_full = is_payload_present(store, justified_root)
    best_child = ChildNode(root=head_root, slot=head_slot, is_payload_present=head_full)

This sets the initial variables for a while loop. We start looking for our head from the justified checkpoint's root. We consider the PTC vote for the justified checkpoint to determine the initial payload content.

This may seem dangerous since it may well happen that the chain that justified this checkpoint and is the current canonical chain does not agree with the PTC vote, but this is not really a problem since we will probe for all descendants from the consensus block, regardless of payload status.

    while True:
        children = [
            ChildNode(root=root, slot=block.slot, is_payload_present=present) for (root, block) in blocks.items()
            if block.parent_root == best_child.root and 
            is_parent_node_full(store, block) == best_child.is_payload_present if root != store.justified_root
            for present in (True, False) if root in store.execution_payload_states or present == False
        ]

We get all the triples (root, slot, bool) of consisting on the block roots, the slots and the payload status of all direct children of the current head candidate. Recall we start with the justified checkpoint so this guarantees that we will only consider descendants of the justified checkpoint for head. The children only care about the consensus blocks that descend from them. We add both versions with a present or an absent payload for any child CL block that we see, with the condition that we only add children with present payload if the payload was indeed imported.

There is a special casing for the justified checkpoint because we do not store the payload status of that justified checkpoint. So the first iteration of the loop will query for children of both the justified checkpoint empty and full. An alternative design is to consider the checkpoint with the payload status, but we felt that opens a can of worms in dealing with FFG considerations.

       if len(children) == 0:
            return best_child

If there aren't any children then we know that we have reached head, return the last computed couple of the head root and it's payload status.

        children += [ChildNode(root=best_child.root, slot=best_child.slot + 1, best_child.is_payload_present)]

If we have children we consider the current head advanced as a possible head.

There is a pathological case in which the justified checkpoint has no descendant and we consider it for head with the PTC vote when perhaps the canonical chain will descend from a different payload status. This can happen for example for an optimistically syncing node that just found out that all his chain but the justified checkpoint is invalid.

        new_best_child = max(children, key=lambda child: (get_weight(store, child.root, child.slot, child.is_payload_present), is_payload_present(store, child.root), child.is_payload_present, child.slot, child.root))

We compute the best child by getting the weight of each of them. We untie them by preferring the child that has a payload according to the PTC vote. Untie then by preferring the child that actually has a payload. We then untie by the higher slot and finally lexycographically by root

         if new_best_child.root == best_child.root:
            return new_best_child

If the best child is the current head just advanced, then we know that ends the loop and we can just stop here and return the current head.

         best_child = new_best_child

Otherwise we update the head CL block and go back one step further. Let us analyze some of the examples encountered in the design notes

Happy case

In this case a vote of 10 was assigned at each slot to their corresponding block that was revealed full. At the start of the loop iteration, the first call for best_child will have the following weights for the three possible children

The skipped node has no votes because we call get_weight with slot=N+1 and at this stage, the votes from the committee at N would not count for N as head during N+1. The votes from the committee of N+1would count for both the empty and full N+1 node as head during N+1. However the votes from the committee of N+2 only support N+1 full. That is why the full node has weight 20 at this step of the while loop. It is chosen as the best child.

The next step of the loop looks similar:

The call this time is to get_weight with slot=N+2. The votes from the committee at N and N+1 are completely ignored this time. This is why the skipped slot has zero weight. The votes from the committee at N+2 will support both the full and the empty block so they are tied. We are ignoring any payload boosts at this time and also the PTC vote. They are untied by the payload being present in the full case, and thus the head will be the full node at N+2. In case we have payload reveal boosts or simply if the PTC committee had agreed on the payload for N+2 being present, we would chose the full block as head anyway.

Late block

The last block in the chain arrived late, thus the attesters for that slot voted for its parent.

At the start of the loop the situation is almost exactly as above

This time the weight for both the full and empty slot N+1 are 20 because they count both the votes from the N+1 and N+2 committees that directly voted for the N+1 beacon block root.

We could make this situation more robust by changing the attestation type in the CL to also mention the payload status in case the vote is for a previous slot's block. But this is a pretty invasive change with minimal benefits.

The full block would be decided by the presence of the payload, regardless if the PTC had achieved consensus or not. The next iteration would look as follows:

The skipped slot has now weight 10 because we call get_weight with slot=N+2. In this case the vote of the committee of N+2 would count for it. And thus the head of the chain after the late block N+2 arrives, remains being the full N+1 block.

Attempted payload reorg

In this case the beacon block for N+1 has a payload, the PTC has achieved threshold for PAYLOAD_PRESENT but the proposer of N+2 has revealed a timely block reorging the payload.

Let us analyze the honest behavior and full calls for get_head_no_il in this situation.

• During slot N the committee voted for N, the payload was present and becomes the head. We will change units in this example and by a vote of
  $1$ we mean the full committee voted for it.
• The PTC has agreed on PAYLOAD_PRESENT.
• During slot N+1 the proposer reveals his block timely. Therefore at the attestation deadline, for a call to get_head with slot = N+1, assuming we start the loop at N honest validators will have:

• The builder's reveal boost is applied to both the missed slot N+1 and the empty slot N+1 as they both descend from the reveal boost block N.

• There is no full N+1 node yet since the payload has not been revealed. The committee for N voted for N during N but those votes do not count for the block as head at N+1. So the weight for N is only the RB.

• The proposer boost for N+1 that was revealed early applies to N+1 but it does not apply to N at slot N+1 (recall it will apply for N at slot N)

  Given the above discussion honest validators in the N+1 committee would vote for N+1. If they hadn't seen N+1 timely then honest validators would have attested for their only possible block which is N.

  Let us suppose that a fraction

  $\beta$ of the committee of
  $N+1$ is malicious, a fraction
  $x$ of the honest validators in the committee saw N+1 timely and therefore
  $1-x-\beta$ didn't.

• At the payload reveal time, the builder sees the following forkchoice diagram

• Notice that the reveal boost is no longer applied after this time (see below in on_payload_attestation_message)
• The builder will disregard the payload boost at this time since attestations were already cast. We make therefore the following assumption
  $2x>1-\beta$. so that the builder decides to reveal his payload.
• The PTC being honest agrees on PAYLOAD_PRESENT
• The builder of N+2 builds on top of the empty block regardless.
• The malicious validators reveal their attestations from committee N+1 attesting for N, that is, as if the block hadn't existed.

There are no attestations yet during N+2. At the time of the attestation deadline honest validators will call get_head_no_il and to obtain head. The loop starts at N and this is the first iteration of the loop

There are many aspects that are exemplified in this diagram:

• The reveal boost is only applied to full N+1 as seen in compute_reveal_boost
• The proposer boost is only applied to empty N+1 since the proposer of N+2 based on it. It does not apply to N either since we are calling get_weight with slot = N+1. It would apply for N at slot N.
• The attacker has revealed attestations for N instead of N-1.

As long as

$RB>PB$ the full N+1 will beat the empty one. This is the case with the proposed values. Similarly, as long as

$$RB>1-2x$$
The full N+1 block will beat the missed N+1 slot. This is guaranteed if

$RB>\beta$ by the above assumption. Thus, in this loop the best child will be full N+1.

The next iteration of the loop will stop early since full N+1 has no children, hence N+2 would not even be considered for head! and honest validators will vote for N+1 as head during N+2.

It may look as though N+2 never stood a chance, but the gist of the algorithm is that proposer boost was indeed counted towards the empty payload.

Attempted full block reorg

In this situation the proposer of N+1 and N+2 are colluding to try to reorg the builder of N+1, this has more chances to succeed. The attack is very similar to the above example so this section will be more succinct. The attacker witholds attestations for N+1 and reveals them for N. The proposer of N+2 builds on the missing N+1 slot, that is on N. At the attestation deadline for N+2 honest validators call to get head. The loop starts now as follows

The only difference is now that the proposer boost is applied to the missing slot instead of the empty slot, as only the missing slot is an ancestor of the boosted block N+2. In these conditions, if

$$RB-PB>1-2x$$
Then the full N+1 slot will still win by weight, and this is guaranteed by the assumption that

$RB-PB>\beta$. The next loop of the iteration again ends early because N+1 full does not have any descendants.

Attempted builder's grief

In this section we analyze the loop for the attack in which the proposers of N+1 and N+2 attempt to trick the builder of N+1 into withholding but still include the consensus block of N+1 so that the builder has to pay the unconditional bid payment to the proposer of N+1.

The attack unfolds as follows

• The proposer of N+1 reveals a block attempting a split
  $x-\beta$ sees their block early and
  $1-x$ sees them late.
• Numbers are such that the builder withholds their payload
• The attacker then reveals
  $\beta$ attestations for N+1.
• The proposer of N+2 builds on top of the empty N+1 block.

Given the above conditions, at the of payload reveal, the builder sees the following diagram

Therefore he withholds if

$2x-1<\beta$.

At the attestation deadline of N+2 the loop starts as follows

• There is no full N+1 node now because the payload was withheld.
• Proposer boost is applied to the empty N+1 node but not the skipped slot because N+2 built on top of N+1.
• Withholding boost is only applied to the skipped slot because the empty N+1 is not an ancestor of the store.payload_withhold_boost_root which is N.

So at this stage the skipped slot will win over the empty one if

$$WB-PB>2x-1$$
And this is guaranteed by

$WB-PB>\beta$. At this step the iteration immediately ends because the head is the same previous head

         if new_best_child.root == best_child.root:
            return new_best_child 

So we see in this case the iteration didn't even move to consider N+1, but still the proposer boost for N+2 played its role.

Modified get_head

This is a wrapper now over get_head_no_il that simply finds the first ancestor with an available inclusion list.

def get_head(store: Store) -> ChildNode:
    head = get_head_no_il(store)
    while not store.inclusion_list_available(head.root):
        head = get_ancestor(store, head.root, head.slot - 1)
    return head

Engine APIs

There isn't much with regard to inclusion lists API calls, these simply wrap a call into engine_newInclusionListV1

New NewInclusionListRequest

@dataclass
class NewInclusionListRequest(object):
    inclusion_list: List[Transaction, MAX_TRANSACTIONS_PER_INCLUSION_LIST]
    summary: List[ExecutionAddress, MAX_TRANSACTIONS_PER_INCLUSION_LIST]
    parent_block_hash: Hash32

New notify_new_inclusion_list

def notify_new_inclusion_list(self: ExecutionEngine,
                              inclusion_list_request: NewInclusionListRequest) -> bool:
    """
    Return ``True`` if and only if the transactions in the inclusion list can be succesfully executed
    starting from the execution state corresponding to the `parent_block_hash` in the inclusion list 
    summary. The execution engine also checks that the total gas limit is less or equal that
    ```MAX_GAS_PER_INCLUSION_LIST``, and the transactions in the list of transactions correspond to the signed summary
    """
    ...

on_block

The handler on_block is modified to consider the pre state of the given consensus beacon block depending not only on the parent block root, but also on the parent blockhash. In addition we delay the checking of blob data availability until the processing of the execution payload.

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

    # Check if this blocks builds on empty or full parent block
    parent_block = store.blocks[block.parent_root]
    header = block.body.signed_execution_payload_header.message
    parent_header = parent_block.body.signed_execution_payload_header.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 header.parent_block_hash == parent_header.parent_block_hash
        state = copy(store.block_states[block.parent_root])

After this state points to the right pre-state, either the one obtained after syncing the parent execution payload (if the parent block was full) or the previous consensus block (if the parent was empty).

We also check here that the current header commits to building a payload who's parent is the right one in the case of an empty parent.

The rest of block processing goes unchanged until:

    store.block_states[block_root] = state
    # Add a new PTC voting for this block to the store
    store.ptc_vote[block_root] = [PAYLOAD_ABSENT]*PTC_SIZE

Thus any newly imported block starts with a PTC vote for the absent payload.

    if not is_parent_node_full(store, block):
        store.inclusion_list_available = True

If the parent block is empty record that the inclusion list for this block has been satisfied.

    store.notify_ptc_messages(state, block.body.payload_attestations)

We process the payload attestations in the block.

on_execution_payload

This is simply a new handler that is called when receiving a new full execution payload envelope from the builder.

def on_execution_payload(store: Store, signed_envelope: SignedExecutionPayloadEnvelope) -> None:
    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, envelope.blob_kzg_commitments)

    # 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

The only new addition is that we add the post-state to the store.

Payload boosts

seconds_into_slot

This simply returns how many seconds have passed into the slot

def seconds_into_slot(store: Store) -> uint64:
    return (store.time - store.genesis_time) % SECONDS_PER_SLOT

Modified on_tick_per_slot

Modified to reset the payload boost roots. The payload boost root is reset at the attestation deadline.

Perhaps we want to reset it at the payload reveal deadline.

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()
    else: 
        # Reset the payload boost if this is the attestation time
        if seconds_into_slot(store) >= SECONDS_PER_SLOT // INTERVALS_PER_SLOT:
            store.payload_withhold_boost_root = Root()
            store.payload_withhold_boost_full = False
            store.payload_reveal_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)

on_payload_attestation_message

This is the main handler analogous to on_attestation it performs all the checks necessary to process a payload attestation.

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

We get first check that the payload attestation corresponds to the slot of the voted blockroot. We do not consider payload attestations for past blocks. We also check that the voter was indeed a PTC member.

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

If the attestation is not from a block check the attester's signature. Also we impose a strong condition: we only process attestations over the wire if they are for the current slot.

    # Update the ptc vote for the block
    ptc_index = ptc.index(ptc_message.validator_index)
    ptc_vote = store.ptc_vote[data.beacon_block_root]
    ptc_vote[ptc_index] = data.payload_status

We then update the PTC vote for the given block root.

    if is_from_block && data.slot + 1 != get_current_slot(store):
        return

For attestations that are are over the wire we only consider current slot ones. For block attestations, we only allow them to be from the previous slot, that is, we may allow the proposer to assert it's view of the PTC vote from the previous slot.

    time_into_slot = (store.time - store.genesis_time) % SECONDS_PER_SLOT
    if is_from_block and time_into_slot >= SECONDS_PER_SLOT // INTERVALS_PER_SLOT:
        return

If the block is late return early cause anyway any payload boost from the previous slot should have been reset by now.

    # Update the payload boosts if threshold has been achieved
    if ptc_vote.count(PAYLOAD_PRESENT) > PAYLOAD_TIMELY_THRESHOLD:
        store.payload_reveal_boost_root = data.beacon_block_root
    if ptc_vote.count(PAYLOAD_WITHHELD) > PAYLOAD_TIMELY_THRESHOLD:
        block = store.blocks[data.beacon_block_root]
        store.payload_withhold_boost_root = block.parent_root
        store.payload_withhold_boost_full = is_parent_node_full(block)

We finally update the payload boosts if we achieved threshold with these attestations.