How a Merkle tree is built
Start with a list of items, for example the transactions in a block. Hash each one: these hashes are the leaves. Then hash the leaves in pairs, hash those results in pairs, and repeat until one hash remains. That final value is the Merkle root.
RFC 6962, the standard behind Certificate Transparency logs, writes the rule down precisely. A leaf hash is SHA-256(0x00 || data) and an interior node is SHA-256(0x01 || left || right). The different one-byte prefixes stop anyone from passing off an interior node as a leaf.[1]
Change one byte in any item and its leaf hash changes, which changes its parent, and so on up to the root. The root is therefore a fingerprint of the whole list in a fixed 32 bytes, whether the list holds 4 items or 4 million.
The hash function varies by system. Bitcoin's developer reference specifies double SHA-256, written SHA256(SHA256()), for its Merkle root. The shape of the tree changes the proof format, but the security argument is the same everywhere: forging a proof means finding a hash collision.[3]
Why the root is useful: inclusion proofs
The point of the tree is the proof. To show that item X is in the list, you do not send the list. You send X plus the sibling hash at each level on the path from X to the root. The verifier hashes upward and checks that the result equals the root they already trust.
RFC 6962 calls this an audit path and defines the exact algorithm for computing and checking it. Certificate Transparency relies on it so browsers can confirm a TLS certificate was publicly logged without downloading the log.[1]
The proof grows with the height of the tree, not its width. A tree with n leaves has a height of about log2(n), so each doubling of the data adds one hash to the proof.
RFC 6962 defines a second proof type as well: a consistency proof, which shows that a newer version of a log contains everything in an older version, with entries only appended. Browsers and monitors use it to catch a log operator that quietly rewrites history. Blockchains get a similar property from linking block headers, and the idea is the same: a short proof, checked against roots you already hold.[1]
A worked example with real numbers
Take a block with 8 transactions, T1 to T8. The tree has 8 leaves, 4 parents, 2 grandparents and 1 root: 15 hashes in total and a height of 3.
To prove T3 is in the block, the prover sends three hashes: the hash of T4 (T3's sibling), the parent of T1 and T2, and the grandparent covering T5 to T8. The verifier computes hash(T3), combines it with hash(T4), combines that with the T1-T2 parent, then with the T5-T8 node, and compares the result with the root in the block header.
Scale it up. With 1,048,576 leaves (2 to the 20th power), the proof is 20 hashes. At 32 bytes each that is 640 bytes, compared with shipping every transaction. That ratio is why light clients and airdrop claims are practical.
| Leaves | Proof length | Proof size |
|---|---|---|
| 8 | 3 hashes | 96 bytes |
| 1,024 | 10 hashes | 320 bytes |
| 1,048,576 | 20 hashes | 640 bytes |
| 1,073,741,824 | 30 hashes | 960 bytes |
Merkle trees in Bitcoin
Satoshi Nakamoto's 2008 whitepaper uses a Merkle tree in two places. Section 7 hashes a block's transactions into a Merkle tree so that old spent transactions can be pruned while the block hash stays valid, with only the root kept in the header.[2]
Section 8 describes Simplified Payment Verification: a light client keeps only block headers and asks for the Merkle branch that links a transaction to the header's root. Section 7 puts a header without transactions at about 80 bytes, or 4.2 MB per year at one block every 10 minutes.[2]
Bitcoin's developer reference confirms the header is serialized in an 80-byte format and that the merkle root field is a SHA256(SHA256()) hash derived from the hashes of all transactions in the block. Change a single transaction and the header hash changes, which breaks the proof of work.[3]
Merkle Patricia Tries in Ethereum
Ethereum needs more than a list: it needs a key-value map of every account that can be updated block by block. Its answer is the Merkle Patricia Trie, which combines a Merkle tree with a radix trie. Nodes are stored in a database keyed by keccak256(rlp(value)), so knowing the root hash guarantees the integrity of everything under it.[4]
Paths are walked one nibble (4 bits) at a time, so a branch node can point to 16 children plus a value, stored as a 17-element array. Each block header carries three such roots: stateRoot, transactionsRoot and receiptsRoot.[4]
This design has a cost. Proofs in a 16-ary trie are large, because each level includes up to 15 sibling hashes. Ethereum's roadmap proposes Verkle trees to shrink these proofs enough for stateless clients, which verify blocks using a witness that arrives with the block instead of a full local copy of state.[5]
Tries inside tries: accounts and storage
Ethereum's state trie does not stop at balances. Each account is a four-item array of nonce, balance, storageRoot and codeHash, and storageRoot is itself the root of a separate trie holding that contract's data. Every contract therefore has its own storage trie, nested under the global state root.[4]
Ethereum.org's walkthrough shows the practical side. To read a mapping entry, you compute the storage position as keccak256 of the key and the slot number, each left-padded to 32 bytes, then query it with eth_getStorageAt. The value comes back as a 32-byte hex word; in the page's example it ends in 04d2, which is 1,234.[4]
The transactions and receipts tries are simpler. Each block has its own receipts trie keyed by rlp(transactionIndex), and it is never updated after the block is built. Only the state trie changes from block to block.[4]
Size is the reason for the roadmap work. Ethereum.org explains that witnesses from Merkle tries are too large to broadcast safely between peers within a 12-second slot, because every level of the path carries its sibling nodes. Verkle trees shorten the path from leaf to root and remove the need to send siblings.[5]
Merkle proofs in smart contracts and airdrops
Airdrops and allowlists often use Merkle trees on chain. The project publishes one 32-byte root in the contract. Each eligible address later submits its own proof, and the contract checks it. Storing a root costs one storage slot instead of one slot per recipient.
OpenZeppelin's MerkleProof library provides verify and processProof functions and a multiproof variant for proving several leaves at once. Its documentation warns against using leaf values that are 64 bytes long before hashing, because a 64-byte leaf can be confused with a pair of interior hashes: the same second-preimage issue RFC 6962 fixes with prefixes.[6]
The practical rule for builders: follow that warning. Hash leaves before building the tree, or use a different hash for leaves, and never let a user-supplied 64-byte value become a leaf directly.[6]
One detail trips up many first implementations: pair order. OpenZeppelin's Hashes library provides commutativeKeccak256, which hashes a sorted pair of 32-byte values. Sorting means the proof does not need to say whether each sibling sits on the left or the right, but the off-chain tree builder must sort the same way or every proof will fail.[6]
See also: OpenZeppelin · Best crypto airdrop trackers
The bottom line
If you remember one number, make it log2(n): a Merkle proof for a million items is 20 hashes, 640 bytes. That is what lets a phone wallet check a Bitcoin payment from 80-byte headers and lets a contract verify an airdrop claim against one stored root. When you build with Merkle proofs, the tree is rarely the bug; the leaf encoding is.
Educational content, not financial advice. Crypto assets are volatile; do your own research.