Implement blocktree data structure

[noot]

Task summary

implement blocktree data structure which tracks the different forks of the network in a tree structure starting from a root node (genesis) and branching out. the nodes should be of type ProtocolState and each node should have only 1 parent (its parent block), but each node can have any number of children

API needed for blocktree:

/// adds a block to the blocktree. should error if the parent node isn't found in the blocktree
add_block(ProtocolState) -> Result 

/// return the list of `ProtocolState`s in between (and including) the start and end `StateHash`es
/// error if `start` or `end` aren't in the blocktree or `end`  isn't a descendant of `start`
subchain(start, end StateHash) -> Result(ProtocolStateChain)

/// this is essentially the `selectLongerChain` algorithm in spec 4.2, it returns the highest block in the tree, if there are multiple highest blocks it uses the tiebreaker logic specified
get_highest_block() -> ProtocolState

/// this returns the highest common ancestor between two nodes (ie, if b1 and b2 are on two different forks, then return the block where they forked) 
/// this can be used as input into `subchain` to get chains which can be used as input for `is_short_range` and `get_min_density`
highest_common_ancestor(b1, b2 ProtocolState) -> ProtocolState

/// this is probably not needed at the moment, but eventually we will need to prune the tree once a block has a very high probability of not being reverted
/// we can also prune a long-range fork if we deem it invalid
prune()

Specification reference

• this will be useful for chain selection, as it will help us easily track all the forks in the network in one structure: https://github.com/jspada/mina/tree/8e6558e5f698cb01f5f99a45dc097d04729f7128/docs/specs/consensus#42-select-chain

Other information and links

found this package, might be handy: https://docs.rs/crate/trees/0.4.2 or feel free to use any other tree package that implements what we need

[jspada]

Rather than root the tree from genesis, don't we want to root it to the most recent succinct state?

[jspada]

Prune should be called whenever a new block extends a chain 290 blocks beyond the (succinct) root. At this point the root is moved forward (i.e. it consumes the first block/ProtocolState from the root) and the block is pruned. AFAIK, it's assumed nothing will branch back further than 290 blocks, so this is a one-way operation (we don't need to implement "unprune"). Probably should double-check for good measure.

[jspada]

Probably also want a method for looking up a block with a given hash.

[noot]

Rather than root the tree from genesis, don't we want to root it to the most recent succinct state?

@jspada yes exactly, I just meant when we initialize the node it starts at genesis. when it syncs, the root of the blocktree will be moved along to the succint root that's 290 blocks behind the highest block like you mentioned. I don't think we'd need to unprune, as past 290 blocks the state should be considered probabilistically finalized, but we can double check.