Merkle Trees: How a Single Hash Verifies Millions of Records

One hash to verify everything

A Merkle tree, named after Ralph Merkle's 1979 patent, is a binary tree where every leaf holds the cryptographic hash of a data block and every internal node holds the hash of the concatenation of its two children's hashes. The result is a single root hash that summarises every byte of every block underneath it — change a single bit anywhere in the data, and the leaf hash changes, which changes its parent, which changes its parent, all the way up to a completely different root. This is what lets systems as different as Git, BitTorrent, ZFS, Certificate Transparency and every major blockchain verify huge datasets using one small, fixed-size fingerprint.

leaf0..leaf3 = H(block0)..H(block3)
node10 = H(leaf0 || leaf1)      node11 = H(leaf2 || leaf3)
root   = H(node10 || node11)
// flip one bit in block2 -> leaf2 changes -> node11 changes -> root changes

Verifying membership without the whole dataset

The property that makes Merkle trees useful in practice, not just elegant, is the Merkle proof (also called an audit path or inclusion proof): to prove that a specific block is part of the tree with a known root, you only need to supply that block plus the sibling hash at each level on the path up to the root — O(log n) hashes for n leaves, instead of the entire dataset. The verifier recomputes the path from the block upward and checks it matches the known root.

// prove leaf2 is under `root`, given siblings [leaf3, node10]
h = H(leaf2)
h = H(h || leaf3)     // combine with sibling at level 1 (leaf2 is left child)
h = H(node10 || h)    // combine with sibling at level 2 (this subtree is right child)
assert(h === root)    // O(log n) hashes prove membership in a set of n items

For a tree over a million leaves, that's about 20 hash computations to prove membership — verifiable in microseconds even on a phone, which is exactly the property Bitcoin's Simplified Payment Verification (SPV) clients rely on: a lightweight client can confirm a transaction is included in a block by checking a ~20-hash Merkle proof against the block header, without downloading or storing the full block.

Why blockchains use them

Each block in Bitcoin and Ethereum stores the Merkle root of all its transactions in its header, not the transactions themselves inside the hashed header. This decouples the size of what needs to be hashed for consensus (a fixed small header) from the number of transactions in the block, and it means any tampering with any transaction, however deep in the tree, is detectable from the header alone. Ethereum goes further with a Merkle Patricia trie — a Merkle tree merged with a radix trie — to make the entire account/state database itself verifiable and efficiently updatable one key at a time, rather than needing to rehash a static list.

Collision resistance is the whole security model

Every guarantee here rests on the underlying hash function being collision-resistant: it must be computationally infeasible to find two different inputs that hash to the same output. If an attacker could find a collision H(x) = H(y) for x ≠ y, they could swap a leaf's data without changing the root, silently forging a Merkle proof. This is why Merkle trees moved away from MD5 and SHA-1 once practical collisions were demonstrated against them, and modern implementations use SHA-256 or Keccak/SHA-3.

A subtler attack, the second-preimage attack against naive Merkle trees, exploits the fact that an internal node's hash and a leaf's hash can look structurally identical if you don't distinguish them — an attacker can sometimes present an internal node as if it were a leaf and forge a valid-looking proof for data that was never actually a leaf. The standard defence, used by Bitcoin's BIP and by the Certificate Transparency RFC, is domain separation: prefix leaf hashes with a distinct byte (e.g. 0x00) and internal-node hashes with another (0x01) before hashing, so a leaf hash can never be mistaken for, or substituted for, an internal node hash.

Building one efficiently

Building the tree bottom-up from n leaves takes O(n) hash operations total (n leaves become n/2 internal nodes, then n/4, and so on — a geometric series summing to just under 2n). For an odd number of leaves at some level, standard practice duplicates the last hash rather than leaving it unpaired, though some implementations instead promote it directly — the important thing is that whichever convention is chosen must be applied consistently by both the tree builder and every verifier, or proofs generated by one will fail to verify against the other.

Frequently asked questions

Try it live

Everything above runs in your browser — open Merkle Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.