forked from Roasbeef/btcutil
-
Notifications
You must be signed in to change notification settings - Fork 0
/
builder.go
398 lines (335 loc) · 11.9 KB
/
builder.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
// Copyright (c) 2017 The btcsuite developers
// Copyright (c) 2017 The Lightning Network Developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package builder
import (
"crypto/rand"
"encoding/binary"
"github.com/roasbeef/btcd/chaincfg/chainhash"
"github.com/roasbeef/btcd/txscript"
"github.com/roasbeef/btcd/wire"
"github.com/roasbeef/btcutil/gcs"
)
// DefaultP is the default collision probability (2^-20)
const DefaultP = 20
// GCSBuilder is a utility class that makes building GCS filters convenient.
type GCSBuilder struct {
p uint8
key [gcs.KeySize]byte
data [][]byte
err error
}
// RandomKey is a utility function that returns a cryptographically random
// [gcs.KeySize]byte usable as a key for a GCS filter.
func RandomKey() ([gcs.KeySize]byte, error) {
var key [gcs.KeySize]byte
// Read a byte slice from rand.Reader.
randKey := make([]byte, gcs.KeySize)
_, err := rand.Read(randKey)
// This shouldn't happen unless the user is on a system that doesn't
// have a system CSPRNG. OK to panic in this case.
if err != nil {
return key, err
}
// Copy the byte slice to a [gcs.KeySize]byte array and return it.
copy(key[:], randKey[:])
return key, nil
}
// DeriveKey is a utility function that derives a key from a chainhash.Hash by
// truncating the bytes of the hash to the appopriate key size.
func DeriveKey(keyHash *chainhash.Hash) [gcs.KeySize]byte {
var key [gcs.KeySize]byte
copy(key[:], keyHash.CloneBytes()[:])
return key
}
// OutPointToFilterEntry is a utility function that derives a filter entry from
// a wire.OutPoint in a standardized way for use with both building and
// querying filters.
func OutPointToFilterEntry(outpoint wire.OutPoint) []byte {
// Size of the hash plus size of int32 index
data := make([]byte, chainhash.HashSize+4)
copy(data[:], outpoint.Hash.CloneBytes()[:])
binary.LittleEndian.PutUint32(data[chainhash.HashSize:], outpoint.Index)
return data
}
// Key retrieves the key with which the builder will build a filter. This is
// useful if the builder is created with a random initial key.
func (b *GCSBuilder) Key() ([gcs.KeySize]byte, error) {
// Do nothing if the builder's errored out.
if b.err != nil {
return [gcs.KeySize]byte{}, b.err
}
return b.key, nil
}
// SetKey sets the key with which the builder will build a filter to the passed
// [gcs.KeySize]byte.
func (b *GCSBuilder) SetKey(key [gcs.KeySize]byte) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
copy(b.key[:], key[:])
return b
}
// SetKeyFromHash sets the key with which the builder will build a filter to a
// key derived from the passed chainhash.Hash using DeriveKey().
func (b *GCSBuilder) SetKeyFromHash(keyHash *chainhash.Hash) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
return b.SetKey(DeriveKey(keyHash))
}
// SetP sets the filter's probability after calling Builder().
func (b *GCSBuilder) SetP(p uint8) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
// Basic sanity check.
if p > 32 {
b.err = gcs.ErrPTooBig
return b
}
b.p = p
return b
}
// Preallocate sets the estimated filter size after calling Builder() to reduce
// the probability of memory reallocations. If the builder has already had data
// added to it, Preallocate has no effect.
func (b *GCSBuilder) Preallocate(n uint32) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
if len(b.data) == 0 {
b.data = make([][]byte, 0, n)
}
return b
}
// AddEntry adds a []byte to the list of entries to be included in the GCS
// filter when it's built.
func (b *GCSBuilder) AddEntry(data []byte) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
b.data = append(b.data, data)
return b
}
// AddEntries adds all the []byte entries in a [][]byte to the list of entries
// to be included in the GCS filter when it's built.
func (b *GCSBuilder) AddEntries(data [][]byte) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
for _, entry := range data {
b.AddEntry(entry)
}
return b
}
// AddOutPoint adds a wire.OutPoint to the list of entries to be included in
// the GCS filter when it's built.
func (b *GCSBuilder) AddOutPoint(outpoint wire.OutPoint) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
return b.AddEntry(OutPointToFilterEntry(outpoint))
}
// AddHash adds a chainhash.Hash to the list of entries to be included in the
// GCS filter when it's built.
func (b *GCSBuilder) AddHash(hash *chainhash.Hash) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
return b.AddEntry(hash.CloneBytes())
}
// AddScript adds all the data pushed in the script serialized as the passed
// []byte to the list of entries to be included in the GCS filter when it's
// built.
func (b *GCSBuilder) AddScript(script []byte) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
// Ignore errors and add pushed data, if any
data, _ := txscript.PushedData(script)
if len(data) == 0 {
return b
}
return b.AddEntries(data)
}
// AddWitness adds each item of the passed filter stack to the filer.
func (b *GCSBuilder) AddWitness(witness wire.TxWitness) *GCSBuilder {
// Do nothing if the builder's already errored out.
if b.err != nil {
return b
}
return b.AddEntries(witness)
}
// Build returns a function which builds a GCS filter with the given parameters
// and data.
func (b *GCSBuilder) Build() (*gcs.Filter, error) {
// Do nothing if the builder's already errored out.
if b.err != nil {
return nil, b.err
}
return gcs.BuildGCSFilter(b.p, b.key, b.data)
}
// WithKeyPN creates a GCSBuilder with specified key and the passed probability
// and estimated filter size.
func WithKeyPN(key [gcs.KeySize]byte, p uint8, n uint32) *GCSBuilder {
b := GCSBuilder{}
return b.SetKey(key).SetP(p).Preallocate(n)
}
// WithKeyP creates a GCSBuilder with specified key and the passed probability.
// Estimated filter size is set to zero, which means more reallocations are
// done when building the filter.
func WithKeyP(key [gcs.KeySize]byte, p uint8) *GCSBuilder {
return WithKeyPN(key, p, 0)
}
// WithKey creates a GCSBuilder with specified key. Probability is set to
// 20 (2^-20 collision probability). Estimated filter size is set to zero, which
// means more reallocations are done when building the filter.
func WithKey(key [gcs.KeySize]byte) *GCSBuilder {
return WithKeyPN(key, DefaultP, 0)
}
// WithKeyHashPN creates a GCSBuilder with key derived from the specified
// chainhash.Hash and the passed probability and estimated filter size.
func WithKeyHashPN(keyHash *chainhash.Hash, p uint8, n uint32) *GCSBuilder {
return WithKeyPN(DeriveKey(keyHash), p, n)
}
// WithKeyHashP creates a GCSBuilder with key derived from the specified
// chainhash.Hash and the passed probability. Estimated filter size is set to
// zero, which means more reallocations are done when building the filter.
func WithKeyHashP(keyHash *chainhash.Hash, p uint8) *GCSBuilder {
return WithKeyHashPN(keyHash, p, 0)
}
// WithKeyHash creates a GCSBuilder with key derived from the specified
// chainhash.Hash. Probability is set to 20 (2^-20 collision probability).
// Estimated filter size is set to zero, which means more reallocations are
// done when building the filter.
func WithKeyHash(keyHash *chainhash.Hash) *GCSBuilder {
return WithKeyHashPN(keyHash, DefaultP, 0)
}
// WithRandomKeyPN creates a GCSBuilder with a cryptographically random key and
// the passed probability and estimated filter size.
func WithRandomKeyPN(p uint8, n uint32) *GCSBuilder {
key, err := RandomKey()
if err != nil {
b := GCSBuilder{err: err}
return &b
}
return WithKeyPN(key, p, n)
}
// WithRandomKeyP creates a GCSBuilder with a cryptographically random key and
// the passed probability. Estimated filter size is set to zero, which means
// more reallocations are done when building the filter.
func WithRandomKeyP(p uint8) *GCSBuilder {
return WithRandomKeyPN(p, 0)
}
// WithRandomKey creates a GCSBuilder with a cryptographically random key.
// Probability is set to 20 (2^-20 collision probability). Estimated filter
// size is set to zero, which means more reallocations are done when
// building the filter.
func WithRandomKey() *GCSBuilder {
return WithRandomKeyPN(DefaultP, 0)
}
// BuildBasicFilter builds a basic GCS filter from a block. A basic GCS filter
// will contain all the previous outpoints spent within a block, as well as the
// data pushes within all the outputs created within a block.
func BuildBasicFilter(block *wire.MsgBlock) (*gcs.Filter, error) {
blockHash := block.BlockHash()
b := WithKeyHash(&blockHash)
// If the filter had an issue with the specified key, then we force it
// to bubble up here by calling the Key() function.
_, err := b.Key()
if err != nil {
return nil, err
}
// In order to build a basic filter, we'll range over the entire block,
// adding the outpoint data as well as the data pushes within the
// pkScript.
for i, tx := range block.Transactions {
// Skip the inputs for the coinbase transaction
if i != 0 {
// Each each txin, we'll add a serialized version of
// the txid:index to the filters data slices.
for _, txIn := range tx.TxIn {
b.AddOutPoint(txIn.PreviousOutPoint)
}
}
// For each output in a transaction, we'll add each of the
// individual data pushes within the script.
for _, txOut := range tx.TxOut {
b.AddScript(txOut.PkScript)
}
}
return b.Build()
}
// BuildExtFilter builds an extended GCS filter from a block. An extended
// filter supplements a regular basic filter by include all the _witness_ data
// found within a block. This includes all the data pushes within any signature
// scripts as well as each element of an input's witness stack. Additionally,
// the _hashes_ of each transaction are also inserted into the filter.
func BuildExtFilter(block *wire.MsgBlock) (*gcs.Filter, error) {
blockHash := block.BlockHash()
b := WithKeyHash(&blockHash)
// If the filter had an issue with the specified key, then we force it
// to bubble up here by calling the Key() function.
_, err := b.Key()
if err != nil {
return nil, err
}
// In order to build an extended filter, we add the hash of each
// transaction as well as each piece of witness data included in both
// the sigScript and the witness stack of an input.
for i, tx := range block.Transactions {
// First we'll compute the bash of the transaction and add that
// directly to the filter.
txHash := tx.TxHash()
b.AddHash(&txHash)
// Skip the inputs for the coinbase transaction
if i != 0 {
// Next, for each input, we'll add the sigScript (if
// it's present), and also the witness stack (if it's
// present)
for _, txIn := range tx.TxIn {
if txIn.SignatureScript != nil {
b.AddScript(txIn.SignatureScript)
}
if len(txIn.Witness) != 0 {
b.AddWitness(txIn.Witness)
}
}
}
}
return b.Build()
}
// GetFilterHash returns the double-SHA256 of the filter.
func GetFilterHash(filter *gcs.Filter) chainhash.Hash {
var zero chainhash.Hash
if filter == nil {
return zero
}
hash1 := chainhash.HashH(filter.NBytes())
return chainhash.HashH(hash1[:])
}
// MakeHeaderForFilter makes a filter chain header for a filter, given the
// filter and the previous filter chain header.
func MakeHeaderForFilter(filter *gcs.Filter, prevHeader chainhash.Hash) chainhash.Hash {
filterTip := make([]byte, 2*chainhash.HashSize)
filterHash := GetFilterHash(filter)
// In the buffer we created above we'll compute hash || prevHash as an
// intermediate value.
copy(filterTip, filterHash[:])
copy(filterTip[chainhash.HashSize:], prevHeader[:])
// The final filter hash is the double-sha256 of the hash computed
// above.
hash1 := chainhash.HashH(filterTip)
return chainhash.HashH(hash1[:])
}