dash/src/blockfilter.cpp

278 lines
7.9 KiB
C++
Raw Permalink Normal View History

Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
// Copyright (c) 2018 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <mutex>
#include <sstream>
#include <set>
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
#include <blockfilter.h>
#include <crypto/siphash.h>
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
#include <hash.h>
#include <primitives/transaction.h>
#include <script/script.h>
#include <streams.h>
#include <util/golombrice.h>
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
/// SerType used to serialize parameters in GCS filter encoding.
static constexpr int GCS_SER_TYPE = SER_NETWORK;
/// Protocol version used to serialize parameters in GCS filter encoding.
static constexpr int GCS_SER_VERSION = 0;
static const std::map<BlockFilterType, std::string> g_filter_types = {
{BlockFilterType::BASIC_FILTER, "basic"},
};
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
uint64_t GCSFilter::HashToRange(const Element& element) const
{
uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
.Write(element.data(), element.size())
.Finalize();
return FastRange64(hash, m_F);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
}
std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
{
std::vector<uint64_t> hashed_elements;
hashed_elements.reserve(elements.size());
for (const Element& element : elements) {
hashed_elements.push_back(HashToRange(element));
}
std::sort(hashed_elements.begin(), hashed_elements.end());
return hashed_elements;
}
GCSFilter::GCSFilter(const Params& params)
: m_params(params), m_N(0), m_F(0), m_encoded{0}
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
{}
GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter)
: m_params(params), m_encoded(std::move(encoded_filter))
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
{
VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
uint64_t N = ReadCompactSize(stream);
m_N = static_cast<uint32_t>(N);
if (m_N != N) {
throw std::ios_base::failure("N must be <2^32");
}
m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
// Verify that the encoded filter contains exactly N elements. If it has too much or too little
// data, a std::ios_base::failure exception will be raised.
BitStreamReader<VectorReader> bitreader(stream);
for (uint64_t i = 0; i < m_N; ++i) {
GolombRiceDecode(bitreader, m_params.m_P);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
}
if (!stream.empty()) {
throw std::ios_base::failure("encoded_filter contains excess data");
}
}
GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
: m_params(params)
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
{
size_t N = elements.size();
m_N = static_cast<uint32_t>(N);
if (m_N != N) {
throw std::invalid_argument("N must be <2^32");
}
m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
WriteCompactSize(stream, m_N);
if (elements.empty()) {
return;
}
BitStreamWriter<CVectorWriter> bitwriter(stream);
uint64_t last_value = 0;
for (uint64_t value : BuildHashedSet(elements)) {
uint64_t delta = value - last_value;
GolombRiceEncode(bitwriter, m_params.m_P, delta);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
last_value = value;
}
bitwriter.Flush();
}
bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
{
VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
// Seek forward by size of N
uint64_t N = ReadCompactSize(stream);
assert(N == m_N);
BitStreamReader<VectorReader> bitreader(stream);
uint64_t value = 0;
size_t hashes_index = 0;
for (uint32_t i = 0; i < m_N; ++i) {
uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
value += delta;
while (true) {
if (hashes_index == size) {
return false;
} else if (element_hashes[hashes_index] == value) {
return true;
} else if (element_hashes[hashes_index] > value) {
break;
}
hashes_index++;
}
}
return false;
}
bool GCSFilter::Match(const Element& element) const
{
uint64_t query = HashToRange(element);
return MatchInternal(&query, 1);
}
bool GCSFilter::MatchAny(const ElementSet& elements) const
{
const std::vector<uint64_t> queries = BuildHashedSet(elements);
return MatchInternal(queries.data(), queries.size());
}
const std::string& BlockFilterTypeName(BlockFilterType filter_type)
{
static std::string unknown_retval = "";
auto it = g_filter_types.find(filter_type);
return it != g_filter_types.end() ? it->second : unknown_retval;
}
bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
for (const auto& entry : g_filter_types) {
if (entry.second == name) {
filter_type = entry.first;
return true;
}
}
return false;
}
const std::set<BlockFilterType>& AllBlockFilterTypes()
{
static std::set<BlockFilterType> types;
static std::once_flag flag;
std::call_once(flag, []() {
for (auto entry : g_filter_types) {
types.insert(entry.first);
}
});
return types;
}
const std::string& ListBlockFilterTypes()
{
static std::string type_list;
static std::once_flag flag;
std::call_once(flag, []() {
std::stringstream ret;
bool first = true;
for (auto entry : g_filter_types) {
if (!first) ret << ", ";
ret << entry.second;
first = false;
}
type_list = ret.str();
});
return type_list;
}
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
const CBlockUndo& block_undo)
{
GCSFilter::ElementSet elements;
for (const CTransactionRef& tx : block.vtx) {
for (const CTxOut& txout : tx->vout) {
const CScript& script = txout.scriptPubKey;
if (script.empty() || script[0] == OP_RETURN) continue;
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
elements.emplace(script.begin(), script.end());
}
}
for (const CTxUndo& tx_undo : block_undo.vtxundo) {
for (const Coin& prevout : tx_undo.vprevout) {
const CScript& script = prevout.out.scriptPubKey;
if (script.empty()) continue;
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
elements.emplace(script.begin(), script.end());
}
}
return elements;
}
BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
std::vector<unsigned char> filter)
: m_filter_type(filter_type), m_block_hash(block_hash)
{
GCSFilter::Params params;
if (!BuildParams(params)) {
throw std::invalid_argument("unknown filter_type");
}
m_filter = GCSFilter(params, std::move(filter));
}
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
: m_filter_type(filter_type), m_block_hash(block.GetHash())
{
GCSFilter::Params params;
if (!BuildParams(params)) {
throw std::invalid_argument("unknown filter_type");
}
m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
}
bool BlockFilter::BuildParams(GCSFilter::Params& params) const
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
{
switch (m_filter_type) {
case BlockFilterType::BASIC_FILTER:
params.m_siphash_k0 = m_block_hash.GetUint64(0);
params.m_siphash_k1 = m_block_hash.GetUint64(1);
params.m_P = BASIC_FILTER_P;
params.m_M = BASIC_FILTER_M;
return true;
case BlockFilterType::INVALID:
return false;
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
}
return false;
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
}
uint256 BlockFilter::GetHash() const
{
const std::vector<unsigned char>& data = GetEncodedFilter();
uint256 result;
CHash256().Write(data).Finalize(result);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
return result;
}
uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
{
const uint256& filter_hash = GetHash();
uint256 result;
CHash256()
.Write(filter_hash)
.Write(prev_header)
.Finalize(result);
Merge #12254: BIP 158: Compact Block Filters for Light Clients 254c85b68794ada713dbdae415db72adf5fcbaf3 bench: Benchmark GCS filter creation and matching. (Jim Posen) f33b717a85363e067316c133a542559d2f4aaeca blockfilter: Optimization on compilers with int128 support. (Jim Posen) 97b64d67daf0336dfb64b132f3e4d6a4c1967da4 blockfilter: Unit test against BIP 158 test vectors. (Jim Posen) a4afb9cadbaecb0676e6475ab8d32a52faecb47a blockfilter: Additional helper methods to compute hash and header. (Jim Posen) cd09c7925b5af4104834971cfe072251e3ac2bda blockfilter: Serialization methods on BlockFilter. (Jim Posen) c1855f6052aca806fdb51be01b30dfeee8b55f40 blockfilter: Construction of basic block filters. (Jim Posen) 53e7874e079f9ddfe8b176f11d46e6b59c7283d5 blockfilter: Simple test for GCSFilter construction and Match. (Jim Posen) 558c536e35a25594881693e6ff01d275c88d7af1 blockfilter: Implement GCSFilter Match methods. (Jim Posen) cf70b550054eed36f194eaa13f4a9cb31e32df38 blockfilter: Implement GCSFilter constructors. (Jim Posen) c454f0ac63c6028f54c7eb51683b3ccdb475b19b blockfilter: Declare GCSFilter class for BIP 158 impl. (Jim Posen) 9b622dc72279b027c59d6541cddff53800fc689b streams: Unit tests for BitStreamReader and BitStreamWriter. (Jim Posen) fe943f99bf0a2bbb12e30bc4803c0337e3c95b93 streams: Implement BitStreamReader/Writer classes. (Jim Posen) 87f2d9ee43a9220076b1959d1ca65245d9591be9 streams: Unit test for VectorReader class. (Jim Posen) 947133dec92cd25ec2b3358c09b8614ba6fb40d4 streams: Create VectorReader stream interface for vectors. (Jim Posen) Pull request description: This implements the compact block filter construction in [BIP 158](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki). The code is not used anywhere in the Bitcoin Core code base yet. The next step towards [BIP 157](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki) support would be to create an indexing module similar to `TxIndex` that constructs the basic and extended filters for each validated block. ### Filter Sizes [Here](https://gateway.ipfs.io/ipfs/QmRqaAAQZ5ZX5eqxP7J2R1MzFrc2WDdKSWJEKtQzyawqog) is a CSV of filter sizes for blocks in the main chain. As you can see below, the ratio of filter size to block size drops after the first ~150,000 blocks: ![filter_sizes](https://user-images.githubusercontent.com/881253/42900589-299772d4-8a7e-11e8-886d-0d4f3f4fbe44.png) The reason for the relatively large filter sizes is that Golomb-coded sets only achieve good compression with a sufficient number of elements. Empirically, the average element size with 100 elements is 14% larger than with 10,000 elements. The ratio of filter size to block size is computed without witness data for basic filters. Here is a summary table of filter size ratios *for blocks after height 150,000*: | Stat | Filter Type | |-------|--------------| | Weighted Size Ratio Mean | 0.0198 | | Size Ratio Mean | 0.0224 | | Size Ratio Std Deviation | 0.0202 | | Mean Element Size (bits) | 21.145 | | Approx Theoretical Min Element Size (bits) | 21.025 | Tree-SHA512: 2d045fbfc3fc45490ecb9b08d2f7e4dbbe7cd8c1c939f06bbdb8e8aacfe4c495cdb67c820e52520baebbf8a8305a0efd8e59d3fa8e367574a4b830509a39223f
2018-08-26 16:57:01 +02:00
return result;
}