Sparse Merkle Trees and Proofs of Non-Membership

A Merkle tree proves that a leaf is present: the verifier hashes the leaf with its siblings up to the root and compares. Proving that a leaf is absent is the harder direction, because absence is not a value that can be hashed. A sparse Merkle tree answers the question directly, at the cost of a committed structure whose shape is fixed by the key space rather than by the data, and a proof whose size is set by the key width rather than by the number of entries.

A tree over the whole key space

Each possible key has a fixed position: the key is hashed to n bits, and those bits are read from the most significant down as a path through a binary tree of depth n. A leaf sits where its path ends. Interior nodes exist only as hashes; their children are either other interior nodes or leaves or placeholder values for empty subtrees.

With n = 256 the tree has 2^256 possible leaves, which is more than any machine can store node by node. It is never stored that way. The tree is materialised sparsely: only the nodes on paths to present leaves are held, and every absent subtree is represented by a single default hash computed from the subtree’s depth.

The default hash at depth n is a leaf-level empty value. The default at depth d is the hash of two copies of the default at depth d+1. The recursion is deterministic and depends only on depth, so any empty subtree’s hash can be computed in n - d hash calls, or precomputed once as a table of n+1 values.

$$ D_n = H_{\text{empty}}, \qquad D_d = H_{\text{node}}(D_{d+1} ,|, D_{d+1}) $$

The stored representation needs only the non-default nodes, so the space is proportional to the number of present leaves times the depth, with sharing of prefixes common to many keys.

Proving absence

A non-membership proof is the list of sibling hashes along the path to the missing key’s position, exactly the shape of an inclusion proof. The verifier recomputes the path using those siblings plus the default hash wherever the path passes through an empty subtree. If the recomputed root matches the committed root, the key’s position is empty, and the key is absent.

What makes this sound is that a position is determined by the key’s hash alone. There is no way to place a leaf elsewhere and still have the path reach its correct position, because the path bits are the key bits. Insertion and absence are therefore mutually exclusive by construction, provided the tree is canonical: one position per key, no two leaves at one position, and no leaf at a position whose path disagrees with its key.

Three failure modes break that soundness, and each is a real implementation bug rather than a theoretical concern.

Uniqueness of position. If two different keys hash to the same 256-bit index, the tree cannot distinguish them. The collision probability is negligible for an honest hash, but it is the reason the index space must be the full digest width rather than a truncated one. Truncating the index to 128 bits reintroduces the birthday bound at 2^64 insertions, which is no longer out of reach for a large data set.

Canonicalisation. Some implementations compress the tree by skipping single-child runs, storing only branching nodes. That reduces proof length but makes the position of a leaf depend on its neighbours, which reintroduces the possibility of presenting a non-canonical tree as if it were canonical. A verifier that accepts a compressed proof has to check that no skipped node could have had another child.

The default-hash rule. A verifier that computes an empty subtree’s hash differently from the builder accepts proofs the builder would reject, and the divergence appears only on inputs that reach an empty subtree. The rule has to be fixed in the specification and covered by test vectors for a tree with a single leaf and a tree with a single leaf in the right half.

The proof-size arithmetic

Every proof is n sibling hashes long, whatever the number of entries. For n = 256 and 32-byte hashes that is 8 KiB per proof, before any compression. A Verkle tree or a similar structure replaces the sibling list with a vector commitment to each node’s children, so a proof carries a constant-size witness per level rather than one hash per level; the same depth of 256 levels then costs 256 small commitments plus the path openings, and the compression depends on the commitment scheme’s proof sizes rather than on the digest width.

The comparison that matters is not proof size in isolation but the product of size and verification work. A sparse Merkle tree proof verifies with n hash evaluations, each cheap, and no elliptic curve arithmetic. A vector-commitment-based tree verifies with far more arithmetic per level, so it is attractive only when the level count can also be reduced, by batching keys into a single commitment at each level rather than committing to one key per level.

There is a structural way to cut the depth: instead of one bit per level, use a wider branching factor. A 16-ary tree over a 256-bit key has depth 64 instead of 256, and each proof carries 15 sibling commitments per level, so the raw size grows while the number of hash evaluations falls. Whether that is a win depends on whether the verifier’s bottleneck is bytes transferred or hash calls, which in turn depends on whether the proof crosses a network.

Where this structure earns its cost

Non-membership proofs are required whenever absence is a claim that carries value. A revocation list commits to the set of revoked certificate serial numbers, and a verifier needs a proof that a given serial is not in the set. A permission system commits to the set of holders, and a denial decision needs a proof that an identity is absent. An accumulator of unspent outputs needs the mirror claim, that a given output has been spent, which is membership in the spent set.

The alternative is to commit to the complement, which requires the committer to know the whole key space, and the key space is usually unbounded. A sparse Merkle tree avoids that by treating the absent part as a default value rather than an enumerated set.

Costs are real. Updating one leaf requires recomputing every ancestor hash, which is n hash calls for a 256-bit key; in a tree of depth 256, that is 256 hashes per insert or delete, and a batch of k updates cannot be cheaper than the number of distinct ancestors they touch. The structure is therefore suited to sets that change far less often than they are read, which describes revocation lists and permission sets more often than it describes transaction outputs.

A second cost is that the committed root changes on every update, so any signature over the root must be reissued. Protocols handle this with an epoch structure: the root changes, a signed manifest of roots accumulates, and the verifier’s trust is in the manifest rather than in a single root. That layering is the same one Certificate Transparency uses for its append-only log, where RFC 6962 defines the tree and the proof formats and leaves the freshness mechanism to the surrounding protocol.

Structure compared with an append-only log

The two structures solve different problems and are often confused. An append-only log commits to a sequence and proves that a leaf was appended at a particular index, with proofs that grow logarithmically with the number of entries. A sparse Merkle tree commits to a set and proves membership or absence of a key, with proofs that are constant in the number of entries and linear in the key width.

A log can support non-membership only by proving that a range of indices between two adjacent present entries contains the missing value, which works when the keys are ordered and the log is complete over a range. A set cannot support append-only consistency proofs without additional structure. Protocols that need both, such as a transparency log that also answers “is this certificate revoked”, end up with two structures, and the composition has to be designed so that an attacker cannot present a stale root for one of them.

The hash-level requirements are the same in both: tags that distinguish leaf from node encodings, a fixed default value that is not a valid leaf, and a length prefix or fixed width for every hashed input. The ways those fail are catalogued in domain separation in Merkle trees, and the chunking and parallelism questions that dominate the cost of building a large tree are the subject of parallel tree hashing. What a sparse tree adds is that its shape is fixed by the key space, so the encoding has to be fixed at the same time and cannot be changed later without changing every root.