Bitcoin ABC  0.22.12
P2P Digital Currency
bloom.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-2016 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #include <bloom.h>
6 
7 #include <hash.h>
9 #include <random.h>
10 #include <script/script.h>
11 #include <script/standard.h>
12 #include <streams.h>
13 
14 #include <cmath>
15 #include <cstdlib>
16 
17 #include <algorithm>
18 
19 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455
20 #define LN2 0.6931471805599453094172321214581765680755001343602552
21 
35 CBloomFilter::CBloomFilter(const uint32_t nElements, const double nFPRate,
36  const uint32_t nTweakIn, uint8_t nFlagsIn)
37  : vData(std::min<uint32_t>(-1 / LN2SQUARED * nElements * log(nFPRate),
39  8),
40  isFull(false), isEmpty(true),
41  nHashFuncs(std::min<uint32_t>(vData.size() * 8 / nElements * LN2,
43  nTweak(nTweakIn), nFlags(nFlagsIn) {}
44 
45 inline uint32_t
46 CBloomFilter::Hash(uint32_t nHashNum,
47  const std::vector<uint8_t> &vDataToHash) const {
48  // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between
49  // nHashNum values.
50  return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) %
51  (vData.size() * 8);
52 }
53 
54 void CBloomFilter::insert(const std::vector<uint8_t> &vKey) {
55  if (isFull) {
56  return;
57  }
58 
59  for (uint32_t i = 0; i < nHashFuncs; i++) {
60  uint32_t nIndex = Hash(i, vKey);
61  // Sets bit nIndex of vData
62  vData[nIndex >> 3] |= (1 << (7 & nIndex));
63  }
64  isEmpty = false;
65 }
66 
67 void CBloomFilter::insert(const COutPoint &outpoint) {
69  stream << outpoint;
70  std::vector<uint8_t> data(stream.begin(), stream.end());
71  insert(data);
72 }
73 
74 void CBloomFilter::insert(const uint256 &hash) {
75  std::vector<uint8_t> data(hash.begin(), hash.end());
76  insert(data);
77 }
78 
79 bool CBloomFilter::contains(const std::vector<uint8_t> &vKey) const {
80  if (isFull) {
81  return true;
82  }
83  if (isEmpty) {
84  return false;
85  }
86  for (uint32_t i = 0; i < nHashFuncs; i++) {
87  uint32_t nIndex = Hash(i, vKey);
88  // Checks bit nIndex of vData
89  if (!(vData[nIndex >> 3] & (1 << (7 & nIndex)))) {
90  return false;
91  }
92  }
93  return true;
94 }
95 
96 bool CBloomFilter::contains(const COutPoint &outpoint) const {
98  stream << outpoint;
99  std::vector<uint8_t> data(stream.begin(), stream.end());
100  return contains(data);
101 }
102 
103 bool CBloomFilter::contains(const uint256 &hash) const {
104  std::vector<uint8_t> data(hash.begin(), hash.end());
105  return contains(data);
106 }
107 
109  vData.assign(vData.size(), 0);
110  isFull = false;
111  isEmpty = true;
112 }
113 
114 void CBloomFilter::reset(const uint32_t nNewTweak) {
115  clear();
116  nTweak = nNewTweak;
117 }
118 
120  return vData.size() <= MAX_BLOOM_FILTER_SIZE &&
122 }
123 
125  bool fFound = false;
126  // Match if the filter contains the hash of tx for finding tx when they
127  // appear in a block
128  if (isFull) {
129  return true;
130  }
131  if (isEmpty) {
132  return false;
133  }
134 
135  const TxId &txid = tx.GetId();
136  if (contains(txid)) {
137  fFound = true;
138  }
139 
140  for (size_t i = 0; i < tx.vout.size(); i++) {
141  const CTxOut &txout = tx.vout[i];
142  // Match if the filter contains any arbitrary script data element in any
143  // scriptPubKey in tx. If this matches, also add the specific output
144  // that was matched. This means clients don't have to update the filter
145  // themselves when a new relevant tx is discovered in order to find
146  // spending transactions, which avoids round-tripping and race
147  // conditions.
149  std::vector<uint8_t> data;
150  while (pc < txout.scriptPubKey.end()) {
151  opcodetype opcode;
152  if (!txout.scriptPubKey.GetOp(pc, opcode, data)) {
153  break;
154  }
155  if (data.size() != 0 && contains(data)) {
156  fFound = true;
158  insert(COutPoint(txid, i));
159  } else if ((nFlags & BLOOM_UPDATE_MASK) ==
161  std::vector<std::vector<uint8_t>> vSolutions;
162  txnouttype type = Solver(txout.scriptPubKey, vSolutions);
163  if (type == TX_PUBKEY || type == TX_MULTISIG) {
164  insert(COutPoint(txid, i));
165  }
166  }
167  break;
168  }
169  }
170  }
171 
172  return fFound;
173 }
174 
176  if (isEmpty) {
177  return false;
178  }
179 
180  for (const CTxIn &txin : tx.vin) {
181  // Match if the filter contains an outpoint tx spends
182  if (contains(txin.prevout)) {
183  return true;
184  }
185 
186  // Match if the filter contains any arbitrary script data element in any
187  // scriptSig in tx
189  std::vector<uint8_t> data;
190  while (pc < txin.scriptSig.end()) {
191  opcodetype opcode;
192  if (!txin.scriptSig.GetOp(pc, opcode, data)) {
193  break;
194  }
195  if (data.size() != 0 && contains(data)) {
196  return true;
197  }
198  }
199  }
200 
201  return false;
202 }
203 
205  bool full = true;
206  bool empty = true;
207  for (const auto d : vData) {
208  full &= (d == 0xff);
209  empty &= (d == 0);
210  }
211  isFull = full;
212  isEmpty = empty;
213 }
214 
216  const double fpRate) {
217  double logFpRate = log(fpRate);
218  /* The optimal number of hash functions is log(fpRate) / log(0.5), but
219  * restrict it to the range 1-50. */
220  nHashFuncs = std::max(1, std::min<int>(round(logFpRate / log(0.5)), 50));
221  /* In this rolling bloom filter, we'll store between 2 and 3 generations of
222  * nElements / 2 entries. */
223  nEntriesPerGeneration = (nElements + 1) / 2;
224  uint32_t nMaxElements = nEntriesPerGeneration * 3;
225  /* The maximum fpRate = pow(1.0 - exp(-nHashFuncs * nMaxElements /
226  * nFilterBits), nHashFuncs)
227  * => pow(fpRate, 1.0 / nHashFuncs) = 1.0 - exp(-nHashFuncs *
228  * nMaxElements / nFilterBits)
229  * => 1.0 - pow(fpRate, 1.0 / nHashFuncs) = exp(-nHashFuncs *
230  * nMaxElements / nFilterBits)
231  * => log(1.0 - pow(fpRate, 1.0 / nHashFuncs)) = -nHashFuncs *
232  * nMaxElements / nFilterBits
233  * => nFilterBits = -nHashFuncs * nMaxElements / log(1.0 -
234  * pow(fpRate, 1.0 / nHashFuncs))
235  * => nFilterBits = -nHashFuncs * nMaxElements / log(1.0 -
236  * exp(logFpRate / nHashFuncs))
237  */
238  uint32_t nFilterBits =
239  uint32_t(ceil(-1.0 * nHashFuncs * nMaxElements /
240  log(1.0 - exp(logFpRate / nHashFuncs))));
241  data.clear();
242  /* For each data element we need to store 2 bits. If both bits are 0, the
243  * bit is treated as unset. If the bits are (01), (10), or (11), the bit is
244  * treated as set in generation 1, 2, or 3 respectively. These bits are
245  * stored in separate integers: position P corresponds to bit (P & 63) of
246  * the integers data[(P >> 6) * 2] and data[(P >> 6) * 2 + 1]. */
247  data.resize(((nFilterBits + 63) / 64) << 1);
248  reset();
249 }
250 
251 /* Similar to CBloomFilter::Hash */
252 static inline uint32_t
253 RollingBloomHash(uint32_t nHashNum, uint32_t nTweak,
254  const std::vector<uint8_t> &vDataToHash) {
255  return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
256 }
257 
258 // A replacement for x % n. This assumes that x and n are 32bit integers, and x
259 // is a uniformly random distributed 32bit value which should be the case for a
260 // good hash. See
261 // https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
262 static inline uint32_t FastMod(uint32_t x, size_t n) {
263  return (uint64_t(x) * uint64_t(n)) >> 32;
264 }
265 
266 void CRollingBloomFilter::insert(const std::vector<uint8_t> &vKey) {
267  if (nEntriesThisGeneration == nEntriesPerGeneration) {
268  nEntriesThisGeneration = 0;
269  nGeneration++;
270  if (nGeneration == 4) {
271  nGeneration = 1;
272  }
273  uint64_t nGenerationMask1 = 0 - uint64_t(nGeneration & 1);
274  uint64_t nGenerationMask2 = 0 - uint64_t(nGeneration >> 1);
275  /* Wipe old entries that used this generation number. */
276  for (uint32_t p = 0; p < data.size(); p += 2) {
277  uint64_t p1 = data[p], p2 = data[p + 1];
278  uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
279  data[p] = p1 & mask;
280  data[p + 1] = p2 & mask;
281  }
282  }
283  nEntriesThisGeneration++;
284 
285  for (int n = 0; n < nHashFuncs; n++) {
286  uint32_t h = RollingBloomHash(n, nTweak, vKey);
287  int bit = h & 0x3F;
288  /* FastMod works with the upper bits of h, so it is safe to ignore that
289  * the lower bits of h are already used for bit. */
290  uint32_t pos = FastMod(h, data.size());
291  /* The lowest bit of pos is ignored, and set to zero for the first bit,
292  * and to one for the second. */
293  data[pos & ~1] = (data[pos & ~1] & ~(uint64_t(1) << bit)) |
294  uint64_t(nGeneration & 1) << bit;
295  data[pos | 1] = (data[pos | 1] & ~(uint64_t(1) << bit)) |
296  uint64_t(nGeneration >> 1) << bit;
297  }
298 }
299 
301  std::vector<uint8_t> vData(hash.begin(), hash.end());
302  insert(vData);
303 }
304 
305 bool CRollingBloomFilter::contains(const std::vector<uint8_t> &vKey) const {
306  for (int n = 0; n < nHashFuncs; n++) {
307  uint32_t h = RollingBloomHash(n, nTweak, vKey);
308  int bit = h & 0x3F;
309  uint32_t pos = FastMod(h, data.size());
310  /* If the relevant bit is not set in either data[pos & ~1] or data[pos |
311  * 1], the filter does not contain vKey */
312  if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) {
313  return false;
314  }
315  }
316  return true;
317 }
318 
319 bool CRollingBloomFilter::contains(const uint256 &hash) const {
320  std::vector<uint8_t> vData(hash.begin(), hash.end());
321  return contains(vData);
322 }
323 
325  nTweak = GetRand(std::numeric_limits<unsigned int>::max());
326  nEntriesThisGeneration = 0;
327  nGeneration = 1;
328  std::fill(data.begin(), data.end(), 0);
329 }
txnouttype Solver(const CScript &scriptPubKey, std::vector< std::vector< uint8_t >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
Definition: standard.cpp:102
uint64_t GetRand(uint64_t nMax) noexcept
Definition: random.cpp:641
uint32_t nHashFuncs
Definition: bloom.h:50
CScript scriptPubKey
Definition: transaction.h:144
uint32_t MurmurHash3(uint32_t nHashSeed, const std::vector< uint8_t > &vDataToHash)
Definition: hash.cpp:13
static uint32_t RollingBloomHash(uint32_t nHashNum, uint32_t nTweak, const std::vector< uint8_t > &vDataToHash)
Definition: bloom.cpp:253
bool isFull
Definition: bloom.h:48
bool contains(const std::vector< uint8_t > &vKey) const
Definition: bloom.cpp:79
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:196
void insert(const std::vector< uint8_t > &vKey)
Definition: bloom.cpp:54
#define LN2
Definition: bloom.cpp:20
std::vector< uint8_t > vData
Definition: bloom.h:47
const std::vector< CTxIn > vin
Definition: transaction.h:227
void reset(const uint32_t nNewTweak)
Definition: bloom.cpp:114
static const uint32_t MAX_HASH_FUNCS
Definition: bloom.h:19
uint32_t Hash(uint32_t nHashNum, const std::vector< uint8_t > &vDataToHash) const
Definition: bloom.cpp:46
uint8_t nFlags
Definition: bloom.h:52
iterator end()
Definition: prevector.h:390
bool MatchAndInsertOutputs(const CTransaction &tx)
Scans output scripts for matches and adds those outpoints to the filter for spend detection...
Definition: bloom.cpp:124
opcodetype
Script opcodes.
Definition: script.h:46
An input of a transaction.
Definition: transaction.h:67
uint32_t nTweak
Definition: bloom.h:51
void clear()
Definition: bloom.cpp:108
CBloomFilter()
Definition: bloom.h:71
uint8_t * end()
Definition: uint256.h:78
const std::vector< CTxOut > vout
Definition: transaction.h:228
An output of a transaction.
Definition: transaction.h:141
uint8_t * begin()
Definition: uint256.h:76
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:22
#define LN2SQUARED
Definition: bloom.cpp:19
CScript scriptSig
Definition: transaction.h:70
void insert(const std::vector< uint8_t > &vKey)
Definition: bloom.cpp:266
txnouttype
Definition: standard.h:41
256-bit opaque blob.
Definition: uint256.h:120
const_iterator end() const
Definition: streams.h:277
const_iterator begin() const
Definition: streams.h:275
A TxId is the identifier of a transaction.
Definition: txid.h:14
static const int PROTOCOL_VERSION
network protocol versioning
Definition: version.h:11
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< uint8_t > &vchRet) const
Definition: script.h:524
iterator begin()
Definition: prevector.h:388
void UpdateEmptyFull()
Checks for empty and full filters to avoid wasting cpu.
Definition: bloom.cpp:204
static const uint32_t MAX_BLOOM_FILTER_SIZE
20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
Definition: bloom.h:18
static uint32_t FastMod(uint32_t x, size_t n)
Definition: bloom.cpp:262
The basic transaction that is broadcasted on the network and contained in blocks. ...
Definition: transaction.h:211
bool contains(const std::vector< uint8_t > &vKey) const
Definition: bloom.cpp:305
bool MatchInputs(const CTransaction &tx)
Scan inputs to see if the spent outpoints are a match, or the input scripts contain matching elements...
Definition: bloom.cpp:175
COutPoint prevout
Definition: transaction.h:69
bool isEmpty
Definition: bloom.h:49
CRollingBloomFilter(const uint32_t nElements, const double nFPRate)
Definition: bloom.cpp:215
bool IsWithinSizeConstraints() const
True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (c...
Definition: bloom.cpp:119
const TxId GetId() const
Definition: transaction.h:261