Sparse Merkle Tree

What Is a Sparse Merkle Tree?

A sparse Merkle tree is a specialized Merkle tree designed to represent a vast key space where only a small fraction of keys actually contain data. In a standard Merkle tree, every leaf corresponds to an actual piece of data in the set. In a sparse Merkle tree, the tree includes a leaf position for every possible key, but most of these leaves are empty, holding a predetermined default value (typically a hash of zero).

Consider a tree with a depth of 256: it has 2²⁵⁶ possible leaf positions, one for every possible 256-bit key. This is roughly the number of atoms in the observable universe. In practice, only a tiny fraction of those positions hold real data. The tree is "sparse" because the overwhelming majority of its leaves are empty.

This structure was formalized by Dahlberg, Pulls, and Peeters in their 2016 paper on efficient sparse Merkle trees. It has since become a foundational data structure for blockchain systems that need to commit to key-value state, from rollup state roots to asset registries.

How It Works

A sparse Merkle tree operates on the same principle as a regular Merkle tree: leaf nodes are hashed, then pairs of hashes are combined and hashed again, layer by layer, until a single Merkle root is produced. The key differences are in how the tree is structured and how it handles empty space.

Tree Structure

Each key determines the path from root to leaf. For a 256-bit key, the tree has 256 levels. At each level, the next bit of the key determines whether to go left (0) or right (1). The full key is read bit by bit from the most significant bit down to the least significant bit, tracing a unique path through the tree.

Because every possible key maps to exactly one leaf position, the root hash depends only on the data stored in the tree, not on the order in which entries were inserted. Two trees with the same key-value pairs always produce the same root, regardless of insertion sequence.

Default Values and Empty Leaves

Every empty leaf holds a default value, typically represented as a hash of zero. The hash of an empty subtree at each level can be precomputed: an empty leaf hashes to H(0), two empty leaves produce H(H(0) || H(0)), and so on. Since these values depend only on the tree depth, they can be calculated once and cached.

// Precompute default hashes for each level (bottom-up)
const defaults = new Array(257);
defaults[0] = hash(EMPTY_LEAF);
for (let i = 1; i <= 256; i++) {
  defaults[i] = hash(concat(defaults[i - 1], defaults[i - 1]));
}
// defaults[256] is the root hash of a completely empty tree

Inclusion Proofs

An inclusion proof in a sparse Merkle tree works the same way as a standard Merkle proof. To prove that a key-value pair exists, you provide the leaf value along with the sibling hashes at each level of the path from leaf to root. The verifier recomputes the root hash and checks it against the known root.

Non-Inclusion Proofs

This is the defining advantage of sparse Merkle trees. To prove that a key does not exist in the dataset, you prove that the leaf at that key's position holds the default empty value. The proof is structurally identical to an inclusion proof: you provide the sibling hashes along the path, and the verifier confirms that the leaf is empty.

In effect, a non-inclusion proof is just an inclusion proof for an empty leaf. Because every possible key has a defined position in the tree, the absence of data at that position is itself a provable fact. Standard Merkle trees cannot do this because they only contain leaves for data that actually exists.

Proof Verification

function verifyProof(root, key, value, siblings) {
  let currentHash = hash(value);
  for (let i = 0; i < 256; i++) {
    const bit = getBit(key, i);
    if (bit === 0) {
      currentHash = hash(concat(currentHash, siblings[i]));
    } else {
      currentHash = hash(concat(siblings[i], currentHash));
    }
  }
  return currentHash === root;
}

// Non-inclusion: call with value = EMPTY_LEAF
// Inclusion: call with the actual stored value

Optimizations

A naive sparse Merkle tree with 2²⁵⁶ leaves would be impossibly large to store. In practice, several optimizations make SMTs efficient.

Empty Subtree Caching

Since the hash of an empty subtree at any given depth is a constant, implementations never store empty branches. When traversing the tree and encountering an empty subtree, the precomputed default hash for that depth is used instead. This reduces storage from the theoretical 2²⁵⁶ nodes to only the nodes along paths to non-empty leaves.

Proof Compression with Bitmaps

Many sibling hashes in a proof are default values (because most subtrees are empty). Instead of including all 256 sibling hashes, a compressed proof uses a 256-bit bitmap where each bit indicates whether the corresponding sibling is a default hash or a real value. Only the non-default siblings are included in the proof data. This reduces proof size from roughly 256 × 32 bytes to approximately 32 + 32 × k bytes, where k is the number of non-empty siblings.

Compacted Trees

Compacted (or compact) sparse Merkle trees take optimization further. If a subtree contains only a single non-empty leaf, that entire subtree can be replaced with a single node encoding the leaf's key and value. This approach, used in implementations like the Jellyfish Merkle Tree (developed for the Diem/Aptos blockchain), dramatically reduces both storage and proof generation time.

Custom Hash Rules

Some implementations define H(0, 0) = 0 as a shortcut: if both children of a node are empty, the parent is also treated as zero without computing a hash. This avoids storing precomputed default hashes entirely. However, this approach requires including the key in the leaf hash to prevent root collisions between different tree configurations.

Comparison with Other Tree Structures

Standard Merkle Trees

A standard Merkle tree is a dense structure: every leaf contains actual data, and the tree grows or shrinks as data is added or removed. This makes them efficient for proving inclusion (that data exists in a set) but unable to prove non-inclusion without additional mechanisms.

Verkle Trees

Verkle trees replace hash-based proofs with polynomial commitments (typically using the Inner Product Argument or KZG commitments). This produces significantly smaller proofs because a single polynomial commitment can attest to multiple child values simultaneously, eliminating the need to include sibling hashes.

The tradeoff is computational cost: building and updating Verkle trees requires more expensive cryptographic operations than the simple hash functions used in sparse Merkle trees. Verkle trees also rely on cryptographic assumptions (like the discrete logarithm problem) that are potentially vulnerable to quantum computers, while hash-based SMTs can use post-quantum hash functions.

Merkle Patricia Tries

Ethereum currently uses a Merkle Patricia trie for state storage, which is a hybrid structure combining a radix trie with Merkle hashing. It supports non-inclusion proofs through its trie structure but suffers from imbalanced trees and complex update logic. Sparse Merkle trees offer simpler, more uniform proof structures at the cost of a larger theoretical tree size.

Use Cases

Rollup State Verification

Layer-2 rollups use sparse Merkle trees to commit to their entire state (account balances, contract storage, nonces) in a single root hash posted to the base layer. The non-inclusion proof capability is critical here: a fraud proof or validity proof may need to demonstrate that an account did not exist before a transaction created it. Systems like zkSync and Polygon's AggLayer use SMTs for their state commitments.

Taproot Assets Protocol

The Taproot Assets protocol on Bitcoin uses a Merkle-Sum Sparse Merkle Tree (MS-SMT) to track asset ownership. The sparse Merkle tree component enables proofs that a specific asset does not exist in a particular tree (preventing double-issuance), while the Merkle-sum component allows verification that the total supply is conserved across transfers. For more on how this fits into Bitcoin's asset layer, see the Taproot Assets protocol deep dive.

Zero-Knowledge Applications

Sparse Merkle trees pair naturally with zero-knowledge proofs. A prover can demonstrate membership or non-membership in a set without revealing which element was checked. This is used in privacy-preserving identity systems, anonymous credential verification, and rate-limiting protocols where users prove they have not exceeded a threshold without revealing their identity.

Certificate Revocation

Certificate authorities can publish an SMT root committing to all revoked certificates. Any party can then verify whether a certificate has been revoked (inclusion proof) or remains valid (non-inclusion proof) without downloading the entire revocation list. This is more efficient than traditional Certificate Revocation Lists (CRLs) and provides cryptographic proof of certificate status.

Risks and Considerations

Storage Overhead

While optimizations dramatically reduce actual storage, sparse Merkle trees still require more overhead per entry than dense data structures. Each insertion affects log(N) nodes (where N is the tree depth), and the path from leaf to root must be stored or recomputable. For applications with millions of entries, this can add up to significant storage and I/O costs compared to simpler data structures.

Proof Size

An uncompressed proof for a 256-level SMT requires 256 sibling hashes, or roughly 8 KB using SHA-256. Compression reduces this substantially, but proofs remain larger than those of Verkle trees, which can achieve similar guarantees in roughly 150 to 200 bytes per proof. For on-chain verification where calldata is expensive, this size difference matters.

Update Cost

Updating a single key-value pair requires recomputing hashes along the entire path from leaf to root. For a 256-level tree, this means 256 hash operations per update. Batch updates can amortize this cost when multiple keys share path prefixes, but individual updates remain relatively expensive compared to simpler authenticated data structures.

Implementation Complexity

Correctly implementing a sparse Merkle tree with all necessary optimizations (caching, compression, compaction) is non-trivial. Bugs in proof generation or verification can lead to false proofs of inclusion or non-inclusion, potentially enabling attacks in systems that rely on SMT proofs for security guarantees like state root verification.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.