sommaire · 10 sections
Your phone wallet shows your balance in a few seconds. It tells you a payment you received is confirmed, and how many blocks have piled on top of it since. Yet it has never downloaded the blockchain: several hundred gigabytes, which no phone keeps. So what does it rely on?
On two building blocks. The first is a data structure dating from 1979, the Merkle tree, which can prove a transaction is in a block with a few hundred bytes. The second is a way to find your own transactions in the mass without telling anyone what you’re looking for — a problem Bitcoin took five years to solve properly. We’ll look at both, on real blocks, recomputing everything we claim.
6,017 transactions, 32 bytes
A block header is 80 bytes, and proof of work covers only those. Yet a block holds thousands of transactions. Those 80 bytes must therefore commit to all of them, so that changing a single one — an amount, a recipient, the order — makes the header wrong. That is the job of the 32-byte field we left aside: the Merkle root.
The simplest solution would be to hash the whole list of transactions in one go. That would work for integrity, but not for what follows: to check that one transaction is in the block, you would have to supply all the others. The Merkle tree, described by Ralph Merkle in 1979 and picked up by Satoshi Nakamoto in the white paper, does better.
Building the tree
The construction fits in three rules:
- The leaves are the transaction identifiers, the txids — themselves double SHA-256 hashes, in block order, coinbase first.
- Go up two by two: each node on the level above is the double SHA-256 of its two children concatenated (64 bytes hashed into 32).
- Repeat until a single hash remains: the root.
One case is left: a level with an odd number of elements. Bitcoin chose a simple, slightly odd rule: the last one is duplicated and paired with itself.
Let’s apply it to block 973,976, the one from the previous article. It contains 6,017 transactions. We fetched its 6,017 txids from mempool.space and rebuilt the tree ourselves:
| Level | Elements | Odd → duplication? |
|---|---|---|
| leaves | 6,017 | yes |
| 1 | 3,009 | yes |
| 2 | 1,505 | yes |
| 3 | 753 | yes |
| 4 | 377 | yes |
| 5 | 189 | yes |
| 6 | 95 | yes |
| 7 → 10 | 48, 24, 12, 6 | no |
| 11 | 3 | yes |
| 12 | 2 | no |
| root | 1 | — |
Thirteen hashing levels, eight duplications, and at the top:
ae6d9ce24ddda2b5ba23f97d20b9423a01e7abc2118aeaba52c1861532a57751
That is exactly the root written in the block header. The recomputation confirms what we expected: these 32 bytes summarise all 6,017 transactions, in their exact order. Changing a single byte of a single one changes its txid, hence the node above, and so on up to the root. The header no longer matches, and the proof of work has to be redone.
The Merkle proof
This is where the tree gets interesting. To prove a transaction is in a block, you don’t need to supply the block. You only need to supply one hash per level: the “sibling” of each node on the path from the transaction to the root. The verifier redoes the hashing, level by level, and compares the result with the root in the header. If they match, the transaction is in the block. If not, the proof is false.
This is the Merkle proof. To check it, you need three things: the transaction (or its txid), its position in the block, and the list of siblings.
The position does a quiet but essential job. Read in binary, right to left, it says at each level whether our node is the left child (bit 0, sibling on the right) or the right child (bit 1, sibling on the left). And order matters: hashing A‖B does not give the same result as B‖A.
On a real block
Take the 222-byte transaction from Anatomy of a Bitcoin transaction
, txid b0d246e7…5353c72f. It was confirmed in block 963,721, which contains 5,064 transactions. It sits at position 35 — in binary, 100011.
mempool.space supplies its proof: 13 hashes. We recombined them ourselves. On the first two levels, our node is on the right (the bits 1 and 1 of 100011); on the next three, on the left; then on the right; then, higher up the tree, always on the left. After the thirteenth hash, we get:
d537bdf1988743b6e9932919a73a5f0ba2d046c6c521ae156671a4775f8a7b24
That is the Merkle root in the header of block 963,721. The transaction is there, proven with 13 × 32 = 416 bytes, while the whole block weighs 1,633,037. Nearly 4,000 times less.
Why it scales
The number of hashes in a proof is the number of levels in the tree, i.e. the base-2 logarithm of the number of transactions, rounded up. The logarithm grows very slowly:
| Transactions in the block | Hashes in the proof | Proof size |
|---|---|---|
| 8 | 3 | 96 bytes |
| 1,000 | 10 | 320 bytes |
| 5,064 (block 963,721) | 13 | 416 bytes |
| 1,000,000 | 20 | 640 bytes |
Making the block a thousand times bigger adds only ten hashes to the proof. This property is what makes light wallets possible.
A second tree, for witnesses
Attentive readers will have spotted a detail: the tree is built on txids, and since SegWit the txid no longer covers signatures. We saw it in the transactions article: signatures live in the witness, excluded from the txid to fix malleability. So the Merkle root in the header does not commit to witnesses.
SegWit solved this without touching the header, which would have required a hard-fork. A second tree is built, this time on wtxids (the identifiers that include the witness), and its root is written into an OP_RETURN output of the coinbase: the witness commitment, which we glimpsed in the mining article. Since the coinbase is itself the first leaf of the first tree, the witnesses end up committed to by the header, one level of indirection away.
In this second tree there is a single exception: the coinbase’s wtxid is replaced by 32 zero bytes, since the coinbase cannot contain the fingerprint of a tree that would contain itself. For block 973,976, we recomputed the 6,017 wtxids, rebuilt this second tree, and found the commitment written in the coinbase, 09014480…68246559.
Blind spots in Bitcoin’s tree
The duplication rule comes at a cost. If the last element of an odd level is paired with itself, then two different transaction lists can produce the same root. Bitcoin Core’s code gives the example: the lists [1,2,3,4,5,6] and [1,2,3,4,5,6,5,6] lead to the same hash.
In 2012 this ambiguity was identified as a vulnerability, recorded as CVE-2012-2459. An attacker could broadcast an “inflated” version of a valid block, with duplicated transactions: same root, same header, same proof of work, but invalid content. A node that marked this block as invalid would then refuse the legitimate version — which has the same hash — and end up cut off from the rest of the network. The fix, still in place: a node checks that no level of the tree contains two identical hashes side by side, and treats a “mutated” block like a block with a wrong root, without blacklisting it.
Satoshi’s light wallet
Back to the phone. The Bitcoin white paper devotes its section 8 to what it calls Simplified Payment Verification, SPV. The idea: a user doesn’t need all the blocks, only their headers. They keep the header chain with the most cumulative work, ask for the Merkle proof of the transaction they care about, and check that it leads to the root of a header in that chain. The blocks stacked on top tell them how much work covers their payment.
Headers are light: 80 bytes per block. Up to block 973,976, that’s 77.9 million bytes, about 78 MB — manageable on a phone, and growing by only 4 MB a year.
The white paper is candid about the limit: an SPV client doesn’t verify transactions itself. It trusts that the chain with the most work contains only valid transactions, which assumes the majority of computing power is honest. A full node doesn’t need that assumption.
One problem remains that the white paper doesn’t address: how does the wallet know which transactions concern it? To ask for a proof, you need to know what to ask for. And to know what to ask for, you have to go through the blocks.
BIP37, or asking the node to search for you
The first answer dates from 2012: BIP37 , written by Mike Hearn and Matt Corallo, shipped in Bitcoin Core 0.8.0 in 2013. The principle: the wallet sends a full node a Bloom filter built from its addresses, and the node sends back, block after block, the matching transactions with their Merkle proofs.
A Bloom filter is a probabilistic structure: an array of bits, where each added element switches on a few cells. To know whether an element “is in”, you look at its cells. If one is off, it’s definitely not in; if all are on, it’s probably in — with a false-positive rate you can tune. BIP37 counted on those false positives to cover the wallet’s tracks: the node would receive the wallet’s transactions mixed in with others, unable to tell them apart.
The model has aged, for three reasons.
Privacy doesn’t hold. In 2014, Arthur Gervais, Ghassan Karame, Damian Gruber and Srdjan Capkun showed that a node receiving the filter of a wallet using a handful of addresses can recover nearly all of them, and that the leak gets worse when the wallet restarts and sends a new filter. The cover was much weaker than expected.
The load falls on the node. For every connected client, the node has to run each requested block through that client’s filter. Malicious clients could use this to exhaust it.
The node can stay silent. It can omit a transaction that matches the filter, and the wallet has no way of knowing: you can prove a transaction is in a block, not that it isn’t.
Since Bitcoin Core 0.19.0 (November 2019), a node no longer serves Bloom filters by default, to close these denial-of-service vectors. The option still exists, but it has to be switched on.
BIP157/158, or swapping the roles
The modern answer was proposed in 2017 by Olaoluwa Osuntokun, Alex Akselrod and Jim Posen: compact block filters, described in BIP157 (the protocol) and BIP158 (the filter). The idea is to swap the roles: it’s no longer the wallet sending a filter to the node, it’s the node publishing one filter per block, the same for everyone. The wallet downloads these filters, tests them at home against its own addresses, and requests only the blocks that match — in full.
A block’s filter contains every locking script that appears in it: those of the outputs created, and those of the outputs spent. It is encoded very compactly, with Golomb-Rice coding: each script is reduced to a number, the numbers are sorted, and only the gaps between them are stored. BIP158’s parameters set the false-positive rate at 1 in 784,931 per element looked up.
The filter of block 973,976, recomputed
Filter sizes quoted online vary by a factor of four. Rather than pick a source, we computed the filter of block 973,976 ourselves. We first wrote BIP158’s algorithm and checked that it reproduced the specification’s ten official test vectors — ten out of ten. Then we applied it to the block:
- 4,611 distinct scripts: 2,505 scripts from outputs created and 2,592 scripts spent by inputs, 486 of which appear on both sides. The block’s 4,794
OP_RETURNoutputs are left out, as the specification requires: they can never be spent, so no wallet looks for them; - a filter of 12,136 bytes, i.e. 21 bits per script;
- 0.71% of the block’s size (1,714,534 bytes), i.e. 141 times smaller.
For a wallet, the order of magnitude is therefore about a dozen kilobytes per block. If every block looked like this one, following a year of chain (about 52,500 blocks) would cost around 640 MB of filters: far less than the blocks themselves, but much more than the 4 MB of headers, and more than BIP37, where the node sent back only the few useful transactions.
What it changes
The node learns nothing about the search. It serves the same filter to everyone. When a wallet asks for a whole block, the node knows that block is of interest, but not for which transaction — and the wallet can spread these requests across several nodes.
Lying becomes detectable. Filters are deterministic: any honest node computes exactly the same one for a given block. BIP157 chains them with filter headers, each committing to the filter and the previous header, like block headers. A wallet that queries several nodes sees immediately if they disagree, and can then download the block to settle it. The limit: these filters are not written into the blocks themselves, so trust rests on at least one of the queried nodes being honest.
The load moves from the node to the client. The node computes each filter once, instead of filtering for each client. Bitcoin Core can build this index since version 0.19.0 and serve it to other nodes since 0.21.0 (January 2021), but only if the operator turns it on.
Who uses it in 2026
Adoption remains a minority. The main users of BIP157/158 are:
- Neutrino , Lightning Labs’ Go light client, which ended up lending its name to the whole protocol. It lets LND, Lightning Labs’ Lightning implementation, run without a full Bitcoin node, which mobile Lightning wallets embedding LND make use of;
- Wasabi Wallet, whose light mode relies on BIP158 filters, and which since version 2.6 can sync directly against the user’s own node, with no intermediate server;
- developer libraries: BDK with the Kyoto client in Rust, and LDK on the Lightning side.
Most mainstream light wallets made a different choice: querying an Electrum or Esplora server, which indexes the blockchain by address and answers directly “here are this address’s transactions”. It’s fast and simple to run, but the server sees every address you ask about. That’s not a flaw if the server is yours, plugged into your own node; it becomes one when it belongs to a third party.
What to take away
- The Merkle root summarises a whole block in 32 bytes: txids are hashed two by two up to the top. Recomputed on block 973,976, it checks out.
- An inclusion proof costs one hash per level: 13 hashes, 416 bytes, to prove a transaction is in a 5,064-transaction block. Making the block a thousand times bigger adds only ten hashes.
- Bitcoin’s tree has blind spots: duplicating the last element (CVE-2012-2459, fixed) and 64-byte transactions (BIP54’s target, not yet activated).
- A light client keeps the headers (78 MB for the whole history) and trusts the majority of computing power for transaction validity.
- BIP37 had the node do the filtering using the wallet’s addresses: poor privacy, server load, lying by omission. Off by default since 2019.
- BIP157/158 has the wallet do the filtering using one public filter per block: the node learns nothing, but the client downloads more. Technically superior, still little adopted compared with Electrum servers.
What’s next
So far we’ve talked about “the” chain, the one with the most cumulative work, as if it were obvious. But what happens when two miners find a block almost at the same time, or when part of the network follows different rules? How do thousands of nodes that don’t know each other agree on a single history? That’s the subject of The Nakamoto consensus (BTC-A-05, coming soon).