Merkle Trees & Merkle Proofs

A Receipt of Receipts

A hash is a fixed-size fingerprint of some data: change one character of the input and the fingerprint changes completely. A Merkle tree applies this idea in layers. Hash every item, join the fingerprints in pairs and hash each pair, then repeat until a single fingerprint remains, called the root. Change any item and the change travels upward, altering every fingerprint above it and the root. The Bitcoin whitepaper illustrates this with four transactions: Hash0 to Hash3 sit at the bottom, Hash01 and Hash23 above them, and one Root Hash on top.

Why a Block Carries One Root

A Bitcoin block header is only 80 bytes, yet the block can hold thousands of transactions. The header carries just the Merkle root, built from the transaction ids. According to the Bitcoin developer reference, this ensures that none of the transactions can be modified without modifying the header. When a level has an odd number of hashes, Bitcoin's rule is to pair the last hash with a copy of itself. A node that keeps the headers therefore holds a compact commitment to the transactions in every block.

Checking One Payment Without the Whole Block

A phone wallet cannot download every block. The whitepaper's answer, simplified payment verification, is to keep only the block headers of the longest chain and to obtain the Merkle branch, the handful of hashes linking one transaction to the root in its block. The wallet cannot check the transaction itself, but it can see that the transaction sits in a block of the chain and that more blocks have been added after it. The whitepaper warns that this method can be fooled by an attacker's fabricated transactions for as long as the attacker overpowers the network.

1. Worked example with four transactions: hash each one to get Hash0, Hash1, Hash2 and Hash3.
2. Join Hash0 with Hash1 and hash the pair to get Hash01; do the same with Hash2 and Hash3 to get Hash23.
3. Join Hash01 with Hash23 and hash them to get the Root Hash stored in the block header.
4. To prove the fourth transaction, send Hash2 and Hash01; the checker recomputes Hash3, Hash23 and the root, then compares the result with the header.

Branches, Audit Paths and Hashing Rules

A Merkle proof is the list of sibling hashes along the path from a leaf to the root. RFC 6962, published in June 2013 for Certificate Transparency and since obsoleted by RFC 9162, calls it an audit path: the shortest list of additional nodes needed to recompute the root. A verifier combines the leaf with one sibling per level and compares the result with a root it already trusts. With n leaves the path holds about log2(n) hashes, so, for example, a tree of 4,096 leaves needs 12 hashes of 32 bytes each, 384 bytes, instead of 4,096 leaves. Bitcoin's documented rule joins two 32-byte hashes as 64 raw bytes, applies SHA256 twice, and pairs a last odd hash with itself.

Light Clients: From Bloom Filters to Block Filters

BIP-37, assigned in October 2012, let a light client send a Bloom filter to a full node, which answered with a merkleblock message: a block header plus part of a Merkle tree proving that the matching transactions were in the block. BIP-37 itself notes that remote peers may correlate transactions with IP addresses, and that lying through omission remains possible. BIP-157, marked Deployed as of October 2026, says BIP-37 has known flaws for security and privacy and that most implementations offer virtually 'zero privacy'. It proposes compact filters that the client downloads and tests locally.

Ethereum: Tries, eth_getProof and Airdrop Claims

Ethereum stores its state in a modified Merkle-Patricia trie whose branch nodes have up to 16 children. According to ethereum.org, a block header carries roots from the state, transactions and receipts tries. EIP-1186 defines the eth_getProof method, which returns an account's values with an accountProof of RLP-encoded trie nodes starting at the stateRoot node. The EIP says that, combined with a stateRoot from a block header, this enables offline verification of any account or storage value.

The Uniswap merkle-distributor contract, as read in October 2026, shows the pattern for token claims. It stores one immutable merkleRoot, and its claim function takes an index, account, amount and Merkle proof. The contract hashes the index, account and amount into a leaf, checks the proof against the root, reverts with InvalidProof if the check fails, and records the index in a bitmap so it cannot be claimed twice. The full recipient list is never stored in the contract.

Where the Construction Breaks

A comment in Bitcoin Core's source warns anyone designing a new system that its Merkle algorithm has a serious flaw related to duplicate txids, tracked as CVE-2012-2459. When a level has an odd number of hashes, the last one is duplicated before the next level is computed, so different transaction lists can produce the same root: the comment shows that the lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] give the same root. An attacker could send a modified block with the same root and block hash, and a node that marked it permanently invalid would refuse the unmodified version. As read in October 2026, the defence is to detect identical hashes paired at the end of a list and treat the block as having an invalid Merkle root.

Domain Separation and the Shape of the Tree

RFC 6962, published in June 2013, takes a different route. It hashes a leaf as SHA-256 of a 0x00 byte followed by the data, and an interior node as SHA-256 of a 0x01 byte followed by its two children, a domain separation it says is required to give second preimage resistance. For n leaves it splits at k, the largest power of two smaller than n, so the shape is uniquely determined by n and nothing is duplicated. The Bitcoin developer reference, read in October 2026, describes no such prefix bytes and does duplicate a trailing hash, which is why the duplicate check above exists.

Append-Only Variants: Mountain Ranges

The Grin documentation, read in October 2026, describes Merkle Mountain Ranges as an alternative to Merkle trees, which rely on perfectly balanced binary trees: a list of such trees, or one tree truncated at the top right, that is strictly append-only and adds a parent as soon as two children exist. Its illustration, read in October 2026, has 11 inserted leaves and a total size of 19.

Proof Size and the Move Away from Hexary Tries

Wider nodes cost more siblings per level. As read in October 2026, EIP-7864 (status Draft) uses a tree of 2^32 entries to show this: its formula gives 15 x 32 x log16(2^32) = 3,840 for one branch of a hexary tree. The same method for a binary tree gives 1 sibling x 32 bytes x 32 levels = 1,024 bytes, a figure calculated for this topic and not stated in the EIP. EIP-6800 (status Stagnant as of October 2026) proposed Verkle trees instead, quoting a witness close to 3 kB per account in the hexary trie against about 200 bytes for Verkle. EIP-7864 also says its hash function is not final.