How can a light client ask whether a block concerns it?

Evidence

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

1. ↩ 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.

   BIP 157 L41–47

   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.

2. ↩ 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

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

   BIP 157 L4–10 BIP 158 L4–9

   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

4. ↩ 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.

   BIP 157 L70–76

   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.

5. ↩ a b c Rule A Golomb-coded set matches all items in the set with probability 1 and other items with probability 1/M.

   BIP 158 L60–63

   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>.

6. ↩ a b c 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.

   BIP 158 L131–134

   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.

7. ↩ 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.

   BIP 158 L134–135

   Quoted source text (1)

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

8. ↩ a b c d 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.

   BIP 158 L269–275

   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.

9. ↩ a b 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).

   BIP 158 L275

   Quoted source text (1)

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

10. ↩ 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.

11. ↩ a b c d 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.

    BIP 158 L431

    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]].

12. ↩ a b 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.

13. ↩ a b Editorial inference A filter holds scripts only; a missing match rules out an output paying to, or an input spending from, that script in the block, and says nothing about data outside the element set (txids, OP_RETURN outputs).

    BIP 158 L270–273 BIP 158 L61–62

    Quoted source text (2)

    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.

    which matches all items in the set with probability 1

14. ↩ 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.

    BIP 158 L87–90 BIP 158 L92–93

    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.

15. ↩ 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.

    BIP 158 L300–303

    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.

16. ↩ Rule A GCS of N items is built by hashing into [0, N·M), sorting, taking differences, and Golomb-Rice coding them.

    BIP 158 L67–71

    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

17. ↩ Author’s rationale Because the hashed items are uniformly distributed, their sorted differences resemble a geometric distribution, which Golomb-Rice coding compresses optimally.

    BIP 158 L124–129

    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.

18. ↩ 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>.

19. ↩ 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.

20. ↩ Rule A GCS takes at least N·(P + 1) bits.

    BIP 158 L191–192

    Quoted source text (1)

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

21. ↩ 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 about 23 bits to write each hashed value at fixed width below N·M.

    BIP 158 L431

    Quoted source text (1)

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

22. ↩ a b 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

23. ↩ Rule Several targets can be checked at once by hashing and sorting them and merging against the decoded set.

    BIP 158 L253–257

    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.

24. ↩ 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.

    BIP 158 L83–84

    Quoted source text (1)

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

25. ↩ 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.

    BIP 157 L80–85

    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

26. ↩ 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.)

    BIP 157 L416–418

    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.

27. ↩ 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.

    BIP 157 L133–137

    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.

28. ↩ 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.

    BIP 157 L122–131

    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.

29. ↩ 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.

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

    BIP 157 L404–405

    Quoted source text (1)

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

31. ↩ Author’s rationale The protocol guarantees that light clients with at least one honest peer can identify the correct block filters.

    BIP 157 L32–34

    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.

32. ↩ 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.

    BIP 157 L377–381

    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.

33. ↩ 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.

    BIP 158 L272 BIP 157 L389–391

    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.

34. ↩ Rule A client MAY check whether a filter is empty from its header before requesting it.

    BIP 157 L407–409

    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.

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.

    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.

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.

    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.

37. ↩ 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.

    BIP 158 L319–321

    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>

38. ↩ 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.

    BIP 157 L425–429

    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.