What is a Merkle tree?
A Merkle tree fingerprints a long list with one short value, the root, so that anyone can prove an item is in the list with a handful of hashes instead of the whole list.
Also called hash tree.
Explain it like I’m five
Eight children each hold a card with their name. Neighbors hold their cards up together, and a teacher writes a fingerprint of the two names on a new card. The new cards are paired and fingerprinted again, and again, until one card is left, the root. That last card is a fingerprint of the whole class. To prove that Mia is in the class, nobody has to line up all eight children. Mia shows her own card and the three cards she was paired with on the way up, and anyone can repeat the three steps and land on the same last card.
What problem it solves
Some lists are too long to send around, yet people need to check one item in them, or check that nothing in them has changed. A Merkle tree gives the whole list one short fingerprint. Anyone who knows the root can verify a single item from a short proof, and any change to any item changes the root. A Bitcoin block commits to all of its transactions this way, and a phone can check that a payment is in a block without downloading the block.
How it works, step by step
- Every item is hashed, and these hashes are the leaves.
- Neighboring hashes are hashed together in pairs, and the results are paired and hashed again, level after level, until one hash remains. Each parent is the hash of its two children.
- That last hash is the root. Publishing it commits to the whole list.
- When the number of items is not a power of two, the tree can be unbalanced. Certificate Transparency splits a list of n items at the largest power of two below n, so the shape depends only on n.
- To prove one item, the prover sends the item and the sibling hash at every level on its way up (the Merkle proof or audit path).
- The verifier hashes the item with the first sibling, hashes the result with the next sibling, and so on, and compares the final hash with the root.
- Changing any item changes every hash above it and so the root, which makes the list tamper-evident.
- Leaves and inner nodes are hashed with different prefixes, such as the bytes 0x00 and 0x01 in Certificate Transparency, so an inner node can never pass for a leaf (second-preimage resistance).
A worked example
With eight items A to H, the proof for F is three hashes: E, the hash of G and H, and the hash of A to D together. The verifier hashes E with F, hashes that with the G and H hash, and hashes that with the A to D hash. A match with the root proves that F is in the list. A list of 1,048,576 items needs a proof of only 20 hashes, which is 640 bytes with 32-byte hashes, and a list of about a billion items needs 30.
What it guarantees
- The root binds the list, because finding a different list with the same root would mean finding a hash collision.
- A proof has one hash per level, so it grows by one hash each time the list doubles, and checking it takes about one hash computation per level.
- A plain tree proves that an item is in the list, and it cannot prove that an item is missing.
- A proof shows only the hashes of the neighbors, never their contents.
- A log that only grows can also give consistency proofs, which show that a newer root extends an older one without rewriting it.
Common misunderstandings
- A Merkle tree stores no data. It is a fingerprint structure, and the items live elsewhere.
- A longer list does not mean a much longer proof. A million times more items add only about 20 hashes.
- A hash tree built without separate prefixes for leaves and inner nodes can be fooled. The root does not show the tree’s depth, so an attacker can present inner hashes as if they were data blocks.
Where it is used
Bitcoin and Ethereum put Merkle roots in their block headers, and Ethereum’s state root is the root of a Merkle Patricia trie, a Merkle tree keyed by path. Certificate Transparency logs publish Merkle roots so that anyone can audit them, and IPFS, BitTorrent and ZFS use hash trees to check blocks and find damaged ones. STARKs use Merkle trees to commit to long lists of values, and shielded pools keep their note commitments in a Merkle tree.
History
Ralph Merkle patented the idea in 1979 and described it in a 1987 paper on digital signatures. Bitcoin’s 2008 whitepaper used it to let nodes discard old transactions and let light clients check payments.
In Redacted
Redacted’s note tree is append-only and holds about 67 million notes, each a SHA-256 commitment, and nothing in it is ever deleted. Proving that a note is in it always takes twenty-six hashes, whether it is the fourth note or the sixty millionth, and a full tree is followed by a fresh one beside it with the same math.
Architecture →Related terms
Sources: RFC 6962, Certificate Transparency, section 2.1 Merkle Hash Trees · Bitcoin: A Peer-to-Peer Electronic Cash System, Satoshi Nakamoto, 2008 · Merkle tree, Wikipedia · Merkle Patricia Trie, ethereum.org
Updated November 1, 2026. All terms