Merkle Mountain Range Multi Proofs

Merkle mountain ranges$^{[1]}$ are an improvement over conventional merkle trees for growing, potentially unbounded lists. Where conventional merkle tree constructions over growing lists prove very inefficient to compute, as all nodes in the tree must be recomputed. Merkle mountain ranges amortise this cost by growing subtrees incrementally and merging subtrees at the same height, rather than growing the full tree.

Merkle mountain ranges, true to their name, are a type of merkle tree composed of perfectly balanced binary subtrees (each subtree has $2^k$ leaves for some $k$) arranged in decreasing height — forming a mountain range silhouette. This construction provides two key benefits over conventional merkle trees:

• Efficient appends. Inserting a leaf into a conventional merkle tree requires recomputing $O(n)$ nodes (every node on the path from the new leaf to the root, plus the root changes position). In an MMR, appending a leaf is amortized $O(\log n)$ — only the rightmost subtrees may need merging.
• Compact proofs over large sets. A proof for a single leaf requires at most $h$ nodes for the subtree proof (where $h$ is the subtree’s height) plus at most $h$ peak hashes for bagging — still $O(\log n)$ total.

Capacity

An MMR where the tallest subtree has height $h$ can hold subtrees of every smaller height as well. When all heights from $h$ down to $0$ are present, the total leaf count is:

$$n = 2^h + 2^{h-1} + \cdots + 2^0 = 2^{h+1} - 1$$

A conventional merkle tree of height $h$ holds exactly $2^h$ leaves. So an MMR with the same maximum proof depth holds nearly twice as many leaves:

	Height $h$	Max leaves	Max proof size
Merkle tree	$h$	$2^h$	$h$
MMR	$h$	$2^{h+1} - 1$	$2h$ (subtree + peaks)

The MMR proof is at most twice as large, but this is a constant factor — both are $O(\log n)$.

MMR Multi Proofs

Our approach to verifying mmr multi proofs is to decompose the MMR into its constituent subtrees and verify each one independently using the position-based indexing model defined in my previous article.

An MMR with $n$ leaves decomposes into subtrees whose sizes are the powers of 2 in the binary representation of $n$:

$$n = \sum_{i} 2^{b_i} \quad \text{where } b_0 > b_1 > \cdots > b_{k-1} \text{ are the set bits of } n$$

The number of subtrees (peaks) equals $\text{popcount}(n)$.

Each subtree is treated as a standalone merkle tree with 1-based position indexing. Within a subtree, leaf indices are converted to tree positions and siblings are paired bottom-up, consuming proof nodes as needed for missing siblings.

Proof Schema

The MMR proof uses a minimal format. The proof is a flat array of hashes, and each leaf carries its 0-based index across the entire MMR. Positions within subtrees are inferred from leafCount.

Verification Algorithm

The algorithm proceeds in three phases:

Phase 1: Decompose into subtrees. Walk through the binary representation of $n$, peeling off the largest power-of-2 subtree at each step. Partition the leaves into each subtree by their index.

Phase 2: Compute subtree roots. For each subtree, convert leaf indices to 1-based tree positions and walk up level by level. At each level, check if the next node is a sibling ($\text{pos} \oplus 1$). If both siblings are known, hash them together; otherwise, consume a proof element as the missing sibling.

Phase 3: Bag the peaks. Combine the subtree roots right-to-left: $\text{root} = H(H(S_3, S_2), S_1)$.

Subtree Root Calculation

Each subtree is a perfect binary tree verified independently by converting leaf indices to tree positions and walking up:

$H_{\text{pair}}$ orders the hash inputs by position — even positions are left children, odd are right:

$$H_{\text{pair}}(v, s) = \begin{cases} H(v.\text{hash} \| s.\text{hash}) & \text{if } v.\text{pos} \text{ is even} \\ H(s.\text{hash} \| v.\text{hash}) & \text{if } v.\text{pos} \text{ is odd} \end{cases}$$

MMR Verification

With SubtreeRoot defined, we can now describe the full MMR verification:

Reference Implementation

A production Solidity implementation of this algorithm is available at polytope-labs/solidity-merkle-trees.

References

$^{[1]}$ P. Todd. Merkle Mountain Ranges. GitHub, 2012. https://opentimestamps.org.