TECHNICAL_DOC // CRYPTOGRAPHY / MERKLE-PROOFS
MERKLE
PROOFS
PROOFS
A Merkle proof allows a party to cryptographically prove that a specific transaction
is included in a block by providing only a logarithmic number of hash values —
without requiring the full block. This is the foundation of SPV (Simplified Payment
Verification), allowing lightweight clients to verify payments trustlessly.
THE_MERKLE_TREE_STRUCTURE
BUILDING THE TREE (4 TRANSACTIONS)
Transactions: TxA TxB TxC TxD
Leaf hashes: HA HB HC HD
(each = SHA256d(tx_bytes))
Level 1: HAB = SHA256d(HA || HB)
HCD = SHA256d(HC || HD)
Root: Merkle Root = SHA256d(HAB || HCD)
(stored in block header)
[ROOT]
/ \
[HAB] [HCD]
/ \ / \
[HA] [HB] [HC] [HD]
TxA TxB TxC TxD
PROOF FOR TxC
MERKLE PROOF — PROVING TxC IS INCLUDED
Proof data (provided by full node):
1. HC (hash of TxC itself)
2. HD (sibling hash, right)
3. HAB (uncle hash, left)
Verifier (SPV node) recomputes:
HCD = SHA256d(HC || HD)
ROOT = SHA256d(HAB || HCD)
If ROOT matches block header's Merkle Root:
→ TxC is provably included in this block ✓
Data transmitted: 3 hashes × 32 bytes = 96 bytes
vs downloading full block: ~1,000,000 bytes
PROOF_SIZE_EFFICIENCY
Logarithmic Proof Size
O(log n)
A Merkle proof requires only log₂(n) hashes to prove inclusion in a block with n transactions — extremely efficient as block size grows.
Transactions Proof size vs Full block
4 2 hashes = 64 bytes
16 4 hashes = 128 bytes
256 8 hashes = 256 bytes
2000 11 hashes = 352 bytes vs ~2 MB block
1,000,000 20 hashes = 640 bytes vs ~1 GB hypothetical
A typical Bitcoin block (~2000 txs):
Proof: ~11 hashes = 352 bytes
Block: ~1,500,000 bytes → 4,261× smaller proof
SPV — Simplified Payment Verification
BIP 37
SPV clients (light wallets) download only block headers and request Merkle proofs for relevant transactions. They can verify inclusion without downloading full blocks.
SPV Verification Process:
1. Download all block headers (~68 MB for full chain)
2. Verify proof-of-work chain (headers only)
3. Request Merkle proof for transaction of interest
via merkleblock message (BIP 37)
4. Verify proof against block header's Merkle Root
5. Confirm: tx included in a block with N confirmations
SPV assumption: the longest PoW chain contains valid txs.
Weakness: cannot detect invalid transactions (no UTXO set check).
Bloom filters (BIP 37) used to request relevant proofs privately.
TERMINOLOGY_INDEX
Merkle Proof
A set of sibling hashes allowing verification that a transaction is included in a block without the full block.
Merkle Root
The single 32-byte hash at the top of the Merkle tree, committing to all transactions in a block.
SPV
Simplified Payment Verification. Light clients verify inclusion via Merkle proofs without downloading full blocks.
merkleblock
A Bitcoin P2P message type that delivers a partial Merkle tree proof for requested transactions.
BIP 158
Compact block filters. Privacy-preserving alternative to BIP 37 bloom filters for finding relevant transactions.
SHA256d
Double SHA-256: SHA256(SHA256(x)). Used for all Merkle tree hashing in Bitcoin.