protoarray

package
v3.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 22, 2022 License: GPL-3.0 Imports: 25 Imported by: 0

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 original implementation by Sigma Prime here: https://github.com/sigp/lighthouse/pull/804

Index

Constants

View Source 
const NonExistentNode = ^uint64(0)

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

Variables

View Source 
var ErrUnknownNodeRoot = errors.New("unknown block root")

Functions

This section is empty.

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() *ForkChoice

New initializes a new fork choice store.

func (*ForkChoice) AllTipsAreInvalid 

func (f *ForkChoice) AllTipsAreInvalid() bool

AllTipsAreInvalid returns true if no forkchoice tip is viable for head

func (*ForkChoice) AncestorRoot 

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

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

func (*ForkChoice) BestJustifiedCheckpoint 

func (f *ForkChoice) BestJustifiedCheckpoint() *forkchoicetypes.Checkpoint

BestJustifiedCheckpoint of fork choice store.

func (*ForkChoice) CachedHeadRoot 

func (f *ForkChoice) CachedHeadRoot() [32]byte

CachedHeadRoot returns the last cached head root

func (*ForkChoice) CommonAncestorRoot 

func (f *ForkChoice) CommonAncestorRoot(ctx context.Context, r1 [32]byte, r2 [32]byte) ([32]byte, error)

CommonAncestorRoot returns the common ancestor root between the two block roots r1 and r2.

func (*ForkChoice) FinalizedCheckpoint 

func (f *ForkChoice) FinalizedCheckpoint() *forkchoicetypes.Checkpoint

FinalizedCheckpoint of fork choice store.

func (*ForkChoice) FinalizedPayloadBlockHash 

func (f *ForkChoice) FinalizedPayloadBlockHash() [32]byte

FinalizedPayloadBlockHash returns the hash of the payload at the finalized checkpoint

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, justifiedStateBalances []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) HighestReceivedBlockSlot 

func (f *ForkChoice) HighestReceivedBlockSlot() types.Slot

HighestReceivedBlockSlot returns the highest slot received by the forkchoice

func (*ForkChoice) InsertNode 

func (f *ForkChoice) InsertNode(ctx context.Context, state state.BeaconState, root [32]byte) error

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

func (*ForkChoice) InsertOptimisticChain 

func (f *ForkChoice) InsertOptimisticChain(ctx context.Context, chain []*forkchoicetypes.BlockAndCheckpoints) error

InsertOptimisticChain inserts all nodes corresponding to blocks in the slice `blocks`. It includes all blocks **except** the first one.

func (*ForkChoice) InsertSlashedIndex 

func (f *ForkChoice) InsertSlashedIndex(ctx 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 this node is optimistically synced A optimistically synced block is synced as usual, but its execution payload is not validated, while the EL is still syncing. This function returns an error if the block is not found in the fork choice store

func (*ForkChoice) JustifiedCheckpoint 

func (f *ForkChoice) JustifiedCheckpoint() *forkchoicetypes.Checkpoint

JustifiedCheckpoint of fork choice store.

func (*ForkChoice) JustifiedPayloadBlockHash 

func (f *ForkChoice) JustifiedPayloadBlockHash() [32]byte

JustifiedPayloadBlockHash returns the hash of the payload at the justified checkpoint

func (*ForkChoice) NewSlot 

func (f *ForkChoice) NewSlot(ctx context.Context, slot types.Slot) error

NewSlot mimics the implementation of `on_tick` in fork choice consensus spec. It resets the proposer boost root in fork choice, and it updates store's justified checkpoint if a better checkpoint on the store's finalized checkpoint chain. This should only be called at the start of every slot interval.

Spec pseudocode definition: 

# Reset store.proposer_boost_root if this is a new slot
if current_slot > previous_slot:
    store.proposer_boost_root = Root()

# Not a new epoch, return
if not (current_slot > previous_slot and compute_slots_since_epoch_start(current_slot) == 0):
    return

# Update store.justified_checkpoint if a better checkpoint on the store.finalized_checkpoint chain
if store.best_justified_checkpoint.epoch > store.justified_checkpoint.epoch:
    finalized_slot = compute_start_slot_at_epoch(store.finalized_checkpoint.epoch)
    ancestor_at_finalized_slot = get_ancestor(store, store.best_justified_checkpoint.root, finalized_slot)
    if ancestor_at_finalized_slot == store.finalized_checkpoint.root:
        store.justified_checkpoint = store.best_justified_checkpoint

func (*ForkChoice) NodeCount 

func (f *ForkChoice) NodeCount() int

NodeCount returns the current number of nodes in the Store

func (*ForkChoice) PreviousJustifiedCheckpoint 

func (f *ForkChoice) PreviousJustifiedCheckpoint() *forkchoicetypes.Checkpoint

PreviousJustifiedCheckpoint of 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) ProposerBoost 

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

ProposerBoost returns the proposerBoost of the store

func (*ForkChoice) ReceivedBlocksLastEpoch 

func (f *ForkChoice) ReceivedBlocksLastEpoch() (uint64, error)

ReceivedBlocksLastEpoch returns the number of blocks received in the last epoch

func (*ForkChoice) ResetBoostedProposerRoot 

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

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

func (*ForkChoice) SetGenesisTime 

func (f *ForkChoice) SetGenesisTime(genesisTime uint64)

SetGenesisTime sets the genesisTime tracked by forkchoice

func (*ForkChoice) SetOptimisticToInvalid 

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

SetOptimisticToInvalid updates the synced_tips map when the block with the given root becomes INVALID. It takes three parameters: the root of the INVALID block, its parent root and the payload Hash of the last valid block

func (*ForkChoice) SetOptimisticToValid 

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

SetOptimisticToValid is called with the root of a block that was returned as VALID by the EL.

WARNING: This method returns an error if the root is not found in forkchoice

func (*ForkChoice) SetOriginRoot 

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

SetOriginRoot sets the genesis block root

func (*ForkChoice) Tips 

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

Tips returns all possible chain heads (leaves of fork choice tree). Heads roots and heads slots are returned.

func (*ForkChoice) UpdateFinalizedCheckpoint 

func (f *ForkChoice) UpdateFinalizedCheckpoint(fc *forkchoicetypes.Checkpoint) error

UpdateFinalizedCheckpoint sets the finalized checkpoint to the given one

func (*ForkChoice) UpdateJustifiedCheckpoint 

func (f *ForkChoice) UpdateJustifiedCheckpoint(jc *forkchoicetypes.Checkpoint) error

UpdateJustifiedCheckpoint sets the justified checkpoint to the given one

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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.