Merkle trees

Why do we need Merkle trees?

Imagine a prover has a huge collection of values:

The verifier wants a compact commitment to the entire collection. Later, the prover may need to convince the verifier that one particular value belongs to that committed collection.

Sending the entire collection every time would defeat the purpose of having a compact commitment.

A Merkle tree solves this by repeatedly hashing pairs of values until only one hash remains:

The final hash is called the Merkle root.

Start with cryptographic hashes

A hash function takes an input of arbitrary length and produces a fixed-size output.

For example, a hash function might map:

We do not normally expect to reverse the digest and recover the input. More importantly for Merkle trees, small input changes should cause unpredictable changes in the output.

Important hash properties

Merkle-tree security relies primarily on the collision/second-preimage resistance of the underlying hash construction and on how the tree is encoded.

Build the smallest possible Merkle tree

Start with two data values:

Hash each leaf:

Then hash the two child hashes together:

Here || means concatenation.

                    root
                      │
                 H(hₐ || hᵦ)
                  /       \
                 /         \
               hₐ           hᵦ
               │             │
             H(A)           H(B)
               │             │
               A             B

The root commits to both values. If either leaf changes, its hash changes, which changes the parent hash, which changes the root.

A 4-leaf Merkle tree

Now consider:

The first level contains:

The next level combines pairs:

Finally:

                         root
                           │
                    H(p₀ || p₁)
                     /       \
                    /         \
                  p₀           p₁
                  │             │
             H(h₀ || h₁)   H(h₂ || h₃)
              /       \       /       \
             h₀       h₁     h₂       h₃
             │         │      │         │
           H(A)      H(B)   H(C)      H(D)
             │         │      │         │
             A         B      C         D

There are four leaves, two internal nodes, and one root.

The recursive structure

A binary Merkle tree repeatedly applies the same operation:

For n = 2ᵏ leaves, there are k levels from the leaves to the root.

The number of nodes is:

So constructing the whole tree takes O(n) hash operations.

What exactly does the Merkle root commit to?

The root depends recursively on every leaf.

For four leaves:

Therefore changing A changes:

The same happens for every leaf. The root is therefore a compact commitment to the complete ordered tree.

How do we prove that a leaf belongs?

Suppose the verifier knows only the root and the prover wants to prove that:

The verifier already knows the root, but does not know B, C, or D.

The prover does not need to send all three values.

For leaf A, the prover sends the sibling hashes:

This is called the Merkle authentication path or Merkle proof.

                         root
                           ▲
                           │
                         p₁
                           ▲
                           │
                    H(h₀ || h₁)
                     ▲       ▲
                     │       │
                    h₀      h₁
                     ▲       ▲
                     │       │
                     A     sibling

The verifier starts from A and reconstructs the path to the root.

Authentication path step by step

For A at index 0:

1. Hash the leaf: h₀ = H(A).
2. Combine it with its sibling: p₀ = H(h₀ || h₁).
3. Combine p₀ with the sibling parent p₁.
4. Compute H(p₀ || p₁).
5. Compare the resulting hash with the known Merkle root.

If the computed root equals the committed root, the proof is valid under the security assumptions of the hash function and tree encoding.

Why does the proof need left/right direction?

Hash concatenation is ordered:

Therefore the verifier needs to know whether each sibling is on the left or right.

For example:

A proof can therefore be represented as pairs such as:

Some implementations derive the direction from the leaf index and the level instead of storing it explicitly.

Why are Merkle proofs small?

For n leaves, the tree height is:

Therefore a membership proof needs only one sibling hash per level:

Compare that with sending all n leaves:

This logarithmic proof size is the main reason Merkle trees are so useful.

What happens when a leaf changes?

Suppose B changes to B′.

Only one path to the root needs to be recomputed:

You do not need to recompute unrelated branches.

Updating one leaf therefore costs approximately:

hash computations, assuming the tree structure and neighboring nodes are already available.

What about adding leaves?

Appending a leaf is slightly more complicated than updating an existing leaf because the tree shape changes.

For a complete power-of-two tree, adding the next leaf may require rebuilding or maintaining additional internal nodes.

Practical systems often use specialized structures such as:

• complete binary Merkle trees
• sparse Merkle trees
• incremental Merkle trees
• Merkle Mountain Ranges

The right structure depends on whether the workload is mostly static, append-only, sparse-keyed, or frequently updated.

What if the number of leaves is not a power of two?

Our simple diagrams assumed:

Real datasets do not necessarily have that shape.

There are several possible conventions:

• pad the leaf set to the next power of two;
• duplicate the last node at certain levels;
• use an unbalanced tree;
• use a tree construction specifically designed for arbitrary lengths.

Why domain separation matters

There is a subtle implementation issue with hashing leaves and internal nodes.

If both are encoded as raw concatenations, it can sometimes be dangerous for a protocol to allow ambiguity between:

A robust design often uses distinct domain-separation tags:

The exact tags are protocol-specific, but the principle is important: make different semantic objects cryptographically distinguishable.

Why changing a leaf should be detectable

Suppose the verifier knows:

A malicious prover wants to replace A with A′ while producing the same root.

At the bottom of the tree, this would require:

or a more complicated collision involving internal nodes.

Collision-resistant hashing is what makes such manipulation computationally infeasible.

Merkle tree in Rust

Here is a small implementation using SHA-256. It constructs a binary Merkle tree, computes the root, generates an inclusion proof, and verifies that proof.

// Cargo.toml:
// sha2 = "0.10"

use sha2::{Digest, Sha256};

type Hash = [u8; 32];

fn hash_leaf(data: &[u8]) -> Hash {
    let mut hasher = Sha256::new();

    // Domain separation: leaf hash.
    hasher.update([0x00]);
    hasher.update(data);

    hasher.finalize().into()
}

fn hash_node(left: &Hash, right: &Hash) -> Hash {
    let mut hasher = Sha256::new();

    // Domain separation: internal node.
    hasher.update([0x01]);
    hasher.update(left);
    hasher.update(right);

    hasher.finalize().into()
}

fn merkle_root(leaves: &[Vec<u8>]) -> Hash {
    assert!(!leaves.is_empty());
    assert!(leaves.len().is_power_of_two());

    let mut level: Vec<Hash> =
        leaves.iter().map(|x| hash_leaf(x)).collect();

    while level.len() > 1 {
        let mut next = Vec::with_capacity(level.len() / 2);

        for pair in level.chunks_exact(2) {
            next.push(hash_node(&pair[0], &pair[1]));
        }

        level = next;
    }

    level[0]
}

/// One sibling per tree level.
/// is_left = true means the sibling is on the left.
#[derive(Debug, Clone)]
struct ProofStep {
    sibling: Hash,
    is_left: bool,
}

fn merkle_proof(
    leaves: &[Vec<u8>],
    mut index: usize,
) -> Vec<ProofStep> {
    assert!(!leaves.is_empty());
    assert!(leaves.len().is_power_of_two());
    assert!(index < leaves.len());

    let mut level: Vec<Hash> =
        leaves.iter().map(|x| hash_leaf(x)).collect();

    let mut proof = Vec::new();

    while level.len() > 1 {
        let sibling_index =
            if index % 2 == 0 {
                index + 1
            } else {
                index - 1
            };

        proof.push(ProofStep {
            sibling: level[sibling_index],
            is_left: index % 2 == 1,
        });

        let mut next = Vec::with_capacity(level.len() / 2);

        for pair in level.chunks_exact(2) {
            next.push(hash_node(&pair[0], &pair[1]));
        }

        level = next;
        index /= 2;
    }

    proof
}

fn verify_proof(
    leaf: &[u8],
    proof: &[ProofStep],
    expected_root: &Hash,
) -> bool {
    let mut current = hash_leaf(leaf);

    for step in proof {
        current = if step.is_left {
            hash_node(&step.sibling, &current)
        } else {
            hash_node(&current, &step.sibling)
        };
    }

    &current == expected_root
}

fn main() {
    let leaves = vec![
        b"Alice".to_vec(),
        b"Bob".to_vec(),
        b"Carol".to_vec(),
        b"Dave".to_vec(),
    ];

    let root = merkle_root(&leaves);

    // Prove that "Carol" at index 2 is included.
    let proof = merkle_proof(&leaves, 2);

    assert!(verify_proof(
        b"Carol",
        &proof,
        &root,
    ));

    // A different value must not verify against the same proof.
    assert!(!verify_proof(
        b"Mallory",
        &proof,
        &root,
    ));

    println!("Merkle proof verified.");
}

What the Rust code is doing

1. Hash every leaf: hash_leaf(data) creates the bottom layer.
2. Hash pairs: hash_node(left, right) creates each parent.
3. Repeat: each level is half the size of the previous one.
4. Root: when one hash remains, it is the Merkle root.
5. Proof: collect one sibling hash per level for the target index.
6. Verification: reconstruct the root from the claimed leaf and proof.

Manual proof verification

Suppose the target leaf is at index 2 in:

The binary index of 2 is:

Its authentication path tells us:

The verifier computes:

If this equals the known root, the inclusion proof succeeds.

What is a Merkle multiproof?

Sometimes the verifier needs several leaves rather than one.

For example:

Providing three completely independent authentication paths repeats sibling hashes unnecessarily.

A multiproof shares common branches between the requested leaves.

The exact format varies by implementation, but the goal is to reduce the number of hashes transmitted and recomputed.

Sparse Merkle trees

A normal Merkle tree is naturally associated with a list of leaves.

A sparse Merkle tree instead represents a huge key space, often indexed by a binary key.

For a key:

each bit determines whether the authentication path moves left or right.

Most leaves are empty, so implementations can exploit known default hashes rather than explicitly storing the entire enormous tree.

This makes sparse Merkle trees useful for authenticated maps and state commitments.

Why Merkle trees matter in ZK

Merkle trees are everywhere in hash-based proof systems because they provide a compact commitment to a large vector of values.

A simplified STARK-style flow looks like:

The Merkle tree does not establish that the vector is low-degree. FRI supplies the low-degree testing. The Merkle tree establishes that the queried values belong to the vector that was committed to.

What a Merkle tree does not provide

It is important not to overstate what the root proves.

Engineering considerations

Hash choice

Choose a cryptographic hash appropriate for the protocol. In ZK circuits, a conventional hash may be expensive to represent as arithmetic constraints, so protocols sometimes use hashes designed to be efficient inside the relevant proof system.

Leaf encoding

The serialization of a leaf must be unambiguous. Two different logical objects should not accidentally serialize to the same byte string.

Internal-node encoding

Use a specified left/right ordering and, where appropriate, domain-separation tags.

Proof format

The verifier needs enough information to reconstruct every parent correctly. The protocol must specify index handling, sibling ordering, padding, and tree shape.

Memory layout

A naive implementation stores every tree level. Large systems may use flat arrays, streaming construction, cached subtrees, or specialized append-only structures.

The whole idea in one map

If polynomial commitments answer “how do we commit to a polynomial?”, a Merkle tree answers “how do we commit to a large vector of values and later prove that selected values belong to it using only logarithmic data?”