forkchoice

Documentation

Overview

Package forkchoice implements the Latest Message Driven GHOST (Greediest Heaviest Observed Sub-Tree) algorithm as the Ethereum Serenity beacon chain fork choice rule. This algorithm is designed to properly detect the canonical chain based on validator votes even in the presence of high network latency, network partitions, and many conflicting blocks. To read more about fork choice, read the official accompanying document: https://github.com/ethereum/eth2.0-specs/blob/v0.8.3/specs/core/0_fork-choice.md

Index

• type ForkChoicer
• type Store
  • func NewForkChoiceService(ctx context.Context, db db.Database) *Store
  • func (s *Store) FinalizedCheckpt() *ethpb.Checkpoint
  • func (s *Store) GenesisStore(ctx context.Context, justifiedCheckpoint *ethpb.Checkpoint, ...) error
  • func (s *Store) Head(ctx context.Context) ([]byte, error)
  • func (s *Store) JustifiedCheckpt() *ethpb.Checkpoint
  • func (s *Store) OnAttestation(ctx context.Context, a *ethpb.Attestation) (uint64, error)
  • func (s *Store) OnBlock(ctx context.Context, b *ethpb.BeaconBlock) error
  • func (s *Store) OnBlockNoVerifyStateTransition(ctx context.Context, b *ethpb.BeaconBlock) error

Types

type ForkChoicer

type ForkChoicer interface {
	Head(ctx context.Context) ([]byte, error)
	OnBlock(ctx context.Context, b *ethpb.BeaconBlock) error
	OnBlockNoVerifyStateTransition(ctx context.Context, b *ethpb.BeaconBlock) error
	OnAttestation(ctx context.Context, a *ethpb.Attestation) (uint64, error)
	GenesisStore(ctx context.Context, justifiedCheckpoint *ethpb.Checkpoint, finalizedCheckpoint *ethpb.Checkpoint) error
	FinalizedCheckpt() *ethpb.Checkpoint
}

ForkChoicer defines a common interface for methods useful for directly applying fork choice to beacon blocks to compute head.

type Store

type Store struct {
	// contains filtered or unexported fields
}

Store represents a service struct that handles the forkchoice logic of managing the full PoS beacon chain.

func NewForkChoiceService

func NewForkChoiceService(ctx context.Context, db db.Database) *Store

NewForkChoiceService instantiates a new service instance that will be registered into a running beacon node.

func (*Store) FinalizedCheckpt

func (s *Store) FinalizedCheckpt() *ethpb.Checkpoint

FinalizedCheckpt returns the latest finalized check point from fork choice store.

func (*Store) GenesisStore

func (s *Store) GenesisStore(
	ctx context.Context,
	justifiedCheckpoint *ethpb.Checkpoint,
	finalizedCheckpoint *ethpb.Checkpoint) error

GenesisStore initializes the store struct before beacon chain starts to advance.

Spec pseudocode definition:

def get_genesis_store(genesis_state: BeaconState) -> Store:
 genesis_block = BeaconBlock(state_root=hash_tree_root(genesis_state))
 root = signing_root(genesis_block)
 justified_checkpoint = Checkpoint(epoch=GENESIS_EPOCH, root=root)
 finalized_checkpoint = Checkpoint(epoch=GENESIS_EPOCH, root=root)
 return Store(
     time=genesis_state.genesis_time,
     justified_checkpoint=justified_checkpoint,
     finalized_checkpoint=finalized_checkpoint,
     blocks={root: genesis_block},
     block_states={root: genesis_state.copy()},
     checkpoint_states={justified_checkpoint: genesis_state.copy()},
 )

func (*Store) Head

func (s *Store) Head(ctx context.Context) ([]byte, error)

Head returns the head of the beacon chain.

Spec pseudocode definition:

def get_head(store: Store) -> Hash:
 # Execute the LMD-GHOST fork choice
 head = store.justified_checkpoint.root
 justified_slot = compute_start_slot_of_epoch(store.justified_checkpoint.epoch)
 while True:
     children = [
         root for root in store.blocks.keys()
         if store.blocks[root].parent_root == head and store.blocks[root].slot > justified_slot
     ]
     if len(children) == 0:
         return head
     # Sort by latest attesting balance with ties broken lexicographically
     head = max(children, key=lambda root: (get_latest_attesting_balance(store, root), root))

func (*Store) JustifiedCheckpt

func (s *Store) JustifiedCheckpt() *ethpb.Checkpoint

JustifiedCheckpt returns the latest justified check point from fork choice store.

func (*Store) OnAttestation

func (s *Store) OnAttestation(ctx context.Context, a *ethpb.Attestation) (uint64, error)

OnAttestation is called whenever an attestation is received, it updates validators latest vote, as well as the fork choice store struct.

Spec pseudocode definition:

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

 # Cannot calculate the current shuffling if have not seen the target
 assert target.root in store.blocks

 # Attestations cannot be from future epochs. If they are, delay consideration until the epoch arrives
 base_state = store.block_states[target.root].copy()
 assert store.time >= base_state.genesis_time + compute_start_slot_of_epoch(target.epoch) * SECONDS_PER_SLOT

 # Store target checkpoint state if not yet seen
 if target not in store.checkpoint_states:
     process_slots(base_state, compute_start_slot_of_epoch(target.epoch))
     store.checkpoint_states[target] = base_state
 target_state = store.checkpoint_states[target]

 # Attestations can only affect the fork choice of subsequent slots.
 # Delay consideration in the fork choice until their slot is in the past.
 attestation_slot = get_attestation_data_slot(target_state, attestation.data)
 assert store.time >= (attestation_slot + 1) * SECONDS_PER_SLOT

 # Get state at the `target` to validate attestation and calculate the committees
 indexed_attestation = get_indexed_attestation(target_state, attestation)
 assert is_valid_indexed_attestation(target_state, indexed_attestation)

 # Update latest messages
 for i in indexed_attestation.custody_bit_0_indices + indexed_attestation.custody_bit_1_indices:
     if i not in store.latest_messages or target.epoch > store.latest_messages[i].epoch:
         store.latest_messages[i] = LatestMessage(epoch=target.epoch, root=attestation.data.beacon_block_root)

func (*Store) OnBlock

func (s *Store) OnBlock(ctx context.Context, b *ethpb.BeaconBlock) error

OnBlock is called when a gossip block is received. It runs regular state transition on the block and update fork choice store.

Spec pseudocode definition:

def on_block(store: Store, block: BeaconBlock) -> None:
 # Make a copy of the state to avoid mutability issues
 assert block.parent_root in store.block_states
 pre_state = store.block_states[block.parent_root].copy()
 # Blocks cannot be in the future. If they are, their consideration must be delayed until the are in the past.
 assert store.time >= pre_state.genesis_time + block.slot * SECONDS_PER_SLOT
 # Add new block to the store
 store.blocks[signing_root(block)] = block
 # Check block is a descendant of the finalized block
 assert (
     get_ancestor(store, signing_root(block), store.blocks[store.finalized_checkpoint.root].slot) ==
     store.finalized_checkpoint.root
 )
 # Check that block is later than the finalized epoch slot
 assert block.slot > compute_start_slot_of_epoch(store.finalized_checkpoint.epoch)
 # Check the block is valid and compute the post-state
 state = state_transition(pre_state, block)
 # Add new state for this block to the store
 store.block_states[signing_root(block)] = state

 # Update justified checkpoint
 if state.current_justified_checkpoint.epoch > store.justified_checkpoint.epoch:
     store.justified_checkpoint = state.current_justified_checkpoint

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

func (*Store) OnBlockNoVerifyStateTransition

func (s *Store) OnBlockNoVerifyStateTransition(ctx context.Context, b *ethpb.BeaconBlock) error

OnBlockNoVerifyStateTransition is called when an initial sync block is received. It runs state transition on the block and without any BLS verification. The BLS verification includes proposer signature, randao and attestation's aggregated signature.