doublylinkedtree

package
v3.2.2 Latest Latest
Warning

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

Go to latest
Published: Mar 6, 2023 License: GPL-3.0 Imports: 25 Imported by: 3

Documentation

Overview

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

Index

Constants

This section is empty.

Variables

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

Functions

This section is empty.

Types

type ForkChoice

type ForkChoice struct {
	sync.RWMutex
	// 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) AncestorRoot

func (f *ForkChoice) AncestorRoot(ctx context.Context, root [32]byte, slot primitives.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) CommonAncestor added in v3.1.0

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

CommonAncestor returns the common ancestor root and slot 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) ForkChoiceDump added in v3.1.0

func (f *ForkChoice) ForkChoiceDump(ctx context.Context) (*v1.ForkChoiceDump, error)

ForkChoiceDump returns a full dump of forkchoice.

func (*ForkChoice) GetProposerHead added in v3.2.2

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

GetProposerHead returns the block root that has to be used as ParentRoot by a proposer. It may not be the actual head of the canonical chain, in certain cases it may be its parent, when the last head block has arrived early and is considered safe to be orphaned.

This function needs to be called only when proposing a block and all attestation processing has already happened.

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,
) ([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) HighestReceivedBlockRoot added in v3.1.2

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

HighestReceivedBlockRoot returns the highest slot root received by the forkchoice

func (*ForkChoice) HighestReceivedBlockSlot

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

HighestReceivedBlockSlot returns the highest slot received by the forkchoice

func (*ForkChoice) InsertChain added in v3.2.2

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

InsertOptimisticChain inserts all nodes corresponding to blocks in the slice `blocks`. This slice must be ordered from child to parent. It includes all blocks **except** the first one (that is the one with the highest slot number). All blocks are assumed to be a strict chain where blocks[i].Parent = blocks[i+1]. Also we assume that the parent of the last block in this list is already included in forkchoice store.

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

func (f *ForkChoice) InsertSlashedIndex(_ context.Context, index primitives.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) 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 primitives.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 primitives.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) SetBalancesByRooter added in v3.1.2

func (f *ForkChoice) SetBalancesByRooter(handler forkchoice.BalancesByRooter)

SetBalancesByRooter sets the balanceByRoot handler in forkchoice

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 [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) SetOriginRoot

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

SetOriginRoot sets the genesis block root

func (*ForkChoice) ShouldOverrideFCU added in v3.2.2

func (f *ForkChoice) ShouldOverrideFCU() (override bool)

ShouldOverrideFCU returns whether the current forkchoice head is weak and thus may be reorged when proposing the next block. This function should only be called if the following two conditions are satisfied: 1- It is immediately after receiving a block that may be subject to a reorg

or

It is right after processAttestationsThreshold and we have processed the
current slots attestations.

2- The caller has already called Forkchoice.Head() so that forkchoice has been updated. 3- The beacon node is serving a validator that will propose during the next slot.

This function only applies an heuristic to decide if the beacon will update the engine's view of head with the parent block or the incoming block. It does not guarantee an attempted reorg. This will only be decided later at proposal time by calling GetProposerHead.

func (*ForkChoice) Tips

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

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

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(ctx context.Context, jc *forkchoicetypes.Checkpoint) error

UpdateJustifiedCheckpoint sets the justified checkpoint to the given one

func (*ForkChoice) Weight added in v3.2.1

func (f *ForkChoice) Weight(root [32]byte) (uint64, error)

Weight returns the weight of the given root if found on the store

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.

type Vote

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

Vote defines an individual validator's vote.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL