Learning Objectives – after this chapter you will be able to:
- Build a Merkle tree and compute its Merkle root.
- Explain a Merkle proof and why it needs only about log₂(n) hashes.
- Describe Simplified Payment Verification (SPV) and light clients.
- Explain how Ethereum uses Merkle Patricia Tries.
What is a Merkle Tree?
A Merkle tree (hash tree) is a binary tree in which every leaf node holds the hash of a data item (e.g. a transaction) and every parent node holds the hash of its two children. The single hash at the top is the Merkle root.
- Invented by Ralph Merkle (patented in 1979, published in 1987–88) and added to time-stamping chains by Bayer, Haber and Stornetta in 1992.
- The Merkle root is stored in the block header. It acts as one fingerprint for all transactions in the block.
- Changing, adding, removing or re-ordering any transaction changes the Merkle root – and therefore the block hash.
Building a Merkle Tree (4 transactions)
| Merkle Root = H( HAB + HCD ) | |||
| HAB = H( HA + HB ) | HCD = H( HC + HD ) | ||
| HA = H(Tx A) | HB = H(Tx B) | HC = H(Tx C) | HD = H(Tx D) |
| Tx A | Tx B | Tx C | Tx D |
- Hash each transaction to form the leaves.
- Concatenate hashes in pairs and hash again to form the next level.
- If a level has an odd number of hashes, Bitcoin duplicates the last one so it can be paired.
- Repeat until a single hash – the Merkle root – remains.
Merkle Proof (Proof of Inclusion)
- To prove that Tx C is in the block, you do not need all transactions. You only need HD and HAB (the “sibling” hashes on the path to the root).
- The verifier computes HC → HCD = H(HC + HD) → root = H(HAB + HCD) and compares it with the Merkle root in the block header.
- A proof needs about log₂(n) hashes. For a block with 4,096 transactions, only 12 hashes are needed instead of 4,096.
| Transactions in block (n) | 8 | 1,024 | 4,096 | 1,000,000 |
|---|---|---|---|---|
| Hashes in Merkle proof (≈ log₂ n) | 3 | 10 | 12 | 20 |
Simplified Payment Verification (SPV) and Light Clients
- The Bitcoin white paper (Section 8) describes SPV: a user can verify payments without running a full node.
- An SPV/light client downloads only the block headers (80 bytes each in Bitcoin) and asks full nodes for Merkle proofs of the transactions it cares about.
- It trusts that the chain with the most work is valid, so it is less secure than a full node but needs very little storage – ideal for mobile wallets.
Merkle Patricia Trie in Ethereum
- Ethereum uses a Merkle Patricia Trie (MPT) – a combination of a Merkle tree and a Patricia (radix) trie – that supports efficient look-ups, inserts and updates by key.
- Each Ethereum block header contains three roots:
- stateRoot – all accounts and their balances, nonces, code hashes and storage roots;
- transactionsRoot – all transactions in the block;
- receiptsRoot – all transaction receipts (status, logs).
- Each contract account also has its own storage trie, whose root is the account’s
storageRoot(Chapter 9).
Key Takeaways
- A Merkle root summarises every transaction in a block in one hash.
- Merkle proofs need only ~log₂(n) hashes, enabling SPV light clients.
- Ethereum’s Merkle Patricia Tries commit to state, transactions and receipts.
Question / Answer (15 questions)
Answer : A Merkle tree is a binary hash tree in which the leaves are hashes of data items (such as transactions) and each internal node is the hash of its two children. The top hash is called the Merkle root.
Answer : Ralph Merkle, who patented the idea in 1979 and published it in a paper on digital signatures in 1987–88.
Answer : The Merkle root is the single hash at the top of the Merkle tree. It is stored in the block header and commits to every transaction in the block.
Answer : Hash every transaction to form the leaves; pair adjacent hashes, concatenate each pair and hash it to form the next level; repeat level by level until one hash, the Merkle root, remains.
Answer : It duplicates the last hash at that level so that it can be paired with itself, and then continues building the tree.
Answer : The leaf hash of that transaction changes, which changes every parent hash on its path up to the root. The Merkle root changes, and therefore the block hash also changes.
Answer : A Merkle proof is the list of sibling hashes along the path from a leaf to the root. With it, anyone can recompute the root and verify that a specific transaction is included in a block, without downloading all transactions.
Answer : About log₂(1,024) = 10 hashes.
Answer : H(D), the sibling of C, and H(AB), the sibling of H(CD). The verifier computes H(C), then H(CD), then the root, and compares it with the header.
Answer : SPV, described in Section 8 of the Bitcoin white paper, lets a client verify that a transaction is in the blockchain by downloading only block headers and requesting Merkle proofs from full nodes.
Answer : Advantages: very small storage and bandwidth, suitable for mobile devices. Limitations: they do not validate every transaction themselves and rely on full nodes and on the assumption that the most-work chain is valid.
Answer : It is the data structure Ethereum uses to store key-value data. It combines a Patricia (radix) trie, which allows efficient key look-ups and updates, with Merkle hashing, which gives a single root hash that commits to all the data.
Answer : stateRoot (all account states), transactionsRoot (all transactions in the block) and receiptsRoot (all transaction receipts).
Answer : Each contract has its own storage trie (a Merkle Patricia Trie). The root hash of that trie is stored in the account’s storageRoot field, which in turn is part of the global state trie.
Answer : They allow compact proofs of inclusion and integrity, so light clients, cross-chain bridges and Layer-2 systems can verify specific data without processing the entire blockchain.
MCQ Test : Check Your Understanding (5 questions)
Select an option and press Check Answer, or answer all questions and press Submit Test to see your score. Each answer comes with an explanation.
Bibliography/References
The notes, questions and MCQs on this page are original explanations written for this course. The works listed below were consulted and are cited for attribution and further reading. Product names, logos and trademarks belong to their respective owners. Short quotations, where used, are marked and attributed.
- Merkle, R. C. (1988). A digital signature based on a conventional encryption function. In Advances in Cryptology – CRYPTO ’87, LNCS 293 (pp. 369–378). Springer. https://doi.org/10.1007/3-540-48184-2_32
- Bayer, D., Haber, S., & Stornetta, W. S. (1993). Improving the efficiency and reliability of digital time-stamping. In Sequences II (pp. 329–334). Springer. https://doi.org/10.1007/978-1-4613-9323-8_24
- Nakamoto, S. (2008). Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf
- ethereum.org. (n.d.). Merkle Patricia Trie. Ethereum Developer Documentation. https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/
- Wood, G. Ethereum: A Secure Decentralised Generalised Transaction Ledger (Ethereum Yellow Paper). https://ethereum.github.io/yellowpaper/paper.pdf
- Bitcoin Project. (n.d.). Bitcoin Developer Guide. developer.bitcoin.org. https://developer.bitcoin.org/devguide/
- Narayanan, A., Bonneau, J., Felten, E., Miller, A., & Goldfeder, S. (2016). Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton University Press. ISBN 978-0-691-17169-2.