Bitcoin Core  22.99.0
P2P Digital Currency
bloom.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-2021 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 <common/bloom.h>
6 
7 #include <hash.h>
9 #include <random.h>
10 #include <script/script.h>
11 #include <script/standard.h>
12 #include <span.h>
13 #include <streams.h>
14 #include <util/fastrange.h>
15 
16 #include <algorithm>
17 #include <cmath>
18 #include <cstdlib>
19 #include <limits>
20 #include <vector>
21 
22 static constexpr double LN2SQUARED = 0.4804530139182014246671025263266649717305529515945455;
23 static constexpr double LN2 = 0.6931471805599453094172321214581765680755001343602552;
24 
25 CBloomFilter::CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweakIn, unsigned char nFlagsIn) :
31  vData(std::min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
37  nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
38  nTweak(nTweakIn),
39  nFlags(nFlagsIn)
40 {
41 }
42 
43 inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const
44 {
45  // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
46  return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
47 }
48 
50 {
51  if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
52  return;
53  for (unsigned int i = 0; i < nHashFuncs; i++)
54  {
55  unsigned int nIndex = Hash(i, vKey);
56  // Sets bit nIndex of vData
57  vData[nIndex >> 3] |= (1 << (7 & nIndex));
58  }
59 }
60 
61 void CBloomFilter::insert(const COutPoint& outpoint)
62 {
64  stream << outpoint;
65  insert(MakeUCharSpan(stream));
66 }
67 
69 {
70  if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
71  return true;
72  for (unsigned int i = 0; i < nHashFuncs; i++)
73  {
74  unsigned int nIndex = Hash(i, vKey);
75  // Checks bit nIndex of vData
76  if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
77  return false;
78  }
79  return true;
80 }
81 
82 bool CBloomFilter::contains(const COutPoint& outpoint) const
83 {
85  stream << outpoint;
86  return contains(MakeUCharSpan(stream));
87 }
88 
90 {
92 }
93 
95 {
96  bool fFound = false;
97  // Match if the filter contains the hash of tx
98  // for finding tx when they appear in a block
99  if (vData.empty()) // zero-size = "match-all" filter
100  return true;
101  const uint256& hash = tx.GetHash();
102  if (contains(hash))
103  fFound = true;
104 
105  for (unsigned int i = 0; i < tx.vout.size(); i++)
106  {
107  const CTxOut& txout = tx.vout[i];
108  // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx
109  // If this matches, also add the specific output that was matched.
110  // This means clients don't have to update the filter themselves when a new relevant tx
111  // is discovered in order to find spending transactions, which avoids round-tripping and race conditions.
113  std::vector<unsigned char> data;
114  while (pc < txout.scriptPubKey.end())
115  {
116  opcodetype opcode;
117  if (!txout.scriptPubKey.GetOp(pc, opcode, data))
118  break;
119  if (data.size() != 0 && contains(data))
120  {
121  fFound = true;
123  insert(COutPoint(hash, i));
125  {
126  std::vector<std::vector<unsigned char> > vSolutions;
127  TxoutType type = Solver(txout.scriptPubKey, vSolutions);
128  if (type == TxoutType::PUBKEY || type == TxoutType::MULTISIG) {
129  insert(COutPoint(hash, i));
130  }
131  }
132  break;
133  }
134  }
135  }
136 
137  if (fFound)
138  return true;
139 
140  for (const CTxIn& txin : tx.vin)
141  {
142  // Match if the filter contains an outpoint tx spends
143  if (contains(txin.prevout))
144  return true;
145 
146  // Match if the filter contains any arbitrary script data element in any scriptSig in tx
148  std::vector<unsigned char> data;
149  while (pc < txin.scriptSig.end())
150  {
151  opcodetype opcode;
152  if (!txin.scriptSig.GetOp(pc, opcode, data))
153  break;
154  if (data.size() != 0 && contains(data))
155  return true;
156  }
157  }
158 
159  return false;
160 }
161 
162 CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const double fpRate)
163 {
164  double logFpRate = log(fpRate);
165  /* The optimal number of hash functions is log(fpRate) / log(0.5), but
166  * restrict it to the range 1-50. */
167  nHashFuncs = std::max(1, std::min((int)round(logFpRate / log(0.5)), 50));
168  /* In this rolling bloom filter, we'll store between 2 and 3 generations of nElements / 2 entries. */
169  nEntriesPerGeneration = (nElements + 1) / 2;
170  uint32_t nMaxElements = nEntriesPerGeneration * 3;
171  /* The maximum fpRate = pow(1.0 - exp(-nHashFuncs * nMaxElements / nFilterBits), nHashFuncs)
172  * => pow(fpRate, 1.0 / nHashFuncs) = 1.0 - exp(-nHashFuncs * nMaxElements / nFilterBits)
173  * => 1.0 - pow(fpRate, 1.0 / nHashFuncs) = exp(-nHashFuncs * nMaxElements / nFilterBits)
174  * => log(1.0 - pow(fpRate, 1.0 / nHashFuncs)) = -nHashFuncs * nMaxElements / nFilterBits
175  * => nFilterBits = -nHashFuncs * nMaxElements / log(1.0 - pow(fpRate, 1.0 / nHashFuncs))
176  * => nFilterBits = -nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs))
177  */
178  uint32_t nFilterBits = (uint32_t)ceil(-1.0 * nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs)));
179  data.clear();
180  /* For each data element we need to store 2 bits. If both bits are 0, the
181  * bit is treated as unset. If the bits are (01), (10), or (11), the bit is
182  * treated as set in generation 1, 2, or 3 respectively.
183  * These bits are stored in separate integers: position P corresponds to bit
184  * (P & 63) of the integers data[(P >> 6) * 2] and data[(P >> 6) * 2 + 1]. */
185  data.resize(((nFilterBits + 63) / 64) << 1);
186  reset();
187 }
188 
189 /* Similar to CBloomFilter::Hash */
190 static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, Span<const unsigned char> vDataToHash)
191 {
192  return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
193 }
194 
196 {
199  nGeneration++;
200  if (nGeneration == 4) {
201  nGeneration = 1;
202  }
203  uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
204  uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
205  /* Wipe old entries that used this generation number. */
206  for (uint32_t p = 0; p < data.size(); p += 2) {
207  uint64_t p1 = data[p], p2 = data[p + 1];
208  uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
209  data[p] = p1 & mask;
210  data[p + 1] = p2 & mask;
211  }
212  }
214 
215  for (int n = 0; n < nHashFuncs; n++) {
216  uint32_t h = RollingBloomHash(n, nTweak, vKey);
217  int bit = h & 0x3F;
218  /* 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. */
219  uint32_t pos = FastRange32(h, data.size());
220  /* The lowest bit of pos is ignored, and set to zero for the first bit, and to one for the second. */
221  data[pos & ~1U] = (data[pos & ~1U] & ~(uint64_t{1} << bit)) | (uint64_t(nGeneration & 1)) << bit;
222  data[pos | 1] = (data[pos | 1] & ~(uint64_t{1} << bit)) | (uint64_t(nGeneration >> 1)) << bit;
223  }
224 }
225 
227 {
228  for (int n = 0; n < nHashFuncs; n++) {
229  uint32_t h = RollingBloomHash(n, nTweak, vKey);
230  int bit = h & 0x3F;
231  uint32_t pos = FastRange32(h, data.size());
232  /* If the relevant bit is not set in either data[pos & ~1] or data[pos | 1], the filter does not contain vKey */
233  if (!(((data[pos & ~1U] | data[pos | 1]) >> bit) & 1)) {
234  return false;
235  }
236  }
237  return true;
238 }
239 
241 {
242  nTweak = GetRand(std::numeric_limits<unsigned int>::max());
244  nGeneration = 1;
245  std::fill(data.begin(), data.end(), 0);
246 }
CTxIn
An input of a transaction.
Definition: transaction.h:65
CTransaction::vin
const std::vector< CTxIn > vin
Definition: transaction.h:290
CRollingBloomFilter::insert
void insert(Span< const unsigned char > vKey)
Definition: bloom.cpp:195
MakeUCharSpan
constexpr auto MakeUCharSpan(V &&v) -> decltype(UCharSpanCast(Span
Like the Span constructor, but for (const) unsigned char member types only.
Definition: span.h:285
CRollingBloomFilter::nGeneration
int nGeneration
Definition: bloom.h:121
Solver
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:144
prevector::const_iterator
Definition: prevector.h:98
LN2SQUARED
static constexpr double LN2SQUARED
Definition: bloom.cpp:22
CBloomFilter::contains
bool contains(Span< const unsigned char > vKey) const
Definition: bloom.cpp:68
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:89
TxoutType
TxoutType
Definition: standard.h:59
streams.h
CBloomFilter::nTweak
unsigned int nTweak
Definition: bloom.h:49
RollingBloomHash
static uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, Span< const unsigned char > vDataToHash)
Definition: bloom.cpp:190
CRollingBloomFilter::CRollingBloomFilter
CRollingBloomFilter(const unsigned int nElements, const double nFPRate)
Definition: bloom.cpp:162
transaction.h
CRollingBloomFilter::nTweak
unsigned int nTweak
Definition: bloom.h:123
BLOOM_UPDATE_P2PUBKEY_ONLY
@ BLOOM_UPDATE_P2PUBKEY_ONLY
Definition: bloom.h:29
opcodetype
opcodetype
Script opcodes.
Definition: script.h:66
MAX_HASH_FUNCS
static constexpr unsigned int MAX_HASH_FUNCS
Definition: bloom.h:18
CBloomFilter::vData
std::vector< unsigned char > vData
Definition: bloom.h:47
GetRand
uint64_t GetRand(uint64_t nMax) noexcept
Generate a uniform random integer in the range [0..range).
Definition: random.cpp:588
CTransaction
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:279
bloom.h
Span< const unsigned char >
prevector::end
iterator end()
Definition: prevector.h:292
random.h
TxoutType::PUBKEY
@ PUBKEY
LN2
static constexpr double LN2
Definition: bloom.cpp:23
CTxOut
An output of a transaction.
Definition: transaction.h:148
CTransaction::vout
const std::vector< CTxOut > vout
Definition: transaction.h:291
CTxOut::scriptPubKey
CScript scriptPubKey
Definition: transaction.h:152
span.h
CRollingBloomFilter::reset
void reset()
Definition: bloom.cpp:240
standard.h
CBloomFilter::CBloomFilter
CBloomFilter()
Definition: bloom.h:65
uint256
256-bit opaque blob.
Definition: uint256.h:126
script.h
BLOOM_UPDATE_MASK
@ BLOOM_UPDATE_MASK
Definition: bloom.h:30
CRollingBloomFilter::nHashFuncs
int nHashFuncs
Definition: bloom.h:124
CRollingBloomFilter::nEntriesThisGeneration
int nEntriesThisGeneration
Definition: bloom.h:120
CRollingBloomFilter::data
std::vector< uint64_t > data
Definition: bloom.h:122
CBloomFilter::insert
void insert(Span< const unsigned char > vKey)
Definition: bloom.cpp:49
CBloomFilter::nFlags
unsigned char nFlags
Definition: bloom.h:50
MurmurHash3
unsigned int MurmurHash3(unsigned int nHashSeed, Span< const unsigned char > vDataToHash)
Definition: hash.cpp:17
BLOOM_UPDATE_ALL
@ BLOOM_UPDATE_ALL
Definition: bloom.h:27
std
Definition: setup_common.h:33
fastrange.h
FastRange32
static uint32_t FastRange32(uint32_t x, uint32_t n)
Fast range reduction with 32-bit input and 32-bit range.
Definition: fastrange.h:19
CTxIn::prevout
COutPoint prevout
Definition: transaction.h:68
CTxIn::scriptSig
CScript scriptSig
Definition: transaction.h:69
prevector::begin
iterator begin()
Definition: prevector.h:290
TxoutType::MULTISIG
@ MULTISIG
CBloomFilter::nHashFuncs
unsigned int nHashFuncs
Definition: bloom.h:48
CDataStream
Double ended buffer combining vector and stream-like interfaces.
Definition: streams.h:184
SER_NETWORK
@ SER_NETWORK
Definition: serialize.h:131
CTransaction::GetHash
const uint256 & GetHash() const
Definition: transaction.h:322
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:26
CBloomFilter::IsRelevantAndUpdate
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes)
Definition: bloom.cpp:94
CRollingBloomFilter::nEntriesPerGeneration
int nEntriesPerGeneration
Definition: bloom.h:119
CRollingBloomFilter::contains
bool contains(Span< const unsigned char > vKey) const
Definition: bloom.cpp:226
PROTOCOL_VERSION
static const int PROTOCOL_VERSION
network protocol versioning
Definition: version.h:12
CScript::GetOp
bool GetOp(const_iterator &pc, opcodetype &opcodeRet, std::vector< unsigned char > &vchRet) const
Definition: script.h:487
CBloomFilter::Hash
unsigned int Hash(unsigned int nHashNum, Span< const unsigned char > vDataToHash) const
Definition: bloom.cpp:43
MAX_BLOOM_FILTER_SIZE
static constexpr 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