Merkle trees let a blockchain summarise all transactions of a block in one 32-byte hash (the Merkle root) stored in the block header, so that any change in any transaction is detected instantly and a single transaction can be proved to be in a block using only about \(\log_2 n\) hashes.
What a Merkle tree is. A binary tree of hashes. Leaves are hashes of transactions; each parent is the hash of its two children concatenated; the top is the Merkle root.
Root = H(H12 + H34)
/ \
H12 = H(H1+H2) H34 = H(H3+H4)
/ \ / \
H1=H(T1) H2=H(T2) H3=H(T3) H4=H(T4)(If the number of transactions is odd, Bitcoin duplicates the last hash.)
Why they are important
- Data integrity / tamper detection: changing even one bit of T3 changes H3, then H34, then the root. Since the root is in the block header, which is hashed into the next block, tampering is immediately visible.
- Efficient proof of membership (Merkle proof): to prove T3 is in the block, only H4 and H12 are needed: compute H3, then H34, then the root, and compare. For 1,000,000 transactions only about 20 hashes are needed instead of all transactions.
- Light clients (SPV, Simplified Payment Verification): mobile wallets store only block headers (80 bytes each in Bitcoin) and verify their payments with Merkle proofs, without downloading the full blockchain.
- Small block headers: however many transactions a block has, the header contains just one fixed-size root, so mining (hashing the header) is fast.
- Efficient synchronisation: nodes can compare roots and sub-tree hashes to find exactly which data differs.
- State storage: Ethereum uses a variant (Merkle Patricia trie) to commit to the whole account state, transactions and receipts.