feature: Store the full history tree for the finalized state

[Metalcape]

Motivation

Currently, only the peaks of the history tree are saved as part of the finalized state. This allows to compute the MMR tree root hash (chainhistoryroot) for the tip of the history chain only.

At the moment the only way to compute chainhistoryroot for an arbitrary block after NU5 activation is to rebuild the history tree from scratch. It might be possible to reuse some of the peaks depending on the height of the block, but in general it could be necessary to read all blocks from the network upgrade activation up to the requested one. If instead we saved all the nodes of the history tree, it would be possible to compute the tree root hash by reading only the nodes that count as peaks of the history tree at that block height.

If we store all the nodes in append order, it's possible to retrieve the subset of nodes for a given block height, and the number of leaves in the tree can be used to determine which nodes are peaks at that block height. The peaks can then used to build a new HistoryTree object and compute the root hash. Additionally, being able to read arbitrary MMR nodes is necessary to build a FlyClient proof for a given block. If this change is implemented, then it will be relatively easy to make zebrad act as a prover for the FlyClient protocol.

This may not be a breaking database change if we store the nodes as an additional column indexed by the order in which the nodes were appended to the MMR tree. Because the history tree is reset after every network upgrade, we would need one column for each upgrade. The list of nodes for the current network upgrade should be kept consistent with the existing history_tree column family and updated at the same time.

Specifications

No response

Complex Code or Requirements

No response

Testing

• Verify that the chain tip history tree peaks are consistent with the stored nodes.
• Compare the chainhistoryroot value computed from stored nodes to the one in the block header and see if they match.

Related Work

This change would allow to add chainhistoryroot to the getblock rpc response as required by #9022 without having to deserialize many blocks to compute its value.