Parallel Verification
- Feature Name: parallel_verification
- Start Date: 2020-07-27
- Design PR: ZcashFoundation/zebra#763
- Zebra Issue: ZcashFoundation/zebra#682
Summary
Zebra verifies blocks in several stages, most of which can be executed in parallel.
We use several different design patterns to enable this parallelism:
- We download blocks and start verifying them in parallel,
- We batch signature and proof verification using verification services, and
- We defer data dependencies until just before the block is committed to the state (see the detailed design RFCs).
Motivation
Zcash (and Bitcoin) are designed to verify each block in sequence, starting from the genesis block. But during the initial sync, and when restarting with an older state, this process can be quite slow.
By deferring data dependencies, we can partially verify multiple blocks in parallel.
By parallelising block and transaction verification, we can use multithreading and batch verification for signatures, proofs, scripts, and hashes.
Definitions
Blockchain:
- chain fork: Zcash is implemented using a tree of blocks. Each block has a single previous block, and zero to many next blocks. A chain fork consists of a tip and all its previous blocks, back to the genesis block.
- genesis: The root of the tree of blocks is called the genesis block. It has no previous block.
- tip: A block which has no next block is called a tip. Each chain fork can be identified using its tip.
Data:
- consensus rule: A protocol rule which all nodes must apply consistently, so they can converge on the same chain fork.
- context-free: Consensus rules which do not have a data dependency on previous blocks.
- data dependency: Information contained in the previous block and its chain fork, which is required to verify the current block.
- state: The set of verified blocks. The state might also cache some dependent data, so that we can efficiently verify subsequent blocks.
Verification Stages:
- structural verification: Parsing raw bytes into the data structures defined by the protocol.
- semantic verification: Verifying the consensus rules on the data structures defined by the protocol.
- contextual verification: Verifying the current block, once its data dependencies have been satisfied by a verified previous block. This verification might also use the cached state corresponding to the previous block.
Guide-level explanation
In Zebra, we want to verify blocks in parallel. Some fields can be verified straight away, because they don't depend on the output of previous blocks. But other fields have data dependencies, which means that we need previous blocks before we can fully validate them.
If we delay checking some of these data dependencies, then we can do more of the verification in parallel.
Example: BlockHeight
Here's how Zebra can verify the different Block Height consensus rules in parallel:
Structural Verification:
- Parse the Block into a BlockHeader and a list of transactions.
Semantic Verification: No Data Dependencies:
- Check that the first input of the first transaction in the block is a coinbase input with a valid block height in its data field.
Semantic Verification: Deferring a Data Dependency:
- Verify other consensus rules that depend on Block Height, assuming that the Block Height is correct. For example, many consensus rules depend on the current Network Upgrade, which is determined by the Block Height. We verify these consensus rules, assuming the Block Height and Network Upgrade are correct.
Contextual Verification:
- Submit the block to the state for contextual verification. When it is ready to be committed (it may arrive before the previous block), check all deferred constraints, including the constraint that the block height of this block is one more than the block height of its parent block. If all constraints are satisfied, commit the block to the state. Otherwise, reject the block as invalid.
Zebra Design
Design Patterns
When designing changes to Zebra verification, use these design patterns:
- perform context-free verification as soon as possible, (that is, verification which has no data dependencies on previous blocks),
- defer data dependencies as long as possible, then
- check the data dependencies.
Minimise Deferred Data
Keep the data dependencies and checks as simple as possible.
For example, Zebra could defer checking both the Block Height and Network Upgrade.
But since the Network Upgrade depends on the Block Height, we only need to defer the Block Height check. Then we can use all the fields that depend on the Block Height, as if it is correct. If the final Block Height check fails, we will reject the entire block, including all the verification we performed using the assumed Network Upgrade.
Implementation Strategy
When implementing these designs, perform as much verification as possible, await any dependencies, then perform the necessary checks.
Reference-level explanation
Verification Stages
In Zebra, verification occurs in the following stages:
- Structural Verification: Raw block data is parsed into a block header and transactions. Invalid data is not representable in these structures: deserialization (parsing) can fail, but serialization always succeeds.
- Semantic Verification: Parsed block fields are verified, based on their
data dependencies:
- Context-free fields have no data dependencies, so they can be verified as needed.
- Fields with simple data dependencies defer that dependency as long as possible, so they can perform more verification in parallel. Then they await the required data, which is typically the previous block. (And potentially older blocks in its chain fork.)
- Fields with complex data dependencies require their own parallel verification designs. These designs are out of scope for this RFC.
- Contextual Verification: After a block is verified, it is added to the state. The details of state updates, and their interaction with semantic verification, are out of scope for this RFC.
This RFC focuses on Semantic Verification, and the design patterns that enable blocks to be verified in parallel.
Verification Interfaces
Verification is implemented by the following traits and services:
- Structural Verification:
zebra_chain::ZcashDeserialize
: A trait for parsing consensus-critical data structures from a byte buffer.
- Semantic Verification:
ChainVerifier
: Provides a verifier service that accepts aBlock
request, performs verification on the block, and responds with ablock::Hash
on success.- Internally, the
ChainVerifier
selects between aCheckpointVerifier
for blocks that are within the checkpoint range, and aBlockVerifier
for recent blocks.
- Contextual Verification:
zebra_state::init
: Provides the state update service, which accepts requests to add blocks to the state.
Checkpoint Verification
The CheckpointVerifier
performs rapid verification of blocks, based on a set
of hard-coded checkpoints. Each checkpoint hash can be used to verify all the
previous blocks, back to the genesis block. So Zebra can skip almost all verification for blocks in the checkpoint range.
The CheckpointVerifier
uses an internal queue to store pending blocks.
Checkpoint verification is cheap, so it is implemented using non-async
functions within the CheckpointVerifier service.
Here is how the CheckpointVerifier
implements each verification stage:
- Structural Verification:
- As Above: the
CheckpointVerifier
accepts parsedBlock
structs.
- As Above: the
- Semantic Verification:
check_height
: makes sure the block height is within the unverified checkpoint range, and adds the block to its internal queue.target_checkpoint_height
: Checks for a continuous range of blocks from the previous checkpoint to a subsequent checkpoint. If the chain is incomplete, returns a future, and waits for more blocks. If the chain is complete, assumes that theprevious_block_hash
fields of these blocks form an unbroken chain from checkpoint to checkpoint, and starts processing the checkpoint range. (This constraint is an implicit part of theCheckpointVerifier
design.)process_checkpoint_range
: makes sure that the blocks in the checkpoint range have an unbroken chain of previous block hashes.
- Contextual Verification:
- As Above: the
CheckpointVerifier
returns success to theChainVerifier
, which sends verifiedBlock
s to the state service.
- As Above: the
Block Verification
The BlockVerifier
performs detailed verification of recent blocks, in parallel.
Here is how the BlockVerifier
implements each verification stage:
- Structural Verification:
- As Above: the
BlockVerifier
accepts parsedBlock
structs.
- As Above: the
- Semantic Verification:
- As Above: verifies each field in the block. Defers any data dependencies as long as possible, awaits those data dependencies, then performs data dependent checks.
- Note: Since futures are executed concurrently, we can use the same function
to:
- perform context-free verification,
- perform verification with deferred data dependencies,
- await data dependencies, and
- check data dependencies. To maximise concurrency, we should write verification functions in this specific order, so the awaits are as late as possible.
- Contextual Verification:
- As Above: the
BlockVerifier
returns success to theChainVerifier
, which sends verifiedBlock
s to the state service.
- As Above: the
Zcash Protocol Design
When designing a change to the Zcash protocol, minimise the data dependencies between blocks.
Try to create designs that:
- Eliminate data dependencies,
- Make the changes depend on a version field in the block header or transaction,
- Make the changes depend on the current Network Upgrade, or
- Make the changes depend on a field in the current block, with an additional consensus rule to check that field against previous blocks.
When making decisions about these design tradeoffs, consider:
- how the data dependency could be deferred, and
- the CPU cost of the verification - if it is trivial, then it does not matter if the verification is parallelised.
Drawbacks
This design is a bit complicated, but we think it's necessary to achieve our goals.
Rationale and alternatives
- What makes this design a good design?
- It enables a significant amount of parallelism
- It is simpler than some other alternatives
- It uses existing Rust language facilities, mainly Futures and await/async
- Is this design a good basis for later designs or implementations?
- We have built a UTXO design on this design
- We believe we can build "recent blocks" and "chain summary" designs on this design
- Each specific detailed design will need to consider how the relevant data dependencies are persisted
- What other designs have been considered and what is the rationale for not choosing them?
- Serial verification
- Effectively single-threaded
- Awaiting data dependencies as soon as they are needed
- Less parallelism
- Providing direct access to the state
- Might cause data races, might be prevented by Rust's ownership rules
- Higher risk of bugs
- Serial verification
- What is the impact of not doing this?
- Verification is slow, we can't batch or parallelise some parts of the verification
Prior art
TODO: expand this section
- zcashd
- serial block verification
- Zebra implements the same consensus rules, but a different design
- tower
Unresolved questions
- Is this design good enough to use as a framework for future RFCs?
-
Does this design require any changes to the current implementation?
- Implement block height consensus rule (check previous block hash and height)
-
Check that the
BlockVerifier
performs checks in the following order:- verification, deferring dependencies as needed,
- await dependencies,
- check deferred data dependencies
Out of Scope:
-
What is the most efficient design for parallel verification?
- (Optimisations are out of scope.)
-
How is each specific field verified?
-
How do we verify fields with complex data dependencies?
-
How does verification change with different network upgrades?
-
How do multiple chains work, in detail?
-
How do state updates work, in detail?
-
Moving the verifiers into the state service
Future possibilities
- Separate RFCs for other data dependencies
- Recent blocks
- Overall chain summaries (for example, total work)
- Reorganisation limit: multiple chains to single chain transition
- Optimisations for parallel verification