Zebra: Tracking: transaction validation

[dconnolly]

Tracking issue for transaction validation. Transaction validation checks should be implemented as a sequence of stateless checks that generate constraints if successful (semantic validation); these constraints are then checked as part of contextual verification when a block is being committed to the state.

See also #428 which tracks block validation.

• [ ] Tree state management
  
  
  
  • [x] Note types (Sprout+Sapling #275)
  
  
  • [ ] Nullifier set (Sprout+Sapling #289) -- design: https://github.com/ZcashFoundation/zebra/pull/983 (basically handled by the state layer)
  
  
  • [ ] Note commitment tree (Sprout #36, Sapling #286) -- design: https://github.com/ZcashFoundation/zebra/pull/983
  
  
• [ ] Bitcoin Script #180
  
  
  
  • [x] FFI to C++ script implementation #622
  
  
  • [x] Create zebra-script interface to FFI crate with zebra-chain types #708
  
  
  • [x] Ensure C++ implementation is threadsafe #869
  
  
  • [x] Async script verification design #868
  
  
  • [ ] Async script verification implementation -- issues to be created after #868
  
  
  • [x] UTXO set implementation #724 (subsumed by state design)
  
  
  • [x] SIGHASH #306 #870
  
  

• [ ] Transaction verifier service: https://github.com/ZcashFoundation/zebra/pull/1100

  • [ ] Look up our computed anchors/roots in the finalized state (see #983)
  • [ ] Batch dispatch Spend, Output, and JoinSplit proof statement verifiers
  • [ ] Depends on Groth16 validation service - #305, maybe #406, #830
  • [ ] For JoinSplits, they may refer to a previous JoinSplit in this transaction, so intermediate treestates need to be computed (see #983)
  • [ ] Validate signatures
  • [ ] Ed25519, including : https://github.com/ZcashFoundation/zebra/issues/1565
  • [ ] RedJubjub
  • [ ] check that modified signatures and modified data don't pass validation
  • [ ] ??? [we need to fill out the rest of the list of checks here, probably by walking through zcashd for block validation, we've walked through transaction validation]

• [ ] Other consensus rules ??? - https://github.com/ZcashFoundation/zebra/issues?q=is%3Aissue++label%3Aconsensus+

  • [ ] Coinbase, Founders Reward, and Dev Fund #801
  • [ ] sapling value balance is zero in v4 transactions with no spends or outputs
  • [ ] a transaction's expiry height must be greater than or equal to its block height
• [ ] Call transaction validation from BlockVerifier

[hdevalence]

We need #180; adding it to the list.

[hdevalence]

Some notes on what our verification architecture could look like below. First, some general desiderata:

• Verification should maximize batching to the greatest extent possible.
• Verification should maximize parallelism to the greatest extent possible.
• Contextual verification (involving chain state) should be separated from semantic verification (e.g., checking proofs) as much as possible.
• Verification should happen before we commit any state updates, so we never persist unverified data.
• We need to have a mandatory checkpointing mechanism that reaches from genesis to Sapling activation, because we won't (initially) support BCTV14 verification.
• Since we need a checkpointing mechanism anyways, it would be good if it were extensible beyond Sapling activation.

Here's a sketch of how we could try to accomplish this. At a high level, we keep all verification logic inside of zebra-consensus, and implement each type of verification as a tower::Service. Then in zebra-chain we have aggregations of data to be verified (blocks aggregate transactions, which aggregate various signatures and proofs, etc.), and in zebra-consensus we have aggregations of verifier Services (a block verifier has a transaction verifier, which has verifiers for various signatures and proofs, etc.).

This lets us do pervasive batching using the strategy in the blog post, and importantly, it allows us to have one implementation independent of the batch size. As an example, consider a version 4 (Sapling) transaction, which can have multiple SpendDescriptions and OutputDescriptions, each with their own Groth16Proof. Depending on the context, multiple levels of batching are possible:

1. we can batch all proofs in a single transaction (e.g., when getting a mempool entry);
2. we can batch all proofs in all transactions in a single block (e.g., when getting a new block);
3. we can batch all proofs in all transactions in many blocks (e.g., when verifying the chain).

Suppose we have a Groth16Verifier: Service performing batch verification, with a similar API as ed25519_zebra::batch, and that the TransactionVerifier: Service aggregates Services for each component (Groth16Verifier, RedJubjubVerifier, etc). Now, if the verification services for the components are passed into the TransactionVerifier constructor, we can get each of these levels of batching with a single verification codepath, by constructing the verification services at the highest level of batching and passing them down through various constructors.

This handles batching. To handle parallelism, we probably want to ensure that as much of the work as possible is in the response future itself, rather than in the call impl, and lean on task spawning to have the runtime drive execution of futures in parallel. We will also need to be careful to spawn blocking work appropriately to not block the runtime.

I think that the futures-based approach could also work well for handling checkpointing, with the caveat that we may need to have many intermediate checkpoints. When doing checkpointing, we have an externally-trusted (h, hash): (BlockHeight, BlockHeaderHash) pair, and the chain is valid up to the checkpoint if the block at height h has hash hash (implying that all previous blocks were valid). This is structurally quite similar to batch verification, but with less work involved. Using futures allows us to avoid maintaining intermediate unverified data by having a CheckpointVerifier whose response futures resolve when the checkpoint is reached. However, this means keeping all of the blocks up to the checkpoint in memory as futures, so we would need to ship a list of checkpoints, say every 500 or 1000 blocks or so.

A nice upside of this approach would be that we could optionally extend it past Sapling activation. This would involve having a hardcoded list of "mandatory" checkpoints (up to Sapling activation), and a way to configure a file or something with other checkpoints. To me this is P-Lo but would be relatively little extra work when we got around to it.

[hdevalence]

I think those ideas touch on most of the desiderata, except:

Contextual verification (involving chain state) should be separated from semantic verification (e.g., checking proofs) as much as possible.

I think there are two next steps:

1. Write down explicitly all of the chain state required to validate transactions. That description could be a starting point for a Request/Response API for the zebra-storage API #136.

2. Go through the protocol spec and write down explicitly a complete list of all of the verification checks we need to do (filling out the checklist above). These could then turn into verification services in zebra-consensus.

WDYT @dconnolly @gtank ?

[dconnolly]

Basically this will be complete when https://github.com/ZcashFoundation/zebra/milestone/2 is complete.

[teor2345]

Contextual verification (involving chain state) should be separated from semantic verification (e.g., checking proofs) as much as possible.

I think there are two next steps:

1. Write down explicitly all of the chain state required to validate transactions.  That description could be a starting point for a `Request`/`Response` API for the `zebra-storage` API #136.

2. Go through the protocol spec and write down explicitly a complete list of all of the verification checks we need to do (filling out the checklist above).  These could then turn into verification services in `zebra-consensus`.

I think there are a few different levels of context:

• semantic verification - no context
• network verification - only needs to know the network
  
  
  
  • for example: checking the embedded network type in the address
  
  
• transaction set verification - needs to know the other transactions in the block or state
  
  
  
  • for example: double-spend checks
  
  
• full contextual verification - needs to know the whole chain state
  
  
  
  • for example, full block validation
  
  

I'll see how I go with splitting checks into these categories in #428.

[hdevalence]

I think this might have been closed by mistake (cc @dconnolly )? (Please feel free to re-close if it wasn't)

[dconnolly]

OOF very mistake, my bad