doublylinkedtree

Documentation

Overview

Package doublylinkedtree implements eth2 LMD GHOST fork choice using the doubly linked proto array node structure.

Index

• Variables
• type ForkChoice
  • func New(justifiedEpoch, finalizedEpoch types.Epoch) *ForkChoice
  • func (f *ForkChoice) AncestorRoot(ctx context.Context, root [32]byte, slot types.Slot) ([]byte, error)
  • func (f *ForkChoice) BoostProposerRoot(_ context.Context, args *forkchoicetypes.ProposerBoostRootArgs) error
  • func (f *ForkChoice) FinalizedEpoch() types.Epoch
  • func (f *ForkChoice) ForkChoiceNodes() []*pbrpc.ForkChoiceNode
  • func (f *ForkChoice) HasNode(root [32]byte) bool
  • func (f *ForkChoice) HasParent(root [32]byte) bool
  • func (f *ForkChoice) Head(ctx context.Context, justifiedEpoch types.Epoch, justifiedRoot [32]byte, ...) ([32]byte, error)
  • func (f *ForkChoice) InsertOptimisticBlock(ctx context.Context, slot types.Slot, ...) error
  • func (f *ForkChoice) InsertSlashedIndex(_ context.Context, index types.ValidatorIndex)
  • func (f *ForkChoice) IsCanonical(root [32]byte) bool
  • func (f *ForkChoice) IsOptimistic(root [32]byte) (bool, error)
  • func (f *ForkChoice) JustifiedEpoch() types.Epoch
  • func (f *ForkChoice) NodeCount() int
  • func (f *ForkChoice) ProcessAttestation(ctx context.Context, validatorIndices []uint64, blockRoot [32]byte, ...)
  • func (f *ForkChoice) ProposerBoost() [fieldparams.RootLength]byte
  • func (f *ForkChoice) Prune(ctx context.Context, finalizedRoot [32]byte) error
  • func (f *ForkChoice) ResetBoostedProposerRoot(_ context.Context) error
  • func (f *ForkChoice) SetOptimisticToInvalid(ctx context.Context, ...) ([][32]byte, error)
  • func (f *ForkChoice) SetOptimisticToValid(ctx context.Context, root [fieldparams.RootLength]byte) error
  • func (f *ForkChoice) Tips() ([][32]byte, []types.Slot)
• type Node
• type Store
  • func (s *Store) PruneThreshold() uint64
• type Vote

Variables

var ErrNilNode = errors.New("invalid nil or unknown node")

Types

type ForkChoice

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

ForkChoice defines the overall fork choice store which includes all block nodes, validator's latest votes and balances.

func New

func New(justifiedEpoch, finalizedEpoch types.Epoch) *ForkChoice

New initializes a new fork choice store.

func (*ForkChoice) AncestorRoot

func (f *ForkChoice) AncestorRoot(ctx context.Context, root [32]byte, slot types.Slot) ([]byte, error)

AncestorRoot returns the ancestor root of input block root at a given slot.

func (*ForkChoice) BoostProposerRoot

func (f *ForkChoice) BoostProposerRoot(_ context.Context, args *forkchoicetypes.ProposerBoostRootArgs) error

BoostProposerRoot sets the block root which should be boosted during the LMD fork choice algorithm calculations. This is meant to reward timely, proposed blocks which occur before a cutoff interval set to SECONDS_PER_SLOT // INTERVALS_PER_SLOT.

time_into_slot = (store.time - store.genesis_time) % SECONDS_PER_SLOT
is_before_attesting_interval = time_into_slot < SECONDS_PER_SLOT // INTERVALS_PER_SLOT
if get_current_slot(store) == block.slot and is_before_attesting_interval:
    store.proposer_boost_root = hash_tree_root(block)

func (*ForkChoice) FinalizedEpoch

func (f *ForkChoice) FinalizedEpoch() types.Epoch

FinalizedEpoch of fork choice store.

func (*ForkChoice) ForkChoiceNodes

func (f *ForkChoice) ForkChoiceNodes() []*pbrpc.ForkChoiceNode

func (*ForkChoice) HasNode

func (f *ForkChoice) HasNode(root [32]byte) bool

HasNode returns true if the node exists in fork choice store, false else wise.

func (*ForkChoice) HasParent

func (f *ForkChoice) HasParent(root [32]byte) bool

HasParent returns true if the node parent exists in fork choice store, false else wise.

func (*ForkChoice) Head

func (f *ForkChoice) Head(
	ctx context.Context,
	justifiedEpoch types.Epoch,
	justifiedRoot [32]byte,
	justifiedStateBalances []uint64,
	finalizedEpoch types.Epoch,
) ([32]byte, error)

Head returns the head root from fork choice store. It firsts computes validator's balance changes then recalculates block tree from leaves to root.

func (*ForkChoice) InsertOptimisticBlock

func (f *ForkChoice) InsertOptimisticBlock(
	ctx context.Context,
	slot types.Slot,
	blockRoot, parentRoot, payloadHash [fieldparams.RootLength]byte,
	justifiedEpoch, finalizedEpoch types.Epoch,
) error

InsertOptimisticBlock processes a new block by inserting it to the fork choice store.

func (*ForkChoice) InsertSlashedIndex

func (f *ForkChoice) InsertSlashedIndex(_ context.Context, index types.ValidatorIndex)

InsertSlashedIndex adds the given slashed validator index to the store-tracked list. Votes from these validators are not accounted for in forkchoice.

func (*ForkChoice) IsCanonical

func (f *ForkChoice) IsCanonical(root [32]byte) bool

IsCanonical returns true if the given root is part of the canonical chain.

func (*ForkChoice) IsOptimistic

func (f *ForkChoice) IsOptimistic(root [32]byte) (bool, error)

IsOptimistic returns true if the given root has been optimistically synced.

func (*ForkChoice) JustifiedEpoch

func (f *ForkChoice) JustifiedEpoch() types.Epoch

JustifiedEpoch of fork choice store.

func (*ForkChoice) NodeCount

func (f *ForkChoice) NodeCount() int

NodeCount returns the current number of nodes in the Store.

func (*ForkChoice) ProcessAttestation

func (f *ForkChoice) ProcessAttestation(ctx context.Context, validatorIndices []uint64, blockRoot [32]byte, targetEpoch types.Epoch)

ProcessAttestation processes attestation for vote accounting, it iterates around validator indices and update their votes accordingly.

func (*ForkChoice) ProposerBoost

func (f *ForkChoice) ProposerBoost() [fieldparams.RootLength]byte

ProposerBoost returns the proposerBoost of the store

func (*ForkChoice) Prune

func (f *ForkChoice) Prune(ctx context.Context, finalizedRoot [32]byte) error

Prune prunes the fork choice store with the new finalized root. The store is only pruned if the input root is different than the current store finalized root, and the number of the store has met prune threshold.

func (*ForkChoice) ResetBoostedProposerRoot

func (f *ForkChoice) ResetBoostedProposerRoot(_ context.Context) error

ResetBoostedProposerRoot sets the value of the proposer boosted root to zeros.

func (*ForkChoice) SetOptimisticToInvalid

func (f *ForkChoice) SetOptimisticToInvalid(ctx context.Context, root, parentRoot, payloadHash [fieldparams.RootLength]byte) ([][32]byte, error)

SetOptimisticToInvalid removes a block with an invalid execution payload from fork choice store

func (*ForkChoice) SetOptimisticToValid

func (f *ForkChoice) SetOptimisticToValid(ctx context.Context, root [fieldparams.RootLength]byte) error

SetOptimisticToValid sets the node with the given root as a fully validated node

func (*ForkChoice) Tips

func (f *ForkChoice) Tips() ([][32]byte, []types.Slot)

Tips returns a list of possible heads from fork choice store, it returns the roots and the slots of the leaf nodes.

type Node

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

Node defines the individual block which includes its block parent, ancestor and how much weight accounted for it. This is used as an array based stateful DAG for efficient fork choice look up.

type Store

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

Store defines the fork choice store which includes block nodes and the last view of checkpoint information.

func (*Store) PruneThreshold

func (s *Store) PruneThreshold() uint64

PruneThreshold of fork choice store.

type Vote

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

Vote defines an individual validator's vote.