Stop double-spends by checking nullifiers in the finalized state

[teor2345]

Motivation

Zebra needs to check the double-spend consensus rule for shielded spends in the finalized state.

Consensus Rule

Nullifiers

A nullifier MUST NOT repeat either within a transaction, or across transactions in a valid blockchain. Sprout and Sapling and Orchard nullifiers are considered disjoint, even if they have the same bit pattern.

https://zips.z.cash/protocol/nu5.pdf#nullifierset

A transaction is not valid if it would have added a nullifier to the nullifier set that already exists in the set

https://zips.z.cash/protocol/nu5.pdf#commitmentsandnullifiers

Existing Design

pub(super) fn queue_and_commit_finalized_blocks(&mut self, queued_block: QueuedBlock)
...
Iterate over the enumerated transactions in the block. For each transaction:
...
For each JoinSplit description in the transaction, insert (nullifiers[0],()) and (nullifiers[1],()) into sprout_nullifiers.
For each Spend description in the transaction, insert (nullifier,()) into sapling_nullifiers.
For each Orchard description in the transaction, insert (nullifier,()) into orchard_nullifiers.

https://github.com/ZcashFoundation/zebra/blob/main/book/src/dev/rfcs/0005-state-updates.md#pubsuper-fn-queue_and_commit_finalized_blocksmut-self-queued_block-queuedblock

Solution

Design Change

• Inserts into RocksDB column families should return an error if the key already exists.

This design change enforces the double-spend rules for each shielded pool.

It also enforces single writes of the other 8 column families in the data structure (as of 1 June 2021):
https://github.com/ZcashFoundation/zebra/blob/main/book/src/dev/rfcs/0005-state-updates.md#rocksdb-data-structures

Implementation Change

• Make sure the existing batch write code propagates errors to the validator
• Make sure duplicate spends of UTXOs are rejected by the finalized state
• Implement a RocksDB merge operator that rejects overwriting existing values
  • https://docs.rs/rocksdb/0.16.0/rocksdb/merge_operator/index.html
  • This is a C callback, so we can't panic in this function.
• Apply it to every column family in FinalizedState::new using set_merge_operator_associative
  • https://docs.rs/rocksdb/0.16.0/rocksdb/struct.Options.html#method.set_merge_operator_associative
• Generate useful error messages

Here's the RocksDB merge feature documentation:
https://github.com/facebook/rocksdb/wiki/Merge-Operator#what

Testing

• Test that duplicate sprout, sapling, and orchard nullifiers are rejected by the finalized state
• Test that duplicate spends of UTXOs are rejected by the finalized state

Optional:

• Proptest the merge operator function

Alternatives

We could try to fetch each value before writing it, but that's error-prone. We'd probably forget to do the check somewhere in the code.

[teor2345]

This ticket is blocked by #2301, because they both want to return errors from the UpdateWith trait.

[teor2345]

This ticket is actually a duplicate of #2231 - if we check for duplicates when adding a block to a non-finalized chain, we don't need to check again in the finalized state.