Zebra: Implement UTXO set in `zebra-state` Service

[yaahc]

As a per-requisite for script verification we need to be able to grab the amount and scriptPubKey of transactions that are being verified. These inputs must come from the pool of unspent transactions rather than from inputs stored in the Transaction itself.

Tracking of these unspent transactions should be owned by the state service. The idea being that once zebra-consensus has validated a transaction and added it to the chain state we should apply the changes contained in the newly added transaction to the utxo set. Any money that was spent in the newly added transaction should be removed from the UTXO set and replaced with the unspent outputs of the transaction.

[teor2345]

Just a reminder: transactions in a block are verified based on the UTXO set of the parent block.

So the UTXO state must be per-block (not per-chain or global).

[yaahc]

It would in practice end up being per-chain though right? Because for each chain there's only ever the next UTXO set for the current tip that needs to be tracked, because you're only ever able to insert the very next block of that chain or start a new chain.

Actually, you could add a new chain from prior parent block couldn't you, in which case you would still need the old UTXO set still. Okay, I think I'm getting there on this one.

@teor2345 we only need to save to disk the UTXO set of the tip of the chain that we've persisted to disk right?

My tenative plan for this is to just use im to track the set for all of the blocks that are only stored in memory.

Now that I think about it I should possibly write the chain reorg and multiple chain tracking logic for zebra-state first.

[yaahc]

blocked by https://github.com/ZcashFoundation/zebra/issues/452

[yaahc]

Design per our discussions after the workshop today

• split the UTXO set representation into two parts
  
  
  
  • the collapsed representation that lives on the disk for the UTXO state up to the reorg limit
  
  
  • the delta representation of UTXO modifications for blocks that have been validated but haven't yet passed the reorg limit
  
  
• the on disk repr will likely just be another tree that lives on the disk of hash -> UTXO or w/e the mapping ends up being
• the delta will be an im set that stores the (hash, Removed|Added) mappings
• the in memory representation may be stored together with the VolatileChains and managed by the same persistence logic as described in https://github.com/ZcashFoundation/zebra/issues/452#issuecomment-662767867

[daira]

What you need is a partially persistent set or map. I wish that was the way we did it in zcashd, rather than treating it as a caching problem. (Cache invalidation is one of the "two hard problems in computer science", whereas it's comparatively easy to view it as a persistent data structure.)

In any case, relying on the reorg limit is a nice simplification for the on-disk representation.

[yaahc]

@daira the im crate provides these kinds of persistent data structures right? that's what we're planning on using, we're just not using that to store the entire UTXO set because that apparently would take 3gigs of ram

[dconnolly]

This design is covered somewhat in https://github.com/ZcashFoundation/zebra/pull/902

[dconnolly]

"In terms of what treestate we need, we 'just' need the anchor, as the nullifier set is just a set we maintain."

[teor2345]

We've implemented the UTXO set in the state service.