Merkle trees: proving one leaf without the whole tree

The problem: proving you're in a book you can't carry

Picture the village ledger as a single book that has grown to the size of a building. Every payment ever made is written somewhere inside it. You made one small payment yesterday, and you want to prove it was recorded — but you carry only a phone, and the book weighs as much as a truck. Copying the whole thing to check one line is absurd. Yet this is exactly the situation a crypto wallet is in: an Bitcoin or Ethereum block can hold hundreds or thousands of transactions, and the chain behind it holds hundreds of millions. Your phone cannot store all of that, but it still needs to confirm "yes, my 0.2 ETH really landed in block #18,000,000."

The Merkle tree, invented by Ralph Merkle in 1979, is the data structure that makes this possible. The trick in one sentence: instead of comparing the whole book, you compare one tiny number that the entire network already agreed on — the Merkle root — and you prove that your transaction "rolls up" to exactly that number. The proof you need is only a few hundred bytes, no matter how big the block is.

Building a Merkle tree, pair by pair

Let's build one with four transactions, A, B, C, D. Throughout, write `H(x)` for "hash of x." (Bitcoin actually applies SHA-256 twice — written SHA-256d — but the shape is identical, so we'll just say `H`.) The tree grows from the bottom up: hash each transaction into a leaf, then keep hashing pairs together until a single value survives at the top.

1. Hash each transaction into a leaf. HA = H(A), HB = H(B), HC = H(C), HD = H(D). Four leaves, each 32 bytes.
2. Hash the leaves in pairs. HAB = H(HA ‖ HB) and HCD = H(HC ‖ HD), where ‖ means "join the two byte strings, then hash." Two leaves became one parent each.
3. Hash that pair. ROOT = H(HAB ‖ HCD). One value is left standing — the Merkle root. It is a 32-byte fingerprint of all four transactions at once.

# H(x) = hash of x.   ||  means "join the two byte strings, then hash".
function merkle_root(transactions):
    layer = [ H(tx) for tx in transactions ]    # the leaf row
    while len(layer) > 1:
        if len(layer) is odd:
            layer.append(layer[-1])              # duplicate the lonely last node
        parents = []
        for i in range(0, len(layer), 2):
            parents.append( H(layer[i] || layer[i+1]) )
        layer = parents
    return layer[0]                              # the Merkle root

What if there's an odd number of nodes in a row — say five? The common rule (Bitcoin's) is to duplicate the last node so it can pair with itself, as the pseudocode does. It's a small detail, but it has bitten real chains, as we'll see at the end.

The Merkle proof: a path of siblings

Here is the magic. To prove transaction B is in the tree, you do not need C, D, or even A's full transaction. You need exactly the hashes that sit beside B on its way up to the root — its siblings along the path. For our four-leaf tree, the proof for B is just two hashes: HA (B's sibling at the leaf level) and HCD (the sibling one level up). That's it.

1. Start at your own leaf: h = H(B).
2. The proof says HA is on the left, so combine: h = H(HA ‖ h) = H(HA ‖ HB) = HAB.
3. The proof says HCD is on the right, so combine: h = H(h ‖ HCD) = H(HAB ‖ HCD) = ROOT.
4. Compare your computed h against the root the network already trusts. If they match, B is provably in the tree — and you never saw A, C, or D.

# proof = ordered list of (sibling_hash, position), from leaf up to root
function verify(tx, proof, known_root):
    h = H(tx)                        # start at our leaf
    for (sibling, position) in proof:
        if position == "left":       # sibling sits on the left
            h = H(sibling || h)
        else:                        # sibling sits on the right
            h = H(h || sibling)
    return h == known_root           # true  ->  tx is provably included

Count the work. Four leaves needed 2 hashes. The pattern is log₂(n): the proof for a tree of n leaves is about log₂(n) sibling hashes deep. A block of 1,024 transactions needs a 10-hash proof; one with 1,048,576 (~a million) needs just 20 hashes. At 32 bytes each, that's a 640-byte proof to pin down one transaction among a million — versus megabytes to download them all. That is why Merkle trees are everywhere.

Why you can't fake a proof

Suppose you want to fool a wallet into accepting a transaction X that was never in the block. You'd have to hand it a list of sibling hashes that, when folded up, still produce the network's agreed root. But you don't get to choose the root — it's already fixed. So you'd need to find inputs to H that collide with the real intermediate values along the path. Finding such a collision in SHA-256 takes on the order of 2¹²⁸ work — utterly infeasible. The security of every Merkle proof rests entirely on the collision resistance (and second-preimage resistance) of the underlying hash. Break the hash and you break the tree; otherwise the proof is as good as math.

Where the root lives: the block header and light clients

A Merkle tree would be a clever toy if the root sat nowhere important. Its real job: the root is stored in the block header. In Bitcoin the header is just 80 bytes, and 32 of them are the Merkle root of every transaction in the block. When miners and nodes agree on a header, they are — via that one 32-byte field — agreeing on the entire set of transactions, without anyone having to compare the transactions one by one.

This is what lets a light client (Satoshi called it SPV — Simplified Payment Verification — in §8 of the Bitcoin whitepaper) live on a phone. It downloads only the chain of 80-byte headers, not the blocks. To check your payment, it asks any full node for a Merkle proof (a "branch") for your transaction, then verifies it against the root in the relevant header. The beautiful part: you don't have to trust the node that gives you the proof. A lying node can't forge a valid proof — a bad one simply won't fold up to the header's root. You only trust the header chain itself (the one with the most work or stake behind it).

Ethereum adds a twist. Its header carries three roots — `transactionsRoot`, `stateRoot`, and `receiptsRoot` — and each is the root of a Merkle Patricia trie, a Merkle tree married to a key→value lookup. That marriage lets you prove not just "transaction X is included," but "account X has balance Y in the world state right now," and update a single account efficiently without rebuilding the whole tree. Same core idea — a root that fingerprints a whole structure — extended from a flat list to a full key-value database.

Gotchas the real chains hit

That innocent "duplicate the last node" rule for odd rows has a sharp edge. In 2012, Bitcoin discovered CVE-2012-2459: by duplicating transactions in just the right way, an attacker could build two different transaction lists that produce the same Merkle root. Because nodes index a block partly by that root, a malicious peer could relay a mutated, invalid copy of a valid block; nodes that accepted it would mark the real block's hash as bad and refuse it — a denial-of-service. The fix was to explicitly reject any block whose Merkle tree contains duplicated hash pairs. A reminder that a one-line edge case in a tree can become a network-wide bug.

Two more practical notes. First, Bitcoin hashes with double SHA-256 and stores hashes in internal little-endian byte order, so naively concatenating the hex you see in a block explorer will give the wrong root — a classic first-implementation bug. Second, if you sort the leaves and store them in order, you gain a bonus: a sorted Merkle tree can also prove non-inclusion ("this address is definitely not in the set") by showing the two neighbors it would fall between.