vectors_test.go raw
1 package filter
2
3 import (
4 "bytes"
5 _ "embed"
6 "encoding/hex"
7 "encoding/json"
8 "fmt"
9 "math/bits"
10 "slices"
11 "testing"
12 )
13
14 // bip158VectorsJSON holds all ten official BIP158 basic filter vectors from
15 // https://github.com/bitcoin/bips/blob/master/bip-0158/testnet-19.json
16 // (testnet heights 0, 2, 3, 15007, 49291, 180480, 926485, 987876, 1263442,
17 // and 1414221). The embedded objects keep the original height, block hash,
18 // block, prevOutputScripts, filter, and note fields; the two filter-header
19 // fields are not needed here.
20 //
21 //go:embed testdata/bip158_testnet19.json
22 var bip158VectorsJSON []byte
23
24 type bip158Vector struct {
25 Height uint32 `json:"height"`
26 BlockHash string `json:"blockHash"`
27 Block string `json:"block"`
28 PrevOutputScripts []string `json:"prevOutputScripts"`
29 Filter string `json:"filter"`
30 Note string `json:"note"`
31 }
32
33 // TestBIP158OfficialVectors rebuilds each official testnet filter from the block
34 // and previous output scripts and checks the exact serialized bytes against the
35 // vector, then checks that every element matches. This covers OP_RETURN
36 // exclusion, empty scripts, duplicate scripts, witness transactions, and the
37 // empty filter.
38 func TestBIP158OfficialVectors(t *testing.T) {
39 var vectors []bip158Vector
40 if err := json.Unmarshal(bip158VectorsJSON, &vectors); err != nil {
41 t.Fatalf("parse test vectors: %v", err)
42 }
43 if len(vectors) == 0 {
44 t.Fatal("no test vectors")
45 }
46
47 for _, v := range vectors {
48 v := v
49 t.Run(fmt.Sprintf("height_%d", v.Height), func(t *testing.T) {
50 block, err := hex.DecodeString(v.Block)
51 if err != nil {
52 t.Fatalf("decode block: %v", err)
53 }
54 outputs, err := blockOutputScripts(block)
55 if err != nil {
56 t.Fatalf("parse block: %v", err)
57 }
58 prev, err := decodeHexScripts(v.PrevOutputScripts)
59 if err != nil {
60 t.Fatalf("decode prev scripts: %v", err)
61 }
62 hash, err := internalBlockHash(v.BlockHash)
63 if err != nil {
64 t.Fatalf("block hash: %v", err)
65 }
66 want, err := hex.DecodeString(v.Filter)
67 if err != nil {
68 t.Fatalf("decode filter: %v", err)
69 }
70
71 // The BIP158 element set excludes OP_RETURN outputs (already
72 // dropped by blockOutputScripts), empty scripts, and exact
73 // duplicates. Height 926485 exercises duplicate scripts.
74 raw := make([][]byte, 0, len(prev)+len(outputs))
75 raw = append(raw, prev...)
76 raw = append(raw, outputs...)
77 elements := dedupeScripts(raw)
78
79 if got := Build(elements, hash); !bytes.Equal(got, want) {
80 t.Fatalf("Build mismatch\n got %x\nwant %x", got, want)
81 }
82 if got := BuildFromScripts(raw, hash); !bytes.Equal(got, want) {
83 t.Fatalf("BuildFromScripts mismatch\n got %x\nwant %x", got, want)
84 }
85 if len(raw) != len(elements) {
86 if got := Build(raw, hash); bytes.Equal(got, want) {
87 t.Fatal("Build(raw) unexpectedly equals filter with duplicate items")
88 }
89 }
90
91 values, n, err := Decode(want)
92 if err != nil {
93 t.Fatalf("Decode: %v", err)
94 }
95 if n != uint64(len(elements)) || len(values) != len(elements) {
96 t.Fatalf("decoded N=%d values=%d, want %d", n, len(values), len(elements))
97 }
98 if !slices.IsSorted(values) {
99 t.Fatal("decoded values are not sorted")
100 }
101
102 for _, element := range elements {
103 ok, err := Match(want, hash, [][]byte{element})
104 if err != nil {
105 t.Fatalf("Match element: %v", err)
106 }
107 if !ok {
108 t.Fatalf("Match(%x) = false, want true", element)
109 }
110 ok, err = MatchScript(want, hash, [][]byte{element})
111 if err != nil || !ok {
112 t.Fatalf("MatchScript(%x) = %v, %v; want true, nil", element, ok, err)
113 }
114 }
115
116 if len(elements) == 0 {
117 ok, err := Match(want, hash, nil)
118 if err != nil || !ok {
119 t.Fatalf("Match(empty filter, nil query) = %v, %v; want true, nil", ok, err)
120 }
121 ok, err = Match(want, hash, [][]byte{[]byte("x")})
122 if err != nil || ok {
123 t.Fatalf("Match(empty filter, query) = %v, %v; want false, nil", ok, err)
124 }
125 return
126 }
127
128 // Find a query whose mapped value is absent from the filter and
129 // verify Match rejects it. Skipping values present in the filter
130 // avoids asserting on a legitimate 1/M false positive.
131 var key [16]byte
132 copy(key[:], hash[:16])
133 f := uint64(len(elements)) * M
134 found := false
135 for i := 0; i < 100; i++ {
136 q := []byte(fmt.Sprintf("nostrino-bip158-negative/%d/%d", v.Height, i))
137 h := siphash24(key, q)
138 hi, _ := bits.Mul64(h, f)
139 if slices.Contains(values, hi) {
140 continue
141 }
142 ok, err := Match(want, hash, [][]byte{q})
143 if err != nil {
144 t.Fatalf("Match negative query: %v", err)
145 }
146 if ok {
147 t.Fatalf("Match(%q) = true, want false", q)
148 }
149 found = true
150 break
151 }
152 if !found {
153 t.Fatal("could not find a query value absent from the filter")
154 }
155 })
156 }
157 }
158
159 func decodeHexScripts(in []string) ([][]byte, error) {
160 out := make([][]byte, len(in))
161 for i, s := range in {
162 b, err := hex.DecodeString(s)
163 if err != nil {
164 return nil, fmt.Errorf("script %d: %w", i, err)
165 }
166 out[i] = b
167 }
168 return out, nil
169 }
170
171 func internalBlockHash(display string) ([32]byte, error) {
172 var hash [32]byte
173 b, err := hex.DecodeString(display)
174 if err != nil {
175 return hash, err
176 }
177 if len(b) != len(hash) {
178 return hash, fmt.Errorf("block hash length %d, want %d", len(b), len(hash))
179 }
180 for i := range hash {
181 hash[i] = b[len(b)-1-i]
182 }
183 return hash, nil
184 }
185
186 func dedupeScripts(scripts [][]byte) [][]byte {
187 seen := make(map[string]struct{}, len(scripts))
188 out := make([][]byte, 0, len(scripts))
189 for _, script := range scripts {
190 if len(script) == 0 {
191 continue
192 }
193 if _, ok := seen[string(script)]; ok {
194 continue
195 }
196 seen[string(script)] = struct{}{}
197 out = append(out, script)
198 }
199 return out
200 }
201
202 // blockOutputScripts extracts non-empty scriptPubKeys that are not OP_RETURN
203 // from a serialized Bitcoin block. It understands the BIP144 witness marker and
204 // flag. This is deliberately test-only: the package does not parse transactions.
205 func blockOutputScripts(block []byte) ([][]byte, error) {
206 r := &blockReader{data: block}
207 _ = r.take(80) // block header
208 txCount := r.compact()
209 var outputs [][]byte
210 for i := uint64(0); i < txCount && r.err == nil; i++ {
211 _ = r.take(4) // version
212 vin := r.compact()
213 segwit := false
214 if vin == 0 {
215 flag := r.take(1)
216 if r.err == nil && (len(flag) != 1 || flag[0] == 0) {
217 return nil, fmt.Errorf("invalid segwit marker/flag in tx %d", i)
218 }
219 segwit = true
220 vin = r.compact()
221 }
222
223 for j := uint64(0); j < vin && r.err == nil; j++ {
224 _ = r.take(36) // previous outpoint
225 scriptLen := r.compact()
226 _ = r.take64(scriptLen)
227 _ = r.take(4) // sequence
228 }
229
230 vout := r.compact()
231 for j := uint64(0); j < vout && r.err == nil; j++ {
232 _ = r.take(8) // value
233 scriptLen := r.compact()
234 script := r.take64(scriptLen)
235 if r.err == nil && len(script) > 0 && script[0] != 0x6a {
236 outputs = append(outputs, script)
237 }
238 }
239
240 if segwit {
241 for j := uint64(0); j < vin && r.err == nil; j++ {
242 items := r.compact()
243 for k := uint64(0); k < items && r.err == nil; k++ {
244 itemLen := r.compact()
245 _ = r.take64(itemLen)
246 }
247 }
248 }
249 _ = r.take(4) // lock time
250 }
251 if r.err != nil {
252 return nil, r.err
253 }
254 if r.pos != len(block) {
255 return nil, fmt.Errorf("block has %d trailing bytes", len(block)-r.pos)
256 }
257 return outputs, nil
258 }
259
260 type blockReader struct {
261 data []byte
262 pos int
263 err error
264 }
265
266 func (r *blockReader) take(n int) []byte {
267 if r.err != nil {
268 return nil
269 }
270 if n < 0 || r.pos+n > len(r.data) {
271 r.err = fmt.Errorf("truncated block at offset %d (need %d bytes)", r.pos, n)
272 return nil
273 }
274 b := r.data[r.pos : r.pos+n]
275 r.pos += n
276 return b
277 }
278
279 func (r *blockReader) take64(n uint64) []byte {
280 if r.err != nil {
281 return nil
282 }
283 if n > uint64(len(r.data)-r.pos) {
284 r.err = fmt.Errorf("truncated block at offset %d (need %d bytes)", r.pos, n)
285 return nil
286 }
287 return r.take(int(n))
288 }
289
290 func (r *blockReader) compact() uint64 {
291 if r.err != nil {
292 return 0
293 }
294 n, size, err := readCompactSize(r.data[r.pos:])
295 if err != nil {
296 r.err = err
297 return 0
298 }
299 r.pos += size
300 return n
301 }
302