Merkle Tree

A Merkle tree is a data structure that summarises a large set of data items in a single short value, called the Merkle root, by hashing the items in pairs, then hashing the results in pairs, and repeating until one hash remains. Changing any item changes the root, so the root acts as a fingerprint of the whole set. Every block on the Bitcoin and Ethereum networks commits to its transactions this way.

The structure is named after the American computer scientist Ralph Merkle, who described it in work on digital signatures in the late 1970s and patented it in 1982. Its great strength is that it lets someone prove that one item belongs to a set by showing only a handful of hashes, rather than the entire set. That property underpins light wallets, exchange proof of reserves, token distributions and many layer 2 systems.

Imagine a knockout tournament with 16 players. In each match two players meet and one name goes forward; after four rounds a single champion is left. If you want to show that a particular player took part, you do not need the full results sheet: you need only the opponents that player's line met on the way to the final, four names in all.

A Merkle tree works like that bracket, except that each "match" combines two fingerprints into one new fingerprint. The champion at the top is the Merkle root. To prove a transaction is in a block, you show the short path of fingerprints from it to the top, and anyone can recombine them to check that the result equals the published root.

On the Bitcoin blockchain, the leaves are the IDs of the block's transactions, each itself a double SHA-256 hash. The tree is built bottom-up:

1. The transaction IDs are arranged in the order the transactions appear in the block, starting with the coinbase.
2. Each adjacent pair is joined and hashed to give one parent hash. If a row has an odd number of entries, the last one is paired with a copy of itself.
3. The new row of parent hashes is paired and hashed in the same way, and the process repeats.
4. When one hash is left, that is the Merkle root, which is stored in the 80-byte block header.

Because the header includes the Merkle root and the header's own hash is what miners work on, altering, adding, removing or reordering any transaction would change the root, the header hash and the proof of work. This is one reason a confirmed transaction cannot be quietly edited. The odd-count duplication rule once allowed a subtle trick in which two different transaction lists produced the same root; Bitcoin software was patched in 2012 to detect it.

A Merkle proof (or Merkle branch) is the list of sibling hashes along the path from one leaf to the root. Its size grows with the logarithm of the number of items:

• $k$ is the number of hashes in the proof.
• $n$ is the number of items (leaves) in the tree.
• $\lceil \cdot \rceil$ means rounding up to the next whole number.

Worked example: a block with $n = 4{,}000$ transactions needs $k = \lceil \log_2 4{,}000 \rceil = \lceil 11.97 \rceil = 12$ hashes. At 32 bytes per hash, the proof is $12 \times 32 = 384$ bytes, compared with well over a megabyte for the full block.

Section 8 of the Bitcoin white paper uses this to describe simplified payment verification (SPV). A light wallet downloads only block headers, and asks a full node for the Merkle branch of a payment it cares about. Matching the branch to the header's root shows the payment is in a block buried under a given number of confirmations, without storing the whole chain. The trade-off is that the light client trusts that the chain it follows is valid.

The Ethereum blockchain uses a more elaborate structure, the Merkle Patricia trie, which combines a Merkle tree with a key-value index. Each block header commits to three of them: one for the global state (every account's balance, nonce, code and storage), one for the block's transactions and one for their receipts. Because the state root summarises every account, a client can prove an account balance or a smart contract storage value with a short proof. Researchers have proposed Verkle trees, which give smaller proofs, as a replacement.

Bitcoin's SegWit upgrade added a second Merkle tree over transactions including their signature data, committed inside the coinbase transaction so that older nodes were not affected. Outside blockchains, Merkle trees also underpin content-addressed storage such as the InterPlanetary File System.

Several common crypto practices rely on Merkle trees:

• Proof of reserves. An exchange publishes the root of a tree whose leaves are customers' balances, so each customer can check that their own balance was included. The method proves inclusion of liabilities a customer can see, not that every liability was included or that matching assets exist, so it is only one part of an audit.
• Token distributions. Projects distributing tokens to a large list of addresses, such as an airdrop or a whitelist sale, store only the root in a contract; each claimant submits a proof, which keeps gas costs low.
• Rollups and bridges. Optimistic rollups and ZK-rollups post state roots to the base chain, and users prove withdrawals against them.

A Merkle tree is only as strong as its hash function: a weak hash would let an attacker build a different set with the same root. A standard tree also proves that an item is present but not that one is absent, unless the leaves are sorted or a different design is used.

• Bitcoin: A Peer-to-Peer Electronic Cash System
• ethereum.org: Merkle Patricia Trie