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.9.0/specs/core/0_fork-choice.md

Index

• Variables
• 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) error
  • func (s *Store) OnBlock(ctx context.Context, signed *ethpb.SignedBeaconBlock) error
  • func (s *Store) OnBlockInitialSyncStateTransition(ctx context.Context, signed *ethpb.SignedBeaconBlock) error

Variables

var ErrTargetRootNotInDB = errors.New("target root does not exist in db")

ErrTargetRootNotInDB returns when the target block root of an attestation cannot be found in the beacon database.

Types

type ForkChoicer

type ForkChoicer interface {
	Head(ctx context.Context) ([]byte, error)
	OnBlock(ctx context.Context, b *ethpb.SignedBeaconBlock) error
	OnBlockInitialSyncStateTransition(ctx context.Context, b *ethpb.SignedBeaconBlock) error
	OnAttestation(ctx context.Context, a *ethpb.Attestation) 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) -> Root:
 # Get filtered block tree that only includes viable branches
 blocks = get_filtered_block_tree(store)
 # Execute the LMD-GHOST fork choice
 head = store.justified_checkpoint.root
 justified_slot = compute_start_slot_at_epoch(store.justified_checkpoint.epoch)
 while True:
     children = [
         root for root in blocks.keys()
         if blocks[root].parent_root == head and 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) 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:
 """
 Run ``on_attestation`` upon receiving a new ``attestation`` from either within a block or directly on the wire.

 An ``attestation`` that is asserted as invalid may be valid at a later time,
 consider scheduling it for later processing in such case.
 """
 target = attestation.data.target

 # Attestations must be from the current or previous epoch
 current_epoch = compute_epoch_at_slot(get_current_slot(store))
 # Use GENESIS_EPOCH for previous when genesis to avoid underflow
 previous_epoch = current_epoch - 1 if current_epoch > GENESIS_EPOCH else GENESIS_EPOCH
 assert target.epoch in [current_epoch, previous_epoch]
 assert target.epoch == compute_epoch_at_slot(attestation.data.slot)

 # Attestations target be for a known block. If target block is unknown, delay consideration until the block is found
 assert target.root in store.blocks
 # Attestations 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_at_epoch(target.epoch) * SECONDS_PER_SLOT

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

 # Store target checkpoint state if not yet seen
 if target not in store.checkpoint_states:
     process_slots(base_state, compute_start_slot_at_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.
 assert store.time >= (attestation.data.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.attesting_indices:
     if i not in store.latest_messages or target.epoch > store.latest_messages[i].epoch:
         store.latest_messages[i] = LatestMessage(epoch=target.epoch, root=attestation.data.beacon_block_root)

func (*Store) OnBlock

func (s *Store) OnBlock(ctx context.Context, signed *ethpb.SignedBeaconBlock) 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:
     if state.current_justified_checkpoint.epoch > store.best_justified_checkpoint.epoch:
         store.best_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) OnBlockInitialSyncStateTransition

func (s *Store) OnBlockInitialSyncStateTransition(ctx context.Context, signed *ethpb.SignedBeaconBlock) error

OnBlockInitialSyncStateTransition 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. It also does not save attestations.