ZIP-221: Integrate history merkle mountain range from librustzcash

[mpguerra]

Is your feature request related to a problem? Please describe.

Part of the work to implement ZIP-221 will involve integrating the history merkle mountain range (MMR) from librustzcash into Zebra.

The goal of this PR is to provide a Zebra-specific API for #2134 and #2135 with tests. (But we want to implement the state changes in #2134 and #2135 in separate PRs.)

Describe the solution you'd like

• [ ] Create a zebra_chain::primitives::zcash_history module

• [ ] Create a zebra_chain::primitives::zcash_history MMR data type:

  • use HashMap<u32, Entry>
  • update using the operations below

Make functions for:

• [ ] Creating librustzcash NodeData from a Zebra Block
  • See zebra_chain::primitives::zcash_primitives for the similar code for transactions
• [ ] Creating a new zcash_history MMR - Tree::new
• [ ] Adding a new block / block iterator - Tree::append_leaf
• [ ] Removing a block / block iterator - Tree::truncate_leaf
• [ ] Pruning old blocks before serialization - #2134
• [ ] Getting the history commitment hash - Tree::root_node().data().hash()

Write tests for:

• [ ] MMR data type serialization round-trip
  • Heartwood and Canopy activation from the BLOCKS test vectors
  • each continuous block after the activation blocks
  • also test history commitment hashes for each block

Additional context

See https://github.com/zcashfoundation/zebra/issues/2091#issuecomment-832311598 for more details

[conradoplg]

After studying the librustzcash implementation, I'm not sure what is the best approach here. I'm writing it down just to make it clearer but we can discuss it further in chat

librustzcash only provides a mechanism to create a MMR tree from a vector of MMR peaks and to add/delete nodes to it. But it is not intended to be used as a data structure to keep around.

zcash uses it like this, from what I could gather, when e.g. there is a new block to be added:

• It builds a vector of MMR peaks on the fly, reading nodes from the state (with a cache, which seems to be used most of the time)
• It then builds the MMR tree also on the fly with the help of librustzcash
• It calls librustzcash to append the new node
• It adds the new leaves returned by librustzcash to the cache. (Not sure yet when they're committed)

We could certainly use the same approach, but librustzcash will solve only part of the problem.

Therefore, we need to decide what will be our approach in order for us to proceed on this issue...

To be more concrete, regarding the tasks in the issue:

• Create a MMR data type: build it from what? A vector of MMR peaks? Directly from (cache) state?
• Adding a new block to a zcash_history MMR: (depending on the above) how to get the MMR? A cached MMR, or build it from a peak vector, or from cached state?
• etc...

[teor2345]

To be more concrete, regarding the tasks in the issue:

* Create a MMR data type: build it from what? A vector of MMR peaks? Directly from (cache) state?

* Adding a new block to a zcash_history MMR: (depending on the above) how to get the MMR? A cached MMR, or build it from a peak vector, or from cached state?

* etc...

In general, we want to do the easiest thing that lets us to #2134 and #2135. But we can definitely chat about the details.

[conradoplg]

Part of this (only the wrapper) was implemented in https://github.com/ZcashFoundation/zebra/pull/2227

Another part (keeping track of what needs to be persisted) will be implemented in a separate PR (should we split the issue too?)

[teor2345]

Part of this (only the wrapper) was implemented in #2227

👍

Another part (keeping track of what needs to be persisted) will be implemented in a separate PR (should we split the issue too?)

I moved the remaining persistent state task to #2134, which deals with the finalized state. So we can close this ticket when #2227 merges.