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

  • Note types (Sprout+Sapling Type out Sprout and Sapling Notes #275)
  • Nullifier set (Sprout+Sapling Nullifier Set #289) -- design: Draft RFC: Treestate management #983 (basically handled by the state layer)
  • Note commitment tree (Sprout Design Sprout note commitment trees. #36, Sapling Implement Sapling note commitment tree #286) -- design: Draft RFC: Treestate management #983

• Bitcoin Script Zcash-compatible Bitcoin script impl #180

  • FFI to C++ script implementation Wrap and re-export zcashconsensus as a rust crate #622
  • Create zebra-script interface to FFI crate with zebra-chain types Make zebra-script wrap the C++ script implementation in zcashconsensus #708
  • Ensure C++ implementation is threadsafe Check that C++ script implementation is threadsafe. #869
  • Async script verification design Add async script RFC #868
  • Async script verification implementation -- issues to be created after Add async script RFC #868
  • UTXO set implementation Implement UTXO set in zebra-state Service #724 (subsumed by state design)
  • SIGHASH Pull in/tidy up SIGHASH  #306 Implement sighash #870

• Transaction verifier service: [WIP] Transaction verifier #1100

  • Look up our computed anchors/roots in the finalized state (see Draft RFC: Treestate management #983)
  • Batch dispatch Spend, Output, and JoinSplit proof statement verifiers
    • Depends on Groth16 validation service - Implement verifiers that accept Groth16 types #305, maybe Implement Groth16 batch verification optimizations #406, Asynchronous Groth16 verification #830
    • For JoinSplits, they may refer to a previous JoinSplit in this transaction, so intermediate treestates need to be computed (see Draft RFC: Treestate management #983)
  • Validate signatures
    • Ed25519, including : Enable ZIP-215: Ed25519 Validation Rules #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 Tracking Issue: Validate coinbase transactions, including the 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 Tracking: State management service. #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

[mpguerra]

Closing this epic as I think we're pretty much done here