ZIP-221: Validate chain history commitments in the non-finalized state

[mpguerra]

Is your feature request related to a problem?

In order to implement ZIP-221 in Zebra, we will need to update our implementation of Zebra state for non-finalized chains, and validate chain history commitments in the non-finalized state.

Describe the solution you'd like

Maintaining history

• Add a history MMR data field to the Chain type
  • this stores the MMR history for each non-finalized tip
• When adding a block to a non-finalized tip:
  • update the history MMR (see ZIP-221: Validate chain history commitments in the finalized state #2134 for details)
  • add blocks using Zebra's API for Tree::append_leaf
  • prune unused entries using Zebra's pruning function
• When forking a new side-chain:
  • clone the list of MMR entries
  • rollback blocks using Zebra's API for Tree::truncate_leaf
  • add blocks using Zebra's API for Tree::append_leaf
  • prune unused entries using Zebra's pruning function

Contextual validation of non-checkpoint blocks

• Add a post-fork contextual validation function to the check module
• Call it from commit_block and commit_new_chain, right before we add the block to the chain
• Check that the history commitment from the history MMR matches the history commitment in the block header
  • if it doesn't, return a new BlockError variant

Describe alternatives you've considered

We could re-calculate each side-chain starting from the finalized tip.

We could keep the (non-finalized) leaf nodes for each non-finalized block, and share forked block state using Arc or im. However this:

• costs some RAM
• should only be done as part of a redesign that avoids rollbacks entirely

Additional context

See #2091 (comment) for further details

[teor2345]

We need the sapling tree root for this change, so testing and full implementation are blocked by the sapling part of #1287.

[teor2345]

#2396 does not actually close this ticket

[conradoplg]

#2562 ended up being similar to this

I think this one can be closed by #2609