Merkle Trees: Transaction Integrity at Scale

A Bitcoin block contains ~2000 transactions. To prove transaction T is included without downloading all 2000 transactions, we need a compact proof. Merkle trees solve this: proof size = O(log n) hashes instead of O(n) transactions.

Leaves: SHA256d (double-SHA256) of each transaction. Parent: SHA256d(left_child_hash || right_child_hash). Repeat until one root hash. If odd number of nodes, duplicate the last node. The root is the Merkle root stored in the block header (32 bytes).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

To prove transaction T is at position i: provide the sibling hashes at each level from T's leaf to the root (O(log n) hashes). The verifier recomputes the root from T and the sibling path. If the computed root matches the block header Merkle root, T is proven.

1024 transactions → Merkle proof = 10 hashes = 320 bytes. Full block = ~1 MB. SPV clients download only the 80-byte header + 320-byte Merkle proof per transaction they care about — 99.97% bandwidth saving compared to downloading the full block.

If any transaction in the tree changes, its leaf hash changes, propagating up to change the Merkle root. The altered root no longer matches the block header (which is PoW-sealed). Any modification is detectable by computing the root from the transactions.

Ethereum extends Merkle trees with tries (Patricia Merkle Trie): a hex-prefix encoded radix trie where each node is Merkle-hashed. Used for: state trie (account balances), transaction trie, receipt trie. Enables efficient proof of account state without full node data.

A Merkle Mountain Range (MMR) is an append-only Merkle structure for log-like data. New elements are appended; peaks (roots of power-of-2 sized subtrees) are maintained. Used in Grin/MimbleWimble and ZCash for efficient compact proofs over an append-only log.

Verkle trees replace Merkle trees in Ethereum's roadmap (EIP-6800): use vector commitments (KZG polynomial commitments) instead of hashes. Proof size: O(1) vs O(log n) for Merkle. Allows stateless clients to verify state without storing the full trie.

Certificate Transparency (RFC 6962) uses an append-only Merkle log: each CA-issued certificate is a leaf. Inclusion proofs verify a cert was logged. Consistency proofs verify the log was append-only (no deletion or insertion). Browser vendors verify SCTs via this log.

Git trees (directory snapshots) are Merkle trees: each tree node hashes its file blobs and subtrees. A commit hash uniquely identifies the entire codebase state. This is why git checkout always gives exactly the same files.

How many hashes does a Merkle proof require to prove inclusion in a tree of 1024 leaves?

Merkle trees enable O(log n) inclusion proofs. Bitcoin stores the Merkle root in block headers; SPV clients use proofs. Ethereum extends to Patricia Merkle Tries. Verkle trees will replace Merkle trees for O(1) proofs. Next: Proof of Work mining and difficulty.