Page MenuHomePhabricator

BIP157 & BIP158 backports
Open, NormalPublic

Description

BIP158 describes compact block filters: highly space-efficient ways for nodes to describe the full set of items (spent outpoints, output scriptpubkeys) that are present in a block, that a wallet can then use to determine which blocks it is interested in (e.g., by detecting which blocks contain transactions outputting to scriptpubkeys owned by the wallet).

The technology at play is sets of short hashes, with a hashspace chosen to be compressible in a nearly entropy-optimal way with Golomb-Rice encoding. The false positive rate is one per 784931. The compressed sets are awkward to update or query individual items compared to Bloom filters, however they are only 70% of the size of a Bloom filter for a similar false-positive rate. Full nodes can calculate these once for a given block, then throw them in a database and serve them as-is on demand.

Wallets download the full set of filters (will generally be about 2-3% of block size), then uses them to check which blocks are interesting. The wallet then downloads full blocks (but only the relevant ones) to reconstruct transaction history. Very little information leaks to the full node (who only learns which blocks were interesting, but not why).

BIP157 describes an upgrade to the p2p protocol to allow clients to fetch the compact block filter from a full node (who will have already computed the filters and stored them in a database). In addition, it describes 'filter headers' which work in a chain, much like block headers but without proof of work. Wallets can use this filter header chain combined with multiple connections, to quickly compare the filter 'tips' of various nodes. In case of disagreement they can rewind to fork point and find the liar. Thus absent an eclipse attack, wallets have good confidence that they are seeing everything of interest in the blockchain. In future, the filter hashes could be committed into the chain by consensus rule, which would simplify this process to have security backed by proof of work.

BIP158 (merged): https://github.com/bitcoin/bitcoin/pull/12254

PR 15532
82c3b3f8e Remove sharp edge (uninitialized m_filter_type) when using the compiler-generated constructor for BlockFilter

PR 14357
4f4993fe2 Remove UBSan suppression
958e1a307 streams: Remove unused seek(size_t)

PR 14172
e4ed8ce2c blockfilter: Remove default clause in switch statement.
c30620983 blockfilter: Additional constructors for BlockFilter.
20b812993 blockfilter: Refactor GCS params into struct.

PR 14074
fef5adcc3 blockfilter: Use unordered_set instead of set in blockfilter.
4fb789e9b Extract CSipHasher to it's own file in crypto/ directory.

PR 14073
f05599557 blockfilter: Omit empty scripts from filter contents.

PR 12254
254c85b68 bench: Benchmark GCS filter creation and matching.
f33b717a8 blockfilter: Optimization on compilers with int128 support.
97b64d67d blockfilter: Unit test against BIP 158 test vectors.
a4afb9cad blockfilter: Additional helper methods to compute hash and header.
cd09c7925 blockfilter: Serialization methods on BlockFilter.
c1855f605 blockfilter: Construction of basic block filters.
53e7874e0 blockfilter: Simple test for GCSFilter construction and Match.
558c536e3 blockfilter: Implement GCSFilter Match methods.
cf70b5500 blockfilter: Implement GCSFilter constructors.
c454f0ac6 blockfilter: Declare GCSFilter class for BIP 158 impl.
9b622dc72 streams: Unit tests for BitStreamReader and BitStreamWriter.
fe943f99b streams: Implement BitStreamReader/Writer classes.
87f2d9ee4 streams: Unit test for VectorReader class.
947133dec streams: Create VectorReader stream interface for vectors.

BIP158 index and RPC: https://github.com/bitcoin/bitcoin/pull/14121

PR 14121
c7efb652f blockfilter: Update BIP 158 test vectors.
19308c9e2 rpc: Add getblockfilter RPC method.
ff3510509 init: Add CLI option to enable block filter index.
accc8b8b1 index: Access functions for global block filter indexes.
2bc90e4e7 test: Unit test for block filter index reorg handling.
6bcf0998c test: Unit tests for block index filter.
b5e8200db index: Implement lookup methods on block filter index.
75a76e361 index: Implement block filter index with write operations.
2ad2338ef serialize: Serialization support for big-endian 32-bit ints.
ba6ff9a6f blockfilter: Functions to translate filter types to/from names.
62b7a4f09 index: Ensure block locator is not stale after chain reorg.
4368384f1 index: Allow atomic commits of index state to be extended.

needs T617 T630 T631

BIP157 : https://github.com/bitcoin/bitcoin/pull/16442

Related Objects

Event Timeline

markblundeberg triaged this task as Normal priority.Apr 11 2019, 01:21
markblundeberg created this task.
markblundeberg updated the task description. (Show Details)Apr 12 2019, 22:49
markblundeberg updated the task description. (Show Details)Apr 13 2019, 18:51

getting commit fef5adcc3 looks like it should be done after T590, though it looks like the rest of backports can proceed independently of that.

nvm, should be fine!

markblundeberg updated the task description. (Show Details)Apr 24 2019, 01:16
markblundeberg updated the task description. (Show Details)Apr 30 2019, 01:19
markblundeberg updated the task description. (Show Details)Apr 30 2019, 01:24
markblundeberg updated the task description. (Show Details)May 2 2019, 01:00
markblundeberg updated the task description. (Show Details)May 2 2019, 02:44
markblundeberg updated the task description. (Show Details)
markblundeberg updated the task description. (Show Details)May 5 2019, 01:42
markblundeberg updated the task description. (Show Details)May 5 2019, 02:46
markblundeberg updated the task description. (Show Details)Jul 9 2019, 22:19
markblundeberg updated the task description. (Show Details)Aug 14 2019, 23:35