BIP 158: Compact Block Filters for Light Clients

jimpo commented at 1:42 am on January 24, 2018: contributor

This implements the compact block filter construction in BIP 158. The code is not used anywhere in the Bitcoin Core code base yet. The next step towards BIP 157 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 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

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

fanquake added the label Consensus on Jan 24, 2018

meshcollider commented at 1:57 am on January 24, 2018: contributor

Big Concept ACK, excited about this

laanwj commented at 2:36 pm on January 24, 2018: member

Should this be labeled consensus? This is a P2P change, right?

jimpo commented at 5:09 pm on January 24, 2018: contributor

@laanwj This is a data structure to be used in a P2P change. I first thought that it shouldn’t be tagged “Consensus”, but there’s an argument to be made for it. It doesn’t affect blockchain consensus, but it is kind of a softer P2P consensus change, where network clients (though not other full nodes) may disconnect/ban you if you serve incorrectly computed block filters. I’ll let you make the call on the tag.

sipa commented at 5:12 pm on January 24, 2018: member

Any fork that can be resolved by a P2P adaptor that speaks both protocols is not a consensus change.

laanwj added the label P2P on Jan 24, 2018

laanwj removed the label Consensus on Jan 24, 2018

laanwj commented at 5:19 pm on January 24, 2018: member

This is a data structure to be used in a P2P change.

Thanks for the explanation. With “consensus” we mean the blockchain consensus rules code. Banning\disconnecting is a P2P level issue. So changing the label to P2P.

jonasschnelli commented at 10:33 pm on January 25, 2018: contributor

Great work @jimpo! Big Concept ACK,… will help to get this done.

in src/blockfilter.cpp:117 in 884ebec137 outdated

112+
113+    if (m_N >= (1ULL << 32)) {
114+        throw std::invalid_argument("N must be <2^32");
115+    }
116+
117+    // Surface any errors decoding the filter on construction.

jonasschnelli commented at 9:13 am on February 9, 2018:

Not sure, but I guess that comments belongs to L113?

jimpo commented at 6:49 pm on February 9, 2018:

No, the idea is that the below lines fully decode the filter in the constructor so that any errors decoding get raised during construction rather than when it is first matched against. I’ll elaborate on the comment.

jonasschnelli commented at 9:46 am on February 9, 2018: contributor

Reviewed and tested a bit… nice, clean PR! I would wish we had more test vectors…

Sjors commented at 3:14 pm on February 9, 2018: member

Concept ACK. Would it useful to add some (hidden) RPC commands so other developers can test it?

jimpo commented at 6:15 pm on February 9, 2018: contributor

@jonasschnelli Thanks for reviewing. The test vectors were generated from a Go program I have that cross-validates against the btcsuite implementation. I can easily add any specific testnet blocks to the list of cases. The blocks were chosen to exercise certain edge cases (eg. empty filters, duplicate pushdatas, invalid output scripts), but the vectors aren’t commented with which edges cases they exercise. I’ll add the comments, because it seems worthwhile. @Sjors I’d definitely like to see RPC commands to fetch specific filters and filter headers, but I think it makes more sense to do that after adding the filter index, so that the RPC handlers just have to look up a precomputed filter/header. (So basically, in a subsequent PR).

jimpo force-pushed on Mar 11, 2018

jimpo force-pushed on Mar 12, 2018

in src/streams.h:143 in 93f702b08e outdated

137@@ -138,6 +138,80 @@ class CVectorWriter
138     size_t nPos;
139 };
140 
141+/* Minimal stream for reading from an existing vector by reference
142+ */
143+class CVectorReader

ryanofsky commented at 6:29 pm on March 15, 2018:

In commit “streams: Create CVectorReader stream interface for vectors.” (93f702b08e413c5c025b155bfb62b721d27939f5)

This is pretty similar to the VectorReader class @TheBlueMatt is adding here: https://github.com/TheBlueMatt/bitcoin/commit/bb608a995e8fd16d156145bf41023e7a77d44971 for https://github.com/bitcoin/bitcoin/compare/master...TheBlueMatt:2018-02-miningserver

Your implementation is more general with support for deserialization in the constructor and more complete comments. But his has a pos() method and uses non-hungarian names which are recommended by the contrib guide. Anyway you may want to incorporate some of his changes.

jimpo commented at 6:22 pm on March 19, 2018:

OK, I can bring that commit over instead or modify this one to remove the hungarian notation.

sipa commented at 7:34 pm on May 12, 2018:

Agree, it would be nice to align the two implementations.

jimpo commented at 5:35 am on May 14, 2018:

Done.

in src/streams.h:148 in 93f702b08e outdated

143+class CVectorReader
144+{
145+private:
146+    const int nType;
147+    const int nVersion;
148+    const std::vector<unsigned char>& vchData;

ryanofsky commented at 6:34 pm on March 15, 2018:

In commit “streams: Create CVectorReader stream interface for vectors.” (93f702b08e413c5c025b155bfb62b721d27939f5)

It would be nice if this just had const unsigned char* and size_t members instead of a requiring a reference to an actual vector. That way the class could be used to efficiently deserialize from any memory location, and be compatible with other containers like std::string.

jimpo commented at 6:27 pm on March 19, 2018:

I’d rather not deal with raw pointers because it leaves space for unsafe accesses. If generality is a concern, I’d prefer a templated approach with random access iterators.

sipa commented at 7:36 pm on May 12, 2018:

An alternative (which could be done later, not a blocker for this PR) is using the Span class that was introduced in #12886 and is being extended in #13062).

ryanofsky commented at 2:30 pm on August 15, 2018:

Re: #12254 (review)

I think it would be good to change VectorReader to SpanReader now that Span exists. It would be a simple change, and better describe what this class does, and make it more reusable.

ryanofsky commented at 6:39 pm on March 15, 2018: member

(edited 2018-08-17)

utACK a23681bd6382f44a1246bcdd430e6f54f71c1f99. Left minor comments (feel free to ignore). Overall code looks very good.

f154ded087a1a1f0c9748dd75ceb8531968b75f7 streams: Create VectorReader stream interface for vectors. (1/14)
bdb34199345ad2c6f98da5d3f303d0993f6c722c streams: Unit test for VectorReader class. (2/14)
faaa4b8432d194acb26ffcac07c379444da327ac streams: Implement BitStreamReader/Writer classes. (3/14)
e15e553b746e64f0eeda420e4c10eccfc747d69f streams: Unit tests for BitStreamReader and BitStreamWriter. (4/14)
a4b03be28699e62a92085e3b75f6a80fe0ad05ea blockfilter: Declare GCSFilter class for BIP 158 impl. (5/14)
515af0398b8f2aab77645871198c69fea91a07ff blockfilter: Implement GCSFilter constructors. (6/14)
6c1262fac124acc70599760798240027ddf58f8e blockfilter: Implement GCSFilter Match methods. (7/14)
e98621135aef92106c5b0a7f7b06877a275c19fb blockfilter: Simple test for GCSFilter construction and Match. (8/14)
f7a5bdb54ba597fe06bcb54e886c43436899ab48 blockfilter: Construction of basic block filters. (9/14)
c14e4d5a950ed40d96a8956e4622e1d9670da72d blockfilter: Serialization methods on BlockFilter. (10/14)
ab852f91602c268d894e8f882f7f8212fd39f9dd blockfilter: Additional helper methods to compute hash and header. (11/14)
9cf17eb1518f9f7c96ceac4f8f91f13e8dd5c9c2 blockfilter: Unit test against BIP 158 test vectors. (12/14)
2837e40ef94d9ae5133c0756ea9ec38d6591d730 blockfilter: Optimization on compilers with int128 support. (13/14)
a23681bd6382f44a1246bcdd430e6f54f71c1f99 bench: Benchmark GCS filter creation and matching. (14/14)

laanwj added this to the "Blockers" column in a project

Sjors commented at 7:07 pm on March 15, 2018: member

@Sjors I’d definitely like to see RPC commands to fetch specific filters and filter headers, but I think it makes more sense to do that after adding the filter index, so that the RPC handlers just have to look up a precomputed filter/header. (So basically, in a subsequent PR).

Even a proof-of-concept PR for that would be useful for review.

jimpo commented at 1:48 am on March 20, 2018: contributor

@Sjors Here is a branch that exposes an RPC for testing/playing around: https://github.com/jimpo/bitcoin/tree/bip158-rpc. Is not intended to be merged for reasons stated above.

laanwj removed this from the "Blockers" column in a project

in src/streams.h:518 in e6e320d600 outdated

513+class BitStreamReader
514+{
515+private:
516+    IStream& m_istream;
517+    uint8_t m_buffer;
518+    int m_offset;

ryanofsky commented at 5:47 pm on April 2, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.”

Comment for m_offset would be helpful. Maybe //!< Number of high order bits in m_buffer already returned by previous Read() calls.

in src/streams.h:522 in e6e320d600 outdated

517+    uint8_t m_buffer;
518+    int m_offset;
519 
520+public:
521+    BitStreamReader(IStream& istream)
522+        : m_istream(istream), m_buffer(0), m_offset(8) {}

ryanofsky commented at 5:57 pm on April 2, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.”

Would be nice to initialize m_buffer, m_offset above, where they are declared (see “Initialize all non-static class members where they are defined” guideline from https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md). Similarly in BitStreamWriter below.

jimpo commented at 1:04 am on April 12, 2018:

Didn’t know about that guideline. Will do.

in src/streams.h:557 in e6e320d600 outdated

545+        return data;
546+    }
547+};
548 
549+template <typename OStream>
550+class BitStreamWriter

ryanofsky commented at 5:59 pm on April 2, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.”

Would be nice to add a simple unit test writing values to a stream with BitStreamWriter, and then making sure same values are returned from BitStreamReader.

jimpo commented at 9:27 am on April 17, 2018:

Added in 5f67272f5a2d8567faf7b139c0239bc2788ed8b1.

in src/streams.h:558 in e6e320d600 outdated

553+    OStream& m_ostream;
554+    uint8_t m_buffer;
555+    int m_offset;
556 
557+public:
558+    BitStreamWriter(OStream& ostream)

ryanofsky commented at 6:05 pm on April 2, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.”

Would be good to add destructor either asserting m_offset == 0, or calling Flush(). Discarding bits that have been written but not flushed seems less safe than you might want as default behavior.

in src/streams.h:555 in e6e320d600 outdated

550+class BitStreamWriter
551+{
552+private:
553+    OStream& m_ostream;
554+    uint8_t m_buffer;
555+    int m_offset;

ryanofsky commented at 6:10 pm on April 2, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.”

Would add = 0; //!< Number of high-order bits in m_buffer that have been written but not yet flushed to the stream.

in src/blockfilter.h:21 in 15d529dfc2 outdated

14+
15+/**
16+ * This implements a Golomb-coded set as defined in BIP 158. It is a
17+ * compact, probabilistic data structure for testing set membership.
18+ */
19+class GCSFilter

ryanofsky commented at 7:31 pm on April 2, 2018:

In commit “blockfilter: Declare GCSFilter class for BIP 158 impl.”

It seems cumbersome for this to be implemented as a class, since none of the class members can change after construction, and some of the stored state is redundant (m_F is derived from m_N and m_P), m_N is redundant with elements.size() and can be derived from m_encoded).

If this were a simple set of functions instead, like:

0
1struct FilterParams { k0; k1; P; };
2
3vector<char> BuildFilter(FilterParams, set<Elements>);
4
5bool FilterContains(FilterParams, vector<char>, Element);
6
7bool FilterContainsAny(FilterParams, vector<char>, set<Element>);

usage would be more obvious, and you could get rid of the current runtime throws and asserts checking for inconsistencies in the state.

jimpo commented at 9:29 am on April 17, 2018:

I originally tried something like that, but I preferred to make it an actual class. I see the ability to store derivable data in private fields and check data consistency before using the data as features of this approach.

in src/blockfilter.cpp:18 in 1b1d231ed7 outdated

11+
12+/// Protocol version used to serialize parameters in GCS filter encoding.
13+constexpr int GCS_SER_VERSION = 0;
14+
15+template <typename OStream>
16+static void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t k, uint64_t n)

ryanofsky commented at 7:39 pm on April 2, 2018:

In commit “blockfilter: Implement GCSFilter constructors.”

Here and other places, N seems like it should be 32 bits instead 64.

jimpo commented at 8:32 am on April 17, 2018:

Why do you say that? This function can encode 64-bit ints if it needs to. Also, it would have to immediately get cast to a uint64_t either way.

sipa commented at 7:55 pm on May 12, 2018:

I don’t understand this comment either.

ryanofsky commented at 4:55 pm on August 17, 2018:

RE: #12254 (review)

I don’t understand this comment either.

The comment was just attached in the wrong place. In 15d529dfc2b65f2badaa520799187aff103af2b6 m_N was uint64_t (fixed now).

in src/blockfilter.cpp:20 in 1b1d231ed7 outdated

13+constexpr int GCS_SER_VERSION = 0;
14+
15+template <typename OStream>
16+static void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t k, uint64_t n)
17+{
18+    // Write quotient as unary-encoded: q 1's followed by one 0.

ryanofsky commented at 7:45 pm on April 2, 2018:

In commit “blockfilter: Implement GCSFilter constructors.”

I wonder if the optimization below actually buys anything over a more direct:

0for (int i = 0; i < q; ++i) bitwriter.Write(1, 1);

in src/blockfilter.cpp:197 in fb96e966c8 outdated

179+    }
180+
181+    return false;
182+}
183+
184+bool GCSFilter::MatchAny(const std::set<Element>& elements) const

ryanofsky commented at 8:12 pm on April 2, 2018:

In commit “blockfilter: Implement GCSFilter Match methods.”

Would suggest implementing Match and MatchAny in terms of a common

0Match(const uint64_t* sorted_element_hashes, size_t size)

method to get rid of all the code duplication between the existing methods. No outside code would need to change, they could just call

0Match(&query, 1);
1Match(queries.data(), queries.size());

respectively.

jimpo commented at 8:16 am on April 17, 2018:

Good suggestion.

practicalswift commented at 6:19 am on April 15, 2018: contributor

Concept ACK

Nice work!

braydonf commented at 1:20 am on April 17, 2018: none

Has there been any work yet on using this to implement BIP 157? I’ve worked on indexing in the past, and could take a look at implementing it.

in src/blockfilter.cpp:237 in 68777c59c9 outdated

232+                CVectorWriter(GCS_SER_TYPE, GCS_SER_VERSION, ser_outpoint, 0, txin.prevout);
233+                elements.insert(std::move(ser_outpoint));
234+            }
235+        }
236+
237+        // Include all data pushes in output scripts.

sipa commented at 1:30 am on April 17, 2018:

This does not seem up to date with the latest version of BIP158 (I’ll review in full later).

jimpo commented at 9:30 am on April 17, 2018:

Fixed.

jimpo force-pushed on Apr 17, 2018

jimpo force-pushed on May 1, 2018

laanwj added this to the "Blockers" column in a project

in src/streams.h:513 in f7426bde30 outdated

508@@ -509,12 +509,102 @@ class CDataStream
509     }
510 };
511 
512+template <typename IStream>

sipa commented at 7:54 pm on May 12, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.”, any reason to not make these operate with a 64-bit (or even larger) buffer? That would both simplify the code (no need to loop in the read/write operations) and possibly improve performance (due to fewer read/flush calls to the underlying buffer).

jimpo commented at 6:42 pm on May 13, 2018:

Perhaps could improve performance, but it’d be trickier to handle streams that are not aligned on 8-byte boundaries. Since the buffer size is an implementation detail, would you be OK leaving that optimization for a later PR?

sipa commented at 7:14 pm on May 13, 2018:

Yeah, let’s look at this later. It would complicate the reader indeed. For the writer I think it’s pretty straightfoward.

tamasblummer commented at 6:31 pm on May 14, 2018:

Agree with @jimpo, used IStream and OStream should be buffered implementations, not this specific algo.

in src/blockfilter.cpp:58 in c0815aa428 outdated

48+// x * n.
49+//
50+// See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
51+static uint64_t MapIntoRange(uint64_t x, uint64_t n)
52+{
53+    // To perform the calculation on 64-bit numbers without losing the

sipa commented at 7:57 pm on May 12, 2018:

Perhaps add a note here to use unsigned __int128 on supported platforms; that should be significantly faster than doing 4 separate multiplications.

jimpo commented at 5:36 am on May 14, 2018:

Fixed in 07df98686ec423dcf38ac28ad8e325708cb5b902.

in src/blockfilter.cpp:197 in a780779b3a outdated

192+    return MatchInternal(&query, 1);
193+}
194+
195+bool GCSFilter::MatchAny(const std::set<Element>& elements) const
196+{
197+    const std::vector<uint64_t>&& queries = BuildHashedSet(elements);

sipa commented at 8:07 pm on May 12, 2018:

I don’t think the reference type is useful here; copy elision should apply, and otherwise at worst a move will occur.

in src/blockfilter.cpp:117 in c0815aa428 outdated

110+
111+    if (m_N >= (1ULL << 32)) {
112+        throw std::ios_base::failure("N must be <2^32");
113+    }
114+
115+    // Verify that the encoded filter contains exactly N elements. If it has too much or too little

sipa commented at 8:08 pm on May 12, 2018:

Is this worth it? The filter will be decoded twice in practice due to this?

jimpo commented at 6:59 pm on May 13, 2018:

I’ll drop it if people prefer. I think having the constructor check its input makes for a better API. I’d also note that Core won’t actually use these match methods unless it implements a light client mode – they are just here for completeness and testing.

sipa commented at 7:16 pm on May 13, 2018:

I expect we’ll start using it for rescanning pretty quickly, regardless of protocol implementations.

Do you have any numbers for how fast it is to iterate through a 10000 element set or so?

jimpo commented at 5:38 am on May 14, 2018:

Benchmarks added in f1b341a9262f24ff72b5961538f83ffbf532d8d9. Decoding a 10,000 element filter and matching against one missing element takes about 20us, and grows linearly in the number of elements (as expected).

sipa commented at 8:15 pm on May 12, 2018: member

Code review ACK.

I’m very skeptical about the usefulness of the extended filter, and don’t think it should be implemented in Bitcoin Core until there is a clear use case, but that’s perhaps a discussion to be had about the BIP itself.

jimpo force-pushed on May 14, 2018

jimpo commented at 5:41 am on May 14, 2018: contributor

@sipa Thanks for the review. I agree on the extended filter – I have dropped it from this PR. The code is in a new branch https://github.com/jimpo/bitcoin/tree/bip-158-extended in case it becomes useful in the future.

jonasschnelli commented at 6:19 am on May 14, 2018: contributor

utACK f1b341a9262f24ff72b5961538f83ffbf532d8d9 I think this is a good and sane start since this is not used yet. I wish there would be more test vectors.

in src/blockfilter.cpp:18 in f1b341a926 outdated

13+
14+/// Protocol version used to serialize parameters in GCS filter encoding.
15+constexpr int GCS_SER_VERSION = 0;
16+
17+template <typename OStream>
18+static void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t k, uint64_t n)

tamasblummer commented at 2:39 pm on May 14, 2018:

k should be checked < 64 to avoid right shift overflow, which could trigger a platform specific response. I know this is practically excluded with m_P <= 32, but if that is the safety net then there is also no need to check nbits <= 64 in bit stream read and write.

jimpo commented at 3:26 pm on May 14, 2018:

I’m not sure this assertion would add much. The reason for the check in the BitStreamReader/Writer is because it is part of a public interface. This function (and decode) are static within this compilation unit and thus part of a private interface.

tamasblummer commented at 4:13 pm on May 14, 2018:

thanks, that is fine then. I did not check the visibility.

tamasblummer commented at 4:43 pm on May 14, 2018:

shouldn’t GolombRiceEncode and GolombRiceEncode functions be rather members of GCSFilter since they always use its initialized m_P as k ?

jimpo commented at 8:02 pm on May 14, 2018:

I prefer they be standalone functions.

in src/blockfilter.cpp:35 in f1b341a926 outdated

30+    // k bits of n, there is no need to mask first.
31+    bitwriter.Write(n, k);
32+}
33+
34+template <typename IStream>
35+static uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t k)

tamasblummer commented at 2:40 pm on May 14, 2018:

same here with k < 64 to avoid shift left overflow

in src/blockfilter.h:28 in f1b341a926 outdated

23+    typedef std::vector<unsigned char> Element;
24+
25+private:
26+    uint64_t m_siphash_k0;
27+    uint64_t m_siphash_k1;
28+    uint8_t m_P;

tamasblummer commented at 5:57 pm on May 14, 2018:

comments would not hurt here. P Golomb-Rice Parameter (2^P), N number of elements in set. F is derived from P and N, so it better would not be here at all.

TheBlueMatt commented at 7:54 pm on May 14, 2018: member

Why match on the txid of each transaction? I can’t imagine a use-case where you’d ever want that where you couldn’t simply match by one (or multiple) of the output scripts for little additional cost.

jimpo commented at 8:07 pm on May 14, 2018: contributor

@TheBlueMatt I can definitely think of use cases where one only has the txid. For example, if a lightning wallet wants to determine if a channel exists, it only gets the txid from the channel_announcement.

I definitely think txids should be included in a filter, though I think there’s a valid argument for putting them in their own filter given that a basic wallet does not need them.

TheBlueMatt commented at 8:12 pm on May 14, 2018: member

Hmm? channel_announcement messages don’t contain a txid, they contain a block number/tx index/txo index, which is obviously way more effecient than storing all the filters (which are pretty huge, in total), scanning all of them, and then downloading the corresponding block to verify the transaction is there (of course an SPV Proof is much more effecient in either case).

On May 14, 2018 8:07:17 PM UTC, Jim Posen notifications@github.com wrote:

@TheBlueMatt I can definitely think of use cases where one only has the txid. For example, if a lightning wallet wants to determine if a channel exists, it only gets the txid from the channel_announcement.

I definitely think txids should be included in a filter, though I think there’s a valid argument for putting them in their own filter given that a basic wallet does not need them.

– You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/bitcoin/bitcoin/pull/12254#issuecomment-388945360

jimpo commented at 10:20 pm on May 14, 2018: contributor

You’re right, I forgot that channel_announcement uses the short ID instead of the channel ID.

Given that it would be a BIP change, I think the conversation about whether to remove TXID from the basic filter and move it to another filter (or drop entirely) is better had on the mailing list.

in src/streams.h:198 in 5a339f4118 outdated

193+        if (n == 0) {
194+            return;
195+        }
196+
197+        // Read from the beginning of the buffer
198+        unsigned int pos_next = m_pos + n;

kallewoof commented at 8:48 am on May 15, 2018:

size_t?

in src/test/streams_tests.cpp:94 in 7a77fc51df outdated

92+    BOOST_CHECK_EQUAL(b, -1);
93+    BOOST_CHECK_EQUAL(reader.size(), 4);
94+    BOOST_CHECK(!reader.empty());
95+
96+    // Read a 4 bytes as a signed int.
97+    unsigned int c;

kallewoof commented at 8:49 am on May 15, 2018:

Comment says signed, but it is unsigned.

in src/test/streams_tests.cpp:105 in 7a77fc51df outdated

103+    // Reading after end of byte vector throws an error.
104+    signed int d;
105+    BOOST_CHECK_THROW(reader >> d, std::ios_base::failure);
106+
107+    // Read a 4 bytes as an unsigned int from the beginning of the buffer.
108+    reader.seek(-6);

kallewoof commented at 8:50 am on May 15, 2018:

d is a signed int, comment says unsigned int.

in src/test/streams_tests.cpp:127 in 84ecb19ab6 outdated

125+    bit_writer.Write(2, 2);
126+    bit_writer.Write(6, 3);
127+    bit_writer.Write(11, 4);
128+    bit_writer.Write(1, 5);
129+    bit_writer.Write(32, 6);
130+    bit_writer.Write(7, 7);

kallewoof commented at 8:56 am on May 15, 2018:

Maybe also include a really high value (e.g. using all 64 bits). These are all single-byte values and will not test the looping part at all, I think?

jimpo commented at 8:04 pm on May 15, 2018:

It’s testing the looping part insofar as some of the writes crossed byte boundaries, but I also added a write/read of a 2-byte value.

in src/test/blockfilter_tests.cpp:21 in a10dc09b7f outdated

16+        GCSFilter::Element rand1(32);
17+        GetRandBytes(rand1.data(), rand1.size());
18+        included_elements.insert(std::move(rand1));
19+
20+        GCSFilter::Element rand2(32);
21+        GetRandBytes(rand2.data(), rand2.size());

kallewoof commented at 9:16 am on May 15, 2018:

I recommend avoiding actual random values for unit tests, as generating random data is expensive and the tests may end up failing only sporadically, making it harder to debug (run the test 10 times and see the error once kinda thing).

A simple approach is to use a random generator “manually” once to generate 200 random numbers as a big static vector. Another is to do e.g. srand(12345); once and then use rand(), but I’m not sure if that has downsides (or if it’s slow, too).

jimpo commented at 8:04 pm on May 15, 2018:

Removed the rand.

in src/test/blockfilter_tests.cpp:57 in d7f8d3838a outdated

49+
50+    // Outpoint spent by first non-coinbase tx in block.
51+    COutPoint prevout(uint256S("36e8f98c5f5733f88ca00dfa05afd7af5dc34dda802790daba6aa1afcb8c6096"), 0);
52+    GCSFilter::Element prevout_element;
53+    CVectorWriter(SER_NETWORK, 0, prevout_element, 0, prevout);
54+    BOOST_CHECK(filter.Match(prevout_element));

kallewoof commented at 9:23 am on May 15, 2018:

Maybe also check that prevout(36e, 1) is not a match while at it.

jimpo commented at 7:56 pm on May 15, 2018:

Good idea.

in src/bench/gcs_filter.cpp:14 in f1b341a926 outdated

 9+static void ConstructGCSFilter(benchmark::State& state)
10+{
11+    std::set<GCSFilter::Element> elements;
12+    for (int i = 0; i < 10000; i++) {
13+        GCSFilter::Element element(32);
14+        GetRandBytes(element.data(), element.size());

kallewoof commented at 9:35 am on May 15, 2018:

Note use of GetRandBytes here as well. Potential inconsistency in test outcomes and potential slowdown.

kallewoof approved

kallewoof commented at 9:36 am on May 15, 2018: member

utACK f1b341a9262f24ff72b5961538f83ffbf532d8d9

Nice!

jimpo force-pushed on May 15, 2018

kallewoof commented at 1:01 am on May 16, 2018: member

re-utACK 669599d

jonasschnelli commented at 6:25 am on May 16, 2018: contributor

Agree with @jimpo: dropping the txid filter check should be addresses via the BIP.

laanwj removed this from the "Blockers" column in a project

MarcoFalke added the label Needs rebase on Jun 6, 2018

jimpo force-pushed on Jul 9, 2018

DrahtBot removed the label Needs rebase on Jul 9, 2018

in src/bench/gcs_filter.cpp:11 in 4fe143a623 outdated

 6+#include <blockfilter.h>
 7+
 8+static void ConstructGCSFilter(benchmark::State& state)
 9+{
10+    std::set<GCSFilter::Element> elements;
11+    for (int i = 0; i < 10000; i++) {

Empact commented at 9:13 pm on July 15, 2018:

nit: ++i here and elsewhere - I think every non-test post-increment can be pre.

in src/blockfilter.cpp:12 in 4fe143a623 outdated

 7+#include <primitives/transaction.h>
 8+#include <script/script.h>
 9+#include <streams.h>
10+
11+/// SerType used to serialize parameters in GCS filter encoding.
12+constexpr int GCS_SER_TYPE = SER_NETWORK;

Empact commented at 9:15 pm on July 15, 2018:

nit: static?

kallewoof commented at 12:35 pm on July 17, 2018:

I’m curious what triggered this request. I may be reading the wrong places, but e.g. https://stackoverflow.com/questions/45987571/difference-between-constexpr-and-static-constexpr-global-variable indicates static does nothing at all here.

Empact commented at 2:18 pm on July 17, 2018:

My thought was to make these explicitly translation-unit local, to communicate that to the reader and to enforce that from the linker. Here’s what cppreference says about what gets internal linkage:

internal linkage. The name can be referred to from all scopes in the current translation unit. Any of the following names declared at namespace scope have internal linkage:

variables, functions, or function templates declared static;

non-volatile non-inline (since C++17) const-qualified variables (including constexpr) that aren’t declared extern and aren’t previously declared to have external linkage;

data members of anonymous unions.

https://en.cppreference.com/w/cpp/language/storage_duration#Linkage

Worth noting that non-static constexpr variables can be declared extern in other contexts and rendered external linkage, while static variables can not be.

Unnamed namespaces are another way to enforce this:

Even though names in an unnamed namespace may be declared with external linkage, they are never accessible from other translation units because their namespace name is unique. https://en.cppreference.com/w/cpp/language/namespace#Unnamed_namespaces

jimpo commented at 3:54 pm on July 17, 2018:

@kallewoof Interesting. I looked it up too and came across this: https://stackoverflow.com/a/13867690.

kallewoof commented at 7:34 am on July 19, 2018:

@jimpo Yeah I read that one too, but the last paragraph was what made me unsure in the end whether it was good or bad

However, there is one case where you wouldn’t want to use static constexper. Unless a constexpr declared object is either ODR-used or declared static, the compiler is free to not include it at all. That’s pretty useful, because it allows the use of compile-time temporary constexpr arrays without polluting the compiled program with unnecessary bytes. In that case, you would clearly not want to use static, since static is likely to force the object to exist at runtime.

I honestly can’t tell if this applies here or not without thinking about it more.

in src/blockfilter.cpp:15 in 4fe143a623 outdated

10+
11+/// SerType used to serialize parameters in GCS filter encoding.
12+constexpr int GCS_SER_TYPE = SER_NETWORK;
13+
14+/// Protocol version used to serialize parameters in GCS filter encoding.
15+constexpr int GCS_SER_VERSION = 0;

Empact commented at 9:16 pm on July 15, 2018:

nit: static?

in src/streams.h:568 in 4fe143a623 outdated

563+    /// Write() calls and not yet flushed to the stream. The next bit to be
564+    /// written to is at this offset from the most significant bit position.
565+    int m_offset{0};
566+
567+public:
568+    BitStreamWriter(OStream& ostream) : m_ostream(ostream) {}

Empact commented at 9:30 pm on July 15, 2018:

nit: explicit?

in src/blockfilter.h:141 in 4fe143a623 outdated

135+                                 BASIC_FILTER_P, BASIC_FILTER_M, std::move(encoded_filter));
136+            break;
137+
138+        default:
139+            throw std::ios_base::failure("unknown filter_type");
140+        }

Empact commented at 9:35 pm on July 15, 2018:

nit: could extract this as a method to share with BlockFilter::BlockFilter

jimpo commented at 5:06 pm on July 16, 2018:

This uses a different form of the constructor from BlockFilter::BlockFilter. Could extract to a templated method, but I don’t think that’s worth it.

in src/streams.h:141 in 4fe143a623 outdated

137@@ -138,6 +138,80 @@ class CVectorWriter
138     size_t nPos;
139 };
140 
141+/* Minimal stream for reading from an existing vector by reference

Empact commented at 9:41 pm on July 15, 2018:

nit: /** here and elsewhere in the class

in src/validation.h:412 in 4fe143a623 outdated

408@@ -408,6 +409,8 @@ bool ReadBlockFromDisk(CBlock& block, const CBlockIndex* pindex, const Consensus
409 bool ReadRawBlockFromDisk(std::vector<uint8_t>& block, const CDiskBlockPos& pos, const CMessageHeader::MessageStartChars& message_start);
410 bool ReadRawBlockFromDisk(std::vector<uint8_t>& block, const CBlockIndex* pindex, const CMessageHeader::MessageStartChars& message_start);
411 
412+bool UndoReadFromDisk(CBlockUndo& blockundo, const CBlockIndex *pindex);

Empact commented at 9:52 pm on July 15, 2018:

Is exposing this in b50195afc40188064d43efc71a9c4feab6667ec8 necessary? I don’t see a call to it.

Checked and this builds just the coins.h include from that commit.

jimpo commented at 4:48 am on July 17, 2018:

Removed that commit.

jimpo force-pushed on Jul 17, 2018

in src/blockfilter.cpp:55 in ad2d7c93a2 outdated

51@@ -52,6 +52,9 @@ static uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t k)
52 // See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
53 static uint64_t MapIntoRange(uint64_t x, uint64_t n)
54 {
55+#ifdef __SIZE_INT128__

sipa commented at 7:10 pm on July 21, 2018:

This doesn’t seem to work for me (x86_64 linux, GCC 7.3.0), verified by looking at the disassembled code.

Interestingly, there is hardly any impact on the benchmarks when I modify the code to use force using 128-bit multiplication - suggesting that most of the time is spent elsewhere (hashing, bit operations?).

jimpo commented at 10:12 am on July 22, 2018:

Oops, that’s a typo. It should be __SIZEOF_INT128__. Will fix.

sipa commented at 5:50 am on July 23, 2018:

Yup, that works.

in src/blockfilter.h:35 in fcbba91012 outdated

30+    uint32_t m_M;  //!< Inverse false positive rate
31+    uint32_t m_N;  //!< Number of elements in the filter
32+    uint64_t m_F;  //!< Range of element hashes, F = N * M
33+    std::vector<unsigned char> m_encoded;
34+
35+    /** Hash a data element to an integer in the range [0, N * 2^P). */

sipa commented at 5:56 am on July 23, 2018:

Nit: should be [0, N * M) or [0, F), I think.

sipa commented at 5:59 am on July 23, 2018: member

utACK fcbba910125dcb98814b0c58f4611bf60280a000 after fixing #12254 (review)

jimpo force-pushed on Jul 23, 2018

gmaxwell commented at 7:30 pm on July 30, 2018: contributor

utACK

in src/streams.h:534 in faaa4b8432 outdated

525+    int m_offset{8};
526 
527+public:
528+    explicit BitStreamReader(IStream& istream) : m_istream(istream) {}
529 
530+    uint64_t Read(int nbits) {

ryanofsky commented at 3:51 pm on August 17, 2018:

In commit “streams: Implement BitStreamReader/Writer classes.” (faaa4b8432d194acb26ffcac07c379444da327ac)

There was previously a comment here (in e6e320d600c70cf4d530b49f3e526cdb7e66be6d). Was it dropped inadvertently?

0    /** Read the specified number of bits from the stream. The data is returned
1     * in the nbits least signficant bits of a 64-bit uint.
2     */

jimpo commented at 9:05 pm on August 20, 2018:

Thanks, good catch.

in src/test/streams_tests.cpp:87 in bdb3419934 outdated

82+    BOOST_CHECK_EQUAL(a, 1);
83+    BOOST_CHECK_EQUAL(reader.size(), 5);
84+    BOOST_CHECK(!reader.empty());
85+
86+    // Read a single byte as a signed char.
87+    char b;

ryanofsky commented at 5:08 pm on August 17, 2018:

In commit “streams: Unit test for VectorReader class.” (bdb34199345ad2c6f98da5d3f303d0993f6c722c)

Should probably say signed char explicitly, since plain char isn’t necessarily signed.

in src/test/streams_tests.cpp:148 in e15e553b74 outdated

143+    BOOST_CHECK_EQUAL(bit_reader.Read(4), 11);
144+    BOOST_CHECK_EQUAL(bit_reader.Read(5), 1);
145+    BOOST_CHECK_EQUAL(bit_reader.Read(6), 32);
146+    BOOST_CHECK_EQUAL(bit_reader.Read(7), 7);
147+    BOOST_CHECK_EQUAL(bit_reader.Read(16), 30497);
148+    BOOST_CHECK_THROW(bit_reader.Read(8), std::ios_base::failure);

ryanofsky commented at 5:19 pm on August 17, 2018:

In commit “streams: Unit tests for BitStreamReader and BitStreamWriter.” (e15e553b746e64f0eeda420e4c10eccfc747d69f)

Might be good to have additional BOOST_CHECK(data.empty()) and BOOST_CHECK(data_copy.empty()) checks to make sure reads & writes are still aligned if somebody modifies the test.

jimpo commented at 9:03 pm on August 20, 2018:

I don’t understand the benefit. The assertion of a std::ios_base::failure is meant to test that the buffer is out of data.

in src/blockfilter.cpp:16 in 515af0398b outdated

11+
12+/// Protocol version used to serialize parameters in GCS filter encoding.
13+static constexpr int GCS_SER_VERSION = 0;
14+
15+template <typename OStream>
16+static void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t k, uint64_t n)

ryanofsky commented at 6:15 pm on August 17, 2018:

In commit “blockfilter: Implement GCSFilter constructors.” (515af0398b8f2aab77645871198c69fea91a07ff)

Maybe use x and P instead of n and k to be consistent with golomb_encode function from BIP158. This would also be more consistent with the GCSFilter class, which uses P.

in src/undo.h:9 in f7a5bdb54b outdated

5@@ -6,6 +6,7 @@
6 #ifndef BITCOIN_UNDO_H
7 #define BITCOIN_UNDO_H
8 
9+#include <coins.h>

ryanofsky commented at 6:41 pm on August 17, 2018:

In commit “blockfilter: Construction of basic block filters.” (f7a5bdb54ba597fe06bcb54e886c43436899ab48)

Change seems unrelated to this commit.

jimpo commented at 8:52 pm on August 20, 2018:

It’s required because blockfilter.h includes undo.h and won’t compile otherwise. This could be moved to separate commit though.

in src/blockfilter.cpp:199 in f7a5bdb54b outdated

194@@ -193,3 +195,41 @@ bool GCSFilter::MatchAny(const std::set<Element>& elements) const
195     const std::vector<uint64_t> queries = BuildHashedSet(elements);
196     return MatchInternal(queries.data(), queries.size());
197 }
198+
199+static std::set<GCSFilter::Element> BasicFilterElements(const CBlock& block,

ryanofsky commented at 7:06 pm on August 17, 2018:

In commit “blockfilter: Construction of basic block filters.” (f7a5bdb54ba597fe06bcb54e886c43436899ab48)

I think it could be beneficial if GCSFilter defined:

0typedef std::unordered_set<Element> Elements;

And if this function, the GCSFilter constructor, BuildHashedSet, and MatchAny all used GCSFilter::Elements instead of std::set<GCSFilter::Element>. It’d be nice to decrease the coupling to one data structure, and since std::set is an ordered set, these functions are pointlessly also sorting the elements when order is not important.

jimpo commented at 6:39 am on August 21, 2018:

I added the typedef to std::set. In commit e645d53b3d5fa5912e3a99cc4fec74aee64e81e5, I change it to std::unordered_set which uses a randomly selected SipHash instance to hash the byte vector. Let me know if you think this is acceptable or whether it should be left as std::set.

in src/blockfilter.cpp:241 in ab852f9160 outdated

232@@ -233,3 +233,24 @@ BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const
233         throw std::invalid_argument("unknown filter_type");
234     }
235 }
236+
237+uint256 BlockFilter::GetHash() const

ryanofsky commented at 7:23 pm on August 17, 2018:

In commit “blockfilter: Serialization methods on BlockFilter.” (c14e4d5a950ed40d96a8956e4622e1d9670da72d)

Note: https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki#filter-headers is the relevant section of the bip describing block filter hash (GetHash) and filter header (ComputeHeader) derivations.

ryanofsky approved

jimpo force-pushed on Aug 21, 2018

jimpo force-pushed on Aug 22, 2018

ryanofsky commented at 4:26 pm on August 24, 2018: member

utACK cc6c570a29118e0b661e66b135a3507081caebbb, with commit squash and fix for travis undefined reference to GetRandBytes error. Only changes since previous review were various code review suggestions.

Question for maintainers: While this PR was fun to review, I’m curious if there’s a specific reason it wasn’t merged previously? It has 4 other acks and doesn’t touch existing functionality, and the new functionality is pretty well covered by test vectors.

jimpo force-pushed on Aug 24, 2018

jimpo commented at 11:24 pm on August 24, 2018: contributor

@ryanofsky Thank you for the review. I’m going to leave GCSElementSet typedef’ed to std::set in this PR and will open a separate PR after this is merged to change to unordered_set. Creating the custom hasher and putting it in an appropriate location requires shuffling some code around which is not relevant to this PR and I’d rather not add another reason to hold off on merging this.

jimpo force-pushed on Aug 24, 2018

streams: Create VectorReader stream interface for vectors.

This is a read analogue for the existing CVectorWriter.

947133dec9

streams: Unit test for VectorReader class. 87f2d9ee43

streams: Implement BitStreamReader/Writer classes.

Golomb-Rice coding, as specified in BIP 158, involves operations on
individual bits. These classes will be used to implement the
encoding/decoding operations.

fe943f99bf

streams: Unit tests for BitStreamReader and BitStreamWriter. 9b622dc722

blockfilter: Declare GCSFilter class for BIP 158 impl. c454f0ac63

blockfilter: Implement GCSFilter constructors. cf70b55005

blockfilter: Implement GCSFilter Match methods. 558c536e35

blockfilter: Simple test for GCSFilter construction and Match. 53e7874e07

blockfilter: Construction of basic block filters. c1855f6052

blockfilter: Serialization methods on BlockFilter. cd09c7925b

blockfilter: Additional helper methods to compute hash and header. a4afb9cadb

blockfilter: Unit test against BIP 158 test vectors.

Full test of block filter and header construction.

97b64d67da

blockfilter: Optimization on compilers with int128 support. f33b717a85

bench: Benchmark GCS filter creation and matching. 254c85b687

jimpo force-pushed on Aug 25, 2018

laanwj commented at 2:23 pm on August 26, 2018: member

Question for maintainers: While this PR was fun to review, I’m curious if there’s a specific reason it wasn’t merged previously? It has 4 other acks and doesn’t touch existing functionality, and the new functionality is pretty well covered by test vectors.

didn’t want to merge it last-minute for 0.17, but it can go in now IMO

laanwj merged this on Aug 26, 2018

laanwj closed this on Aug 26, 2018

laanwj referenced this in commit c775dc4a94 on Aug 26, 2018

in src/blockfilter.cpp:211 in 254c85b687

206+    GCSFilter::ElementSet elements;
207+
208+    for (const CTransactionRef& tx : block.vtx) {
209+        for (const CTxOut& txout : tx->vout) {
210+            const CScript& script = txout.scriptPubKey;
211+            if (script[0] == OP_RETURN) continue;

TheBlueMatt commented at 4:07 pm on August 26, 2018:

Isnt this an OOB read?

jimpo deleted the branch on Aug 26, 2018

in src/streams.h:532 in 254c85b687

527+
528+public:
529+    explicit BitStreamReader(IStream& istream) : m_istream(istream) {}
530+
531+    /** Read the specified number of bits from the stream. The data is returned
532+     * in the nbits least signficant bits of a 64-bit uint.

practicalswift commented at 3:30 pm on August 27, 2018:

Post-merge nit: “signficant” should be “significant”.

This misspelling was automatically identified by codespell.

Automatic codespell checking is introduced in PR #13954. It warns (note: warn only, no build failure) when a PR introduces spelling errors. Please review :-)

laanwj referenced this in commit 3f96908448 on Aug 31, 2018

laanwj referenced this in commit 880bc728b4 on Nov 6, 2018

PastaPastaPasta referenced this in commit 68ce07f498 on Jan 26, 2020

PastaPastaPasta referenced this in commit ae226c5ef0 on Apr 15, 2020

PastaPastaPasta referenced this in commit 2ee9526dfd on Apr 15, 2020

PastaPastaPasta referenced this in commit 1335afa0eb on Apr 16, 2020

PastaPastaPasta referenced this in commit 919d9211b5 on Apr 16, 2020

PastaPastaPasta referenced this in commit 8248a1a283 on Apr 16, 2020

PastaPastaPasta referenced this in commit b85986189d on Apr 16, 2020

PastaPastaPasta referenced this in commit 296660e562 on Apr 16, 2020

PastaPastaPasta referenced this in commit 6d26c14e28 on Apr 16, 2020

PastaPastaPasta referenced this in commit 059a9c4675 on Apr 16, 2020

PastaPastaPasta referenced this in commit 374eb49568 on Apr 16, 2020

PastaPastaPasta referenced this in commit 1aa37dd7d7 on Jun 12, 2020

PastaPastaPasta referenced this in commit cbb91e5d08 on Jun 12, 2020

PastaPastaPasta referenced this in commit 17929071d4 on Jun 13, 2020

PastaPastaPasta referenced this in commit ea90d1b6c1 on Jun 13, 2020

PastaPastaPasta referenced this in commit 348c2d56f0 on Jun 17, 2020

PastaPastaPasta referenced this in commit 6e873a5b91 on Jun 17, 2020

gades referenced this in commit 6393db0c7f on Jun 30, 2021

gades referenced this in commit 302aadff56 on Jul 1, 2021

DrahtBot locked this on Sep 8, 2021

BIP 158: Compact Block Filters for Light Clients #12254

Filter Sizes