1 package filter
2 3 import (
4 "encoding/binary"
5 "errors"
6 "fmt"
7 "math/bits"
8 "slices"
9 )
10 11 // Filter parameters defined by BIP158 for the basic filter type.
12 const (
13 // FilterTypeBasic is the BIP158 basic block filter type.
14 FilterTypeBasic = 0
15 16 // M is the inverse target false positive rate of a basic filter.
17 M uint64 = 784931
18 19 // P is the Golomb-Rice remainder bit length of a basic filter.
20 P uint = 19
21 22 // maxFilterElements bounds the element count accepted by Match and Decode.
23 // BIP158 requires N < 2^32; a block cannot realistically contain anywhere
24 // near this many scripts, so a much tighter bound is used to reject absurd
25 // serialized counts before allocating or decoding.
26 maxFilterElements = 1 << 20
27 28 // maxFilterValue is the exclusive upper bound on any mapped value in a
29 // filter with maxFilterElements elements.
30 maxFilterValue = uint64(maxFilterElements) * M
31 32 // maxGolombQuotient bounds the unary part of a decoded delta.
33 maxGolombQuotient = maxFilterValue>>P + 1
34 )
35 36 // Errors returned for malformed or implausible filters.
37 var (
38 // ErrInvalidFilter indicates that a filter is truncated, non-canonical, or
39 // otherwise not a valid BIP158 basic filter serialization.
40 ErrInvalidFilter = errors.New("filter: invalid compact block filter")
41 42 // ErrTooManyElements indicates that the CompactSize element count exceeds
43 // the implementation limit.
44 ErrTooManyElements = errors.New("filter: element count exceeds limit")
45 )
46 47 // Build constructs the BIP158 serialization of the basic compact block filter
48 // for items, keyed by the first 16 bytes of blockHash in internal
49 // (little-endian) byte order.
50 //
51 // Build encodes exactly the items it is given: the serialized element count is
52 // len(items), and duplicate items produce duplicate mapped values, which appear
53 // as zero deltas. The BIP158 element set is a set of distinct, non-empty
54 // elements, so callers supplying raw block data should remove duplicates and
55 // empty elements first. BuildFromScripts is a convenience that does so.
56 //
57 // An empty item set produces the single byte 0x00.
58 func Build(items [][]byte, blockHash [32]byte) []byte {
59 n := len(items)
60 out := appendCompactSize(make([]byte, 0, 1+((n*3)/2)), uint64(n))
61 if n == 0 {
62 return out
63 }
64 65 var key [16]byte
66 copy(key[:], blockHash[:16])
67 68 // F = N * M fits in 64 bits because N is bounded by an int on supported
69 // platforms and a real block's element count is far below 2^32.
70 f := uint64(n) * M
71 values := make([]uint64, n)
72 for i, item := range items {
73 h := siphash24(key, item)
74 hi, _ := bits.Mul64(h, f) // (h * F) >> 64
75 values[i] = hi
76 }
77 slices.Sort(values)
78 79 w := bitWriter{buf: out}
80 var last uint64
81 for _, v := range values {
82 w.writeGolomb(v-last, P)
83 last = v
84 }
85 w.flush()
86 return w.buf
87 }
88 89 // Match reports whether any element of query maps to a value in filter.
90 //
91 // The filter must be a complete BIP158 serialization (CompactSize element count
92 // followed by the Golomb-Rice bitstream). It is decoded only as far as needed:
93 // decoding stops when the next filter value exceeds every remaining query value,
94 // and ErrInvalidFilter is returned if the bitstream is truncated or malformed
95 // before that point. The block hash key is blockHash[0:16].
96 //
97 // For a filter over the empty set, Match returns true only for an empty query.
98 func Match(filter []byte, blockHash [32]byte, query [][]byte) (bool, error) {
99 n, payload, err := decodeHeader(filter)
100 if err != nil {
101 return false, err
102 }
103 if n == 0 {
104 return len(query) == 0, nil
105 }
106 if len(query) == 0 {
107 // Validate the serialization even though there is nothing to match.
108 if _, _, err := Decode(filter); err != nil {
109 return false, err
110 }
111 return false, nil
112 }
113 114 var key [16]byte
115 copy(key[:], blockHash[:16])
116 f := uint64(n) * M
117 118 targets := make([]uint64, len(query))
119 for i, item := range query {
120 h := siphash24(key, item)
121 hi, _ := bits.Mul64(h, f)
122 targets[i] = hi
123 }
124 slices.Sort(targets)
125 126 r := bitReader{data: payload}
127 var last uint64
128 target := 0
129 for i := uint64(0); i < n; i++ {
130 delta, err := r.readGolomb(P)
131 if err != nil {
132 return false, err
133 }
134 if delta >= f-last {
135 return false, fmt.Errorf("%w: Golomb value out of range", ErrInvalidFilter)
136 }
137 last += delta
138 139 // Values are strictly increasing (duplicates become zero deltas, so
140 // they compare equal). Drop query values that are now too small.
141 for target < len(targets) && targets[target] < last {
142 target++
143 }
144 if target == len(targets) {
145 return false, nil
146 }
147 if targets[target] == last {
148 return true, nil
149 }
150 }
151 152 if err := r.checkPadding(); err != nil {
153 return false, err
154 }
155 return false, nil
156 }
157 158 // MatchScript reports whether any of scripts appears in filter. It is an alias
159 // for Match, provided for symmetry with the caller's element kind.
160 func MatchScript(filter []byte, blockHash [32]byte, scripts [][]byte) (bool, error) {
161 return Match(filter, blockHash, scripts)
162 }
163 164 // MatchAny reports whether any of items appears in filter. It is an alias for
165 // Match.
166 func MatchAny(filter []byte, blockHash [32]byte, items [][]byte) (bool, error) {
167 return Match(filter, blockHash, items)
168 }
169 170 // Decode parses and fully decodes a filter, returning its sorted mapped values
171 // and the serialized element count N. It is intended for tests and debugging;
172 // Match avoids materializing the values.
173 //
174 // Decode rejects truncated bitstreams, non-zero or overlong padding, and
175 // element counts above the implementation limit.
176 func Decode(filter []byte) (values []uint64, n uint64, err error) {
177 n, payload, err := decodeHeader(filter)
178 if err != nil {
179 return nil, 0, err
180 }
181 if n == 0 {
182 return nil, 0, nil
183 }
184 185 f := uint64(n) * M
186 values = make([]uint64, 0, int(n))
187 r := bitReader{data: payload}
188 var last uint64
189 for i := uint64(0); i < n; i++ {
190 delta, err := r.readGolomb(P)
191 if err != nil {
192 return nil, 0, err
193 }
194 if delta >= f-last {
195 return nil, 0, fmt.Errorf("%w: Golomb value out of range", ErrInvalidFilter)
196 }
197 last += delta
198 values = append(values, last)
199 }
200 if err := r.checkPadding(); err != nil {
201 return nil, 0, err
202 }
203 return values, n, nil
204 }
205 206 // decodeHeader reads the CompactSize element count and returns the filter's
207 // Golomb bitstream payload. Empty filters must be exactly one 0x00 byte.
208 func decodeHeader(filter []byte) (n uint64, payload []byte, err error) {
209 n, off, err := readCompactSize(filter)
210 if err != nil {
211 return 0, nil, err
212 }
213 if n > maxFilterElements {
214 return 0, nil, fmt.Errorf("%w: %d elements", ErrTooManyElements, n)
215 }
216 if n == 0 {
217 if off != len(filter) {
218 return 0, nil, fmt.Errorf("%w: trailing bytes after empty filter", ErrInvalidFilter)
219 }
220 return 0, nil, nil
221 }
222 return n, filter[off:], nil
223 }
224 225 func appendCompactSize(dst []byte, n uint64) []byte {
226 switch {
227 case n < 0xfd:
228 return append(dst, byte(n))
229 case n <= 0xffff:
230 dst = append(dst, 0xfd)
231 var buf [2]byte
232 binary.LittleEndian.PutUint16(buf[:], uint16(n))
233 return append(dst, buf[:]...)
234 case n <= 0xffffffff:
235 dst = append(dst, 0xfe)
236 var buf [4]byte
237 binary.LittleEndian.PutUint32(buf[:], uint32(n))
238 return append(dst, buf[:]...)
239 default:
240 dst = append(dst, 0xff)
241 var buf [8]byte
242 binary.LittleEndian.PutUint64(buf[:], n)
243 return append(dst, buf[:]...)
244 }
245 }
246 247 // readCompactSize decodes a canonical Bitcoin CompactSize integer. It returns
248 // the value and the number of bytes consumed.
249 func readCompactSize(data []byte) (n uint64, size int, err error) {
250 if len(data) == 0 {
251 return 0, 0, fmt.Errorf("%w: missing CompactSize", ErrInvalidFilter)
252 }
253 254 switch data[0] {
255 case 0xfd:
256 if len(data) < 3 {
257 return 0, 0, fmt.Errorf("%w: truncated CompactSize", ErrInvalidFilter)
258 }
259 n = uint64(binary.LittleEndian.Uint16(data[1:3]))
260 if n < 0xfd {
261 return 0, 0, fmt.Errorf("%w: non-canonical CompactSize", ErrInvalidFilter)
262 }
263 return n, 3, nil
264 case 0xfe:
265 if len(data) < 5 {
266 return 0, 0, fmt.Errorf("%w: truncated CompactSize", ErrInvalidFilter)
267 }
268 n = uint64(binary.LittleEndian.Uint32(data[1:5]))
269 if n <= 0xffff {
270 return 0, 0, fmt.Errorf("%w: non-canonical CompactSize", ErrInvalidFilter)
271 }
272 return n, 5, nil
273 case 0xff:
274 if len(data) < 9 {
275 return 0, 0, fmt.Errorf("%w: truncated CompactSize", ErrInvalidFilter)
276 }
277 n = binary.LittleEndian.Uint64(data[1:9])
278 if n <= 0xffffffff {
279 return 0, 0, fmt.Errorf("%w: non-canonical CompactSize", ErrInvalidFilter)
280 }
281 return n, 9, nil
282 default:
283 return uint64(data[0]), 1, nil
284 }
285 }
286 287 // bitWriter appends bits most-significant first, as required by the BIP158
288 // write_bits_big_endian primitive.
289 type bitWriter struct {
290 buf []byte
291 cur byte
292 n uint8 // number of bits currently held in cur
293 }
294 295 func (w *bitWriter) writeBit(bit uint) {
296 w.cur = w.cur<<1 | byte(bit&1)
297 w.n++
298 if w.n == 8 {
299 w.buf = append(w.buf, w.cur)
300 w.cur = 0
301 w.n = 0
302 }
303 }
304 305 func (w *bitWriter) writeBits(v uint64, n uint) {
306 for i := n; i > 0; i-- {
307 w.writeBit(uint(v >> (i - 1)))
308 }
309 }
310 311 func (w *bitWriter) writeGolomb(v uint64, p uint) {
312 q := v >> p
313 for ; q > 0; q-- {
314 w.writeBit(1)
315 }
316 w.writeBit(0)
317 w.writeBits(v&(1<<p-1), p)
318 }
319 320 // flush pads the final partial byte with zero bits.
321 func (w *bitWriter) flush() {
322 if w.n > 0 {
323 w.buf = append(w.buf, w.cur<<(8-w.n))
324 w.cur = 0
325 w.n = 0
326 }
327 }
328 329 // bitReader reads bits most-significant first.
330 type bitReader struct {
331 data []byte
332 bit uint64 // absolute bit position
333 }
334 335 func (r *bitReader) readBit() (uint, error) {
336 total := uint64(len(r.data)) * 8
337 if r.bit >= total {
338 return 0, fmt.Errorf("%w: truncated bitstream", ErrInvalidFilter)
339 }
340 b := (r.data[r.bit>>3] >> (7 - (r.bit & 7))) & 1
341 r.bit++
342 return uint(b), nil
343 }
344 345 func (r *bitReader) readBits(n uint) (uint64, error) {
346 var v uint64
347 for i := uint(0); i < n; i++ {
348 b, err := r.readBit()
349 if err != nil {
350 return 0, err
351 }
352 v = v<<1 | uint64(b)
353 }
354 return v, nil
355 }
356 357 func (r *bitReader) readGolomb(p uint) (uint64, error) {
358 var q uint64
359 for {
360 b, err := r.readBit()
361 if err != nil {
362 return 0, err
363 }
364 if b == 0 {
365 break
366 }
367 q++
368 if q > maxGolombQuotient {
369 return 0, fmt.Errorf("%w: Golomb quotient too large", ErrInvalidFilter)
370 }
371 }
372 373 rem, err := r.readBits(p)
374 if err != nil {
375 return 0, err
376 }
377 if q > (^uint64(0)-rem)>>p {
378 return 0, fmt.Errorf("%w: Golomb value overflow", ErrInvalidFilter)
379 }
380 return q<<p | rem, nil
381 }
382 383 // checkPadding verifies that at most seven zero bits remain. A valid filter is
384 // padded only to the next byte boundary, so extra bytes are rejected too.
385 func (r *bitReader) checkPadding() error {
386 total := uint64(len(r.data)) * 8
387 if total-r.bit >= 8 {
388 return fmt.Errorf("%w: trailing bytes after bitstream", ErrInvalidFilter)
389 }
390 for r.bit < total {
391 b, err := r.readBit()
392 if err != nil {
393 return err
394 }
395 if b != 0 {
396 return fmt.Errorf("%w: non-zero padding bits", ErrInvalidFilter)
397 }
398 }
399 return nil
400 }
401