Change Details

[[ https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki | 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). [[ https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki | 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 BIP157 (as-yet open): https://github.com/bitcoin/bitcoin/pull/14121

[[ https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki | 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). [[ https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki | 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 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. ``` BIP157 (as-yet open): https://github.com/bitcoin/bitcoin/pull/14121

[[ https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki | 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). [[ https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki | 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 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. ``` BIP157 (as-yet open): https://github.com/bitcoin/bitcoin/pull/14121