Merkle Multi Proofs

Do not index

Merkle multi proofs enable more efficient merkle proofs by re-using the intermediate nodes shared by the proof leaves during the recalculation of the root hash of the tree. In order to understand the benefits provided by merkle multi proofs, let’s look at the number of proof items needed for the green node in the tree below:

Proof schema for a single item in the tree. We need log₂(n) = 4 proof nodes.

Proof schema for another item in the merkle tree, which uses 3 proof nodes. (note: this tree is unbalanced)

A combined merkle multi proof uses only 5 proof nodes, in contrast to the total of 7 proof nodes required for verifying each node individually.

This scheme brings significant space savings when proving the existence of multiple items in a merkle tree. In this article, we introduce a custom proof format that gives us computational savings at the cost of additional space complexity for execution environments where the cost of execution may be too high.

We first define the -index of any node in the tree as it’s distance to the leftmost node at every level of the tree:

Using this -index. we can model the relationship between a parent node and it’s children nodes as:

Where:

-index of left child node.

-index of right child node.

-index of parent node.

With the knowledge of the -index of each node and its relationship with it’s parent, we can position the nodes in each layer sorted by this -index to perform the correct hashing procedure needed to arrive at the parent node and it’s -index for the next layer. We repeat this procedure until we reach the root node.

We can define our proof schema as a 2-dimensional array, where the first dimension encodes the layers of the tree, and the second dimension holds the proof nodes for that layer:

Second Pre-image Attacks

Second pre-image attacks arise when merkle tree proof schemes do not check the tree depth when verifying merkle proofs. This allows for attackers to construct either arbitrarily deep or shallow trees that have the same root hash as the verifier’s, in order to fool the verifier that some forged items are in the original tree.

In order to mitigate this, given our current proof scheme, it is necessary that the verifier knows the number of items in the tree. With this knowledge, the height of the tree can be computed using:

and compared to the length of the 2D proof array (which encodes the height of the tree). If they do not match then the proof can safely be rejected because it describes a different tree and is attempting to perform a pre-image collision attack.

Pseudocode

Given this proof schema, we can describe the rust version of this algorithm as:

type Hash = [u8; 32];

struct Node {
    k_index: usize,
    node: Hash,
}

pub fn calculate_merkle_multi_root(leaves: Vec<Node>, proof: Vec<Vec<Node>>) -> Hash {
    let mut next_layer = vec![];
    // add the leaves to the bottom layer.
    proof[0].extend(leaves);
    // sort the nodes at the bottom layer by their k-index.
    proof[0].sort_by(|a, b| a.k_index.cmp(&b.k_index));

    for layer in proof {
        let mut current_layer = vec![];
        if next_layer.len() == 0 {
            current_layer = layer;
        } else {
            // merge the nodes from hashing the previous layer with the proof nodes at this layer.
            current_layer.extend(next_layer.drain(..));
            current_layer.extend(&layer);
            // sort the nodes in this new layer by their k-index.
            current_layer.sort_by(|a, b| a.k_index.cmp(&b.k_index));
        }

        for index in (0..current_layer.len()).step_by(2) {
            if index + 1 >= current_layer.len() {
                // this is an un-even layer, push this node directly to the next layer.
                let mut node = current_layer[index].clone();
                node.k_index = node.k_index.div_floor(2);
                next_layer.push(node);
            } else {
                let mut concat = vec![];
                let mut left = current_layer[index].clone();
                let right = current_layer[index + 1].clone();
                concat.extend(&left.node);
                concat.extend(&right.node);
                let hash = hash(&concat);
                let parent = Node { k_index: left.k_index.div_floor(2), node: hash };

                next_layer.push(parent);
            }
        }
    }

    debug_assert_eq!(next_layer.len(), 1);

    next_layer[0].node
}