import { Epoch , RootHex } from "@chainsafe/lodestar-types" ; import { IProtoBlock , IProtoNode , HEX_ZERO_HASH } from "./interface" ; import { ProtoArrayError , ProtoArrayErrorCode } from "./errors" ; export const DEFAULT_PRUNE_THRESHOLD = 0 ; export class ProtoArray { pruneThreshold : number ; justifiedEpoch : Epoch ; justifiedRoot : RootHex ; finalizedEpoch : Epoch ; finalizedRoot : RootHex ; nodes : IProtoNode [ ] ; indices : Map < RootHex , number > ; constructor ( { pruneThreshold , justifiedEpoch , justifiedRoot , finalizedEpoch , finalizedRoot , } ) { this . pruneThreshold = pruneThreshold ; this . justifiedEpoch = justifiedEpoch ; this . justifiedRoot = justifiedRoot ; this . finalizedEpoch = finalizedEpoch ; this . finalizedRoot = finalizedRoot ; this . nodes = [ ] ; this . indices = new Map < string , number > ( ) ; } static initialize ( block ) { const protoArray = new ProtoArray ( { pruneThreshold : DEFAULT_PRUNE_THRESHOLD , justifiedEpoch : block . justifiedEpoch , justifiedRoot : block . justifiedRoot , finalizedEpoch : block . finalizedEpoch , finalizedRoot : block . finalizedRoot , } ) ; protoArray . onBlock ( { ... block , targetRoot : block . blockRoot , } as IProtoBlock ) ; return protoArray ; } /**
     * Iterate backwards through the array, touching all nodes and their parents and potentially
     * the best-child of each parent.
     *
     * The structure of the `self.nodes` array ensures that the child of each node is always
     * touched before its parent.
     *
     * For each node, the following is done:
     *
     * - Update the node's weight with the corresponding delta.
     * - Back-propagate each node's delta to its parents delta.
     * - Compare the current node with the parents best-child, updating it if the current node
     * should become the best child.
     * - If required, update the parents best-descendant with the current node or its best-descendant.
     */ applyScoreChanges ( { deltas , justifiedEpoch , justifiedRoot , finalizedEpoch , finalizedRoot , } ) { if ( deltas . length !== this . indices . size ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_DELTA_LEN , deltas : deltas . length , indices : this . indices . size , } ) ; } if ( justifiedEpoch !== this . justifiedEpoch || finalizedEpoch !== this . finalizedEpoch || justifiedRoot !== this . justifiedRoot || finalizedRoot !== this . finalizedRoot ) { this . justifiedEpoch = justifiedEpoch ; this . finalizedEpoch = finalizedEpoch ; this . justifiedRoot = justifiedRoot ; this . finalizedRoot = finalizedRoot ; } for ( let nodeIndex = this . nodes . length - 1 ; nodeIndex >= 0 ; nodeIndex -- ) { const node = this . nodes [ nodeIndex ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : nodeIndex , } ) ; } if ( node . blockRoot === HEX_ZERO_HASH ) { continue ; } const nodeDelta = deltas [ nodeIndex ] ; if ( nodeDelta === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_DELTA , index : nodeIndex , } ) ; } node . weight += nodeDelta ; const parentIndex = node . parent ; if ( parentIndex !== undefined ) { const parentDelta = deltas [ parentIndex ] ; if ( parentDelta === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_PARENT_DELTA , index : parentIndex , } ) ; } deltas [ parentIndex ] += nodeDelta ; } } for ( let nodeIndex = this . nodes . length - 1 ; nodeIndex >= 0 ; nodeIndex -- ) { const node = this . nodes [ nodeIndex ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : nodeIndex , } ) ; } const parentIndex = node . parent ; if ( parentIndex !== undefined ) { this . maybeUpdateBestChildAndDescendant ( parentIndex , nodeIndex ) ; } } } /**
     * Register a block with the fork choice.
     *
     * It is only sane to supply an undefined parent for the genesis block
     */ onBlock ( block ) { if ( this . indices . has ( block . blockRoot ) ) { return ; } const node = { ... block , parent : this . indices . get ( block . parentRoot ) , weight : 0 , bestChild : undefined , bestDescendant : undefined , } ; let nodeIndex = this . nodes . length ; this . indices . set ( node . blockRoot , nodeIndex ) ; this . nodes . push ( node ) ; let parentIndex = node . parent ; let n = node ; while ( parentIndex !== undefined ) { this . maybeUpdateBestChildAndDescendant ( parentIndex , nodeIndex ) ; nodeIndex = parentIndex ; n = this . getNodeByIndex ( nodeIndex ) ; parentIndex = n ?. parent ; } } /**
     * Follows the best-descendant links to find the best-block (i.e., head-block).
     */ findHead ( justifiedRoot ) { const justifiedIndex = this . indices . get ( justifiedRoot ) ; if ( justifiedIndex === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . JUSTIFIED_NODE_UNKNOWN , root : justifiedRoot , } ) ; } const justifiedNode = this . nodes [ justifiedIndex ] ; if ( justifiedNode === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_JUSTIFIED_INDEX , index : justifiedIndex , } ) ; } const bestDescendantIndex = justifiedNode . bestDescendant ?? justifiedIndex ; const bestNode = this . nodes [ bestDescendantIndex ] ; if ( bestNode === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_BEST_DESCENDANT_INDEX , index : bestDescendantIndex , } ) ; } /**
         * Perform a sanity check that the node is indeed valid to be the head
         * The justified node is always considered viable for head per spec:
         * def get_head(store: Store) -> Root:
         * blocks = get_filtered_block_tree(store)
         * head = store.justified_checkpoint.root
         */ if ( bestDescendantIndex !== justifiedIndex && ! this . nodeIsViableForHead ( bestNode ) ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_BEST_NODE , startRoot : justifiedRoot , justifiedEpoch : this . justifiedEpoch , finalizedEpoch : this . finalizedEpoch , headRoot : justifiedNode . blockRoot , headJustifiedEpoch : justifiedNode . justifiedEpoch , headFinalizedEpoch : justifiedNode . finalizedEpoch , } ) ; } return bestNode . blockRoot ; } /**
     * Update the tree with new finalization information. The tree is only actually pruned if both
     * of the two following criteria are met:
     *
     * - The supplied finalized epoch and root are different to the current values.
     * - The number of nodes in `self` is at least `self.prune_threshold`.
     *
     * # Errors
     *
     * Returns errors if:
     *
     * - The finalized epoch is less than the current one.
     * - The finalized epoch is equal to the current one, but the finalized root is different.
     * - There is some internal error relating to invalid indices inside `this`.
     */ maybePrune ( finalizedRoot ) { const finalizedIndex = this . indices . get ( finalizedRoot ) ; if ( finalizedIndex === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . FINALIZED_NODE_UNKNOWN , root : finalizedRoot , } ) ; } if ( finalizedIndex < this . pruneThreshold ) { return [ ] ; } for ( let nodeIndex = 0 ; nodeIndex < finalizedIndex ; nodeIndex ++ ) { const node = this . nodes [ nodeIndex ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : nodeIndex } ) ; } this . indices . delete ( node . blockRoot ) ; } const removed = this . nodes . slice ( 0 , finalizedIndex ) ; this . nodes = this . nodes . slice ( finalizedIndex ) ; for ( const [ key , value ] of this . indices . entries ( ) ) { if ( value < finalizedIndex ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INDEX_OVERFLOW , value : "indices" , } ) ; } this . indices . set ( key , value - finalizedIndex ) ; } for ( let i = 0 , len = this . nodes . length ; i < len ; i ++ ) { const node = this . nodes [ i ] ; const parentIndex = node . parent ; if ( parentIndex !== undefined ) { node . parent = parentIndex < finalizedIndex ? undefined : parentIndex - finalizedIndex ; } const bestChild = node . bestChild ; if ( bestChild !== undefined ) { if ( bestChild < finalizedIndex ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INDEX_OVERFLOW , value : "bestChild" , } ) ; } node . bestChild = bestChild - finalizedIndex ; } const bestDescendant = node . bestDescendant ; if ( bestDescendant !== undefined ) { if ( bestDescendant < finalizedIndex ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INDEX_OVERFLOW , value : "bestDescendant" , } ) ; } node . bestDescendant = bestDescendant - finalizedIndex ; } } return removed ; } /**
     * Observe the parent at `parent_index` with respect to the child at `child_index` and
     * potentially modify the `parent.best_child` and `parent.best_descendant` values.
     *
     * ## Detail
     *
     * There are four outcomes:
     *
     * - The child is already the best child but it's now invalid due to a FFG change and should be removed.
     * - The child is already the best child and the parent is updated with the new
     * best-descendant.
     * - The child is not the best child but becomes the best child.
     * - The child is not the best child and does not become the best child.
     */ maybeUpdateBestChildAndDescendant ( parentIndex , childIndex ) { const childNode = this . nodes [ childIndex ] ; if ( childNode === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : childIndex , } ) ; } const parentNode = this . nodes [ parentIndex ] ; if ( parentNode === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : parentIndex , } ) ; } const childLeadsToViableHead = this . nodeLeadsToViableHead ( childNode ) ; type ChildAndDescendant = [ number | undefined , number | undefined ] ; const changeToNull = [ undefined , undefined ] ; const changeToChild = [ childIndex , childNode . bestDescendant ?? childIndex ] ; const noChange = [ parentNode . bestChild , parentNode . bestDescendant ] ; let newChildAndDescendant ; const bestChildIndex = parentNode . bestChild ; if ( bestChildIndex !== undefined ) { if ( bestChildIndex === childIndex && ! childLeadsToViableHead ) { newChildAndDescendant = changeToNull ; } else if ( bestChildIndex === childIndex ) { newChildAndDescendant = changeToChild ; } else { const bestChildNode = this . nodes [ bestChildIndex ] ; if ( bestChildNode === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_BEST_CHILD_INDEX , index : bestChildIndex , } ) ; } const bestChildLeadsToViableHead = this . nodeLeadsToViableHead ( bestChildNode ) ; if ( childLeadsToViableHead && ! bestChildLeadsToViableHead ) { newChildAndDescendant = changeToChild ; } else if ( ! childLeadsToViableHead && bestChildLeadsToViableHead ) { newChildAndDescendant = noChange ; } else if ( childNode . weight === bestChildNode . weight ) { if ( childNode . blockRoot >= bestChildNode . blockRoot ) { newChildAndDescendant = changeToChild ; } else { newChildAndDescendant = noChange ; } } else { if ( childNode . weight >= bestChildNode . weight ) { newChildAndDescendant = changeToChild ; } else { newChildAndDescendant = noChange ; } } } } else if ( childLeadsToViableHead ) { newChildAndDescendant = changeToChild ; } else { newChildAndDescendant = noChange ; } parentNode . bestChild = newChildAndDescendant [ 0 ] ; parentNode . bestDescendant = newChildAndDescendant [ 1 ] ; } /**
     * Indicates if the node itself is viable for the head, or if it's best descendant is viable
     * for the head.
     */ nodeLeadsToViableHead ( node ) { let bestDescendantIsViableForHead ; const bestDescendantIndex = node . bestDescendant ; if ( bestDescendantIndex !== undefined ) { const bestDescendantNode = this . nodes [ bestDescendantIndex ] ; if ( bestDescendantNode === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_BEST_DESCENDANT_INDEX , index : bestDescendantIndex , } ) ; } bestDescendantIsViableForHead = this . nodeIsViableForHead ( bestDescendantNode ) ; } else { bestDescendantIsViableForHead = false ; } return bestDescendantIsViableForHead || this . nodeIsViableForHead ( node ) ; } /**
     * This is the equivalent to the `filter_block_tree` function in the eth2 spec:
     *
     * https://github.com/ethereum/eth2.0-specs/blob/v1.0.1/specs/phase0/fork-choice.md#filter_block_tree
     *
     * Any node that has a different finalized or justified epoch should not be viable for the
     * head.
     */ nodeIsViableForHead ( node ) { const correctJustified = ( node . justifiedEpoch === this . justifiedEpoch && node . justifiedRoot === this . justifiedRoot ) || this . justifiedEpoch === 0 ; const correctFinalized = ( node . finalizedEpoch === this . finalizedEpoch && node . finalizedRoot === this . finalizedRoot ) || this . finalizedEpoch === 0 ; return correctJustified && correctFinalized ; } /**
     * Iterate from a block root backwards over nodes
     */ * iterateAncestorNodes ( blockRoot ) { const startIndex = this . indices . get ( blockRoot ) ; if ( startIndex === undefined ) { return ; } const node = this . nodes [ startIndex ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : startIndex , } ) ; } yield * this . iterateAncestorNodesFromNode ( node ) ; } /**
     * Iterate from a block root backwards over nodes
     */ * iterateAncestorNodesFromNode ( node ) { while ( node . parent !== undefined ) { node = this . getNodeFromIndex ( node . parent ) ; yield node ; } } /**
     * Get all nodes from a block root backwards
     */ getAllAncestorNodes ( blockRoot ) { const startIndex = this . indices . get ( blockRoot ) ; if ( startIndex === undefined ) { return [ ] ; } let node = this . nodes [ startIndex ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : startIndex , } ) ; } const nodes = [ node ] ; while ( node . parent !== undefined ) { node = this . getNodeFromIndex ( node . parent ) ; nodes . push ( node ) ; } return nodes ; } /**
     * The opposite of iterateNodes.
     * iterateNodes is to find ancestor nodes of a blockRoot.
     * this is to find non-ancestor nodes of a blockRoot.
     */ getAllNonAncestorNodes ( blockRoot ) { const startIndex = this . indices . get ( blockRoot ) ; if ( startIndex === undefined ) { return [ ] ; } let node = this . nodes [ startIndex ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index : startIndex , } ) ; } const result = [ ] ; let nodeIndex = startIndex ; while ( node . parent !== undefined ) { const parentIndex = node . parent ; node = this . getNodeFromIndex ( parentIndex ) ; result . push ( ... this . getNodesBetween ( nodeIndex , parentIndex ) ) ; nodeIndex = parentIndex ; } result . push ( ... this . getNodesBetween ( nodeIndex , 0 ) ) ; return result ; } hasBlock ( blockRoot ) { return this . indices . has ( blockRoot ) ; } getNode ( blockRoot ) { const blockIndex = this . indices . get ( blockRoot ) ; if ( blockIndex === undefined ) { return undefined ; } return this . getNodeByIndex ( blockIndex ) ; } getBlock ( blockRoot ) { const node = this . getNode ( blockRoot ) ; if ( ! node ) { return undefined ; } return { ... node , } ; } /**
     * Returns `true` if the `descendantRoot` has an ancestor with `ancestorRoot`.
     * Always returns `false` if either input roots are unknown.
     * Still returns `true` if `ancestorRoot` === `descendantRoot` (and the roots are known)
     */ isDescendant ( ancestorRoot , descendantRoot ) { const ancestorNode = this . getNode ( ancestorRoot ) ; if ( ! ancestorNode ) { return false ; } if ( ancestorRoot === descendantRoot ) { return true ; } for ( const node of this . iterateAncestorNodes ( descendantRoot ) ) { if ( node . slot < ancestorNode . slot ) { return false ; } if ( node . blockRoot === ancestorNode . blockRoot ) { return true ; } } return false ; } /**
     * Returns a common ancestor for nodeA or nodeB or null if there's none
     */ getCommonAncestor ( nodeA , nodeB ) { while ( true ) { if ( nodeA . slot > nodeB . slot ) { if ( nodeA . parent === undefined ) { return null ; } nodeA = this . getNodeFromIndex ( nodeA . parent ) ; } else if ( nodeA . slot < nodeB . slot ) { if ( nodeB . parent === undefined ) { return null ; } nodeB = this . getNodeFromIndex ( nodeB . parent ) ; } else { if ( nodeA . blockRoot === nodeB . blockRoot ) { return nodeA ; } if ( nodeA . parent === undefined || nodeB . parent === undefined ) { return null ; } nodeA = this . getNodeFromIndex ( nodeA . parent ) ; nodeB = this . getNodeFromIndex ( nodeB . parent ) ; } } } length ( ) { return this . indices . size ; } private getNodeFromIndex ( index ) { const node = this . nodes [ index ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index } ) ; } return node ; } private getNodeByIndex ( blockIndex ) { const node = this . nodes [ blockIndex ] ; if ( node === undefined ) { return undefined ; } return node ; } private getNodesBetween ( upperIndex , lowerIndex ) { const result = [ ] ; for ( let index = upperIndex - 1 ; index > lowerIndex ; index -- ) { const node = this . nodes [ index ] ; if ( node === undefined ) { throw new ProtoArrayError ( { code : ProtoArrayErrorCode . INVALID_NODE_INDEX , index , } ) ; } result . push ( node ) ; } return result ; } }