The idea: one hash in the header stands for every transaction
A Bitcoin block has two parts: an 80-byte header and the list of transactions, often a megabyte or more. The header does not list the transactions. It holds one 32-byte value, the Merkle root, computed from all of them. Because the proof of work is done on the header, that one hash locks in the whole list: change any transaction and the root no longer matches.
The root comes from a Merkle tree. The leaves are the txids, the hash of each transaction. Each parent is the hash of its two children put side by side, H(left + right), and the hashing goes up level by level until one hash is left. On the page, H is a 16-bit hash shown as 4 hex digits so you can read every value; Bitcoin uses SHA-256d (SHA-256 applied twice) with 32-byte results.
Building the tree
The miner orders the transactions (the coinbase transaction, which pays the miner, is always first), hashes each into its txid, then hashes pairs: 8 txids give 4 parents, then 2, then the root (Demo: build the tree). Changing a single byte of a transaction gives a completely different txid, and the change carries up to the root.
Odd counts: the last hash is paired with itself
A level with an odd number of hashes has nothing to pair the last one with. Bitcoin's rule is to duplicate the last hash: it is hashed together with a copy of itself. With 5 transactions this happens twice: at the txids (a5ca is paired with a5ca) and at the next level (8db2 with 8db2) (Demo: odd count). The copies are drawn grey on the canvas.
This rule has a known quirk: a block whose last two transactions are the same gives the same root as the block without the repeat. Bitcoin Core had to reject such blocks explicitly (CVE-2012-2459), and newer designs pad differently.
SPV: proving one transaction with a few hashes
A phone wallet cannot download every block. A light client using SPV (simplified payment verification, section 8 of the Bitcoin paper) downloads only the chain of headers, 80 bytes per block, and checks their proof of work. To learn that a payment is in a block, it asks a full node for a Merkle proof (also called a Merkle branch): the transaction plus the sibling hash at every level of its path.
The client hashes the transaction to get its txid, then combines it with each sibling in turn, on the left or the right as the position says, until it reaches a root. If that root equals the merkle root in its header, the transaction is in the block (Demo: SPV proof for tx5). It never needed the other transactions.
| Transactions in the block | Hashes in the proof | Proof size (32-byte hashes) |
|---|---|---|
| 5 to 8 (the page) | 3 | 96 bytes |
| 1,000 | 10 | 320 bytes |
| 4,000 | 12 | 384 bytes |
| 1,000,000 | 20 | 640 bytes |
The proof grows with log2(n), rounded up. A duplicated hash can be a sibling too: for tx4 in a 5-transaction block, the siblings at levels 0 and 1 are copies of the path hash itself (Demo: proof that uses a duplicated hash).
Tampering changes the root
Suppose someone edits tx2 to pay Mal instead of Cat. Its txid changes, so its parent changes, and so on up: exactly one hash per level, the ones on tx2's path, and the root goes from 1df2 to b4b0 (Demo: tamper with tx2). The sibling hashes do not change. The header still says 1df2, so the block is now invalid.
A full node that serves the edited transaction cannot build a proof that passes: whatever it sends, the client's re-hashing ends at b4b0, not the 1df2 in its header (Demo: proof against a tampered block fails). To make the header agree, the attacker would have to write the new root into it, which changes the block hash, so the nonce found by mining no longer works; the block, and every block after it, would have to be mined again. How that work is done is on the Proof of Work page.
What SPV does and does not prove
- It proves that a transaction is in a block whose header has enough work on top of it.
- It does not prove the transaction is valid (the client trusts that miners checked signatures and amounts), and a full node can hide a transaction by simply not answering.
- Asking full nodes for "my" transactions also tells them which addresses are yours; Bloom filters (BIP 37) leaked this, and compact block filters (BIP 157/158) were made to fix it.
The same tree trick is used elsewhere: replicas compare Merkle roots to find what differs (see Merkle Trees for Anti-Entropy Repair), and the guarantees come from the hash function (see Encryption vs Hashing). Who may spend a coin is proved by signatures, not by the tree (see Digital Signatures).
What the page leaves out
Real txids are 32-byte double SHA-256 hashes, stored in little-endian byte order (so they look reversed in block explorers); since SegWit, the header's tree uses txids without witness data, and a second tree of witness txids is committed inside the coinbase transaction. The page leaves out the merkleblock message format (partial Merkle tree with flag bits), Bloom filters, transaction ordering rules, the full header fields and their encoding, and what happens when headers fork. Mining, difficulty and the nonce search are on the Proof of Work page.