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, finalizedEpoch types.Epoch, finalizedRoot [32]byte) *ForkChoice
  • func (f *ForkChoice) AncestorRoot(ctx context.Context, root [32]byte, slot types.Slot) ([]byte, error)
  • 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) IsCanonical(root [32]byte) bool
  • 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 types.Slot, blockRoot, parentRoot, graffiti [32]byte, ...) error
  • func (f *ForkChoice) Prune(ctx context.Context, finalizedRoot [32]byte) error
  • func (f *ForkChoice) Store() *Store
• type Node
  • func (n *Node) BestChild() uint64
  • func (n *Node) BestDescendant() uint64
  • func (n *Node) FinalizedEpoch() types.Epoch
  • func (n *Node) Graffiti() [32]byte
  • func (n *Node) JustifiedEpoch() types.Epoch
  • func (n *Node) Parent() uint64
  • func (n *Node) Root() [32]byte
  • func (n *Node) Slot() types.Slot
  • func (n *Node) Weight() uint64
• type Store
  • func (s *Store) FinalizedEpoch() types.Epoch
  • func (s *Store) JustifiedEpoch() types.Epoch
  • func (s *Store) Nodes() []*Node
  • func (s *Store) NodesIndices() map[[32]byte]uint64
  • func (s *Store) PruneThreshold() uint64
• 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, finalizedEpoch types.Epoch, finalizedRoot [32]byte) *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) 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) IsCanonical

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

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

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 types.Epoch)

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 types.Slot,
	blockRoot, parentRoot, graffiti [32]byte,
	justifiedEpoch, finalizedEpoch types.Epoch,
) 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 {
	// 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.

func (*Node) BestChild

func (n *Node) BestChild() uint64

BestChild of the fork choice node.

func (*Node) BestDescendant

func (n *Node) BestDescendant() uint64

BestDescendant of the fork choice node.

func (*Node) FinalizedEpoch

func (n *Node) FinalizedEpoch() types.Epoch

FinalizedEpoch of the fork choice node.

func (*Node) Graffiti

func (n *Node) Graffiti() [32]byte

Graffiti of the fork choice node.

func (*Node) JustifiedEpoch

func (n *Node) JustifiedEpoch() types.Epoch

JustifiedEpoch of the fork choice node.

func (*Node) Parent

func (n *Node) Parent() uint64

Parent of the fork choice node.

func (*Node) Root

func (n *Node) Root() [32]byte

Root of the fork choice node.

func (*Node) Slot

func (n *Node) Slot() types.Slot

Slot of the fork choice node.

func (*Node) Weight

func (n *Node) Weight() uint64

Weight of the fork choice node.

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

func (s *Store) FinalizedEpoch() types.Epoch

FinalizedEpoch of fork choice store.

func (*Store) JustifiedEpoch

func (s *Store) JustifiedEpoch() types.Epoch

JustifiedEpoch of fork choice store.

func (*Store) Nodes

func (s *Store) Nodes() []*Node

Nodes of fork choice store.

func (*Store) NodesIndices

func (s *Store) NodesIndices() map[[32]byte]uint64

NodesIndices of fork choice store.

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.