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

1 files changed, 43 insertions, 0 deletions

diff --git a/src/bench/gcs_filter.cpp b/src/bench/gcs_filter.cpp
new file mode 100644
index 0000000000..6f4e384e3b
--- /dev/null
+++ b/src/bench/gcs_filter.cpp
@@ -0,0 +1,43 @@
+// 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 <bench/bench.h>
+#include <blockfilter.h>
+
+static void ConstructGCSFilter(benchmark::State& state)
+{
+    GCSFilter::ElementSet elements;
+    for (int i = 0; i < 10000; ++i) {
+        GCSFilter::Element element(32);
+        element[0] = static_cast<unsigned char>(i);
+        element[1] = static_cast<unsigned char>(i >> 8);
+        elements.insert(std::move(element));
+    }
+
+    uint64_t siphash_k0 = 0;
+    while (state.KeepRunning()) {
+        GCSFilter filter(siphash_k0, 0, 20, 1 << 20, elements);
+
+        siphash_k0++;
+    }
+}
+
+static void MatchGCSFilter(benchmark::State& state)
+{
+    GCSFilter::ElementSet elements;
+    for (int i = 0; i < 10000; ++i) {
+        GCSFilter::Element element(32);
+        element[0] = static_cast<unsigned char>(i);
+        element[1] = static_cast<unsigned char>(i >> 8);
+        elements.insert(std::move(element));
+    }
+    GCSFilter filter(0, 0, 20, 1 << 20, elements);
+
+    while (state.KeepRunning()) {
+        filter.Match(GCSFilter::Element());
+    }
+}
+
+BENCHMARK(ConstructGCSFilter, 1000);
+BENCHMARK(MatchGCSFilter, 50 * 1000);