Skip to content
BIP ATLAS

BIP 0157 · 0158

How can a wallet find the blocks it needs?

Download a small filter, test it locally, and fetch the block only if it might contain a payment you care about. A match is a reason to look closer.

A light wallet needs to find its payments without downloading every block. Asking a server to search for its addresses gives that server information about the wallet. BIPs 157 and 158 move the search onto the wallet instead.123

A full node publishes a compact filter for each block. Everyone receives the same filter. The wallet checks its own scripts locally; if one matches, it downloads the block to see what actually happened. The filter can produce a false alarm, but a correctly built filter will not miss a script in its included set.345

The two proposals have different jobs. BIP 158 defines what goes into a filter and how it is compressed. BIP 157 defines how peers serve filters and how a wallet checks them before relying on their answers.678910

Source revision
bitcoin/bips @ 3a10b5b
Source checked
1 October 2026
Review state
Awaiting review
Source details

This chapter is an independent explanation, not the proposal itself. Preamble fields are shown as the pinned files record them, without author e-mail addresses. Status is the proposal’s own field. It is not an endorsement or a sign of consensus.

BIP 157: Client Side Block Filtering

BIP
157
Layer
Peer Services
Title
Client Side Block Filtering
Authors
Olaoluwa Osuntokun
Alex Akselrod
Jim Posen
Status
Deployed
Type
Specification
Assigned
2017-05-24
License
CC0-1.0
Requires
158

Pinned source · Reader view on bips.dev
SHA-256 5405acbf04ebd8a1b92ae2b7188022f4c14723ed8a0ae0d077d12a1e6908da9a
Git blob 8b8d3bac250ea77c56addf4788f4dda479d304e9

BIP 158: Compact Block Filters for Light Clients

BIP
158
Layer
Peer Services
Title
Compact Block Filters for Light Clients
Authors
Olaoluwa Osuntokun
Alex Akselrod
Status
Deployed
Type
Specification
Assigned
2017-05-24
License
CC0-1.0
Requires
157

Pinned source · Reader view on bips.dev
SHA-256 93a560d966852e081f5e7894f43eddae55ac471ff8bcb99d93eae73f5a859954
Git blob 9456809fbc24ed8399c46a868b1627def270ecb3

Fig. A16.1 Search locally, download selectively

Search locally, download selectivelyA full node publishes the same filter to every client. Shown is the published filter of testnet block 926,485, 25 bytes. The wallet tests watched scripts locally. A match may be a false positive, so it requests the block and checks it; a miss rules out only scripts in a correctly built filter's included set. Watched scripts are not sent with the filter request, but a peer serving a requested block can observe that request. Network layout is schematic.PUBLIC · THE SAME FILTER FOR EVERYONEBLOCKCOMPACT FILTER9 included scripts · 25 bytesDOWNLOAD THE FILTERINSIDE YOUR WALLETFILTER OF BLOCK 926,485 · 25 BYOUR WATCHED SCRIPTSTEST LOCALLYno address list sentNO MATCHskip this block*MAYBE A MATCHfetch the block and check*FOR INCLUDED SCRIPTS, GIVEN THE CORRECT FILTERA BLOCK REQUEST IS STILL VISIBLE TO ITS PEER
The filter travels to the wallet; the wallet’s watched scripts stay there. A match leads to a block request, which the serving peer can still observe.1231112

A match means “download and check”

A match is deliberately only a maybe. Several scripts can map to the same filter value. The wallet downloads the block and checks the actual transactions before treating anything as a payment.41314

A miss is firmer, within the included set. Every item in the set matches with probability 1, so a miss in a correctly constructed basic filter rules out a matching included output or spent-output script. It says nothing about excluded items, including empty scripts and outputs beginning with OP_RETURN.4515

Compare a match, a miss and the illustrated false alarm. Follow each to the wallet’s next step. Watch when it skips the block and when it must fetch the block to inspect the transactions.3451315

Fig. A16.2 Follow the wallet: skip, fetch, or find a false alarm

Static view: the full workflow for a matching script. With JavaScript, compare a miss and a schematic false positive.

Which blocks should the wallet fetch?Testnet block 926,485: the tested model matches an included script. The surrounding wallet workflow is schematic. 1. GET THE FILTER: Check it against its filter header. 2. TEST THE WATCHED SCRIPT LOCALLY: Match: this block may be relevant. 3. REQUEST THE FULL BLOCK: The serving peer sees the block request. 4. CHECK OUTPUTS AND SPENDS: A relevant output or spend is present. With a correctly constructed filter, a miss rules out only the scripts it includes. The watched script stays local. The peer sees which blocks the wallet requests.WATCHING A SCRIPT · BLOCK 926,4851 · GET THE FILTERCheck it against its filter header.2 · TEST THE WATCHED SCRIPT LOCALLYMatch: this block may be relevant.3 · REQUEST THE FULL BLOCKThe serving peer sees the block request.4 · CHECK OUTPUTS AND SPENDSA relevant output or spend is present.

A relevant output or spend is present.

With a correctly constructed filter, a miss rules out only the scripts it includes. The watched script stays local. The peer sees which blocks the wallet requests.

Testnet block 926,485: the tested model matches an included script. The surrounding wallet workflow is schematic.

How the filter is encoded: explore published blocks

Static view: the first block, its first test script and the filter's first bits. With JavaScript you can choose among 6 published blocks and test other scripts.

A filter, built and queriedTestnet block 926485: 9 scripts hashed onto 0 to F = 7,064,379: 10,156, 1,923,207, 2,341,508, 3,078,625, 3,418,462, 3,453,444, 4,395,247, 5,217,833, 5,378,249. A script from this block hashes to 1,923,207. Value 2 equals it: a match, so the block may concern this script. Decoded: 10,156, 1,923,207; values not read are drawn empty. The filter, 25 bytes, starts with N = 9, then the codes 0 0000010011110101100, 1110 1010011000011011011, 0 1100110000111111101, 10 0110011111101011101, 0 1010010111101111101, 0 0001000100010100110, and more.76a914876fbb82…TEST SCRIPT · FROM THIS BLOCKSIPHASH→ 1,923,207TARGET IN [0, F)KEY: FIRST 16 B OF THE BLOCK HASH0F = N·M = 7,064,379MATCH · MAYBEEMPTY MARK: IN THE FILTER, NOT READTHE FILTER'S FIRST BITS · 25 BYTES IN ALLGAP 10,156GAP 1,913,051GAP 418,301N…
A filter, built and queriedTestnet block 926485: 9 scripts hashed onto 0 to F = 7,064,379: 10,156, 1,923,207, 2,341,508, 3,078,625, 3,418,462, 3,453,444, 4,395,247, 5,217,833, 5,378,249. A script from this block hashes to 1,923,207. Value 2 equals it: a match, so the block may concern this script. Decoded: 10,156, 1,923,207; values not read are drawn empty. The filter, 25 bytes, starts with N = 9, then the codes 0 0000010011110101100, 1110 1010011000011011011, 0 1100110000111111101, 10 0110011111101011101, 0 1010010111101111101, 0 0001000100010100110, and more.76a914876fbb82…TEST SCRIPT · FROM THIS BLOCKSIPHASH→ 1,923,207TARGET IN [0, F)KEY: FIRST 16 B OF THE BLOCK HASH0F = N·M = 7,064,379MATCH · MAYBEEMPTY MARK: IN THE FILTER, NOT READTHE FILTER'S FIRST BITS · 25 BYTES IN ALLGAP 10,156GAP 1,913,051N…

A script from this block hashes to 1,923,207. Value 2 equals it: a match, so the block may concern this script.

Exact values for this view
Test script
76a914876fbb82ec05caa6af7a3b5e5a983aae6c6cc6d688ac
Filter (25 bytes)
09027acea61b6cc3fb33f5d52f7d088a6b2f75d234e89ca800
Hashed values
10,156, 1,923,207, 2,341,508, 3,078,625, 3,418,462, 3,453,444, 4,395,247, 5,217,833, 5,378,249

BIP 158 testnet-19.json, block 926,485 (“Duplicate pushdata 913bcc2be49cb534c20474c4dee1e9c4c317e7eb”). Filter and header rebuilt by the tested model and equal to the vector.

The wallet tests its watched script locally. A miss skips the block; a match leads to a block download and a transaction check. Match and miss use published test data. The false-positive branch is schematic, not a published vector.345671112131516171819
How often a false match happens

A match says the block may concern the client, not that it does. With M = 784931, an unrelated script matches a given filter with probability 1/784931, about 1.3 in a million. That is small per test, but a wallet tests many scripts against many blocks: 100 scripts checked against 10,000 blocks give an expected 1.3 false matches, each costing a needless block download.41420

Filters do not hide what the client does next. The authors argue that privacy improves because blocks can be fetched from any source, so no single peer learns everything a client needs. Still, whoever serves a block sees that it was requested. A client fetching blocks from the network SHOULD therefore pick outbound peers at random, to limit what intersection analysis can learn. The most cautious clients may use private information retrieval.1112

Which scripts are included?

The one filter type BIP 158 defines, basic, is meant to hold everything a regular wallet needs. For each transaction in the block it MUST contain exactly two kinds of item. One is the script being spent by each input, except in the coinbase transaction. The other is the scriptPubKey of each output, except outputs that start with OP_RETURN. “Nil” (empty) items MUST NOT be included, and each script goes in once: the BIP calls the result a set.621

Fig. A16.3 What goes in

What goes inTestnet block 926485, 5 transactions: 10 output scripts and 8 spent scripts. Left out: 1 output starting with OP_RETURN, 8 repeats of an earlier script. The set keeps 9 distinct scripts: 76a914876fbb82ec05caa6af7a3b5e5a983aae6c6cc6d688ac, 52534b424c4f434b3acd16772ad61a3c5f00287480b720f6035d5e54c9efc71be94bb5e3727f109090, 76a9143ebc40e411ed3c76f86711507ab952300890397288ac, 76a91450333046115eaa0ac9e0216565f945070e44573988ac, 76a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac, a914b7e6f7ff8658b2d1fb107e3d7be7af4742e6b1b387, 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac, a9148fc37ad460fdfbd2b44fe446f6e3071a4f64faa687, a914feb8a29635c56d9cd913122f90678756bf23887687.BLOCK 926,485 · 5 TRANSACTIONSOUTPUT SCRIPTS · 1076a91487…6a24aa21…OP_RETURN52534b42…76a9143e…76a91450…76a914c0…a914b7e6…76a91491…a9148fc3…76a91491…REPEATSPENT SCRIPTS · 8a914feb8…76a914c0…REPEAT76a91491…REPEAT76a91491…REPEAT76a91491…REPEAT76a91491…REPEAT76a91491…REPEAT76a91491…REPEATTHE SET · 9 SCRIPTSEACH ONE ONCE76a91487…52534b42…76a9143e…76a91450…76a914c0…a914b7e6…76a91491…a9148fc3…a914feb8…
Every script, in full
  1. 76a914876fbb82ec05caa6af7a3b5e5a983aae6c6cc6d688ac output
  2. 6a24aa21a9ed5c748e121c0fe146d973a4ac26fa4a68b0549d46ee22d25f50a5e46fe1b377ee output, left out: starts with OP_RETURN
  3. 52534b424c4f434b3acd16772ad61a3c5f00287480b720f6035d5e54c9efc71be94bb5e3727f109090 output
  4. 76a9143ebc40e411ed3c76f86711507ab952300890397288ac output
  5. 76a91450333046115eaa0ac9e0216565f945070e44573988ac output
  6. 76a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac output
  7. a914b7e6f7ff8658b2d1fb107e3d7be7af4742e6b1b387 output
  8. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac output
  9. a9148fc37ad460fdfbd2b44fe446f6e3071a4f64faa687 output
  10. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac output, left out: duplicate of an earlier element
  11. a914feb8a29635c56d9cd913122f90678756bf23887687 spent
  12. 76a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac spent, left out: duplicate of an earlier element
  13. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac spent, left out: duplicate of an earlier element
  14. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac spent, left out: duplicate of an earlier element
  15. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac spent, left out: duplicate of an earlier element
  16. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac spent, left out: duplicate of an earlier element
  17. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac spent, left out: duplicate of an earlier element
  18. 76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88ac spent, left out: duplicate of an earlier element
Testnet block 926,485 touches 18 scripts. Its OP_RETURN output and every repeat are left out; 9 distinct scripts remain.61521

The filter watches scripts, not transaction IDs or arbitrary text. A wallet can look for an output paying to one of its scripts or an input spending such an output. Empty scripts and OP_RETURN outputs are outside that promise.56

Excluded scripts and the published test cases

The authors give a reason for leaving OP_RETURN outputs out. A future soft fork could then commit to the filters, probably in an OP_RETURN output of the coinbase, without the commitment having to contain itself.22

BIP 158’s test vectors exercise these rules on real testnet blocks. One has a transaction that pays to an empty script, and one spends from an empty script. In another, scripts repeat and the coinbase carries an OP_RETURN witness commitment, which is left out. One more is a block with nothing to put in the filter at all, whose filter is the single byte 00.6151921

Store the gaps, not the scripts

The filter does not contain a list of addresses. Each included script is hashed into a bounded range. Those values are sorted, and the filter stores the gaps between them. Small gaps take fewer bits to write, which is where the compression comes from.7161723

Fig. A16.4 From scripts to a short filter

  1. Building block 1,263,442's filter, step 1 of 5The 3 distinct scripts of testnet block 1263442 (76a914f2c25ac3d59f3d674b1d1d0a25c27339aaac0ba688ac, 001446c29eabe8208a33aa1023c741fa79aa92e881ff, 002027a5000c7917f785d8fc6e5a55adfca8717ecb973ebb7743849ff956d896a7ed) are hashed with SipHash-2-4 under the key 335fbc2314a20d310b6f9eba7ed4be41, the first 16 bytes of the block hash in little-endian order.76a914f2c2…001446c29e…002027a500…SIPHASH2-4KEY 335fbc23…

    The block's 3 scripts go through SipHash-2-4, keyed with the first 16 bytes of the block hash.

  2. Building block 1,263,442's filter, step 2 of 5Each hash is multiplied by F = 2354793 and the top 64 bits kept, giving 570774, 1341840, 1483084.0F = 2,354,793570,7741,341,8401,483,084

    Each 64-bit hash is scaled into [0, F), F = N · M = 3 × 784,931.

  3. Building block 1,263,442's filter, step 3 of 5Sorted, the values give the gaps 570774, 771066, 141244.0F = 2,354,793570,774771,066141,244

    Sorted, only the gaps between neighbours are kept.

  4. Building block 1,263,442's filter, step 4 of 5Gap 570774: q = 1, 10 then 0001011010110010110. Gap 771066: q = 1, 10 then 0111100001111111010. Gap 141244: q = 0, 0 then 0100010011110111100.GAP 570,774100001011010110010110GAP 771,066100111100001111111010GAP 141,24400100010011110111100

    Each gap becomes a Golomb-Rice code: the quotient by 2^19 in unary, then 19 remainder bits.

  5. Building block 1,263,442's filter, step 5 of 562 code bits and 2 padding bits make 8 bytes; with N = 3 as a one-byte CompactSize in front, the filter is 0385acb4f0fe889ef0, as published.0385acb4f0fe889ef0N = 362 CODE BITS + 2 PADDING

    Pad with 2 zero bits to whole bytes and put N in front: the 9-byte filter, equal to the published one.

Exact values
Block hash
000000006f27ddfe1dd680044a34548f41bed47eba9e6f0b310da21423bc5f33
SipHash key
335fbc2314a20d310b6f9eba7ed4be41
Script 1
76a914f2c25ac3d59f3d674b1d1d0a25c27339aaac0ba688ac
Script 2
001446c29eabe8208a33aa1023c741fa79aa92e881ff
Script 3
002027a5000c7917f785d8fc6e5a55adfca8717ecb973ebb7743849ff956d896a7ed
Filter (9 bytes)
0385acb4f0fe889ef0
Hash the scripts, sort the values, then encode the gaps. This published example fits into the filter bytes shown at the end.71617181924

To query it, the wallet hashes a watched script using the same block-specific key and range. It reads the gaps and adds them up until it reaches or passes the target. Equality means a match; passing the target means it can stop. Several watched scripts can be sorted and checked in one pass.1325

Fig. A16.5 How tight the coding is

How tight the coding isBlock 180480: 13 elements. The floor N·(P + 1) is 260 bits; the published filter is 35 bytes; after its one-byte N, 272 bits of codes and padding, about 20.9 per element; writing each value below F = 10204103 at fixed width would take 24 bits each, 312 in all; the scripts themselves are 2,760 bits. Block 926485: 9 elements. The floor N·(P + 1) is 180 bits; the published filter is 25 bytes; after its one-byte N, 192 bits of codes and padding, about 21.3 per element; writing each value below F = 7064379 at fixed width would take 23 bits each, 207 in all; the scripts themselves are 1,880 bits.BLOCK 180,480 · 13 ELEMENTSFLOOR 260CODED 272 · 20.9/ELFIXED 312 · 24/ELSCRIPTS 2,760 →BLOCK 926,485 · 9 ELEMENTSFLOOR 180CODED 192 · 21.3/ELFIXED 207 · 23/ELSCRIPTS 1,880 →BITS AFTER THE N BYTE, TO SCALE EXCEPT THE BROKEN BAR
Two published filters, in bits after the N byte: the floor of P + 1 bits per element, the coded filter, and each hashed value written at fixed width.2627
Exact hashing, coding and size rules

Each script is first hashed with SipHash, which BIP 158 requires with parameters c = 2 and d = 4. The key is the first 16 bytes of the block’s hash in little-endian order, so it is deterministic but differs from block to block. The 64-bit output is then mapped into the range [0, N·M), where N is the number of items, by multiplying by N·M and keeping the top 64 bits of the product.1718

The hashed values are sorted, and only the gaps between neighbours are written. Because the values are spread uniformly at random, the gaps follow roughly a geometric distribution, with small gaps common and large ones rarer. Golomb-Rice coding is built for exactly that. The gap divided by 2^P goes in unary, as that many ones and a zero, and the remainder follows in P bits. The bit stream is padded with zeros to a whole byte and prefixed with N as a CompactSize. A filter with no items MUST be a single zero byte.7161923

For the basic filter, P MUST be 19 and M MUST be 784931. The authors cite analysis that M ≈ 1.497137·2^P is close to optimal, and empirical analysis that these values minimize bandwidth once both the filters themselves and the blocks downloaded because of false positives are counted.2024

The coding is tight. Each code needs at least P + 1 bits, so a filter of N items takes at least N·(P + 1) bits, 20 per item for the basic filter. In the published vectors, block 180,480’s filter holds 13 scripts in 35 bytes and block 926,485’s holds 9 in 25. That is about 21 bits per item, close to that floor, against 24 and 23 bits to write each hashed value at fixed width. The scripts themselves take hundreds of bits.2627

BIP 158 illustrates Golomb-Rice coding with a P = 2 table. The model reproduces every row of that table, as well as the first P = 19 code of a published basic filter.1628

A small filter can still be wrong

A dishonest peer could omit a script from a filter. BIP 157 therefore links filter hashes into a chain and recommends comparing that chain across peers. A disagreement tells the wallet where it needs to investigate; it does not by itself tell the wallet which peer is right.8293031

Fig. A16.6 When peers disagree

  1. When peers disagree, step 1 of 3Schematic. Peer A sends filter headers H1 to H4; peer B sends H1, H2, then different headers H3′ and H4′. The first disagreement is at the third header.PEER AH1H2H3H4PEER BH1H2H3′H4′FIRST DIFFERENCE

    The client asks several peers for filter headers. Two agree up to H2 and differ from H3 on.

  2. When peers disagree, step 2 of 3Schematic. The client downloads the block at the first disagreement and obtains the scripts its inputs spend, which the block does not contain; it computes the filter, and from the filter hash and the agreed header H2 the third header.CLIENTBLOCKSPENTSCRIPTS: NOT IN THE BLOCKFILTER+ H2H3

    It downloads that block, gets the scripts its inputs spend, and builds the filter and the header from H2 itself.

  3. When peers disagree, step 3 of 3Schematic. The client's own third header equals peer A's H3 and not peer B's H3′, so it bans peer B. With at least one honest peer the client can identify the correct filters.PEER AH1H2H3H4PEER BH1H2H3′H4′BANNED: THE PEER THAT DISAGREED WITH THE BLOCK

    Peer B's header does not match the block, so the client should ban it. With one honest peer, the authors argue, it can find the right filters.

Schematic: what BIP 157 recommends when two peers serve different filter headers.89303132

Rebuilding the disputed filter requires more than the block. The filter includes the scripts of outputs its inputs spend, and those scripts may be in earlier blocks. BIP 157 does not specify how a light client should obtain and check them. For an empty filter, the committed hash can let the client skip the filter request entirely.3233

Filter headers and the recommended peer checks

A filter cannot be checked by looking at it, so BIP 157 chains them. A filter’s hash is the double SHA-256 of its bytes, and its header is the double SHA-256 of that hash followed by the previous block’s filter header. The previous header for the genesis block is 32 zero bytes. Like block headers, each filter header commits to everything before it.2930

The BIP’s recommended client procedure leans on that chain. A client SHOULD sync block headers first, then download and verify filter headers, and MAY first fetch the filter header at every 1,000th block (getcfcheckpt), then fill in each interval and check it against them. Unless it has a trusted peer, it SHOULD ask several. If two peers disagree, it SHOULD find the first header they disagree on, download that block, compute the filter itself, and ban any peer whose header does not match. It SHOULD also check every filter it downloads against its header. The authors’ claim is that a client with at least one honest peer can identify the correct filters.893134

Serving filters and protocol request limits

The serving side is kept cheap. Nodes SHOULD build and store each block’s filters as the block connects, and SHOULD NOT build them on request, since a peer could otherwise ask for small filters of large blocks and force expensive I/O. Requests are bounded: at most 1,000 blocks of filters, or 2,000 filter headers, at a time. A node signals support with the NODE_COMPACT_FILTERS service bit, and the authors chose this P2P-only design over a consensus change that would make blocks commit to their filters.10353637

Proposal history and the older Bloom-filter approach

A light client does not download every block. It downloads the block headers, 80 bytes each, checks their proof of work, and follows the chain with the most work. Then it needs to learn which blocks touch its own coins without fetching them all. The older answer, BIP 37, had the client hand a Bloom filter of its interests to a full node. The authors of BIP 157 argue that most implementations gave wallets virtually zero privacy, let a malicious node omit data with little risk of detection, and let crafted filters burden honest nodes.12

BIPs 157 and 158, both assigned in 2017 and recorded as Deployed, reverse the direction. Full nodes build one deterministic filter per block, once, and serve it to anyone; the client tests the filter itself and downloads a block only if it matches. The filter is a Golomb-coded set: it matches every item in the set, and any other item with probability 1/M.3438

The filter helps the wallet decide where to look. A match still needs the block and its transactions; a miss is useful only for the included set in a correctly constructed filter.34513

Evidence

Each numbered marker in the text points here, and the ↩ links lead back to the text. Quotes are verbatim from the BIP files at commit 3a10b5b, wiki markup included. Links open the exact lines. Labels say what kind of statement each entry is: a rule, the author’s rationale, history, a test vector, or our own inference.

  1. ↩ a b c Rule Light clients download all block headers, verify proof of work, follow the most-work chain, and then download only the data relevant to them; headers are a fixed 80 bytes.

    Quoted source text (1)

    They achieve this by downloading all block headers, verifying the proofs of work, and following the longest proof-of-work chain. Since block headers are a fixed 80-bytes and are generated every 10 minutes on average, the bandwidth required to sync the block headers is minimal. Light clients then download only the blockchain data relevant to them directly from peers and validate inclusion in the header chain.

    BIP 157, lines 41–47
  2. ↩ a b c Author’s rationale The authors argue that with BIP 37 the client sends a Bloom filter to a full node, that most implementations offer virtually zero privacy, that malicious nodes can omit data with little risk of detection, and that crafted filters are a DoS vector.

    Quoted source text (4)

    With BIP 37, a client sends a Bloom filter it wants to watch to a full node peer, then receives notifications for each new transaction or block that matches the filter.

    BIP 157, lines 51–53

    It has been shown, however, that most implementations available offer virtually ''zero privacy'' to wallets and other

    BIP 157, lines 57–59

    Additionally, malicious full nodes serving light clients can omit critical data with little risk of detection

    BIP 157, lines 61–62

    honest nodes servicing BIP 37 light clients may incur significant I/O and CPU resource usage due to maliciously crafted Bloom filters, creating a denial-of-service (DoS) vector

    BIP 157, lines 64–66
  3. ↩ a b c d e f g Author’s rationale BIP 157 is the opposite of BIP 37: full nodes generate deterministic filters of block data, built once and stored, and the client downloads a block if the filter matches.

    Quoted source text (1)

    The alternative detailed in this document can be seen as the opposite of BIP 37: instead of the client sending a filter to a full node peer, full nodes generate deterministic filters on block data that are served to the client. A light client can then download an entire block if the filter matches the data it is watching for. Since filters are deterministic, they only need to be constructed once and stored on disk, whenever a new block is connected to the chain.

    BIP 157, lines 70–76
  4. ↩ a b c d e f g h Rule A Golomb-coded set matches all items in the set with probability 1 and other items with probability 1/M.

    Quoted source text (1)

    compressed into a probabilistic structure called a ''Golomb-coded set'' (GCS), which matches all items in the set with probability 1, and matches other items with probability <code>1/M</code> for some integer parameter <code>M</code>.

    BIP 158, lines 60–63
  5. ↩ a b c d e f Editorial inference A correctly constructed basic filter holds its specified set of scripts; a miss rules out a matching included output or spent-output script, but says nothing about excluded items (empty scripts and OP_RETURN outputs) or other data such as transaction IDs.

    Quoted source text (2)

    sync a regular Bitcoin wallet. A basic filter MUST contain exactly the following items for each transaction in a block: * The previous output script (the script being spent) for each input, except for the coinbase transaction. * The scriptPubKey of each output, aside from all <code>OP_RETURN</code> output scripts. Any "nil" items MUST NOT be included into the final set of filter elements.

    BIP 158, lines 270–275

    which matches all items in the set with probability 1

    BIP 158, lines 61–62
  6. ↩ a b c d e f Rule A basic filter MUST contain exactly, for each transaction, the previous output script of each input (except the coinbase) and each output's scriptPubKey except OP_RETURN outputs; nil items MUST NOT be included.

    Quoted source text (1)

    The basic filter is designed to contain everything that a light client needs to sync a regular Bitcoin wallet. A basic filter MUST contain exactly the following items for each transaction in a block: * The previous output script (the script being spent) for each input, except for the coinbase transaction. * The scriptPubKey of each output, aside from all <code>OP_RETURN</code> output scripts. Any "nil" items MUST NOT be included into the final set of filter elements.

    BIP 158, lines 269–275
  7. ↩ a b c d e Rule A GCS of N items is built by hashing into [0, N·M), sorting, taking differences, and Golomb-Rice coding them.

    Quoted source text (1)

    At a high level, a GCS is constructed from a set of <code>N</code> items by: # hashing all items to 64-bit integers in the range <code>[0, N * M)</code> # sorting the hashed values in ascending order # computing the differences between each value and the previous one # writing the differences sequentially, compressed with Golomb-Rice coding

    BIP 158, lines 67–71
  8. ↩ a b c d Rule Clients SHOULD sync block headers first, then download and verify filter headers (getcfheaders), MAY first fetch checkpoints every 1,000 blocks (getcfcheckpt), SHOULD connect to multiple peers unless a trusted peer serves headers, and on conflict SHOULD download the block, derive the filter and ban peers whose header does not match.

    Quoted source text (4)

    Clients SHOULD first sync the entire block header chain from peers using the standard headers-first syncing mechanism before downloading any block filters or filter headers.

    BIP 157, lines 367–369

    Once a client's block headers are in sync, it SHOULD download and verify filter headers for all blocks and filter types that it might later download. The client SHOULD send <code>getcfheaders</code> messages to peers and derive and store the filter headers for each block. The client MAY first fetch headers at evenly spaced intervals of 1,000 by sending <code>getcfcheckpt</code>.

    BIP 157, lines 374–378

    Unless securely connected to a trusted peer that is serving filter headers, the client SHOULD connect to multiple outbound peers that support each filter type to mitigate the risk of downloading incorrect headers.

    BIP 157, lines 383–385

    The client then SHOULD download the full block from any peer and derive the correct filter and filter header. The client SHOULD ban any peers that sent a filter header that does not match the computed one.

    BIP 157, lines 389–392
  9. ↩ a b c Rule The client SHOULD test that each filter links to its filter header and ban peers that send incorrect filters.

    Quoted source text (1)

    The client SHOULD test that each filter links to its corresponding filter header and ban peers that send incorrect filters.

    BIP 157, lines 404–405
  10. ↩ a b Rule BIP 158 allocates service bit NODE_COMPACT_FILTERS (1 << 6); a node that sets it MUST respond to all BIP 157 messages for filter type 0x00.

    Quoted source text (1)

    | NODE_COMPACT_FILTERS | style="white-space: nowrap;" | <code>1 << 6</code> | If enabled, the node MUST respond to all BIP 157 messages for filter type <code>0x00</code>

    BIP 158, lines 319–321
  11. ↩ a b c Author’s rationale The authors argue privacy improves because blocks can be downloaded from any source, so no one peer gets complete information; very privacy-conscious clients may use Private Information Retrieval.

    Quoted source text (1)

    Finally, client privacy is improved because blocks can be downloaded from ''any source'', so that no one peer gets complete information on the data required by a client. Extremely privacy conscious light clients may opt to anonymously fetch blocks using advanced techniques such a Private Information Retrieval

    BIP 157, lines 80–85
  12. ↩ a b c Rule A client fetching full blocks from the P2P network SHOULD download them from outbound peers at random to mitigate privacy loss from transaction intersection analysis. (Inference: the peer serving a downloaded block sees which block was requested.)

    Quoted source text (1)

    If a client is fetching full blocks from the P2P network, they SHOULD be downloaded from outbound peers at random to mitigate privacy loss due to transaction intersection analysis.

    BIP 157, lines 416–418
  13. ↩ a b c d e Rule To query, the target is hashed the same way and the decoded deltas are summed in order; the search stops once a value exceeds the target.

    Quoted source text (2)

    To check membership of an item in a compressed GCS, one must reconstruct the hashed set members from the encoded deltas. The procedure to do so is the reverse of the compression: deltas are decoded one by one and added to a cumulative sum. Each intermediate sum represents a hashed value in the original set. The queried item is hashed in the same way as the set members

    BIP 158, lines 219–223

    // Since the values in the set are sorted, terminate the search once // the decoded value exceeds the target. if set_item > target_hash: break

    BIP 158, lines 243–246
  14. ↩ a b Test vector With M = 784931, an unrelated script matches a given filter with probability 1/784931, about 1.3 in a million; checking 100 scripts against 10,000 blocks gives an expected 1.3 false matches.

    Quoted source text (1)

    Set membership queries against the hash outputs will have a false positive rate of <code>1 / M</code>.

    BIP 158, lines 83–84
  15. ↩ a b c d e Test vector This site's block-filter model rebuilds all ten of BIP 158's testnet filter vectors (the BIP's text says five blocks; the pinned file has ten) from the blocks and spent scripts, byte for byte, and reproduces their filter headers; the figures show some of them, rebuilt at build time.

    Quoted source text (1)

    Test vectors for basic block filters on five testnet blocks, including the filters and filter headers, can be found [[bip-0158/testnet-19.json|here]].

    BIP 158, line 431
  16. ↩ a b c d e Rule Golomb-Rice coding splits a value into a quotient and a remainder modulo 2^P; the quotient is written in unary (q ones then a zero) and the remainder as P big-endian bits.

    Quoted source text (1)

    With Golomb-Rice, a value is split into a quotient and remainder modulo <code>2^P</code>, which are encoded separately. The quotient <code>q</code> is encoded as ''unary'', with a string of <code>q</code> 1's followed by one 0. The remainder <code>r</code> is represented in big-endian by P bits.

    BIP 158, lines 131–134
  17. ↩ a b c d Rule Items are hashed with SipHash, which MUST use c = 2 and d = 4, and mapped into [0, F) by multiplying by F and taking the top 64 bits of the 128-bit product.

    Quoted source text (2)

    The items are first passed through the pseudorandom function ''SipHash'', which takes a 128-bit key <code>k</code> and a variable-sized byte vector and produces a uniformly random 64-bit output. Implementations of this BIP MUST use the SipHash parameters <code>c = 2</code> and <code>d = 4</code>.

    BIP 158, lines 87–90

    The 64-bit SipHash outputs are then mapped uniformly over the desired range by multiplying with F and taking the top 64 bits of the 128-bit result.

    BIP 158, lines 92–93
  18. ↩ a b c Rule The key k MUST be the first 16 bytes of the block hash in little-endian representation, so it is deterministic but varies by block.

    Quoted source text (1)

    The parameter <code>k</code> MUST be set to the first 16 bytes of the hash (in standard little-endian representation) of the block for which the filter is constructed. This ensures the key is deterministic while still varying from block to block.

    BIP 158, lines 300–303
  19. ↩ a b c d Rule The bit stream is padded with zeros to a byte boundary; the serialized filter is N as a CompactSize followed by the compressed bytes; a zero-element filter MUST be one zero byte.

    Quoted source text (3)

    Finally, the bit stream is padded with 0's to the nearest byte boundary and serialized to the output byte vector.

    BIP 158, lines 197–198

    Since the value <code>N</code> is required to decode a GCS, a serialized GCS includes it as a prefix, written as a <code>CompactSize</code>. Thus, the complete serialization of a filter is: * <code>N</code>, encoded as a <code>CompactSize</code> * The bytes of the compressed filter itself

    BIP 158, lines 305–309

    A zero element filter MUST be written as one byte containing zeroes.

    BIP 158, line 311
  20. ↩ a b Author’s rationale The authors cite analysis that M = 1.497137·2^P is close to optimal when P and M are chosen independently, and empirical analysis that these parameters minimize bandwidth, counting both false-positive block downloads and filter size.

    Quoted source text (2)

    Analysis has shown that if one is able to select <code>P</code> and <code>M</code> independently, then setting <code>M=1.497137 * 2^P</code> is close to optimal

    BIP 158, lines 291–294

    Empirical analysis also shows that these parameters minimize the bandwidth utilized, considering both the expected number of blocks downloaded due to false positives and the size of the filters themselves.

    BIP 158, lines 296–298
  21. ↩ a b c Test vector Each script enters the filter once: BIP 158 calls the elements a set, and the published filter for block 926,485, whose scripts repeat, only reproduces when duplicates are collapsed (9 elements, not 17).

    Quoted source text (1)

    Any "nil" items MUST NOT be included into the final set of filter elements.

    BIP 158, line 275
  22. ↩ Author’s rationale OP_RETURN outputs are excluded so filters can later be committed to by soft fork, likely in a coinbase OP_RETURN, without a circular dependency.

    Quoted source text (2)

    We exclude all outputs that start with <code>OP_RETURN</code> in order to allow filters to easily be committed to in the future via a soft-fork. A likely area for future commitments is an additional <code>OP_RETURN</code> output in the coinbase transaction similar to the current witness commitment

    BIP 158, lines 277–283

    we avoid a circular dependency between the commitment, and the item being committed to.

    BIP 158, lines 282–283
  23. ↩ a b Author’s rationale Because the hashed items are uniformly distributed, their sorted differences resemble a geometric distribution, which Golomb-Rice coding compresses optimally.

    Quoted source text (1)

    Since the items are distributed uniformly, it can be shown that the differences resemble a geometric distribution<ref>https://en.wikipedia.org/wiki/Geometric_distribution</ref>. ''Golomb-Rice'' ''coding''<ref>https://en.wikipedia.org/wiki/Golomb_coding#Rice_coding</ref> is a technique that optimally compresses geometrically distributed values.

    BIP 158, lines 124–129
  24. ↩ a b Rule The basic filter (type 0x00) MUST use P = 19 and M = 784931.

    Quoted source text (2)

    * Basic (<code>0x00</code>) ** <code>M = 784931</code> ** <code>P = 19</code>

    BIP 158, lines 263–265

    The parameter <code>P</code> MUST be set to <code>19</code>, and the parameter <code>M</code> MUST be set to <code>784931</code>.

    BIP 158, lines 290–291
  25. ↩ Rule Several targets can be checked at once by hashing and sorting them and merging against the decoded set.

    Quoted source text (1)

    Some applications may need to check for set intersection instead of membership of a single item. This can be performed far more efficiently than checking each item individually by leveraging the sorted structure of the compressed GCS. First the query elements are all hashed and sorted, then compared in order against the decompressed GCS contents.

    BIP 158, lines 253–257
  26. ↩ a b Rule A GCS takes at least N·(P + 1) bits.

    Quoted source text (1)

    The result is a byte vector with a minimum size of <code>N * (P + 1)</code> bits.

    BIP 158, lines 191–192
  27. ↩ a b Test vector In the published vectors, block 180,480's filter has 13 elements in 35 bytes and block 926,485's has 9 in 25 bytes: about 21 bits per element, close to the 20-bit floor, against 24 and 23 bits to write each hashed value at fixed width below N·M.

    Quoted source text (1)

    Test vectors for basic block filters on five testnet blocks, including the filters and filter headers

    BIP 158, line 431
  28. ↩ Test vector The model reproduces every row of BIP 158's P = 2 Golomb-Rice table, and the first code of a published filter with P = 19.

    Quoted source text (1)

    For example, this is a table of Golomb-Rice coded values using <code>P=2</code>:

    BIP 158, lines 134–135
  29. ↩ a b Rule A filter's hash is the double-SHA256 of the serialized filter; its header is the double-SHA256 of the filter hash concatenated with the previous filter header; the genesis block's previous header is 32 zero bytes.

    Quoted source text (1)

    The canonical hash of a block filter is the double-SHA256 of the serialized filter. Filter headers are 32-byte hashes derived for each block filter. They are computed as the double-SHA256 of the concatenation of the filter hash with the previous filter header. The previous filter header used to calculate that of the genesis block is defined to be the 32-byte array of 0's.

    BIP 157, lines 133–137
  30. ↩ a b c Author’s rationale Filter headers commit to all previous filters, like block headers; if peers' header chains differ, the client finds where they diverge, downloads the block, computes the correct filter, and identifies the faulty peer.

    Quoted source text (1)

    Similar to how block headers have a Merkle commitment to all transaction data in the block, we define filter headers that have commitments to the block filters. Also like block headers, filter headers each have a commitment to the preceding one. Before downloading the block filters themselves, a light client can download all filter headers for the current block chain and use them to verify the authenticity of the filters. If the filter header chains differ between multiple peers, the client can identify the point where they diverge, then download the full block and compute the correct filter, thus identifying which peer is faulty.

    BIP 157, lines 122–131
  31. ↩ a b c Author’s rationale The protocol guarantees that light clients with at least one honest peer can identify the correct block filters.

    Quoted source text (1)

    The resulting protocol guarantees that light clients with at least one honest peer are able to identify the correct block filters.

    BIP 157, lines 32–34
  32. ↩ a b Editorial inference To recompute a basic filter one needs the scripts the block's inputs spend, which the block itself does not contain; BIP 157 does not say how a light client should obtain or check them.

    Quoted source text (2)

    * The previous output script (the script being spent) for each input, except for the coinbase transaction.

    BIP 158, line 272

    The client then SHOULD download the full block from any peer and derive the correct filter and filter header.

    BIP 157, lines 389–391
  33. ↩ Rule A client MAY check whether a filter is empty from its header before requesting it.

    Quoted source text (1)

    The client MAY check if a filter is empty before requesting it by checking if the filter header commits to the hash of the empty filter, saving a round trip if that is the case.

    BIP 157, lines 407–409
  34. ↩ Rule Clients configured with trusted checkpoints MAY sync block headers only from the last checkpoint; separately, a client MAY fetch filter headers at every 1,000th block with getcfcheckpt and verify each 1,000-header range against them.

    Quoted source text (1)

    The client MAY first fetch headers at evenly spaced intervals of 1,000 by sending <code>getcfcheckpt</code>. The header checkpoints allow the client to download filter headers for different intervals from multiple peers in parallel, verifying each range of 1,000 headers against the checkpoints.

    BIP 157, lines 377–381
  35. ↩ Rule Nodes SHOULD generate and persist filters for each new block, and SHOULD NOT generate filters dynamically on request, because small filters of large blocks would allow DoS through asymmetric I/O.

    Quoted source text (2)

    For each new block that is connected to the main chain, nodes SHOULD generate filters for all supported types and persist them.

    BIP 157, lines 347–349

    Nodes SHOULD NOT generate filters dynamically on request, as malicious peers may be able to perform DoS attacks by requesting small filters derived from large blocks.

    BIP 157, lines 355–357
  36. ↩ Rule A getcfilters request MUST span a height difference strictly less than 1,000 (at most 1,000 blocks) and a getcfheaders request strictly less than 2,000; checkpoints are filter headers at heights that are positive multiples of 1,000.

    Quoted source text (3)

    The height of the block with hash StopHash MUST be greater than or equal to StartHeight, and the difference MUST be strictly less than 1000.

    BIP 157, line 170

    The height of the block with hash StopHash MUST be greater than or equal to StartHeight, and the difference MUST be strictly less than 2,000.

    BIP 157, line 234

    The filter headers included are the set of all filter headers on the requested chain where the height is a positive multiple of 1,000.

    BIP 157, lines 308–310
  37. ↩ Author’s rationale The authors chose filter headers at the P2P layer over requiring blocks to commit to filters, which would need a consensus change.

    Quoted source text (1)

    An alternative solution is to require Bitcoin blocks to include commitments to derived block filters, so light clients can verify authenticity given block headers and some additional witness data. This would require a network-wide change to the Bitcoin consensus rules, however, whereas this document proposes a solution purely at the P2P layer.

    BIP 157, lines 425–429
  38. ↩ History BIP 157 (Osuntokun, Akselrod, Posen) and BIP 158 (Osuntokun, Akselrod) were both assigned on 2017-05-24 and are recorded as Deployed.

    Quoted source text (2)

    Title: Client Side Block Filtering Authors: Olaoluwa Osuntokun <laolu32@gmail.com> Alex Akselrod <alex@akselrod.org> Jim Posen <jimpo@coinbase.com> Status: Deployed Type: Specification Assigned: 2017-05-24

    BIP 157, lines 4–10

    Title: Compact Block Filters for Light Clients Authors: Olaoluwa Osuntokun <laolu32@gmail.com> Alex Akselrod <alex@akselrod.org> Status: Deployed Type: Specification Assigned: 2017-05-24

    BIP 158, lines 4–9