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