1 package bloom
2 3 import (
4 "encoding/binary"
5 "math"
6 "sync"
7 8 "github.com/p9c/p9/pkg/chainhash"
9 "github.com/p9c/p9/pkg/txscript"
10 "github.com/p9c/p9/pkg/util"
11 "github.com/p9c/p9/pkg/wire"
12 )
13 14 // ln2Squared is simply the square of the natural log of 2.
15 const ln2Squared = math.Ln2 * math.Ln2
16 17 // minUint32 is a convenience function to return the minimum value of the two passed uint32 values.
18 func minUint32(a, b uint32) uint32 {
19 if a < b {
20 return a
21 }
22 return b
23 }
24 25 // Filter defines a bitcoin bloom filter that provides easy manipulation of raw filter data.
26 type Filter struct {
27 mtx sync.Mutex
28 msgFilterLoad *wire.MsgFilterLoad
29 }
30 31 // NewFilter creates a new bloom filter instance, mainly to be used by SPV clients. The tweak parameter is a random
32 // value added to the seed value. The false positive rate is the probability of a false positive where 1.0 is "match
33 // everything" and zero is unachievable.
34 //
35 // Thus, providing any false positive rates less than 0 or greater than 1 will be adjusted to the valid range. For more
36 // information on what values to use for both elements and fprate, see https://en.wikipedia.org/wiki/Bloom_filter.
37 func NewFilter(elements, tweak uint32, fprate float64, flags wire.BloomUpdateType) *Filter {
38 // Massage the false positive rate to sane values.
39 if fprate > 1.0 {
40 fprate = 1.0
41 }
42 if fprate < 1e-9 {
43 fprate = 1e-9
44 }
45 // Calculate the size of the filter in bytes for the given number of elements and false positive rate. Equivalent to
46 // m = -(n*ln(p) / ln(2)^2), where m is in bits. Then clamp it to the maximum filter size and convert to bytes.
47 dataLen := uint32(-1 * float64(elements) * math.Log(fprate) / ln2Squared)
48 dataLen = minUint32(dataLen, wire.MaxFilterLoadFilterSize*8) / 8
49 // Calculate the number of hash functions based on the size of the filter calculated above and the number of
50 // elements. Equivalent to k = (m/n) * ln(2) Then clamp it to the maximum allowed hash funcs.
51 hashFuncs := uint32(float64(dataLen*8) / float64(elements) * math.Ln2)
52 hashFuncs = minUint32(hashFuncs, wire.MaxFilterLoadHashFuncs)
53 data := make([]byte, dataLen)
54 msg := wire.NewMsgFilterLoad(data, hashFuncs, tweak, flags)
55 return &Filter{
56 msgFilterLoad: msg,
57 }
58 }
59 60 // LoadFilter creates a new Filter instance with the given underlying wire.MsgFilterLoad.
61 func LoadFilter(filter *wire.MsgFilterLoad) *Filter {
62 return &Filter{
63 msgFilterLoad: filter,
64 }
65 }
66 67 // IsLoaded returns true if a filter is loaded, otherwise false.
68 //
69 // This function is safe for concurrent access.
70 func (bf *Filter) IsLoaded() bool {
71 bf.mtx.Lock()
72 loaded := bf.msgFilterLoad != nil
73 bf.mtx.Unlock()
74 return loaded
75 }
76 77 // Reload loads a new filter replacing any existing filter.
78 //
79 // This function is safe for concurrent access.
80 func (bf *Filter) Reload(filter *wire.MsgFilterLoad) {
81 bf.mtx.Lock()
82 bf.msgFilterLoad = filter
83 bf.mtx.Unlock()
84 }
85 86 // Unload unloads the bloom filter. This function is safe for concurrent access.
87 func (bf *Filter) Unload() {
88 bf.mtx.Lock()
89 bf.msgFilterLoad = nil
90 bf.mtx.Unlock()
91 }
92 93 // hash returns the bit offset in the bloom filter which corresponds to the passed data for the given indepedent hash
94 // function number.
95 func (bf *Filter) hash(hashNum uint32, data []byte) uint32 {
96 // bitcoind: 0xfba4c795 chosen as it guarantees a reasonable bit difference between hashNum values. Note that << 3
97 // is equivalent to multiplying by 8, but is faster. Thus the returned hash is brought into range of the number of
98 // bits the filter has and returned.
99 mm := MurmurHash3(hashNum*0xfba4c795+bf.msgFilterLoad.Tweak, data)
100 return mm % (uint32(len(bf.msgFilterLoad.Filter)) << 3)
101 }
102 103 // matches returns true if the bloom filter might contain the passed data and false if it definitely does not.
104 //
105 // This function MUST be called with the filter lock held.
106 func (bf *Filter) matches(data []byte) bool {
107 if bf.msgFilterLoad == nil {
108 return false
109 }
110 // The bloom filter does not contain the data if any of the bit offsets which result from hashing the data using
111 // each independent hash are not set. The shifts and masks below are a faster equivalent of:
112 //
113 // arrayIndex := idx / 8 (idx >> 3)
114 // bitOffset := idx % 8 (idx & 7)
115 // if filter[arrayIndex] & 1<<bitOffset == 0 { ... }
116 for i := uint32(0); i < bf.msgFilterLoad.HashFuncs; i++ {
117 idx := bf.hash(i, data)
118 if bf.msgFilterLoad.Filter[idx>>3]&(1<<(idx&7)) == 0 {
119 return false
120 }
121 }
122 return true
123 }
124 125 // Matches returns true if the bloom filter might contain the passed data and false if it definitely does not.
126 //
127 // This function is safe for concurrent access.
128 func (bf *Filter) Matches(data []byte) bool {
129 bf.mtx.Lock()
130 match := bf.matches(data)
131 bf.mtx.Unlock()
132 return match
133 }
134 135 // matchesOutPoint returns true if the bloom filter might contain the passed outpoint and false if it definitely does
136 // not.
137 //
138 // This function MUST be called with the filter lock held.
139 func (bf *Filter) matchesOutPoint(outpoint *wire.OutPoint) bool {
140 // Serialize
141 var buf [chainhash.HashSize + 4]byte
142 copy(buf[:], outpoint.Hash[:])
143 binary.LittleEndian.PutUint32(buf[chainhash.HashSize:], outpoint.Index)
144 return bf.matches(buf[:])
145 }
146 147 // MatchesOutPoint returns true if the bloom filter might contain the passed outpoint and false if it definitely does
148 // not.
149 //
150 // This function is safe for concurrent access.
151 func (bf *Filter) MatchesOutPoint(outpoint *wire.OutPoint) bool {
152 bf.mtx.Lock()
153 match := bf.matchesOutPoint(outpoint)
154 bf.mtx.Unlock()
155 return match
156 }
157 158 // add adds the passed byte slice to the bloom filter.
159 //
160 // This function MUST be called with the filter lock held.
161 func (bf *Filter) add(data []byte) {
162 if bf.msgFilterLoad == nil {
163 return
164 }
165 // Adding data to a bloom filter consists of setting all of the bit offsets which result from hashing the data using
166 // each independent hash function. The shifts and masks below are a faster equivalent of:
167 //
168 // arrayIndex := idx / 8 (idx >> 3)
169 // bitOffset := idx % 8 (idx & 7)
170 // filter[arrayIndex] |= 1<<bitOffset
171 // editors note: most CPUs now implement power of two multiplication and division as shifts anyway
172 for i := uint32(0); i < bf.msgFilterLoad.HashFuncs; i++ {
173 idx := bf.hash(i, data)
174 bf.msgFilterLoad.Filter[idx>>3] |= 1 << (7 & idx)
175 }
176 }
177 178 // Add adds the passed byte slice to the bloom filter.
179 //
180 // This function is safe for concurrent access.
181 func (bf *Filter) Add(data []byte) {
182 bf.mtx.Lock()
183 bf.add(data)
184 bf.mtx.Unlock()
185 }
186 187 // AddHash adds the passed chainhash.Hash to the Filter.
188 //
189 // This function is safe for concurrent access.
190 func (bf *Filter) AddHash(hash *chainhash.Hash) {
191 bf.mtx.Lock()
192 bf.add(hash[:])
193 bf.mtx.Unlock()
194 }
195 196 // addOutPoint adds the passed transaction outpoint to the bloom filter.
197 //
198 // This function MUST be called with the filter
199 // lock held.
200 func (bf *Filter) addOutPoint(outpoint *wire.OutPoint) {
201 // Serialize
202 var buf [chainhash.HashSize + 4]byte
203 copy(buf[:], outpoint.Hash[:])
204 binary.LittleEndian.PutUint32(buf[chainhash.HashSize:], outpoint.Index)
205 bf.add(buf[:])
206 }
207 208 // AddOutPoint adds the passed transaction outpoint to the bloom filter.
209 //
210 // This function is safe for concurrent access.
211 func (bf *Filter) AddOutPoint(outpoint *wire.OutPoint) {
212 bf.mtx.Lock()
213 bf.addOutPoint(outpoint)
214 bf.mtx.Unlock()
215 }
216 217 // maybeAddOutpoint potentially adds the passed outpoint to the bloom filter depending on the bloom update flags and the type of the passed public key script. This function MUST be called with the filter lock held.
218 func (bf *Filter) maybeAddOutpoint(pkScript []byte, outHash *chainhash.Hash, outIdx uint32) {
219 switch bf.msgFilterLoad.Flags {
220 case wire.BloomUpdateAll:
221 outpoint := wire.NewOutPoint(outHash, outIdx)
222 bf.addOutPoint(outpoint)
223 case wire.BloomUpdateP2PubkeyOnly:
224 class := txscript.GetScriptClass(pkScript)
225 if class == txscript.PubKeyTy || class == txscript.MultiSigTy {
226 outpoint := wire.NewOutPoint(outHash, outIdx)
227 bf.addOutPoint(outpoint)
228 }
229 }
230 }
231 232 // matchTxAndUpdate returns true if the bloom filter matches data within the passed transaction, otherwise false is returned. If the filter does match the passed transaction, it will also update the filter depending on the bloom update flags set via the loaded filter if needed. This function MUST be called with the filter lock held.
233 func (bf *Filter) matchTxAndUpdate(tx *util.Tx) bool {
234 // Chk if the filter matches the hash of the transaction. This is useful for finding transactions when they appear in a block.
235 matched := bf.matches(tx.Hash()[:])
236 // Chk if the filter matches any data elements in the public key scripts of any of the outputs. When it does, add the outpoint that matched so transactions which spend from the matched transaction are also included in the filter. This removes the burden of updating the filter for this scenario from the client. It is also more efficient on the network since it avoids the need for another filteradd message from the client and avoids some potential races that could otherwise occur.
237 for i, txOut := range tx.MsgTx().TxOut {
238 pushedData, e := txscript.PushedData(txOut.PkScript)
239 if e != nil {
240 continue
241 }
242 for _, data := range pushedData {
243 if !bf.matches(data) {
244 continue
245 }
246 matched = true
247 bf.maybeAddOutpoint(txOut.PkScript, tx.Hash(), uint32(i))
248 break
249 }
250 }
251 // Nothing more to do if a match has already been made.
252 if matched {
253 return true
254 }
255 // At this point, the transaction and none of the data elements in the public key scripts of its outputs matched. Chk if the filter matches any outpoints this transaction spends or any any data elements in the signature scripts of any of the inputs.
256 for _, txin := range tx.MsgTx().TxIn {
257 if bf.matchesOutPoint(&txin.PreviousOutPoint) {
258 return true
259 }
260 pushedData, e := txscript.PushedData(txin.SignatureScript)
261 if e != nil {
262 continue
263 }
264 for _, data := range pushedData {
265 if bf.matches(data) {
266 return true
267 }
268 }
269 }
270 return false
271 }
272 273 // MatchTxAndUpdate returns true if the bloom filter matches data within the passed transaction, otherwise false is returned. If the filter does match the passed transaction, it will also update the filter depending on the bloom update flags set via the loaded filter if needed. This function is safe for concurrent access.
274 func (bf *Filter) MatchTxAndUpdate(tx *util.Tx) bool {
275 bf.mtx.Lock()
276 match := bf.matchTxAndUpdate(tx)
277 bf.mtx.Unlock()
278 return match
279 }
280 281 // MsgFilterLoad returns the underlying wire.MsgFilterLoad for the bloom filter. This function is safe for concurrent access.
282 func (bf *Filter) MsgFilterLoad() *wire.MsgFilterLoad {
283 bf.mtx.Lock()
284 msg := bf.msgFilterLoad
285 bf.mtx.Unlock()
286 return msg
287 }
288