Merkle Trees — One Hash for Many Transactions
Meera runs a light client on her phone. She wants to be sure that Asha's payment really is inside block 812, but that block holds 3,000 transactions and she does not want to download them all. A Merkle tree lets a full node send her a proof of just twelve hashes, and lets her check that proof herself.
The rule
Hash in pairs, level by level, until one root remains.
Here is the tree for four transactions, A, B, C and D. H means "hash of", and + means the two hashes are joined end to end before hashing.
Root = H(H_AB + H_CD)
/ \
H_AB = H(H_A + H_B) H_CD = H(H_C + H_D)
/ \ / \
H_A H_B H_C H_D
| | | |
A B C D- Hash each transaction to get the leaves: H_A, H_B, H_C and H_D.
- Join neighbouring pairs and hash each pair: H_AB and H_CD.
- Repeat until a single hash is left. That is the Merkle root, and it goes in the block header.
When a level has an odd number of hashes, Bitcoin pairs the last one with a copy of itself; other chains use their own rule. Change any transaction and its leaf changes, then its parent, and so on up to the root. This is why the block hash, computed from the header, commits to every single transaction.
The shortcut
To prove one transaction is in a block, you need only the sibling hashes along its path to the root: one per level. With n transactions that is about log₂ n hashes, so doubling the number of transactions adds just one more hash to the proof.
Start from the leaf
Meera hashes transaction C herself to get H_C.
Sizes worth knowing: 4 transactions need 2 proof hashes, 8 need 3, 1,024 need 10, and about a million need 20. Block 812's 3,000 transactions fit under 4,096, which is 2 to the 12th power, so twelve hashes are enough.
The trap is thinking the proof must include the other transactions. It only ever needs their hashes, never their contents.
Drills
Answer fast — trust the rule.
What does the block header store from the Merkle tree?
A block holds 8 transactions. How many sibling hashes does a proof for one of them contain?
In the four-transaction tree, someone alters transaction B. Which hashes change?
A block grows from 1,024 to 2,048 transactions. How does the size of a Merkle proof change?
Remember
- Hash in pairs, level by level, until one root remains. The root sits in the header.
- Shortcut: a proof is one sibling hash per level, about log₂ n hashes in total.
- Trap: a proof needs the siblings' hashes, not the other transactions themselves.