protoarray

Documentation

Overview

Package protoarray implements proto array fork choice as outlined: https://github.com/protolambda/lmd-ghost#array-based-stateful-dag-proto_array This was motivated by the the original implementation by Sigma Prime here: https://github.com/sigp/lighthouse/pull/804

Index

• Constants
• type ForkChoice
  • func New(justifiedEpoch uint64, finalizedEpoch uint64, finalizedRoot [32]byte) *ForkChoice
  • func (f *ForkChoice) HasNode(root [32]byte) bool
  • func (f *ForkChoice) Head(ctx context.Context, justifiedEpoch uint64, justifiedRoot [32]byte, ...) ([32]byte, error)
  • func (f *ForkChoice) Node(root [32]byte) *Node
  • func (f *ForkChoice) Nodes() []*Node
  • func (f *ForkChoice) ProcessAttestation(ctx context.Context, validatorIndices []uint64, blockRoot [32]byte, ...)
  • func (f *ForkChoice) ProcessBlock(ctx context.Context, slot uint64, blockRoot [32]byte, parentRoot [32]byte, ...) error
  • func (f *ForkChoice) Prune(ctx context.Context, finalizedRoot [32]byte) error
  • func (f *ForkChoice) Store() *Store
• type Node
• type Store
• type Vote

Constants

const NonExistentNode = ^uint64(0)

NonExistentNode defines an unknown node which is used for the array based stateful DAG.

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 uint64, finalizedEpoch uint64, finalizedRoot [32]byte) *ForkChoice

New initializes a new fork choice store.

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

func (f *ForkChoice) Head(ctx context.Context, justifiedEpoch uint64, justifiedRoot [32]byte, justifiedStateBalances []uint64, finalizedEpoch uint64) ([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) Node

func (f *ForkChoice) Node(root [32]byte) *Node

Node returns the copied node in the fork choice store.

func (*ForkChoice) Nodes

func (f *ForkChoice) Nodes() []*Node

Nodes returns the copied list of block nodes in the fork choice store.

func (*ForkChoice) ProcessAttestation

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

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

func (*ForkChoice) ProcessBlock

func (f *ForkChoice) ProcessBlock(ctx context.Context, slot uint64, blockRoot [32]byte, parentRoot [32]byte, graffiti [32]byte, justifiedEpoch uint64, finalizedEpoch uint64) error

ProcessBlock processes a new block by inserting it to the fork choice 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) Store

func (f *ForkChoice) Store() *Store

Store returns the fork choice store object which contains all the information regarding proto array fork choice.

type Node

type Node struct {
	Slot           uint64   // Slot of the block converted to the node.
	Root           [32]byte // Root of the block converted to the node.
	Parent         uint64   // Parent index of this node.
	JustifiedEpoch uint64   // JustifiedEpoch of this node.
	FinalizedEpoch uint64   // FinalizedEpoch of this node.
	Weight         uint64   // Weight of this node.
	BestChild      uint64   // BestChild index of this node.
	BestDescendant uint64   // BestDescendant of this node.
	Graffiti       [32]byte // Graffiti of the block node.
}

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 {
	PruneThreshold uint64 // do not prune tree unless threshold is reached.
	JustifiedEpoch uint64 // latest justified epoch in store.
	FinalizedEpoch uint64 // latest finalized epoch in store.

	Nodes       []*Node             // list of block nodes, each node is a representation of one block.
	NodeIndices map[[32]byte]uint64 // the root of block node and the Nodes index in the list.
	// contains filtered or unexported fields
}

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

type Vote

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

Vote defines an individual validator's vote.