Blockchain/Level II · Mechanics/2.3 Blocks and the chain/Lesson 2
Merkle trees
The 32-byte fingerprint that binds thousands of transactions
MaterialsA block explorer with Merkle branch visualizationFour short alphanumeric labels (A, B, C, D)A double SHA-256 hashing tool
Wonder
- How does a single hash value certify the inclusion of four thousand distinct transactions?
- Why did Satoshi choose to pair a lone last entry with itself, and what did that choice cost?
- What specific vulnerability did the duplicate-pairing rule introduce in Bitcoin’s early implementation?
Explore
- Ralph Merkle filed a patent on the binary hash tree in 1979 (granted 1982), a data structure designed to summarize large datasets efficiently. In Bitcoin, this architecture reduces thousands of transaction identifiers to a single 32-byte value known as the Merkle root. This root is embedded directly into the 80-byte block header, creating an immutable cryptographic commitment to every transaction within that specific block.
- Construction proceeds recursively from the bottom up. Transaction IDs are concatenated in pairs and processed through double SHA-256 hashing to generate parent nodes. This pairing continues level by level until a single root hash remains. If any level contains an odd number of entries, the final entry is paired with itself to maintain the binary structure, ensuring the tree balances correctly at every stage.
- The logarithmic nature of this structure enables simplified payment verification (SPV). A light client does not download full blocks; instead, it requests a Merkle branch from a full node. This branch consists only of the sibling hashes along the path from a specific transaction to the root. For a block with 4,000 transactions, this proof requires approximately twelve hash values, a fraction of the total data size.
- By combining its own transaction hash with these provided siblings, a light client recomputes the Merkle root and compares it against the value in the downloaded block header. If they match, inclusion is verified cryptographically without storing the entire chain. This mechanism allows mobile wallets to function securely on devices with limited storage and processing power.
- Segregated Witness (SegWit), activated in August 2017, introduced a second Merkle tree structure. While the original tree commits to transaction IDs, the witness tree commits to witness transaction IDs. The root of this second tree is not stored in the header; it is committed in an OP_RETURN output of the coinbase transaction, which old nodes treat as ordinary data, preserving compatibility.
- The self-pairing rule hid a flaw (CVE-2012-2459). Because a lone last entry is paired with itself, a transaction list ending in a duplicated pair produces the same Merkle root as the list without the duplicate. An attacker could relay that malformed variant of a valid block; nodes that rejected it could mark the genuine block’s hash as invalid and fall out of step with the network. The 2012 fix makes nodes recognize the pattern instead of caching the block as bad.
Key facts
- The Merkle root is a single 32-byte hash stored in the block header that commits to all transactions in the block.
- Bitcoin uses double SHA-256 hashing at every level of the Merkle tree construction.
- An odd number of entries at any level is handled by pairing the last entry with itself.
- A Merkle proof for a transaction in a large block typically requires around twelve sibling hashes.
- SegWit added a second Merkle tree over witness transaction IDs, committed in the coinbase transaction.
- CVE-2012-2459 was a bug related to duplicate-pairing logic in early Bitcoin Core versions.
Exercise nine, six, three, one
9CollectList 9 real-world systems or protocols that utilize hash trees for data integrity verification.
6ClusterGroup the 9 into 6 by what they protect: files, software packages, certificates, databases, blockchains, or other.
3DistillReduce the 6 groups to 3 core reasons why a logarithmic proof structure is preferred over linear scanning for large datasets.
1CrystallizeWrite one sentence explaining how a single bit change in a leaf node alters the entire root hash.
Fact check
Dates, figures and claims checked against the published sources listed below.