Merkle Verifier
This section covers the verification component of the Merkle commitment scheme. The following struct implements the verifier of the Merkle commitment scheme.
pub struct MerkleVerifier<H: MerkleHasher> {
pub root: H::Hash,
pub column_log_sizes: Vec<u32>,
pub n_columns_per_log_size: BTreeMap<u32, usize>,
}
The struct elements are defined as follows:
root: root hash of the Merkle tree committing to column datacolumn_log_sizes: a vector containing log size values of all the columnsn_columns_per_log_size: a map that associates each column log size with the number of columns of that size
Verifying the decommitment
The verify function is the main function defined for the MerkleVerifier. It takes the following input:
queries_per_log_size: A map from log size to a vector of query indices for columns of that size.queried_values: The queried column values, which is one of the outputs of thedecommitfunction.decommitment:MerkleDecommitmentcontaining thehash_witnessandcolumn_witnessrequired to check inclusion of thequeried_valuesin the Merkle tree. This is also one of the outputs of thedecommitfunction.
Below is the complete implementation of the verify function:
pub fn verify(
&self,
queries_per_log_size: &BTreeMap<u32, Vec<usize>>,
queried_values: Vec<BaseField>,
decommitment: MerkleDecommitment<H>,
) -> Result<(), MerkleVerificationError> {
let Some(max_log_size) = self.column_log_sizes.iter().max() else {
return Ok(());
};
let mut queried_values = queried_values.into_iter();
// Prepare read buffers.
let mut hash_witness = decommitment.hash_witness.into_iter();
let mut column_witness = decommitment.column_witness.into_iter();
let mut last_layer_hashes: Option<Vec<(usize, H::Hash)>> = None;
for layer_log_size in (0..=*max_log_size).rev() {
let n_columns_in_layer = *self
.n_columns_per_log_size
.get(&layer_log_size)
.unwrap_or(&0);
// Prepare write buffer for queries to the current layer. This will propagate to the
// next layer.
let mut layer_total_queries = vec![];
// Queries to this layer come from queried node in the previous layer and queried
// columns in this one.
let mut prev_layer_queries = last_layer_hashes
.iter()
.flatten()
.map(|(q, _)| *q)
.collect_vec()
.into_iter()
.peekable();
let mut prev_layer_hashes = last_layer_hashes.as_ref().map(|x| x.iter().peekable());
let mut layer_column_queries =
option_flatten_peekable(queries_per_log_size.get(&layer_log_size));
// Merge previous layer queries and column queries.
while let Some(node_index) =
next_decommitment_node(&mut prev_layer_queries, &mut layer_column_queries)
{
prev_layer_queries
.peek_take_while(|q| q / 2 == node_index)
.for_each(drop);
let node_hashes = prev_layer_hashes
.as_mut()
.map(|prev_layer_hashes| {
{
// If the left child was not computed, read it from the witness.
let left_hash = prev_layer_hashes
.next_if(|(index, _)| *index == 2 * node_index)
.map(|(_, hash)| Ok(*hash))
.unwrap_or_else(|| {
hash_witness
.next()
.ok_or(MerkleVerificationError::WitnessTooShort)
})?;
// If the right child was not computed, read it to from the witness.
let right_hash = prev_layer_hashes
.next_if(|(index, _)| *index == 2 * node_index + 1)
.map(|(_, hash)| Ok(*hash))
.unwrap_or_else(|| {
hash_witness
.next()
.ok_or(MerkleVerificationError::WitnessTooShort)
})?;
Ok((left_hash, right_hash))
}
})
.transpose()?;
// If the column values were queried, read them from `queried_value`.
let (err, node_values_iter) = match layer_column_queries.next_if_eq(&node_index) {
Some(_) => (
MerkleVerificationError::TooFewQueriedValues,
&mut queried_values,
),
// Otherwise, read them from the witness.
None => (
MerkleVerificationError::WitnessTooShort,
&mut column_witness,
),
};
let node_values = node_values_iter.take(n_columns_in_layer).collect_vec();
if node_values.len() != n_columns_in_layer {
return Err(err);
}
layer_total_queries.push((node_index, H::hash_node(node_hashes, &node_values)));
}
last_layer_hashes = Some(layer_total_queries);
}
// Check that all witnesses and values have been consumed.
if hash_witness.next().is_some() {
return Err(MerkleVerificationError::WitnessTooLong);
}
if queried_values.next().is_some() {
return Err(MerkleVerificationError::TooManyQueriedValues);
}
if column_witness.next().is_some() {
return Err(MerkleVerificationError::WitnessTooLong);
}
let [(_, computed_root)] = last_layer_hashes.unwrap().try_into().unwrap();
if computed_root != self.root {
return Err(MerkleVerificationError::RootMismatch);
}
Ok(())
}
Let's break down the function step by step:
-
Initialize Variables:
- Convert
queried_valuesinto an iterator for consumption during verification. - Create iterators for
hash_witnessandcolumn_witnessfrom thedecommitment. - Initialize
last_layer_hashesto track computed hashes from the previous layer.
- Convert
-
Layer-by-Layer Verification:
- For each layer (from largest to smallest):
- Get the number of columns in the current layer (
n_columns_in_layer) from the mapn_columns_per_log_size. - Prepare iterators for previous layer queries (
prev_layer_queries), previous layer hashes (prev_layer_hashes) and current layer column queries (layer_column_queries). - For each node index:
- Reconstruct
node_hashes: Use computed hashes from theprev_layer_hashesor read missing sibling hashes fromhash_witness. - Get Node Values: If the node is queried, read column values from
queried_values; otherwise, read fromcolumn_witness. - Compute Hash: Use the hash function to compute the hash of the current node from its children hashes and column values.
- Store the computed hash for propagation to the next layer.
- Reconstruct
- Get the number of columns in the current layer (
- For each layer (from largest to smallest):
-
Final Verification:
- Check that all witnesses and queried values have been fully consumed (no excess data).
- Verify that the computed root matches the expected root stored in the verifier.
- Return
Ok(())if verification succeeds, or an appropriate error otherwise.
Example: Verify the decommitment
The same example from the decommit process is used to verify the output of the decommit function. The input to the verify function is as follows:
queries_per_log_size:queried_values:decommitment:hash_witness:column_witness:
Below is a walkthrough of the main loop in the verify function, showing how the verifier reconstructs the Merkle root:
-
layer_log_size = 2 (columns of size 4):
n_columns_in_layer: 2 (for and )last_layer_hashes:None(first layer)prev_layer_queries: emptylayer_column_queries:- For
node_index = 0:node_hashes:None(no previous layer)node_values: Read fromqueried_values→- Compute hash:
- Add to
layer_total_queries:
- At this stage:
last_layer_hashes=
-
layer_log_size = 1 (columns of size 2):
n_columns_in_layer: 1 (for )last_layer_hashes:prev_layer_queries:layer_column_queries:- For
node_index = 0:node_hashes: Left child is (computed fromlast_layer_hashes), right child read fromhash_witnessnode_values: Read fromcolumn_witness→- Compute hash:
- Add to
layer_total_queries:
- For
node_index = 1:node_hashes: Both children read fromhash_witnessnode_values: Read fromqueried_values→- Compute hash:
- Add to
layer_total_queries:
- At this stage:
last_layer_hashes=
-
layer_log_size = 0 (root):
n_columns_in_layer: 0 (no columns of size 1)last_layer_hashes:prev_layer_queries:layer_column_queries: empty- For
node_index = 0:node_hashes: Left child is , right child is (both computed fromlast_layer_hashes)node_values: empty (no columns)- Compute hash:
- Add to
layer_total_queries:
- At this stage:
last_layer_hashes=
Final verification:
- Check that all iterators are exhausted:
hash_witness,queried_values, andcolumn_witnessshould all be empty. - Compare the computed
rootwith the expected root stored in theMerkleVerifier. - If they match, return
Ok(()); otherwise, returnErr(MerkleVerificationError::RootMismatch).