Merkle Prover

​

MerkleProver Structure

pub struct MerkleProver<B: MerkleOps<H>, H: MerkleHasher> {
    /// Layers of the Merkle tree.
    /// The first layer is the root layer.
    /// The last layer is the largest layer.
    /// See [MerkleOps::commit_on_layer] for more details.
    pub layers: Vec<Col<B, H::Hash>>,
}

​

The Commit Process

    pub fn commit(columns: Vec<&Col<B, BaseField>>) -> Self {
        let _span = span!(Level::TRACE, "Merkle", class = "MerkleCommitment").entered();
        if columns.is_empty() {
            return Self {
                layers: vec![B::commit_on_layer(0, None, &[])],
            };
        }

        let columns = &mut columns
            .into_iter()
            .sorted_by_key(|c| Reverse(c.len()))
            .peekable();

        let mut layers: Vec<Col<B, H::Hash>> = Vec::new();

        let max_log_size = columns.peek().unwrap().len().ilog2();
        for log_size in (0..=max_log_size).rev() {
            // Take columns of the current log_size.
            let layer_columns = columns
                .peek_take_while(|column| column.len().ilog2() == log_size)
                .collect_vec();

            layers.push(B::commit_on_layer(log_size, layers.last(), &layer_columns));
        }
        layers.reverse();
        Self { layers }
    }

1. Sort Columns by Length: Columns are sorted in descending order of length (columns with the most elements appear first). This ensures that the largest columns are committed first.
2. Layer-by-Layer Commitment:
   • For each layer (from largest to smallest), the function collects all columns of the current size and computes the hashes for that layer using the commit_on_layer function.
   • For the largest layer, the previous layer’s hashes are empty, so the hash is computed directly from the column values.
   • For subsequent layers, the hash is computed from the previous layer’s hashes and the current layer’s column values.
3. Reverse Layers: After all layers are computed, the list of layers is reversed so that the root layer is at the beginning.

​

Example: Commit Process

Figure 1: Example column data to commit using a Merkle tree

• First Layer (Leaves): The hashes are computed directly from the column values: $[h_{00}, h_{01}, h_{10}, h_{11}] = [H(\textcolor{red}{a}, \textcolor{green}{p}), H(\textcolor{red}{b}, \textcolor{green}{q}), H(\textcolor{red}{c}, \textcolor{green}{r}), H(\textcolor{red}{d}, \textcolor{green}{s})]$
• Second Layer: The next layer uses the previous hashes and the values from $\textcolor{blue}{\text{Column 2}}$: $[h_0, h_1] = [H(h_{00}, h_{01}, \textcolor{blue}{u}), H(h_{10}, h_{11}, \textcolor{blue}{v})]$
• Root: The root is computed as $root = H(h_0, h_1)$.

Figure 2: Merkle tree structure after commitment

​

The Decommit Process

pub struct MerkleDecommitment<H: MerkleHasher> {
    /// Hash values that the verifier needs but cannot deduce from previous computations, in the
    /// order they are needed.
    pub hash_witness: Vec<H::Hash>,
    /// Column values that the verifier needs but cannot deduce from previous computations, in the
    /// order they are needed.
    /// This complements the column values that were queried. These must be supplied directly to
    /// the verifier.
    pub column_witness: Vec<BaseField>,
}

• queries_per_log_size: A map from log size to a vector of query indices for columns of that size.
• columns: The column data that was committed to in the Merkle tree.

• A vector of queried values, ordered as they are opened (from largest to smallest layer).
• A MerkleDecommitment containing the hash and column witnesses needed for verification.

    pub fn decommit(
        &self,
        queries_per_log_size: &BTreeMap<u32, Vec<usize>>,
        columns: Vec<&Col<B, BaseField>>,
    ) -> (Vec<BaseField>, MerkleDecommitment<H>) {
        // Prepare output buffers.
        let mut queried_values = vec![];
        let mut decommitment = MerkleDecommitment::empty();

        // Sort columns by layer.
        let mut columns_by_layer = columns
            .iter()
            .sorted_by_key(|c| Reverse(c.len()))
            .peekable();

        let mut last_layer_queries = vec![];
        for layer_log_size in (0..self.layers.len() as u32).rev() {
            // Prepare write buffer for queries to the current layer. This will propagate to the
            // next layer.
            let mut layer_total_queries = vec![];

            // Each layer node is a hash of column values as previous layer hashes.
            // Prepare the relevant columns and previous layer hashes to read from.
            let layer_columns = columns_by_layer
                .peek_take_while(|column| column.len().ilog2() == layer_log_size)
                .collect_vec();
            let previous_layer_hashes = self.layers.get(layer_log_size as usize + 1);

            // 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_queries.into_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)
            {
                if let Some(previous_layer_hashes) = previous_layer_hashes {
                    // If the left child was not computed, add it to the witness.
                    if prev_layer_queries.next_if_eq(&(2 * node_index)).is_none() {
                        decommitment
                            .hash_witness
                            .push(previous_layer_hashes.at(2 * node_index));
                    }

                    // If the right child was not computed, add it to the witness.
                    if prev_layer_queries
                        .next_if_eq(&(2 * node_index + 1))
                        .is_none()
                    {
                        decommitment
                            .hash_witness
                            .push(previous_layer_hashes.at(2 * node_index + 1));
                    }
                }

                // If the column values were queried, return them.
                let node_values = layer_columns.iter().map(|c| c.at(node_index));
                if layer_column_queries.next_if_eq(&node_index).is_some() {
                    queried_values.extend(node_values);
                } else {
                    // Otherwise, add them to the witness.
                    decommitment.column_witness.extend(node_values);
                }

                layer_total_queries.push(node_index);
            }

            // Propagate queries to the next layer.
            last_layer_queries = layer_total_queries;
        }

        (queried_values, decommitment)
    }

1. Sort Columns by Length:
   • As in the commit function, columns are sorted in descending order of length.
2. Layer-by-Layer Decommitment:
   • For each layer (from largest to smallest):
     • Collect all columns of the current size (layer_columns) and the previous layer’s hashes (previous_layer_hashes).
     • Retrieve the queries for the current layer (layer_column_queries) and the previous layer’s queries (prev_layer_queries).
     • For each node index to be decommitted in this layer:
       • Check if the child node hashes of the current node can be computed by the verifier, and if not, add the missing child node hashes to the hash_witness in the decommitment.
       • If the node index is queried, fetch the corresponding column values and append them to queried_values.
       • If not queried, add the column values to the column_witness in the decommitment.
     • The set of node indices decommitted in this layer is propagated as queries to the next layer.

​

Example: Decommit Process

• The 0th element of columns of size $2^2=4$: $\textcolor{red}{a}$ from $\textcolor{red}{\text{\textit{Column} 0}}$ and $\textcolor{green}{p}$ from $\textcolor{green}{\text{\textit{Column} 1}}$.
• The 1st element of the column of size $2^1=2$: $\textcolor{blue}{v}$ from $\textcolor{blue}{\text{\textit{Column} 2}}$.

• layer_log_size = 2 (columns of size 4):
  • layer_columns: $[\textcolor{red}{\text{\textit{Column} 0}}, \textcolor{green}{\text{\textit{Column} 1}}]$
  • previous_layer_hashes: None (first layer)
  • prev_layer_queries: empty
  • layer_column_queries: $[0]$
  • For node_index = 0:
    • node_values: $[\textcolor{red}{a}, \textcolor{green}{p}]$
    • Queried, so append to queried_values: $[\textcolor{red}{a}, \textcolor{green}{p}]$
    • Add node_index = 0 to layer_total_queries (to propagate to next layer)
  • At this stage: queried_values = $[\textcolor{red}{a}, \textcolor{green}{p}]$, decommitment is empty.
• layer_log_size = 1 (columns of size 2):
  • layer_columns: $[\textcolor{blue}{\text{\textit{Column} 2}}]$
  • previous_layer_hashes: $[h_{00}, h_{01}, h_{10}, h_{11}]$
  • prev_layer_queries: $[0]$
  • layer_column_queries: $[1]$
  • For node_index = 0:
    • Add $h_{01}$ to hash_witness in decommitment.
    • node_values: $[\textcolor{blue}{u}]$
    • Not queried, so append to column_witness in decommitment.
    • Add node_index = 0 to layer_total_queries.
  • At this stage: queried_values = $[\textcolor{red}{a}, \textcolor{green}{p}]$, hash_witness = $[h_{01}]$, column_witness = $[\textcolor{blue}{u}]$, layer_total_queries = $[0]$.
  • For node_index = 1:
    • Add $h_{10}, h_{11}$ to hash_witness in decommitment.
    • node_values: $[\textcolor{blue}{v}]$
    • Queried, so append to queried_values.
    • Add node_index = 1 to layer_total_queries.
  • At this stage: queried_values = $[\textcolor{red}{a}, \textcolor{green}{p}, \textcolor{blue}{v}]$, hash_witness = $[h_{01}, h_{10}, h_{11}]$, column_witness = $[\textcolor{blue}{u}]$, layer_total_queries = $[0, 1]$ (to propagate to next layer).
• layer_log_size = 0 (root):
  • layer_columns: empty
  • previous_layer_hashes: $[h_{0}, h_{1}]$
  • prev_layer_queries: $[0, 1]$
  • layer_column_queries: empty
  • No values are added to queried_values, hash_witness, or column_witness in this layer.

• queried_values: $[\textcolor{red}{a}, \textcolor{green}{p}, \textcolor{blue}{v}]$
• decommitment:
  • hash_witness: $[h_{01}, h_{10}, h_{11}]$
  • column_witness: $[\textcolor{blue}{u}]$