Bitcoin Core  0.20.99
P2P Digital Currency
bloom.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-2019 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 
8 #include <hash.h>
9 #include <script/script.h>
10 #include <script/standard.h>
11 #include <random.h>
12 #include <streams.h>
13 
14 #include <math.h>
15 #include <stdlib.h>
16 
17 #include <algorithm>
18 
19 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455
20 #define LN2 0.6931471805599453094172321214581765680755001343602552
21 
22 CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweakIn, unsigned char nFlagsIn) :
28  vData(std::min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
34  nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
35  nTweak(nTweakIn),
36  nFlags(nFlagsIn)
37 {
38 }
39 
40 inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const
41 {
42  // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
43  return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
44 }
45 
46 void CBloomFilter::insert(const std::vector<unsigned char>& vKey)
47 {
48  if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
49  return;
50  for (unsigned int i = 0; i < nHashFuncs; i++)
51  {
52  unsigned int nIndex = Hash(i, vKey);
53  // Sets bit nIndex of vData
54  vData[nIndex >> 3] |= (1 << (7 & nIndex));
55  }
56 }
57 
58 void CBloomFilter::insert(const COutPoint& outpoint)
59 {
61  stream << outpoint;
62  std::vector<unsigned char> data(stream.begin(), stream.end());
63  insert(data);
64 }
65 
66 void CBloomFilter::insert(const uint256& hash)
67 {
68  std::vector<unsigned char> data(hash.begin(), hash.end());
69  insert(data);
70 }
71 
72 bool CBloomFilter::contains(const std::vector<unsigned char>& vKey) const
73 {
74  if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
75  return true;
76  for (unsigned int i = 0; i < nHashFuncs; i++)
77  {
78  unsigned int nIndex = Hash(i, vKey);
79  // Checks bit nIndex of vData
80  if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
81  return false;
82  }
83  return true;
84 }
85 
86 bool CBloomFilter::contains(const COutPoint& outpoint) const
87 {
89  stream << outpoint;
90  std::vector<unsigned char> data(stream.begin(), stream.end());
91  return contains(data);
92 }
93 
94 bool CBloomFilter::contains(const uint256& hash) const
95 {
96  std::vector<unsigned char> data(hash.begin(), hash.end());
97  return contains(data);
98 }
99 
101 {
102  return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
103 }
104 
106 {
107  bool fFound = false;
108  // Match if the filter contains the hash of tx
109  // for finding tx when they appear in a block
110  if (vData.empty()) // zero-size = "match-all" filter
111  return true;
112  const uint256& hash = tx.GetHash();
113  if (contains(hash))
114  fFound = true;
115 
116  for (unsigned int i = 0; i < tx.vout.size(); i++)
117  {
118  const CTxOut& txout = tx.vout[i];
119  // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx
120  // If this matches, also add the specific output that was matched.
121  // This means clients don't have to update the filter themselves when a new relevant tx
122  // is discovered in order to find spending transactions, which avoids round-tripping and race conditions.
124  std::vector<unsigned char> data;
125  while (pc < txout.scriptPubKey.end())
126  {
127  opcodetype opcode;
128  if (!txout.scriptPubKey.GetOp(pc, opcode, data))
129  break;
130  if (data.size() != 0 && contains(data))
131  {
132  fFound = true;
134  insert(COutPoint(hash, i));
135  else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY)
136  {
137  std::vector<std::vector<unsigned char> > vSolutions;
138  TxoutType type = Solver(txout.scriptPubKey, vSolutions);
139  if (type == TxoutType::PUBKEY || type == TxoutType::MULTISIG) {
140  insert(COutPoint(hash, i));
141  }
142  }
143  break;
144  }
145  }
146  }
147 
148  if (fFound)
149  return true;
150 
151  for (const CTxIn& txin : tx.vin)
152  {
153  // Match if the filter contains an outpoint tx spends
154  if (contains(txin.prevout))
155  return true;
156 
157  // Match if the filter contains any arbitrary script data element in any scriptSig in tx
159  std::vector<unsigned char> data;
160  while (pc < txin.scriptSig.end())
161  {
162  opcodetype opcode;
163  if (!txin.scriptSig.GetOp(pc, opcode, data))
164  break;
165  if (data.size() != 0 && contains(data))
166  return true;
167  }
168  }
169 
170  return false;
171 }
172 
173 CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const double fpRate)
174 {
175  double logFpRate = log(fpRate);
176  /* The optimal number of hash functions is log(fpRate) / log(0.5), but
177  * restrict it to the range 1-50. */
178  nHashFuncs = std::max(1, std::min((int)round(logFpRate / log(0.5)), 50));
179  /* In this rolling bloom filter, we'll store between 2 and 3 generations of nElements / 2 entries. */
180  nEntriesPerGeneration = (nElements + 1) / 2;
181  uint32_t nMaxElements = nEntriesPerGeneration * 3;
182  /* The maximum fpRate = pow(1.0 - exp(-nHashFuncs * nMaxElements / nFilterBits), nHashFuncs)
183  * => pow(fpRate, 1.0 / nHashFuncs) = 1.0 - exp(-nHashFuncs * nMaxElements / nFilterBits)
184  * => 1.0 - pow(fpRate, 1.0 / nHashFuncs) = exp(-nHashFuncs * nMaxElements / nFilterBits)
185  * => log(1.0 - pow(fpRate, 1.0 / nHashFuncs)) = -nHashFuncs * nMaxElements / nFilterBits
186  * => nFilterBits = -nHashFuncs * nMaxElements / log(1.0 - pow(fpRate, 1.0 / nHashFuncs))
187  * => nFilterBits = -nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs))
188  */
189  uint32_t nFilterBits = (uint32_t)ceil(-1.0 * nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs)));
190  data.clear();
191  /* For each data element we need to store 2 bits. If both bits are 0, the
192  * bit is treated as unset. If the bits are (01), (10), or (11), the bit is
193  * treated as set in generation 1, 2, or 3 respectively.
194  * These bits are stored in separate integers: position P corresponds to bit
195  * (P & 63) of the integers data[(P >> 6) * 2] and data[(P >> 6) * 2 + 1]. */
196  data.resize(((nFilterBits + 63) / 64) << 1);
197  reset();
198 }
199 
200 /* Similar to CBloomFilter::Hash */
201 static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) {
202  return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
203 }
204 
205 
206 // A replacement for x % n. This assumes that x and n are 32bit integers, and x is a uniformly random distributed 32bit value
207 // which should be the case for a good hash.
208 // See https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
209 static inline uint32_t FastMod(uint32_t x, size_t n) {
210  return ((uint64_t)x * (uint64_t)n) >> 32;
211 }
212 
213 void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
214 {
215  if (nEntriesThisGeneration == nEntriesPerGeneration) {
216  nEntriesThisGeneration = 0;
217  nGeneration++;
218  if (nGeneration == 4) {
219  nGeneration = 1;
220  }
221  uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
222  uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
223  /* Wipe old entries that used this generation number. */
224  for (uint32_t p = 0; p < data.size(); p += 2) {
225  uint64_t p1 = data[p], p2 = data[p + 1];
226  uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
227  data[p] = p1 & mask;
228  data[p + 1] = p2 & mask;
229  }
230  }
231  nEntriesThisGeneration++;
232 
233  for (int n = 0; n < nHashFuncs; n++) {
234  uint32_t h = RollingBloomHash(n, nTweak, vKey);
235  int bit = h & 0x3F;
236  /* FastMod works with the upper bits of h, so it is safe to ignore that the lower bits of h are already used for bit. */
237  uint32_t pos = FastMod(h, data.size());
238  /* The lowest bit of pos is ignored, and set to zero for the first bit, and to one for the second. */
239  data[pos & ~1] = (data[pos & ~1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration & 1)) << bit;
240  data[pos | 1] = (data[pos | 1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration >> 1)) << bit;
241  }
242 }
243 
245 {
246  std::vector<unsigned char> vData(hash.begin(), hash.end());
247  insert(vData);
248 }
249 
250 bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
251 {
252  for (int n = 0; n < nHashFuncs; n++) {
253  uint32_t h = RollingBloomHash(n, nTweak, vKey);
254  int bit = h & 0x3F;
255  uint32_t pos = FastMod(h, data.size());
256  /* If the relevant bit is not set in either data[pos & ~1] or data[pos | 1], the filter does not contain vKey */
257  if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) {
258  return false;
259  }
260  }
261  return true;
262 }
263 
264 bool CRollingBloomFilter::contains(const uint256& hash) const
265 {
266  std::vector<unsigned char> vData(hash.begin(), hash.end());
267  return contains(vData);
268 }
269 
271 {
272  nTweak = GetRand(std::numeric_limits<unsigned int>::max());
273  nEntriesThisGeneration = 0;
274  nGeneration = 1;
275  std::fill(data.begin(), data.end(), 0);
276 }
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:586
CRollingBloomFilter(const unsigned int nElements, const double nFPRate)
Definition: bloom.cpp:173
CScript scriptPubKey
Definition: transaction.h:124
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet) const
Definition: script.h:472
unsigned int nTweak
Definition: bloom.h:49
void insert(const std::vector< unsigned char > &vKey)
Definition: bloom.cpp:213
unsigned char nFlags
Definition: bloom.h:50
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes) ...
Definition: bloom.cpp:105
static const unsigned int MAX_BLOOM_FILTER_SIZE
20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
Definition: bloom.h:17
std::vector< unsigned char > vData
Definition: bloom.h:47
unsigned int Hash(unsigned int nHashNum, const std::vector< unsigned char > &vDataToHash) const
Definition: bloom.cpp:40
unsigned int nHashFuncs
Definition: bloom.h:48
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:201
#define LN2
Definition: bloom.cpp:20
void insert(const std::vector< unsigned char > &vKey)
Definition: bloom.cpp:46
unsigned char * begin()
Definition: uint256.h:54
unsigned char * end()
Definition: uint256.h:59
const std::vector< CTxIn > vin
Definition: transaction.h:268
bool contains(const std::vector< unsigned char > &vKey) const
Definition: bloom.cpp:250
iterator end()
Definition: prevector.h:292
unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector< unsigned char > &vDataToHash)
Definition: hash.cpp:15
opcodetype
Script opcodes.
Definition: script.h:54
An input of a transaction.
Definition: transaction.h:57
const uint256 & GetHash() const
Definition: transaction.h:303
TxoutType
Definition: standard.h:119
static uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector< unsigned char > &vDataToHash)
Definition: bloom.cpp:201
CBloomFilter()
Definition: bloom.h:65
const std::vector< CTxOut > vout
Definition: transaction.h:269
An output of a transaction.
Definition: transaction.h:120
static const unsigned int MAX_HASH_FUNCS
Definition: bloom.h:18
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:18
#define LN2SQUARED
Definition: bloom.cpp:19
CScript scriptSig
Definition: transaction.h:61
256-bit opaque blob.
Definition: uint256.h:120
const_iterator end() const
Definition: streams.h:290
const_iterator begin() const
Definition: streams.h:288
static const int PROTOCOL_VERSION
network protocol versioning
Definition: version.h:12
TxoutType Solver(const CScript &scriptPubKey, std::vector< std::vector< unsigned char >> &vSolutionsRet)
Parse a scriptPubKey and identify script type for standard scripts.
Definition: standard.cpp:109
iterator begin()
Definition: prevector.h:290
static uint32_t FastMod(uint32_t x, size_t n)
Definition: bloom.cpp:209
The basic transaction that is broadcasted on the network and contained in blocks. ...
Definition: transaction.h:251
COutPoint prevout
Definition: transaction.h:60
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:100
bool contains(const std::vector< unsigned char > &vKey) const
Definition: bloom.cpp:72