Few data structures have shaped cryptography as deeply as the Merkle tree. Invented by Ralph Merkle in 1979, this simple tree-of-hashes idea now underpins Bitcoin, certificate transparency, distributed file systems, and the post-quantum hash-based signature standards LMS, XMSS, and SLH-DSA. Anyone working with quantum-resistant cryptography needs to understand Merkle trees because every hash-based signature scheme is essentially Merkle's 1979 idea, refined.
This post walks through what a Merkle tree is, how Ralph Merkle proposed using it for signatures, why it survives quantum attack, and where you encounter it today inside QNSQY and beyond.
The 1979 Idea That Outlived Most of Cryptography
In 1979, Ralph Merkle published "Secrecy, Authentication, and Public Key Systems," his Stanford PhD thesis. RSA had appeared two years earlier. Diffie-Hellman three years before that. The world of public-key cryptography was being invented in real time.
Merkle's thesis introduced what he called a "tree authentication" scheme. The basic insight: if you hash pairs of values together, then hash the results, then hash those, you build a tree where every internal node summarizes everything below it. The root hash commits to the entire data set with a single 32-byte value.
The original use case was certificate management for many users. Instead of signing each certificate individually with an expensive RSA signature, sign the root of a Merkle tree containing all certificates with one signature. Anyone verifying a single certificate gets a small "Merkle path" that proves the certificate is in the signed set.
Forty-six years later, Merkle's tree shows up in places he could not have foreseen: Bitcoin transactions, Git commits, BitTorrent file integrity, LMS post-quantum signatures, and certificate transparency logs scanning every TLS certificate ever issued.
How a Merkle Tree Is Built
Start with a list of leaves. Each leaf is the hash of some data. For four data items D1, D2, D3, D4:
L1 equals hash(D1) L2 equals hash(D2) L3 equals hash(D3) L4 equals hash(D4)
Pair them up and hash:
N12 equals hash(L1 concatenated with L2) N34 equals hash(L3 concatenated with L4)
Hash the next level:
Root equals hash(N12 concatenated with N34)
The root is a single 32-byte (for SHA-256) or smaller commitment to all four data items. Change any single bit of any data item and the root changes too. This is the key property.
A Merkle tree with 1024 leaves uses about 1023 internal nodes plus 10 levels of depth. Verification of a single leaf requires log2(1024) equals 10 hashes plus 10 sibling hashes provided as a "Merkle path."
A useful analogy is sealing a stack of documents in nested envelopes. The outermost envelope is the root. Inside it are two envelopes. Each of those contains two more, and so on. Open one envelope and you can verify everything inside it without opening the others. Tampering with any document changes the seal on every envelope above it.
Merkle's Original Signature Scheme
Merkle's 1979 thesis proposed a signature scheme using one-time signatures and a Merkle tree.
Step 1: generate many one-time signature key pairs. Each pair signs exactly one message and is then thrown away. Lamport signatures from 1979 work for this; modern variants use Winternitz one-time signatures (W-OTS) for compactness.
Step 2: hash all the public keys together with a Merkle tree. The root of the tree is the long-term public key.
Step 3: to sign a message, pick an unused one-time key pair, sign with it, and provide the Merkle path from that public key to the root.
Step 4: verifier checks the one-time signature, then checks that the path hashes up to the long-term public key.
Each one-time key is used exactly once. After 2^h messages (where h is the tree height), the long-term key is exhausted.
This 1979 design is the direct ancestor of modern stateful hash-based signatures. LMS (RFC 8554) and XMSS (RFC 8391) are essentially Merkle's scheme with refined one-time signatures and parameter tuning. Both are NIST SP 800-208 approved for production use.
Why Hash-Based Signatures Survive Quantum Attack
Shor's algorithm breaks RSA and elliptic curve cryptography because it efficiently factors integers and computes discrete logarithms. Both rest on number-theoretic problems with hidden algebraic structure.
Hash-based signatures rest on a completely different foundation: the assumption that the underlying hash function is one-way and collision-resistant. To forge a signature, an attacker needs to find a hash collision or invert a hash, problems that no efficient quantum algorithm solves.
Grover's algorithm gives a quadratic speedup for hash inversion: an n-bit hash gives only n/2 bits of post-quantum security. SHA-256 thus provides 128 bits of post-quantum collision resistance, which is comfortable for current standards. SHA-3 and SHAKE256 provide stronger margins. Modern hash-based schemes like LMS and XMSS use these stronger hashes to deliver Level 3 or Level 5 quantum security.
So Merkle trees plus a strong hash function give signatures that resist any known quantum attack. NIST's SLH-DSA (formerly SPHINCS+, FIPS 205) is a stateless hash-based signature scheme that bundles many Merkle trees together and uses SHAKE256 internally.
Beyond Signatures: Merkle Trees Everywhere
The Merkle tree pattern shows up in places far beyond cryptographic signatures.
Bitcoin uses Merkle trees to commit to all transactions in a block. The block header contains the Merkle root, and lightweight clients can verify a single transaction with a Merkle path of about 10 hashes, never downloading the full block.
Git uses a Merkle-tree-like structure for commits. Every commit hash depends on the parent commit hash and the current content tree. Tampering with any historical commit changes every subsequent commit hash, making the chain tamper-evident.
Certificate Transparency logs use Merkle trees to prove that a certificate was logged and that the log has not been tampered with. Every certificate added to the log is a leaf, and consistency proofs use Merkle paths.
BitTorrent uses Merkle hashes to verify file pieces during download. Each piece is hashed; the hashes form a Merkle tree; clients verify pieces independently and detect corruption immediately.
Distributed file systems like IPFS use Merkle trees in the form of Merkle DAGs, where files and directories are content-addressed by their root hashes.
Anywhere you need to commit to a large data structure with a small fixed-size value, Merkle trees fit the role.
Performance: Logarithmic Verification
The signature use case shows Merkle's main performance advantage: log-time verification of leaves in a tree of size 2^h.
A tree with 2^20 (about 1 million) leaves has 20 levels. Verifying any single leaf requires 20 hash computations and 20 sibling hashes provided as proof. The proof size is 20 times 32 bytes equals 640 bytes for SHA-256.
For Bitcoin, this means a smartphone client can verify any transaction in any historical block by downloading less than a kilobyte of proof data and computing 20 SHA-256 hashes. No need to download the full block.
For LMS at height 20, the same numbers apply: each signature includes a 20-element Merkle path of 640 bytes. Add the W-OTS signature (about 1700 bytes) and a few overhead fields and you get about 3KB total signature size. Verification is fast: 20 hashes for the Merkle path, plus W-OTS verification.
QNSQY supports LMS on the Business tier for users who need the smallest possible signatures and the most conservative quantum security. The signature size is small thanks to Merkle trees.
Merkle Trees in Practice: Bitcoin Block Verification
To make the abstract concrete, walk through how a Bitcoin lightweight client verifies a transaction.
A Bitcoin block has a header (about 80 bytes) and a list of transactions (potentially megabytes). The header includes the Merkle root of the transaction list.
A user wants to verify that transaction T was included in block B. They have the block header (80 bytes). They request a Merkle proof from a full node.
The Merkle proof contains:
- The transaction T (about 250 bytes for a typical transaction).
- The Merkle path: about log2(N) sibling hashes where N is the number of transactions. For a block with 4096 transactions, this is 12 hashes equals 384 bytes.
- An index telling them which side each sibling is on.
The user computes:
- Hash of T equals leaf.
- Combine with first sibling at the right index, hash to get parent.
- Continue up the tree, combining with each sibling, until reaching the root.
- Compare to the root in the block header.
If the computed root matches, T was definitely in block B. About 700 bytes of data, twelve hash computations. Compare to downloading the entire block (potentially 1 MB or more).
This is the simplest example of why Merkle trees matter for system design.
Stateful vs Stateless Trade-Offs
Merkle's original signature scheme is stateful: the signer must remember which one-time keys have been used. Reusing a key compromises the entire scheme. State management is the core hazard.
LMS (RFC 8554) and XMSS (RFC 8391) are stateful schemes that descend directly from Merkle 1979. Both require careful state management: lose your state file, restore from a stale backup, or run on multiple machines and you risk reusing one-time keys.
SLH-DSA (FIPS 205) is a stateless variant that uses many Merkle trees randomly. The signer hashes the message to a leaf-selection seed and uses that seed to pick which one-time keys to use. No state management is needed. The cost is much larger signatures: SLH-DSA-128s signatures are about 8KB, versus 3KB for LMS.
QNSQY supports both LMS (smaller signatures, stateful) and SLH-DSA (larger signatures, stateless) for users with different operational profiles.
Merkle Tree Variants and Optimizations
Cryptographers have developed several variants of the basic Merkle tree.
Sparse Merkle trees handle very large key spaces (like 2^256 keys) without storing every leaf. Empty leaves use a default value. Used in Ethereum's state tree and in some certificate transparency designs.
Merkle Mountain Ranges support efficient append operations. Used in Mimblewimble and some blockchain protocols.
Multitrees support multiple roots over the same data, with different traversal orders. Useful for some advanced signature schemes.
Hashed Subtree Trees (HSS) chain multiple LMS trees together for very long signature lifetimes without exhausting any single tree.
Forest of Random Subsets (FORS) is the variant used in SLH-DSA, where many small Merkle trees with random subsets of one-time keys give the stateless property.
For QNSQY's purposes, the key takeaway is that all hash-based signatures, no matter how sophisticated, ultimately rest on the simple Merkle tree idea from 1979.
Frequently Asked Questions
Is a Merkle tree the same as a hash chain?
No. A hash chain is a sequence of hashes where each one depends on the previous: H1, H2 equals hash(H1 plus data2), H3 equals hash(H2 plus data3), and so on. A Merkle tree branches: each node has two children, and the structure is a balanced binary tree. Merkle trees support log-time verification of any leaf, while hash chains require linear-time verification.
Why do hash-based signatures resist quantum attack?
They rest on hash function security (one-way and collision-resistant), which Grover's algorithm only quadratically speeds up. There is no Shor-like exponential speedup for inverting hashes. With SHA-256 or SHAKE256, hash-based signatures provide 128 to 256 bits of post-quantum security.
What hash function should be used in a Merkle tree?
For pre-quantum: SHA-256 or BLAKE3. For post-quantum: SHAKE256 or SHA-256 with extra parameter margin. NIST SP 800-208 specifies the approved hash functions for LMS and XMSS.
What happens if a leaf changes in a Merkle tree?
Every node from that leaf up to the root changes. Anyone with the old root can detect tampering by recomputing the path. This is the tamper-evident property that makes Merkle trees useful for integrity proofs.
Does QNSQY use Merkle trees?
Yes, indirectly. QNSQY supports LMS and SLH-DSA on the Business tier, both of which use Merkle trees internally. The user does not need to interact with the trees directly: the library handles state management for LMS and tree selection for SLH-DSA.
Sources
- Merkle, R. C. (1979). "Secrecy, Authentication, and Public Key Systems." Stanford PhD Thesis. https://www.merkle.com/papers/Thesis1979.pdf
- NIST SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes. https://csrc.nist.gov/pubs/sp/800/208/final
- NIST FIPS 205: Stateless Hash-Based Digital Signature Standard (2024). https://csrc.nist.gov/pubs/fips/205/final
- RFC 8391: XMSS Extended Hash-Based Signatures (Hülsing et al., 2018). https://datatracker.ietf.org/doc/html/rfc8391
- RFC 8554: Leighton-Micali Hash-Based Signatures (McGrew, Curcio, Fluhrer, 2019). https://datatracker.ietf.org/doc/html/rfc8554
Related Articles
- LMS Stateful Signatures
- XMSS Signatures Explained
- BLAKE3 Hashing
- ML-DSA vs SLH-DSA
- What Is Post-Quantum Cryptography?
Protect Your Data Before Q-Day Arrives
QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.