Prysm Forkchoice Implementation

Fork choice defines how an honest node should follow the chain and determine the current head. This page outlines Prysm's fork choice implementation, which differs slightly from the spec due to various optimizations and tradeoffs. One can think of fork choice as representing a tree of blocks and a set of votes determining which branch is the head.

The following documentation refers to the implementation at https://github.com/prysmaticlabs/prysm/tree/develop/beacon-chain/forkchoice

Forkchoice objects

In Prysm's implementation, a

$ForkChoice$ store object consists of:

• A list of
  $votes$
  • Each
    $vote$ contains
    $\{current\mathrm{\_}root,next\mathrm{\_}root,next\mathrm{\_}epoch\}$
  • The
    $index$ of the list corresponds to the validator index in consensus state
• A list of validator
  $balances$ and
  $justified\mathrm{\_}balances$
• A
  $proposer\mathrm{\_}boost\mathrm{\_}root$, cached after processing a timely block
• A
  $committee\mathrm{\_}weight$, calculated as total active validator balance divided by the number of slots per epoch
• A tree root
  $node$, representing the root of the fork choice tree
• A head
  $node$, representing the current head of the chain which should be the node of the highest weight
• Several key-value structures to track
  $node$ by its block root or block hash

An individual

$Node$ object consists of:

• The block’s
  $slot$
• The block’s
  $root$
• The block’s
  $parent$ as a
  $node$
• A list of
  $node$ as
  $children$
• The node’s
  $justified$,
  $unrealized\mathrm{\_}justified$,
  $finalized$, and
  $unrealized\mathrm{\_}finalized$ epochs
• The total
  $balance$ of validators that directly voted for the
  $node$
• The
  $weight$ of the
  $node$, including both its own
  $balance$ and the balances of its
  $children$

$ForkChoice$ exposes three main functions to the outside world to compute the head of the chain

1. Input validator votes
2. Input a new block
3. Compute the new head

Input votes

Callers can input newer validator votes into the

$ForkChoice$ store either on demand as unseen verified attestations arrive or at intervals after attestations are batched and aggregated. The caller provides:

• The attestation’s block
  $root$
• The
  $target\mathrm{\_}epoch$ of the attestation
• A list of validator
  $index$ that voted

The function updates the

$ForkChoice$ store's list of

$votes$ by replacing the

$vote$ at each given

$index$ with the new

$root$ and

$target\mathrm{\_}epoch$, but only if the new

$target\mathrm{\_}epoch$ is higher than the existing one.

for _, index := range validatorIndices {
	for index >= uint64(len(f.votes)) {
		f.votes = append(f.votes, Vote{currentRoot: params.BeaconConfig().ZeroHash, nextRoot: params.BeaconConfig().ZeroHash})
	}
	newVote := f.votes[index].nextRoot == params.BeaconConfig().ZeroHash && f.votes[index].currentRoot == params.BeaconConfig().ZeroHash
	if newVote || targetEpoch > f.votes[index].nextEpoch {
			f.votes[index].nextEpoch = targetEpoch
			f.votes[index].nextRoot = blockRoot
	}
}

Input block

When inserting a block into

$ForkChoice$, the user provides a

$block$ and its corresponding

$post\mathrm{\_}state$. The justified and finalized epochs are extracted from the

$post\mathrm{\_}state$, while the

$root$,

$slot$, and

$parent\mathrm{\_}root$ are extracted from the

$block$. If the block is post-Bellatrix, the execution

$block\mathrm{\_}hash$ is also extracted from the payload.

The function first checks whether the node already exists. If not, a new node is created and marked as

$optimistic$ by default.

The

$target$ checkpoint is determined as follows:

• If the
  $slot$ is at an epoch boundary, the node sets itself as its own
  $target$
• If the node is in the same epoch as its parent, it inherits the parent's
  $target$
• Otherwise, the node sets its parent as the
  $target$

The node is then inserted into key-value stores, both by

$payload\mathrm{\_}hash$ and by

$root$.

If the node has no parent and the tree root is not already set, it becomes the

$tree\mathrm{\_}root\mathrm{\_}node$.

For nodes with a parent:

• The node is appended to the parent’s
  $children$ list
• If it is the first block of the slot and within the proposer boost window, it becomes the
  $proposer\mathrm{\_}boost\mathrm{\_}root$. This is determined by computing seconds into the slot and checking against the boost threshold

Finally, the function calls updateBestDescendant (see explanation below under Compute New Head) starting from the tree’s root node, using the current justified, finalized, and current epochs to refresh fork choice viability.

Compute new head

A caller can call compute new head at any time. Typically, callers invoke this after a new block is processed or at intervals when sufficient attestations have been handled and they want an updated view of the head of the chain. Compute new head can be broken down into the following sub-functions:

• Update individual
  $node$ balances
• Update
  $proposer\mathrm{\_}boost$ score
• Update every
  $node$ weight
• Update every
  $node$’s best descendant
• Cache updated head in
  $ForkChoice$ store

Update node's balance

Update balances is a critical part of the

$ForkChoice$ algorithm that determines how validator balances are applied to nodes in the tree. This method takes no input directly. Instead, it operates based on the already cached validator

$votes$ and

$balances$ in the

$ForkChoice$ object.

We loop through each

$vote$ and determine whether it affects any node’s

$balance$. Slashed validators are ignored. An update occurs only if the validator’s voted

$block\mathrm{\_}root$ has changed or the validator’s

$balance$ has changed.

If the

$next\mathrm{\_}root$ in the vote points to a known node (and is not the zero hash), we increase that node’s

$balance$. If a validator is moving their vote from one node to another, we subtract the

$balance$ from the old node.

Finally, fork choice rotates the validator vote so that the

$next\mathrm{\_}root$ becomes the

$current\mathrm{\_}root$ and the new

$balance$ becomes the current

$balance$.

Update proposer boost score

Update proposer boost score adjusts some node balances to reflect proposer boost for the current slot. If a previous proposer boost was applied, its

$balance$ is reduced by the previous boost score. Next, we apply the proposer boost to the current node, identified by the cached

$proposer\mathrm{\_}boost\mathrm{\_}root$. The boost is calculated as:

$committee\mathrm{\_}weight\times \frac{ProposerScoreBoost}{100}$

Where

$committee\mathrm{\_}weight$ is the total active validator balance divided by the number of slots per epoch, and

$ProposerScoreBoost$ (default 40%) is a configuration parameter.

After applying the boost, we rotate the current proposer boost root and score to the previous ones in preparation for the next update. Calling apply proposer boost multiple times is safe because of the subtraction and addition.

func (f *ForkChoice) applyProposerBoostScore() error {
	if s.previousProposerBoostRoot != params.BeaconConfig().ZeroHash {
		previousNode, ok := s.nodeByRoot[s.previousProposerBoostRoot]
		previousNode.balance -= s.previousProposerBoostScore
		}
	}
	if s.proposerBoostRoot != params.BeaconConfig().ZeroHash {
		currentNode, ok := s.nodeByRoot[s.proposerBoostRoot]
		proposerScore = (s.committeeWeight * params.BeaconConfig().ProposerScoreBoost) / 100
		currentNode.balance += proposerScore
		}
	}
	...
}

Update node's weight

Update weight is a recursive function that updates the weight for a given node and all its children under the fork choice tree. The weight is used to determine what is the head. When the function gets called, it visits every child node and recurses down, aggregating the total weight from the children for bottom-up computation.

func (n *Node) applyWeightChanges(ctx context.Context, proposerBoostRoot [32]byte, proposerBootScore uint64) error {
	childrenWeight := uint64(0)
	for _, child := range n.children {
		if err := child.applyWeightChanges(ctx, proposerBoostRoot, proposerBootScore); err != nil {
			return err
		}
		childrenWeight += child.weight
	}
    ...

Update node's best descendant

Update best descendant is one of the final functions called during head computation. It's a recursive function that determines the best descendant for each node in the fork choice tree based on weight and fork choice viability. Starting from the leaves, it traverses child nodes to identify those that lead to a viable head.
The function only considers nodes that can lead to a viable head. The recursive function leads to viable head checks whether a child node or any of its descendants is viable to be the head. A node is considered viable if its justified epoch matches the fork choice store’s justified epoch, or if it comes from an earlier epoch but its justification is still recent—within two epochs of the current one.
Among viable children, it selects the one with the highest weight, using the block root as a tie-breaker if weights are equal. The selected child or its best descendant is then assigned as the current node’s best descendant. If no viable child is found, the best descendant field is cleared.

func (n *Node) updateBestDescendant(ctx context.Context, justifiedEpoch primitives.Epoch, finalizedEpoch primitives.Epoch, currentSlot primitives.Slot, secondsSinceSlotStart uint64, committeeWeight uint64) error {
	var bestChild *Node
	for _, child := range n.children {
		if err := child.updateBestDescendant(ctx, justifiedEpoch, finalizedEpoch, currentSlot, secondsSinceSlotStart, committeeWeight)
        ...
		childLeadsToViableHead := child.leadsToViableHead(justifiedEpoch, currentEpoch)
		if childLeadsToViableHead && !hasViableDescendant {
			bestWeight = child.weight
			bestChild = child
			hasViableDescendant = true
		} else if childLeadsToViableHead {
			if child.weight == bestWeight {
				if bytes.Compare(child.root[:], bestChild.root[:]) > 0 {
					bestChild = child
				}
			} else if child.weight > bestWeight {
				bestChild = child
				bestWeight = child.weight
			}
		}
	}
	if hasViableDescendant {
		if bestChild.bestDescendant == nil {
			n.bestDescendant = bestChild
		} else {
			n.bestDescendant = bestChild.bestDescendant
		}
        ...
	return nil
}

Get head

The final get head function returns the

$root$ of the current head block in the fork choice tree, starting from the justified checkpoint node. It first retrieves the node corresponding to

$justified\mathrm{\_}checkpoint\mathrm{\_}root$, handling an edge case if it's the genesis checkpoint. It then selects the

$best\mathrm{\_}descendant$ of the justified node, or the justified node itself if nothing exists. Before finalizing the head, it checks whether the chosen block is still viable based on justification and finalization rules. If the block is invalid, an error is returned and a flag is set. Otherwise, the function updates internal tracking and metrics and returns the new head

$root$