Audit: A Closer Look at Zebra’s Finalized State

[mpguerra]

This note is mainly a discussion around zebra-state’s handling of finalized block state. The Zebrad application’s start command spawns the Syncer service which will continuously request chain tips and blocks from the peers until it downloads and verifies enough history of the chain to be able to validate blocks. It obtains some prospective tips and iteratively tries to extend them and download the missing blocks. In the snippet below, the Syncer’s download_and_verify() function rejects blocks that are more than MAX_BLOCK_REORG_HEIGHT (99) blocks from the tip height:

zebra/zebrad/src/components/sync/downloads.rs

Lines 364 to 377 in 5a88fe7

	// Get the finalized tip height, assuming we're using the non-finalized state.
	//
	// It doesn't matter if we're a few blocks off here, because blocks this low
	// are part of a fork with much less work. So they would be rejected anyway.
	//
	// And if we're still checkpointing, the checkpointer will reject blocks behind
	// the finalized tip anyway.
	//
	// TODO: get the actual finalized tip height
	let min_accepted_height = tip_height
	.map(|tip_height| {
	block::Height(tip_height.0.saturating_sub(zs::MAX_BLOCK_REORG_HEIGHT))
	})
	.unwrap_or(block::Height(0));

Then the Syncer uses a clone of the ChainVerifier to verify the newly downloaded block, which for blocks below the latest configured checkpoint height will use the CheckpointVerifier instead of full block verification. The CheckpointVerifier will not process blocks beyond the target checkpoint until it receives all the required blocks that it needs in order to be able to verify the blocks that chain back to the previous checkpoint. In the snippet below, the CheckpointVerifier uses the state service to contextually verify the block and commit it to the finalized state:

zebra/zebra-consensus/src/checkpoint.rs

Lines 980 to 1002 in 5a88fe7

	let state_service = self.state_service.clone();
	let commit_finalized_block = tokio::spawn(async move {
	let hash = req_block
	.rx
	.await
	.map_err(Into::into)
	.map_err(VerifyCheckpointError::CommitFinalized)
	.expect("CheckpointVerifier does not leave dangling receivers")?;
	// We use a `ServiceExt::oneshot`, so that every state service
	// `poll_ready` has a corresponding `call`. See #1593.
	match state_service
	.oneshot(zs::Request::CommitFinalizedBlock(req_block.block))
	.map_err(VerifyCheckpointError::CommitFinalized)
	.await?
	{
	zs::Response::Committed(committed_hash) => {
	assert_eq!(committed_hash, hash, "state must commit correct hash");
	Ok(hash)
	}
	_ => unreachable!("wrong response for CommitFinalizedBlock"),
	}
	});

Note that a checkpointed/finalized block can be a settled network upgrade or a block beyond the rollback/reorg limit. The state service processes the finalized block and queues it to be committed to state (finalized blocks can be optionally saved to disk.). The state service will not commit any non-finalized blocks until the finalized blocks’ queue is fully drained and committed:

zebra/zebra-state/src/service.rs

Lines 639 to 662 in 5a88fe7

	// We've finished sending finalized blocks when:
	// - we've sent the finalized block for the last checkpoint, and
	// - it has been successfully written to disk.
	//
	// We detect the last checkpoint by looking for non-finalized blocks
	// that are a child of the last block we sent.
	//
	// TODO: configure the state with the last checkpoint hash instead?
	if self.finalized_block_write_sender.is_some()
	&& self
	.queued_non_finalized_blocks
	.has_queued_children(self.last_sent_finalized_block_hash)
	&& self.read_service.db.finalized_tip_hash() == self.last_sent_finalized_block_hash
	{
	// Tell the block write task to stop committing finalized blocks,
	// and move on to committing non-finalized blocks.
	std::mem::drop(self.finalized_block_write_sender.take());
	// We've finished committing finalized blocks, so drop any repeated queued blocks.
	self.clear_finalized_block_queue(
	"already finished committing finalized blocks: dropped duplicate block, \
	block is already committed to the state",
	);
	}

Once the finalized block writer is finished, the state service will validate and commit the non-finalized queued blocks whose parents have recently arrived in breadth-first ordering (lowest to highest heights). Thus, when validate_and_commit_non_finalized() calls the check::initial_contextual_validity() for the first time there are some finalized blocks in the state to be used to validate the block’s difficulty threshold and timestamp. The assert_eq!() check below expects at least 28 blocks in the relevant chain:

zebra/zebra-state/src/service/check.rs

Lines 85 to 97 in 5a88fe7

	// skip this check during tests if we don't have enough blocks in the chain
	#[cfg(test)]
	if relevant_chain.len() < POW_AVERAGING_WINDOW + POW_MEDIAN_BLOCK_SPAN {
	return Ok(());
	}
	// process_queued also checks the chain length, so we can skip this assertion during testing
	// (tests that want to check this code should use the correct number of blocks)
	assert_eq!(
	relevant_chain.len(),
	POW_AVERAGING_WINDOW + POW_MEDIAN_BLOCK_SPAN,
	"state must contain enough blocks to do proof of work contextual validation, \
	and validation must receive the exact number of required blocks"
	);

For the first non-finalized block to be validated there must be at least 28 blocks in the finalized state. If an honest node fails to obtain enough finalized blocks from its peers during syncing, an attacker could send it a non-finalized block to verify, which will fail this assertion and crash the Zebra node.

A relevant issue (“On startup, check that the finalized state blocks match the checkpoint
hashes”) was fixed by the maintainers after the audit branch was cut. It ensures that, on startup, the Zebrad node would not indefinitely follow a forked chain that does not include the socially accepted checkpoints.

[teor2345]

How do we want to resolve the auditors concerns about checkpoint vs full verification syncing?

It might help to change the state request names (and related functions, variables, comments) to something like:

• CommitFinalizedBlock: CommitCheckpoint(Verified)Block, CommitContextuallyVerifiedBlock, CommitBlock(Direct)ToFinalizedState, ...
• CommitBlock: CommitFullVerifiedBlock, CommitSemanticallyVerifiedBlock, CommitBlockToNonFinalizedState, ...

Anyone have better names? Which names do you prefer?
(It seems like the auditors would have found names with "Checkpoint" and "SemanticallyVerified" easier.)

Is there anything else we could do to make this code clearer?
Which documentation should we update?

[teor2345]

Relatedly, should the Block types be renamed to match? Like SemanticallyVerifiedBlock, ContextuallyVerifiedBlock,

That's a good system design principle: name things after what they are, rather than what they do at the moment, or what they contain right now. Because what things do or contain changes over time.

I think naming those types based on "what they are" would help a lot. We already have a ContextuallyVerifiedBlock, so it would help to have a CheckpointVerifiedBlock and SemanticallyVerifiedBlock.

Did you want to make a list?

or enum variants of a Block ? Less pressing bit might align our language

We use wrapper types at the moment, rather than enum variants. Switching to enums would be a much more significant design change than renaming existing types, so we would need a stronger justification.

[dconnolly]

We use wrapper types at the moment, rather than enum variants. Switching to enums would be a much more significant design change than renaming existing types, so we would need a stronger justification.

Agreed

[arya2]

Maybe enum variant wrappers?

Request::Commit(
  BlockVerification::Checkpoint(FinalizedBlock) 
  | BlockVerification::Semantic(PreparedBlock)
)

Which documentation should we update?

We should leave some of your explanation below to the queue_and_commit_* methods and Request::{CommitFinalizedBlock, CommitBlock} variants.

[teor2345]

Maybe enum variant wrappers?

Request::Commit(
  BlockVerification::Checkpoint(FinalizedBlock) 
  | BlockVerification::Semantic(PreparedBlock)
)

That seems low-risk but also possibly an optional change?
Since it's more than a rename, I'd like to do it in a separate PR after the renames, so that it's easier to review.

[teor2345]

Here's a list of the renames we could do, feel free to edit it:

Add to docs:

• The difference between a CheckpointVerifiedBlock and a ContextuallyVerifiedBlock is that the CheckpointVerifier doesn't bind the transaction authorizing data to the ChainHistoryBlockTxAuthCommitmentHash, but the NonFinalizedState and FinalizedState do.

zebra-consensus:

• BlockVerifier -> SemanticBlockVerifier
• ChainVerifier -> BlockVerifierRouter

The CheckpointVerifier doesn't need to be renamed.

zebra-state:

SemanticBlockVerifier Request:

• CommitBlock(PreparedBlock) -> CommitSemanticallyVerifiedBlock(SemanticallyVerifiedBlock)
• PreparedBlock -> SemanticallyVerifiedBlock
• any variables, functions, methods, and documentation that mentions non_finalized where it should say semantically_verified (mainly in service.rs, queued_blocks.rs, request.rs, and response.rs)

CheckpointBlockVerifier Request:

• CommitFinalizedBlock(FinalizedBlock) -> CommitCheckpointVerifiedBlock(CheckpointVerifiedBlock)
• FinalizedBlock -> CheckpointVerifiedBlock
• any variables, functions, methods, and documentation that mentions finalized where it should say checkpoint_verified (mainly in service.rs, queued_blocks.rs, request.rs, and response.rs)

Used inside the NonFinalizedState:

• ContextuallyValidBlock -> ContextuallyVerifiedBlock
• FinalizedWithTrees -> ContextuallyVerifiedBlockWithTrees
• any variables, functions, methods, and documentation that mentions finalized where it should say contextually_verified (mainly FinalizedState::commit_finalized_direct() and callers)

I usually use fastmod then cargo fmt --all to do renames, but any search and replace tool should make it pretty easy.

[teor2345]

Here is some of the confusion in this auditor note that we should resolve in our documentation:

Note that a checkpointed/finalized block can be a settled network upgrade or a block beyond the rollback/reorg limit. The state service processes the finalized block and queues it to be committed to state

This is the core of the confusion:

• a settled network upgrade is specified as a network upgrade that has "social consensus": it has enough confirmations on enough nodes that it can't be rolled back
• checkpointed blocks are a Zebra implementation detail: every release, we generate checkpoints for all finalized blocks in the chain, because those blocks can't be rolled back by Zebra, and are very unlikely to be be rolled back by zcashd. This includes settled network upgrades, but it also goes beyond them to include almost all settled blocks.
• finalized blocks can come from checkpoints, or from a contextually verified block which is beyond the rollback limit
• the state service processes:
  • checkpoint verified blocks direct to the finalized state
  • contextually verified blocks into the non-finalized state, and then into the finalized state once they reach the rollback limit (or if they are on a side chain that will never be committed to the finalized state, they get dropped)

(finalized blocks can be optionally saved to disk.)

All valid finalized blocks are saved to disk, that's what finalization means in Zebra. Saving to disk is not under user control, and it's not a choice the application makes automatically dynamically. The only thing that can stop a finalized block being saved to disk is invalid data, which causes a verification failure in the block commitment, authorization, or chain history roots.

Non-finalized blocks are saved to disk if they are part of the best chain, and beyond the rollback limit. If they are not part of the best chain and beyond the rollback limit, they are dropped.

the state service will validate and commit the non-finalized queued blocks whose parents have recently arrived

To do contextual validation, the state service will:

• queue blocks whose ancestors have not arrived in the state yet
• send queued blocks to the block write task after all their ancestors have been sent
• validate blocks as they arrive in the block write task, as long as their ancestors were valid
• commit valid blocks to the non-finalized state

Breadth-first order is not guaranteed, because a lower height block from another fork can arrive at any time. Forks are allowed from the finalized tip, and any non-finalized block.

For the first non-finalized block to be validated there must be at least 28 blocks in the finalized state.

The 28 most recent ancestor blocks must have been validated and committed by the state, regardless of whether they are finalized or non-finalized.

If an honest node fails to obtain enough finalized blocks from its peers during syncing, an attacker could send it a non-finalized block to verify, which will fail this assertion and crash the Zebra node.

This is incorrect, due to the confusion above.

Verification Order

The Zebra implementation chooses to verify blocks using checkpoints or semantic/contextual verification, based on their heights and its checkpoints. Checkpoint verification happens in strict height order, in both zebra-consensus and zebra-state. There is only one chain fork when checkpointing.

Semantic verification happens in parallel in the zebra-consensus verifiers, but contextual verification happens in chain order in zebra-state. Each chain fork is verified in height order, different forks can have different tip heights. (Different chain forks could also be contextually verified in parallel, but Zebra doesn't implement that.)

Guaranteed Chain Context

So blocks are not validated by the state until all their ancestors have been validated. If a contextually verified block's ancestors aren't validated, it will wait in the queue and timeout, or be rejected with an error when it is received by the block write task. So validate_and_commit_non_finalized() won't be called unless a block has at least 28 ancestors, because it is only called during contextual validation. And before contextual validation starts, Zebra commits at least 1 million blocks using checkpoints.

No Cross-Module Dependencies

In most cases, the syncer or gossip downloaders will reject blocks that are too far in front of the tip. This prevents CPU and memory denial of service. But peers can't make Zebra panic by submitting blocks out of order, even if they convince these services to submit those blocks by the state. If that happens, the state will timeout or reject the block.

[teor2345]

(finalized blocks can be optionally saved to disk.)

All valid finalized blocks are saved to disk, that's what finalization means in Zebra. Saving to disk is not under user control, and it's not a choice the application makes automatically dynamically.

There's also some potential user confusion here between:

• thin clients: programs that don't download or store the whole chain, and skip some validation
• full nodes: programs that download the whole chain, fully validate it, and store it

We've had multiple requests for Zebra to become a thin client, so it's important for us to avoid confusion in our user documentation.

The ephemeral config only controls state cleanup behaviour, it doesn't impact block validation or storage. Regardless of its setting, Zebra still functions correctly as a fully validating node. (It just doesn't have a cache when it next starts up, which is an entirely valid state.)

[mpguerra]

@arya2 @upbqdn and @oxarbitrage any thoughts on this discussion? :)

[arya2]

Looks like a naming issue but it could use better documentation too.

On a tangent, I wonder about adjusting the lookahead limit so that it keeps downloading blocks if what's cached above the tip is below a size constraint? (i.e. keep increasing the lookahead multiplier until it hits a size limit.)

[teor2345]

On a tangent, I wonder about adjusting the lookahead limit so that it keeps downloading blocks if what's cached above the tip is below a size constraint? (i.e. keep increasing the lookahead multiplier until it hits a size limit.)

Increasing the lookahead limit could be good for performance, but since those blocks are completely unverified (except for checking their heights), it could also allow peers to fill up our verify queue with hundreds of thousands of tiny invalid blocks. That could stop or delay larger valid blocks from being downloaded. (We've seen this happen before, the entire pipeline stalls for 5-10 minutes until those blocks time out.)

This seems like an unnecessary risk, unless it solves a specific serious bug?

[mpguerra]

The audit is over and all fixes have been implemented