up:: Classical Cryptography MOC

Merkle Tree

A Merkle tree is a data structure that takes a set of data items, hashes each one with a cryptographic hash function, then repeatedly hashes those digests together in pairs, level by level, until a single digest remains at the top called the Merkle root. Because every level feeds into the one above it, the root is a fingerprint of the entire dataset: change any single item and the root changes too. That property lets a Merkle tree do two things cheaply that a flat list of hashes cannot. It commits to a whole dataset in one small root value, and it lets anyone prove that one specific item belongs to that dataset using only a short chain of sibling hashes rather than the whole dataset. Ralph Merkle introduced the idea, which he called tree authentication, in his 1979 Stanford thesis, and it now underpins certificate transparency logs, version-control systems, blockchains, and the hash-based signatures that carry through the quantum transition.

Source: Ralph C. Merkle, “Secrecy, Authentication, and Public Key Systems,” PhD thesis, Stanford University, 1979, ralphmerkle.com/papers/Thesis1979.pdf.

The short version:

• A Merkle tree hashes data items into leaf digests, then hashes those in pairs up to a single top digest called the Merkle root.
• The root is a compact fingerprint of the whole dataset, so any change to any item changes the root, which makes tampering detectable.
• A Merkle proof shows one item belongs to the tree using only about log2(n) sibling hashes, not the whole dataset, so verification stays cheap even for billions of items.
• Merkle trees are the structural core of hash-based signatures, XMSS and LMS and the stateless SLH-DSA, where one root public key authenticates a huge number of one-time keys.
• Because a Merkle tree is built only from a hash function, its quantum-safety rests entirely on that hash, which is why hash-based signatures survive the quantum era while RSA and ECC do not.
• Familiar deployments include certificate transparency logs, Git, and blockchains, all of which name and audit data by its Merkle root.

An everyday way to picture it

Picture a single-elimination tournament bracket, but running upward instead of downward. At the bottom row you have your data items, and each gets a sealed tag, its hash. You pair the tags up and staple each pair together under a new combined tag, then pair those combined tags and staple again, and you keep going until the whole bracket funnels into one tag at the very top. That top tag is the Merkle root. Now the useful part: if a friend hands you one item at the bottom and claims it was in the original bracket, you don’t need to see every other item to check. You just need the handful of tags along that item’s path to the top, one sibling at each level, and you can restaple your way up and see whether you land on the same root. If a single item anywhere in the bracket was swapped, the root at the top comes out different, and the fraud is obvious.

What is a Merkle tree?

A Merkle tree, also called a hash tree or Merkle hash tree, is a tree in which every leaf node is the hash of a data item and every non-leaf node is the hash of the concatenation of its child nodes. The single node at the top is the Merkle root, and it serves as a cryptographic commitment to the entire set of leaves beneath it. Ralph Merkle first described this construction as “tree authentication” in his 1979 thesis, as a way to authenticate a large number of public values from one authenticated root.

Two ideas are doing the work here. The first is that a cryptographic hash is a one-way, collision-resistant fingerprint: you cannot feasibly find two different inputs with the same digest, so a matching digest is strong evidence of matching data. The second is composition: by feeding child digests into a parent hash, the tree chains those fingerprints together, so the root depends on every leaf through an unbroken sequence of hashes. Break the chain anywhere, by altering one leaf, and the change propagates up every level to the root.

A Merkle tree is not an encryption scheme and holds no secret. It is a public integrity structure. Everything about it is derived from the data and the hash function, and its whole purpose is to let a small root value stand in, verifiably, for a large body of data.

Source: Ralph C. Merkle, “Secrecy, Authentication, and Public Key Systems,” Stanford University, 1979, ralphmerkle.com/papers/Thesis1979.pdf.

How does a Merkle tree work?

A Merkle tree is built from the bottom up in three passes, using a single hash function throughout:

1. Hash the leaves. Take each data item and hash it. These digests are the leaf nodes. If the number of leaves is odd at any level, implementations either duplicate the last node or promote it, following the specific scheme’s rules, so the level can be paired.
2. Hash upward in pairs. Concatenate each pair of adjacent nodes and hash the result to produce their parent node. So a parent is H(left_child || right_child), where || is concatenation and H is the hash function.
3. Repeat until one node remains. Keep hashing each new level in pairs. Each pass halves the number of nodes, so the tree closes to a single node, the Merkle root, after about log2(n) levels for n leaves.

Worked example with four items A, B, C, D. First the leaves: H(A), H(B), H(C), H(D). Next the middle level: H(AB) = H(H(A) || H(B)) and H(CD) = H(H(C) || H(D)). Finally the root: Root = H(H(AB) || H(CD)). Every leaf reaches the root through exactly one path, and the root is a single fixed-size digest regardless of whether the tree holds four items or four billion.

The security of the whole structure inherits directly from the hash function. Rebuilding a different dataset that produces the same root would require finding a hash collision somewhere along the way, which is infeasible for an approved hash like SHA-256. That is the entire basis of the tamper-evidence, and it is why the choice of hash function is the only cryptographic assumption a Merkle tree makes.

Source: Ralph C. Merkle, “A Digital Signature Based on a Conventional Encryption Function,” Advances in Cryptology, CRYPTO ‘87, LNCS 293, Springer, 1988, link.springer.com/chapter/10.1007/3-540-48184-2_32.

What is a Merkle proof, and why is it so efficient?

A Merkle proof, also called an inclusion proof or audit proof, is the short list of sibling hashes that lets someone verify a single item belongs to a tree without seeing any other item, given only the trusted Merkle root. It is the feature that makes Merkle trees worth using instead of a flat list of hashes.

Here is how it works, using the four-item tree above. To prove that item A is in the tree, the prover hands the verifier item A plus two sibling hashes: H(B) and H(CD). The verifier then recomputes the path: hash A to get H(A), combine with the supplied H(B) to get H(AB), then combine with the supplied H(CD) to get a candidate root. If that candidate equals the trusted root, the proof holds, and A is confirmed to be in the tree exactly as committed. The verifier never touched items B, C, or D directly.

The efficiency is logarithmic, and that is the whole point. A membership proof needs one sibling per level, and a tree over n leaves has about log2(n) levels. An inclusion proof needs at most ceil(log2(n)) sibling hashes; RFC 9162 specifies the certificate-transparency inclusion-proof algorithm (the explicit node bound it states, ceil(log2(n)) + 1, is for consistency proofs). The practical scale is striking:

Items in the tree (n)	Sibling hashes in a membership proof (about log2 n)
1,000	about 10
1,000,000	about 20
1,000,000,000	about 30

A Merkle tree also supports a second kind of proof. A consistency proof shows that one version of a tree is an append-only extension of an earlier version, meaning nothing already committed was removed or changed, only new leaves were added. RFC 9162 uses consistency proofs to let anyone verify that a certificate transparency log never rewrote its own history. Both proof types are short, and both rest only on the collision resistance of the underlying hash.

Source: B. Laurie, E. Messeri, R. Stradling, “Certificate Transparency Version 2.0,” RFC 9162, 2021, rfc-editor.org/rfc/rfc9162.

Why do Merkle trees matter for post-quantum cryptography?

Merkle trees matter for the quantum transition because they are the structural core of hash-based signatures, which are the most conservative family of quantum-resistant signatures and the only one whose security rests on nothing but a hash function. A one-time signature scheme can sign a single message safely, but reusing its key is catastrophic, so on its own it is impractical. Merkle’s insight solved that: build a tree whose leaves are the public keys of many one-time signatures, and publish only the Merkle root as your single long-lived public key. Each signature then includes the one-time public key it used plus the Merkle proof tying that key back to the trusted root, so one root authenticates a huge number of one-time keys.

This is exactly how the NIST-recommended stateful schemes and the FIPS stateless scheme are built:

Scheme	Standard	How the Merkle tree is used
LMS	NIST SP 800-208	A Merkle tree over many one-time keys; the root is the public key, and state tracks which leaf was used so no one-time key repeats
SLH-DSA	FIPS 205	A stateless hypertree, meaning Merkle trees stacked on Merkle trees, so signing needs no state while still authenticating from a single root

XMSS is literally named the eXtended Merkle Signature Scheme, which tells you the tree is the central object. NIST SP 800-208 approves LMS, HSS, XMSS, and the multi-tree XMSS_MT variant for stateful hash-based signing, and SLH-DSA standardizes the stateless variant.

The quantum-safety argument is clean. A Merkle tree and the one-time signatures at its leaves are built only from hashing, and hashing is the part of cryptography that survives quantum computers. Shor’s algorithm, which breaks RSA and ECC by solving their underlying algebra, has no algebraic structure to attack inside a hash. The only quantum pressure is Grover’s algorithm, which merely square-root-speeds the search for a preimage and is handled by a large enough digest. So a hash-based signature is as quantum-safe as its hash function, and Merkle’s tree is what turns that guarantee into a usable signature scheme.

Sources: David Cooper et al., “Recommendation for Stateful Hash-Based Signature Schemes,” NIST SP 800-208, October 2020, csrc.nist.gov/pubs/sp/800/208/final; NIST, “Stateless Hash-Based Digital Signature Standard,” FIPS 205, August 2024, csrc.nist.gov/pubs/fips/205/final.

Where are Merkle trees used in practice?

Merkle trees show up wherever a system needs to prove that a large body of data is intact, or that one item belongs to a set, without shipping the whole set around. The recurring jobs:

1. Certificate transparency logs. Public logs of every issued TLS certificate use a binary Merkle tree so anyone can verify a certificate was logged (an inclusion proof) and that the log never rewrote its history (a consistency proof). RFC 9162 specifies this directly, and it is how the certificate ecosystem holds certificate authorities accountable.
2. Post-quantum signatures. XMSS and LMS and SLH-DSA authenticate many one-time keys from a single Merkle root, as covered above.
3. Version control and content addressing. Git models a repository’s history as a tree of hashes, so a commit hash certifies the entire snapshot beneath it, and content-addressed storage systems name data by its digest the same way.
4. Blockchains. Bitcoin and other chains put each block’s transactions in a Merkle tree and store only the root in the block header, so a lightweight client can verify a transaction is in a block with a short Merkle proof instead of downloading every transaction.
5. File and backup integrity. Distributed file systems and peer-to-peer transfer protocols split large files into chunks under a Merkle tree, so a receiver can verify each chunk against the root as it arrives and re-fetch only the chunks that fail.

The common thread is that the Merkle root is a single trustworthy anchor, and everything below it can be verified against that anchor a piece at a time. That is the same shape whether the leaves are certificates, one-time keys, transactions, or file chunks.

Source: B. Laurie, E. Messeri, R. Stradling, “Certificate Transparency Version 2.0,” RFC 9162, 2021, rfc-editor.org/rfc/rfc9162.

Common misconceptions

1. “A Merkle tree encrypts or hides the data.” It does not. A Merkle tree is a public integrity structure with no key and no secret. It proves data is intact and that items belong to a set, which is a different job from keeping data confidential.
2. “You need the whole dataset to verify one item.” The opposite is the entire benefit. A Merkle proof verifies one item from the root using only about log2(n) sibling hashes, so a billion-item tree needs roughly 30 hashes to check membership.
3. “Merkle trees are a blockchain invention.” Ralph Merkle described tree authentication in 1979, decades before blockchains. Certificate transparency, Git, and hash-based signatures all use Merkle trees independently of any blockchain.
4. “A Merkle tree needs its own special cryptography for the quantum era.” It needs only a quantum-resistant hash function, which the SHA-2 and SHA-3 families already provide. The tree inherits its quantum-safety directly from the hash, with no new math required.
5. “The Merkle root proves the data is genuine on its own.” The root only proves the data matches whatever was committed. It is a commitment, so it is only as trustworthy as the source you got the root from. Certificate transparency and hash-based signatures both add an authentication step to establish that the root itself is trusted.

Questions people ask

What is the difference between a Merkle tree and a hash? A hash is a single fingerprint of a single input. A Merkle tree arranges many hashes into a tree so that one top-level hash, the Merkle root, fingerprints an entire dataset, and it lets you prove any one item belongs to that dataset with a short proof. The tree is a way of composing hashes, not a replacement for them.

What is a Merkle root? The Merkle root is the single digest at the top of the tree, computed by hashing everything below it in pairs, level by level. It acts as a compact commitment to the whole dataset, so publishing the root pins down every leaf, and any later change to any leaf produces a different root.

How big is a Merkle proof? About log2(n) hashes for a tree of n items, one sibling per level. An inclusion proof needs at most ceil(log2(n)) hashes (RFC 9162 specifies the CT inclusion-proof algorithm), so proving membership in a million-item tree takes roughly 20 hashes and a billion-item tree roughly 30.

Are Merkle trees quantum-safe? Yes, as long as the hash function underneath is. A Merkle tree has no algebraic structure for Shor’s algorithm to attack, and Grover’s algorithm only weakens hash preimage search by a square root, which a large enough digest absorbs. This is why hash-based signatures built on Merkle trees are among the most trusted post-quantum signatures.

Why do hash-based signatures use Merkle trees? One-time signature keys are safe to use only once, which is impractical alone. A Merkle tree solves that by placing many one-time keys at the leaves and publishing only the root as one long-lived public key, so a single root can authenticate an enormous number of one-time keys, each tied back to the root by a Merkle proof.

What is the difference between XMSS and SLH-DSA? XMSS is stateful, so the signer must track which one-time leaf has been used and never reuse it, and NIST specifies it in SP 800-208. SLH-DSA is stateless, using a hypertree of Merkle trees plus randomization so no state has to be kept, at the cost of larger, slower signatures.

What is a consistency proof? A consistency proof shows that a newer version of a Merkle tree is an append-only extension of an older version, meaning every leaf already committed is still there, unchanged, and only new leaves were added. Certificate transparency logs use consistency proofs so observers can confirm a log never rewrote its own history.

Is a Merkle tree the same as a blockchain? No. A Merkle tree is a data structure for committing to and proving membership in a dataset. A blockchain is a broader system that happens to use Merkle trees inside each block to summarize its transactions. The tree is a component, not the whole system.

---

Everything here is the map, given freely. When your team needs its own signing and integrity infrastructure sorted into what carries through the quantum transition and what has to move, that’s the work I do, and there’s an alignment briefing for it.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.