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