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 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
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
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.
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 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.
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
Every script, in full
76a914876fbb82ec05caa6af7a3b5e5a983aae6c6cc6d688acoutput6a24aa21a9ed5c748e121c0fe146d973a4ac26fa4a68b0549d46ee22d25f50a5e46fe1b377eeoutput, left out: starts with OP_RETURN52534b424c4f434b3acd16772ad61a3c5f00287480b720f6035d5e54c9efc71be94bb5e3727f109090output76a9143ebc40e411ed3c76f86711507ab952300890397288acoutput76a91450333046115eaa0ac9e0216565f945070e44573988acoutput76a914c01a7ca16b47be50cbdbc60724f701d52d75156688acoutputa914b7e6f7ff8658b2d1fb107e3d7be7af4742e6b1b387output76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acoutputa9148fc37ad460fdfbd2b44fe446f6e3071a4f64faa687output76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acoutput, left out: duplicate of an earlier elementa914feb8a29635c56d9cd913122f90678756bf23887687spent76a914c01a7ca16b47be50cbdbc60724f701d52d75156688acspent, left out: duplicate of an earlier element76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acspent, left out: duplicate of an earlier element76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acspent, left out: duplicate of an earlier element76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acspent, left out: duplicate of an earlier element76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acspent, left out: duplicate of an earlier element76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acspent, left out: duplicate of an earlier element76a914913bcc2be49cb534c20474c4dee1e9c4c317e7eb88acspent, left out: duplicate of an earlier element
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
The block's 3 scripts go through SipHash-2-4, keyed with the first 16 bytes of the block hash.
Each 64-bit hash is scaled into [0, F), F = N · M = 3 × 784,931.
Sorted, only the gaps between neighbours are kept.
Each gap becomes a Golomb-Rice code: the quotient by 2^19 in unary, then 19 remainder bits.
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
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
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
The client asks several peers for filter headers. Two agree up to H2 and differ from H3 on.
It downloads that block, gets the scripts its inputs spend, and builds the filter and the header from H2 itself.
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.
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.
-
↩ 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.
-
↩ 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.
BIP 157 L51–53 BIP 157 L57–59 BIP 157 L61–62 BIP 157 L64–66
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.
It has been shown, however, that most implementations available offer virtually ''zero privacy'' to wallets and other
Additionally, malicious full nodes serving light clients can omit critical data with little risk of detection
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
-
↩ 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.
-
↩ 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>.
-
↩ 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.
BIP 158 L270–275 BIP 158 L61–62
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.
which matches all items in the set with probability 1
-
↩ 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.
-
↩ 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
-
↩ 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.
BIP 157 L367–369 BIP 157 L374–378 BIP 157 L383–385 BIP 157 L389–392
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.
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>.
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.
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.
-
↩ 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.
-
↩ 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>
-
↩ 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
-
↩ 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.
-
↩ 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.
BIP 158 L219–223 BIP 158 L243–246
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
// Since the values in the set are sorted, terminate the search once // the decoded value exceeds the target. if set_item > target_hash: break
-
↩ 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>.
-
↩ 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]].
-
↩ 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.
-
↩ 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>.
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.
-
↩ 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.
-
↩ 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.
BIP 158 L197–198 BIP 158 L305–309 BIP 158 L311
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.
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
A zero element filter MUST be written as one byte containing zeroes.
-
↩ 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.
BIP 158 L291–294 BIP 158 L296–298
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
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.
-
↩ 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.
-
↩ 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.
BIP 158 L277–283 BIP 158 L282–283
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
we avoid a circular dependency between the commitment, and the item being committed to.
-
↩ 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.
-
↩ a b Rule The basic filter (type 0x00) MUST use P = 19 and M = 784931.
BIP 158 L263–265 BIP 158 L290–291
Quoted source text (2)
* Basic (<code>0x00</code>) ** <code>M = 784931</code> ** <code>P = 19</code>
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>.
-
↩ 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.
-
↩ 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.
-
↩ 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
-
↩ 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>:
-
↩ 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.
-
↩ 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.
-
↩ 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.
-
↩ 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.
The client then SHOULD download the full block from any peer and derive the correct filter and filter header.
-
↩ 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.
-
↩ 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.
-
↩ 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.
BIP 157 L347–349 BIP 157 L355–357
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.
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.
-
↩ 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.
BIP 157 L170 BIP 157 L234 BIP 157 L308–310
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.
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.
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.
-
↩ 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.
-
↩ 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
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