Merkle Tree

A Merkle tree turns a set of data blocks into one short hash. Hash each block to get the leaves. Hash each pair of leaves to get the level above. Keep going until one hash remains: the root. The root commits to every byte of every block, so two copies of the same dataset always produce the same root, and one changed byte anywhere produces a different one.

The figure above builds a tree over four blocks: alpha, beta, gamma, and delta. Press play and watch the hashes climb from the leaves to the root. The figure uses a short four-character hash so the values fit on screen. A real Merkle tree uses SHA-256, and every step is identical. Ralph Merkle patented the scheme in 1979, and it still underpins systems that verify data they never store.

Build from the bottom up

Every leaf holds the hash of one block. In the figure, H("alpha") = 61d0 and H("beta") = 46c4. A leaf commits to exactly one block, and it says nothing about any other.

Press play again and watch the order. The leaves fill in left to right, then the branches, then the root. A hash appears only after the values it consumes, so the tree builds level by level, never mid-air.

Each branch node holds the hash of its two children, concatenated in order. The left branch computes H(61d0 · 46c4) = 3c60, and the right branch computes H(1388 · b94c) = 27ea. Order matters, because H(a · b) and H(b · a) are different hashes. A branch commits to its children and to which child sat on the left.

One more round combines the branches, and the root 7acf commits to all four blocks. For n blocks the tree holds 2n − 1 hashes in total, so building one costs O(n) hashing and O(n) space.

Commit has a precise meaning here. Given only the root, nobody can produce a different dataset with the same root, because that would mean beating the hash function at some level of the tree. The root is small, but it stands for everything beneath it.

Real datasets rarely come in neat powers of two. When a level has an odd number of hashes, the last hash is duplicated to make a pair, and the build continues. The demo trees never trigger the rule, but every implementation needs it.

One edit reaches the root

Open the figure again and change beta to beta! in the block input. Three hashes flip, one per level. The leaf 46c4 becomes 1ed8, the branch 3c60 becomes e16b, and the root 7acf becomes 5d68. The other four hashes never move.

The cascade is the hash function's doing. A hash mixes its input, so a one-character change produces an unrelated output. The branch above the edited leaf consumes the new hash, so the branch changes, and so does every node up to the root. The path from a leaf to the root has log₂ n nodes, so an edit costs O(log n) recomputes, not a rebuild.

This cascade is the trick the whole structure exists for. To check whether two copies of a dataset agree, compare the roots. Equal roots mean equal data, with near-certainty. Different roots mean something diverged, and comparing children walks straight to the differing subtree in log₂ n steps. Two machines can audit a billion blocks by exchanging a handful of hashes.

The rest of the tree stays untouched because its inputs stay untouched. A hash covers exactly the nodes beneath it, so a change travels only along the path from the edited leaf to the root. Everything off that path keeps its value, and nobody recomputes it.

The build fits in a dozen lines. Leaves hash with a 0x00 prefix and branches with 0x01, so a leaf can never be mistaken for a pair of children. The implementation panel below adds proof generation and verification, in Python and JavaScript.

import hashlib

def H(data: bytes) -> bytes:
	return hashlib.sha256(data).digest()

def merkle_root(blocks: list[bytes]) -> bytes:
	level = [H(b"\x00" + block) for block in blocks]
	while len(level) > 1:
		if len(level) % 2 == 1:
			level.append(level[-1])  # duplicate the odd hash
		level = [H(b"\x01" + level[i] + level[i + 1])
				 for i in range(0, len(level), 2)]
	return level[0]

A proof shows one block without the rest

The root has a second use, and it is the surprising one. Say you store eight blocks, and a verifier trusts the root c1f3. To prove that gamma is in the tree, you could send all eight blocks and let the verifier rebuild the tree. Or you could send gamma and three hashes.

The three hashes are the siblings on the path from gamma's leaf to the root: b94c beside the leaf, 3c60 beside the first branch, and 5866 beside the second. The block plus those siblings is the proof. Everything else in the tree stays hidden.

The verifier hashes gamma to get 1388, then combines the running hash with each sibling, on the side the sibling came from. First H(1388 · b94c) = 27ea, then H(3c60 · 27ea) = 7acf, then H(7acf · 5866) = c1f3. The candidate root equals the known root, so the block is in. Had any byte of gamma differed, the first hash would differ, and the mismatch would climb to the root exactly as it does in the edit demo.

The prover has an easy job too. Walking from the leaf to the root and collecting the sibling at each level takes log₂ n reads from a stored tree, so serving a proof is as cheap as checking one.

Step through the figure. The dashed nodes are hashes the verifier never sees: eight of the fifteen. Flip the tamper switch to change one byte of the block, and the candidate root lands on d9ed instead of c1f3. The proof fails before the data is even stored.

A proof cannot be faked, because faking one means finding different input that hashes to a value already in the tree. That is a second-preimage attack on the hash function, and for SHA-256 no practical attack exists. The tree's safety is exactly the hash function's safety.

Notice what the verifier had to store: one root, thirty-two bytes with SHA-256. From that alone it can check any block anyone ever shows it, against a dataset it has never seen. That is the exchange a Merkle tree offers. A little trust at the top buys certainty about everything below.

What a proof costs

A proof holds one sibling hash per level, and a tree over n blocks has log₂ n levels. Verification costs the same number of hashes. Both grow painfully slowly:

A billion blocks prove with thirty hashes. A Bitcoin block with two thousand transactions proves any one of them with eleven. That asymmetry is the whole point: one side stores everything, the other side stores almost nothing, and the root ties them together.

Where it earns its keep

Merkle trees show up wherever a small commitment must stand in for a large dataset:

• Bitcoin. Every transaction in a block feeds into a Merkle tree, and the block header carries only the root. A light wallet downloads no transactions at all. It verifies a payment from a proof.

• Git. A repository is a Merkle tree of blobs, trees, and commits, and the commit hash is the root. That is why rewriting one commit rewrites the hash of every commit after it.

• Certificate Transparency. Logs append every issued certificate to a Merkle tree and publish signed roots, so anyone can prove a certificate was logged.

• BitTorrent and IPFS. A file is named by the root of its chunk tree. Each downloaded chunk is verified against its path before it is used, so untrusted peers can serve the pieces.

• Ethereum. Every block commits to the entire state of the chain through a Merkle-style trie, so a light client can ask for one account balance and check the proof itself.

• Distributed databases. Dynamo and Cassandra compare per-range Merkle trees between replicas. Matching roots skip the data entirely, and mismatching subtrees mark the rows to repair.

What a Merkle tree cannot do

Three limits follow from the design:

• Prove absence. A proof shows that a block is in the tree. Showing that a block is nowhere in the tree needs a different structure, such as a sparse Merkle tree.

• Vouch for itself. A proof is only as honest as the root it checks against. The root must come from a source you trust: signed, published, or pinned ahead of time.

• Hold the data. The tree stores hashes, not blocks. Someone must keep the blocks, because the root cannot rebuild them.

Keep the two directions straight and the practice problems below get easier: hashing climbs from the leaves, and trust flows down from the root. Several are tree problems whose fast solution is a Merkle tree in disguise. Hash each subtree, then compare roots.