doublylinkedtree

package
v4.2.1 Latest Latest
Warning

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

 Go to latest Published: Jan 26, 2024 License: GPL-3.0 Imports: 24 Imported by: 6

Documentation

Overview

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

Index

Constants

View Source 
const ProcessAttestationsThreshold = 10

ProcessAttestationsThreshold is the number of seconds after which we process attestations for the current slot

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

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

CachedHeadRoot returns the last cached head root

func (*ForkChoice) CommonAncestor 

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 

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

ForkChoiceDump returns a full dump of forkchoice.

func (*ForkChoice) GetProposerHead 

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) HighestReceivedBlockDelay added in v4.2.1 

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

HighestReceivedBlockSlotDelay returns the number of slots that the highest received block was late when receiving it

func (*ForkChoice) HighestReceivedBlockSlot 

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

HighestReceivedBlockSlot returns the highest slot received by the forkchoice

func (*ForkChoice) InsertChain 

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

InsertChain 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) IsViableForCheckpoint added in v4.0.4 

func (f *ForkChoice) IsViableForCheckpoint(cp *forkchoicetypes.Checkpoint) (bool, error)

IsViableForCheckpoint returns whether the root passed is a checkpoint root for any known chain in forkchoice.

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) LastRoot added in v4.1.0 

func (f *ForkChoice) LastRoot(epoch primitives.Epoch) [32]byte

LastRoot returns the last canonical block root in the given epoch

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 

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 

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 a 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) Slot added in v4.0.4 

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

Slot returns the slot of the given root if it's known to forkchoice

func (*ForkChoice) TargetRootForEpoch added in v4.2.0 

func (f *ForkChoice) TargetRootForEpoch(root [32]byte, epoch primitives.Epoch) ([32]byte, error)

TargetRootForEpoch returns the root of the target block for a given epoch. The epoch parameter is crucial to identify the correct target root. For example: When inserting a block at slot 63 with block root 0xA and target root 0xB (pointing to the block at slot 32), and at slot 64, where the block is skipped, the attestation will reference the target root as 0xA (for slot 63), not 0xB (for slot 32). This implies that if the input slot exceeds the block slot, the target root will be the same as the block root. We also allow for the epoch to be below the current target for this root, in which case we return the root of the checkpoint of the chain containing the passed root, at the given epoch

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) UnrealizedJustifiedPayloadBlockHash added in v4.0.2 

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

UnrealizedJustifiedPayloadBlockHash returns the hash of the payload at the unrealized justified checkpoint

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 

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.

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.