Merkle Multi Proofs

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, consider proving leaf L0 (position 8) individually — we need 3 proof nodes: its sibling (9), its uncle (5), and the right subtree root (3):

Now consider proving leaf L4 (position 12) individually — again 3 proof nodes: its sibling (13), its uncle (7), and the left subtree root (2):

Proving both leaves separately requires $3 + 3 = 6$ proof nodes in total. But notice that node $3$ (needed to prove L0) is the ancestor of L4, and node $2$ (needed to prove L4) is the ancestor of L0. In a merkle multi proof, these intermediate nodes are computed during verification rather than supplied — so the combined proof needs only $4$ proof nodes instead of $6$:

This scheme brings significant space savings when proving the existence of multiple items in a merkle tree, and the savings grow as more leaves share intermediate ancestors. 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.

Position-Based Indexing

We use a 1-based position numbering scheme where the root node is at position $1$:

$$\text{parent}(i) = \lfloor i / 2 \rfloor \qquad \text{left}(i) = 2i \qquad \text{right}(i) = 2i + 1 \qquad \text{sibling}(i) = i \oplus 1$$

Even positions are always left children, odd positions are always right children. The sibling of any node is found by toggling the least significant bit.

Given $n$ leaves in the tree, the height is $h = \lceil \log_2(n) \rceil$ and the first leaf position is $2^h$. A leaf at 0-based index $k$ maps to tree position $2^h + k$.

Unbalanced Trees

In practice, the number of leaves in a merkle tree is rarely a power of 2. A tree with $n$ leaves has height $h = \lceil \log_2(n) \rceil$, which means the leaf level has $2^h$ slots but only $n$ are occupied. The rightmost positions at each level may have no sibling:

When walking up from a node whose sibling doesn’t exist (e.g. position 12 has sibling $12 \oplus 1 = 13$, but position 13 is beyond the tree), the node is promoted unchanged to the parent level — no hashing occurs. Position 12 promotes to become position 6, which itself has no sibling (position 7 doesn’t exist), so it promotes again to position 3.

To detect this, the verifier tracks the number of valid nodes at each level. Starting from $n$ at the leaf level and computing $\lceil n / 2 \rceil$ for each level above, the last valid position at any level is:

$$\text{lastValid} = 2^{\lfloor \log_2(\text{pos}) \rfloor} + \text{nodesAtLevel} - 1$$

A sibling at position $\text{pos} \oplus 1 > \text{lastValid}$ does not exist in the tree.

Proof Schema

Each leaf carries its 0-based index and hash. The proof is a flat array of sibling hashes — no position metadata. The verifier derives positions internally from the leaf indices and leafCount.

Verification Algorithm

The algorithm converts leaf indices to 1-based tree positions ($\text{pos} = 2^h + \text{index}$), then walks up the tree level by level. At each level, for each node it resolves the sibling:

1. Sibling in the working set — the next node has position $\text{pos} \oplus 1$, hash them together
2. Sibling in the proof — consume the next proof element as the sibling
3. Sibling doesn’t exist — unbalanced tree edge, promote unchanged (see above)

$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}$$

The working set is written in-place, shrinking each iteration.

Reference Implementation

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