1 package builder
2 3 import (
4 "crypto/rand"
5 "fmt"
6 "math"
7 8 "github.com/p9c/p9/pkg/chainhash"
9 "github.com/p9c/p9/pkg/gcs"
10 "github.com/p9c/p9/pkg/txscript"
11 "github.com/p9c/p9/pkg/wire"
12 )
13 14 const (
15 // DefaultP is the default collision probability (2^-19)
16 DefaultP = 19
17 // DefaultM is the default value used for the hash range.
18 DefaultM uint64 = 784931
19 )
20 21 // GCS is a utility class that makes building GCS filters convenient.
22 type GCS struct {
23 p uint8
24 m uint64
25 key [gcs.KeySize]byte
26 // data is a set of entries represented as strings. This is done to deduplicate items as they are added.
27 data map[string]struct{}
28 err error
29 }
30 31 // RandomKey is a utility function that returns a cryptographically random [gcs.KeySize]byte usable as a key for a GCS
32 // filter.
33 func RandomKey() (key [gcs.KeySize]byte, e error) {
34 // Read a byte slice from rand.Reader.
35 randKey := make([]byte, gcs.KeySize)
36 _, e = rand.Read(randKey)
37 // This shouldn't happen unless the user is on a system that doesn't have a system CSPRNG. OK to panic in this case.
38 if e != nil {
39 return key, e
40 }
41 // Copy the byte slice to a [gcs.KeySize]byte array and return it.
42 copy(key[:], randKey[:])
43 return key, nil
44 }
45 46 // DeriveKey is a utility function that derives a key from a chainhash.Hash by truncating the bytes of the hash to the
47 // appopriate key size.
48 func DeriveKey(keyHash *chainhash.Hash) [gcs.KeySize]byte {
49 var key [gcs.KeySize]byte
50 copy(key[:], keyHash.CloneBytes()[:])
51 return key
52 }
53 54 // Key retrieves the key with which the builder will podbuild a filter. This is useful if the builder is created with a
55 // random initial key.
56 func (b *GCS) Key() ([gcs.KeySize]byte, error) {
57 // Do nothing if the builder's errored out.
58 if b.err != nil {
59 return [gcs.KeySize]byte{}, b.err
60 }
61 return b.key, nil
62 }
63 64 // SetKey sets the key with which the builder will podbuild a filter to the passed [gcs.KeySize]byte.
65 func (b *GCS) SetKey(key [gcs.KeySize]byte) *GCS {
66 // Do nothing if the builder's already errored out.
67 if b.err != nil {
68 return b
69 }
70 copy(b.key[:], key[:])
71 return b
72 }
73 74 // SetKeyFromHash sets the key with which the builder will podbuild a filter to a key derived from the passed
75 // chainhash.Hash using DeriveKey().
76 func (b *GCS) SetKeyFromHash(keyHash *chainhash.Hash) *GCS {
77 // Do nothing if the builder's already errored out.
78 if b.err != nil {
79 return b
80 }
81 return b.SetKey(DeriveKey(keyHash))
82 }
83 84 // SetP sets the filter's probability after calling Builder().
85 func (b *GCS) SetP(p uint8) *GCS {
86 // Do nothing if the builder's already errored out.
87 if b.err != nil {
88 return b
89 }
90 // Basic sanity check.
91 if p > 32 {
92 b.err = gcs.ErrPTooBig
93 return b
94 }
95 b.p = p
96 return b
97 }
98 99 // SetM sets the filter's modulous value after calling Builder().
100 func (b *GCS) SetM(m uint64) *GCS {
101 // Do nothing if the builder's already errored out.
102 if b.err != nil {
103 return b
104 }
105 // Basic sanity check.
106 if m > uint64(math.MaxUint32) {
107 b.err = gcs.ErrPTooBig
108 return b
109 }
110 b.m = m
111 return b
112 }
113 114 // Preallocate sets the estimated filter size after calling Builder() to reduce the probability of memory reallocations.
115 // If the builder has already had data added to it, Preallocate has no effect.
116 func (b *GCS) Preallocate(n uint32) *GCS {
117 // Do nothing if the builder's already errored out.
118 if b.err != nil {
119 return b
120 }
121 if b.data == nil {
122 b.data = make(map[string]struct{}, n)
123 }
124 return b
125 }
126 127 // AddEntry adds a []byte to the list of entries to be included in the GCS filter when it's built.
128 func (b *GCS) AddEntry(data []byte) *GCS {
129 // Do nothing if the builder's already errored out.
130 if b.err != nil {
131 return b
132 }
133 b.data[string(data)] = struct{}{}
134 return b
135 }
136 137 // AddEntries adds all the []byte entries in a [][]byte to the list of entries to be included in the GCS filter when
138 // it's built.
139 func (b *GCS) AddEntries(data [][]byte) *GCS {
140 // Do nothing if the builder's already errored out.
141 if b.err != nil {
142 return b
143 }
144 for _, entry := range data {
145 b.AddEntry(entry)
146 }
147 return b
148 }
149 150 // AddHash adds a chainhash.Hash to the list of entries to be included in the GCS filter when it's built.
151 func (b *GCS) AddHash(hash *chainhash.Hash) *GCS {
152 // Do nothing if the builder's already errored out.
153 if b.err != nil {
154 return b
155 }
156 return b.AddEntry(hash.CloneBytes())
157 }
158 159 // AddWitness adds each item of the passed filter stack to the filter, and then
160 // adds each item as a script.
161 func (b *GCS) AddWitness(witness wire.TxWitness) *GCS {
162 // Do nothing if the builder's already errored out.
163 if b.err != nil {
164 return b
165 }
166 return b.AddEntries(witness)
167 }
168 169 // Build returns a function which builds a GCS filter with the given parameters and data.
170 func (b *GCS) Build() (*gcs.Filter, error) {
171 // Do nothing if the builder's already errored out.
172 if b.err != nil {
173 return nil, b.err
174 }
175 // We'll ensure that all the parmaters we need to actually podbuild the filter properly are set.
176 if b.p == 0 {
177 return nil, fmt.Errorf("p value is not set, cannot podbuild")
178 }
179 if b.m == 0 {
180 return nil, fmt.Errorf("m value is not set, cannot podbuild")
181 }
182 dataSlice := make([][]byte, 0, len(b.data))
183 for item := range b.data {
184 dataSlice = append(dataSlice, []byte(item))
185 }
186 return gcs.BuildGCSFilter(b.p, b.m, b.key, dataSlice)
187 }
188 189 // WithKeyPNM creates a GCS with specified key and the passed probability, modulus and estimated filter size.
190 func WithKeyPNM(key [gcs.KeySize]byte, p uint8, n uint32, m uint64) *GCS {
191 b := GCS{}
192 return b.SetKey(key).SetP(p).SetM(m).Preallocate(n)
193 }
194 195 // WithKeyPM creates a GCS with specified key and the passed probability. Estimated filter size is set to zero,
196 // which means more reallocations are done when building the filter.
197 func WithKeyPM(key [gcs.KeySize]byte, p uint8, m uint64) *GCS {
198 return WithKeyPNM(key, p, 0, m)
199 }
200 201 // WithKey creates a GCS with specified key. Probability is set to 19 (2^-19 collision probability). Estimated
202 // filter size is set to zero, which means more reallocations are done when building the filter.
203 func WithKey(key [gcs.KeySize]byte) *GCS {
204 return WithKeyPNM(key, DefaultP, 0, DefaultM)
205 }
206 207 // WithKeyHashPNM creates a GCS with key derived from the specified chainhash.Hash and the passed probability and
208 // estimated filter size.
209 func WithKeyHashPNM(
210 keyHash *chainhash.Hash, p uint8, n uint32,
211 m uint64,
212 ) *GCS {
213 return WithKeyPNM(DeriveKey(keyHash), p, n, m)
214 }
215 216 // WithKeyHashPM creates a GCS with key derived from the specified chainhash.Hash and the passed probability.
217 // Estimated filter size is set to zero, which means more reallocations are done when building the filter.
218 func WithKeyHashPM(keyHash *chainhash.Hash, p uint8, m uint64) *GCS {
219 return WithKeyHashPNM(keyHash, p, 0, m)
220 }
221 222 // WithKeyHash creates a GCS with key derived from the specified chainhash.Hash. Probability is set to 20 (2^-20
223 // collision probability). Estimated filter size is set to zero, which means more reallocations are done when building
224 // the filter.
225 func WithKeyHash(keyHash *chainhash.Hash) *GCS {
226 return WithKeyHashPNM(keyHash, DefaultP, 0, DefaultM)
227 }
228 229 // WithRandomKeyPNM creates a GCS with a cryptographically random key and the passed probability and estimated
230 // filter size.
231 func WithRandomKeyPNM(p uint8, n uint32, m uint64) *GCS {
232 key, e := RandomKey()
233 if e != nil {
234 b := GCS{err: e}
235 return &b
236 }
237 return WithKeyPNM(key, p, n, m)
238 }
239 240 // WithRandomKeyPM creates a GCS with a cryptographically random key and the passed probability. Estimated filter
241 // size is set to zero, which means more reallocations are done when building the filter.
242 func WithRandomKeyPM(p uint8, m uint64) *GCS {
243 return WithRandomKeyPNM(p, 0, m)
244 }
245 246 // WithRandomKey creates a GCS with a cryptographically random key. Probability is set to 20 (2^-20 collision
247 // probability). Estimated filter size is set to zero, which means more reallocations are done when building the filter.
248 func WithRandomKey() *GCS {
249 return WithRandomKeyPNM(DefaultP, 0, DefaultM)
250 }
251 252 // BuildBasicFilter builds a basic GCS filter from a block. A basic GCS filter will contain all the previous output
253 // scripts spent by inputs within a block, as well as the data pushes within all the outputs created within a block.
254 func BuildBasicFilter(block *wire.Block, prevOutScripts [][]byte) (*gcs.Filter, error) {
255 blockHash := block.BlockHash()
256 b := WithKeyHash(&blockHash)
257 // If the filter had an issue with the specified key, then we force it to bubble up here by calling the Key()
258 // function.
259 _, e := b.Key()
260 if e != nil {
261 return nil, e
262 }
263 // In order to podbuild a basic filter, we'll range over the entire block, adding each whole script itself.
264 for _, tx := range block.Transactions {
265 // For each output in a transaction, we'll add each of the individual data pushes within the script.
266 for _, txOut := range tx.TxOut {
267 if len(txOut.PkScript) == 0 {
268 continue
269 }
270 // In order to allow the filters to later be committed to within an OP_RETURN output, we ignore all
271 // OP_RETURNs to avoid a circular dependency.
272 if txOut.PkScript[0] == txscript.OP_RETURN &&
273 txscript.IsPushOnlyScript(txOut.PkScript[1:]) {
274 continue
275 }
276 b.AddEntry(txOut.PkScript)
277 }
278 }
279 // In the second pass, we'll also add all the prevOutScripts individually as elements.
280 for _, prevScript := range prevOutScripts {
281 if len(prevScript) == 0 {
282 continue
283 }
284 b.AddEntry(prevScript)
285 }
286 return b.Build()
287 }
288 289 // GetFilterHash returns the double-SHA256 of the filter.
290 func GetFilterHash(filter *gcs.Filter) (chainhash.Hash, error) {
291 filterData, e := filter.NBytes()
292 if e != nil {
293 return chainhash.Hash{}, e
294 }
295 return chainhash.DoubleHashH(filterData), nil
296 }
297 298 // MakeHeaderForFilter makes a filter chain header for a filter, given the filter and the previous filter chain header.
299 func MakeHeaderForFilter(filter *gcs.Filter, prevHeader chainhash.Hash) (chainhash.Hash, error) {
300 filterTip := make([]byte, 2*chainhash.HashSize)
301 filterHash, e := GetFilterHash(filter)
302 if e != nil {
303 return chainhash.Hash{}, e
304 }
305 // In the buffer we created above we'll compute hash || prevHash as an intermediate value.
306 copy(filterTip, filterHash[:])
307 copy(filterTip[chainhash.HashSize:], prevHeader[:])
308 // The final filter hash is the double-sha256 of the hash computed above.
309 return chainhash.DoubleHashH(filterTip), nil
310 }
311