Stop double-spends by checking nullifiers and UTXO spends in each non-finalized chain

[teor2345]

Motivation

Zebra needs to check the double-spend consensus rule for shielded and transparent inputs, in each non-finalized chain.

Consensus Rules

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

A note can change from being unspent to spent as a node’s view of the best valid block chain is extended by new transactions. Also, block chain reorganizations can cause a node to switch to a different best valid block chain that does not contain the transaction in which a note was output

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

Note: reorganizations can also change the best chain to one where a note was spent

UTXO spends

Validation state associated with transparent inputs and outputs, such as the UTXO (Unspent Transaction Output) set, is not described in this document; it is used in essentially the same way as in Bitcoin.

https://zips.z.cash/protocol/protocol.pdf#transactions

each output of a particular transaction can only be used as an input once in the block chain.
Any subsequent reference is a forbidden double spend - an attempt to spend the same satoshis twice.

https://developer.bitcoin.org/devguide/block_chain.html#introduction

Any input within this block can spend an output which also appears in this block (assuming the spend is otherwise valid).
However, the TXID corresponding to the output must be placed at some point before the TXID corresponding to the input.
This ensures that any program parsing block chain transactions linearly will encounter each output before it is used as an input.

https://developer.bitcoin.org/reference/block_chain.html#merkle-trees

Existing Design

pub fn push(&mut self, block: Arc<Block>)
...
Add nullifiers to the appropriate self.<version>_nullifiers

https://github.com/ZcashFoundation/zebra/blob/main/book/src/dev/rfcs/0005-state-updates.md#pub-fn-pushmut-self-block-arcblock

Solution

Design Change

• Inserts into Chain.<version>_nullifiers should return an error if the key already exists
• Before adding a block to a non-finalized chain, check that its nullifiers are not in the finalized state

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

• Check transparent spends against previous transactions in the block, the relevant non-finalized chain, and the finalized state

Testing

• Test that duplicate sprout, sapling, and orchard nullifiers are rejected by the non-finalized state
• Test that duplicate transparent UTXOs are rejected by the non-finalized state

Alternatives

This is a required consensus rule. There aren't really any alternatives to returning an error here.

[teor2345]

This ticket is blocked by #2417, because they both modify similar code in the Chain struct and functions.

#2417 returns errors when blocks are added to a chain. But I'm not sure if this ticket will error during pre-commit or the actual commit. So there might also be a merge conflict there.

[teor2345]

This got accidentally closed by #2504.