Branch data Line data Source code
# 1 : : // Copyright (c) 2012-2020 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 <primitives/transaction.h>
# 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) :
# 23 : : /**
# 24 : : * The ideal size for a bloom filter with a given number of elements and false positive rate is:
# 25 : : * - nElements * log(fp rate) / ln(2)^2
# 26 : : * We ignore filter parameters which will create a bloom filter larger than the protocol limits
# 27 : : */
# 28 : : vData(std::min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
# 29 : : /**
# 30 : : * The ideal number of hash functions is filter size * ln(2) / number of elements
# 31 : : * Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
# 32 : : * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
# 33 : : */
# 34 : : nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
# 35 : : nTweak(nTweakIn),
# 36 : : nFlags(nFlagsIn)
# 37 : 44 : {
# 38 : 44 : }
# 39 : :
# 40 : : inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const
# 41 : 3627 : {
# 42 : : // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
# 43 : 3627 : return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
# 44 : 3627 : }
# 45 : :
# 46 : : void CBloomFilter::insert(const std::vector<unsigned char>& vKey)
# 47 : 85 : {
# 48 [ + + ]: 85 : if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
# 49 : 2 : return;
# 50 [ + + ]: 1479 : for (unsigned int i = 0; i < nHashFuncs; i++)
# 51 : 1396 : {
# 52 : 1396 : unsigned int nIndex = Hash(i, vKey);
# 53 : : // Sets bit nIndex of vData
# 54 : 1396 : vData[nIndex >> 3] |= (1 << (7 & nIndex));
# 55 : 1396 : }
# 56 : 83 : }
# 57 : :
# 58 : : void CBloomFilter::insert(const COutPoint& outpoint)
# 59 : 22 : {
# 60 : 22 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
# 61 : 22 : stream << outpoint;
# 62 : 22 : std::vector<unsigned char> data(stream.begin(), stream.end());
# 63 : 22 : insert(data);
# 64 : 22 : }
# 65 : :
# 66 : : void CBloomFilter::insert(const uint256& hash)
# 67 : 18 : {
# 68 : 18 : std::vector<unsigned char> data(hash.begin(), hash.end());
# 69 : 18 : insert(data);
# 70 : 18 : }
# 71 : :
# 72 : : bool CBloomFilter::contains(const std::vector<unsigned char>& vKey) const
# 73 : 904 : {
# 74 [ - + ]: 904 : if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
# 75 : 0 : return true;
# 76 [ + + ]: 2311 : for (unsigned int i = 0; i < nHashFuncs; i++)
# 77 : 2231 : {
# 78 : 2231 : unsigned int nIndex = Hash(i, vKey);
# 79 : : // Checks bit nIndex of vData
# 80 [ + + ]: 2231 : if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
# 81 : 824 : return false;
# 82 : 2231 : }
# 83 : 904 : return true;
# 84 : 904 : }
# 85 : :
# 86 : : bool CBloomFilter::contains(const COutPoint& outpoint) const
# 87 : 183 : {
# 88 : 183 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
# 89 : 183 : stream << outpoint;
# 90 : 183 : std::vector<unsigned char> data(stream.begin(), stream.end());
# 91 : 183 : return contains(data);
# 92 : 183 : }
# 93 : :
# 94 : : bool CBloomFilter::contains(const uint256& hash) const
# 95 : 163 : {
# 96 : 163 : std::vector<unsigned char> data(hash.begin(), hash.end());
# 97 : 163 : return contains(data);
# 98 : 163 : }
# 99 : :
# 100 : : bool CBloomFilter::IsWithinSizeConstraints() const
# 101 : 9 : {
# 102 [ + + ][ + + ]: 9 : return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
# 103 : 9 : }
# 104 : :
# 105 : : bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
# 106 : 163 : {
# 107 : 163 : bool fFound = false;
# 108 : : // Match if the filter contains the hash of tx
# 109 : : // for finding tx when they appear in a block
# 110 [ - + ]: 163 : if (vData.empty()) // zero-size = "match-all" filter
# 111 : 0 : return true;
# 112 : 163 : const uint256& hash = tx.GetHash();
# 113 [ + + ]: 163 : if (contains(hash))
# 114 : 26 : fFound = true;
# 115 : :
# 116 [ + + ]: 431 : for (unsigned int i = 0; i < tx.vout.size(); i++)
# 117 : 268 : {
# 118 : 268 : 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.
# 123 : 268 : CScript::const_iterator pc = txout.scriptPubKey.begin();
# 124 : 268 : std::vector<unsigned char> data;
# 125 [ + + ]: 1269 : while (pc < txout.scriptPubKey.end())
# 126 : 1027 : {
# 127 : 1027 : opcodetype opcode;
# 128 [ - + ]: 1027 : if (!txout.scriptPubKey.GetOp(pc, opcode, data))
# 129 : 0 : break;
# 130 [ + + ][ + + ]: 1027 : if (data.size() != 0 && contains(data))
# 131 : 26 : {
# 132 : 26 : fFound = true;
# 133 [ + + ]: 26 : if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL)
# 134 : 14 : insert(COutPoint(hash, i));
# 135 [ + + ]: 12 : else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY)
# 136 : 4 : {
# 137 : 4 : std::vector<std::vector<unsigned char> > vSolutions;
# 138 : 4 : TxoutType type = Solver(txout.scriptPubKey, vSolutions);
# 139 [ + + ][ - + ]: 4 : if (type == TxoutType::PUBKEY || type == TxoutType::MULTISIG) {
# 140 : 2 : insert(COutPoint(hash, i));
# 141 : 2 : }
# 142 : 4 : }
# 143 : 26 : break;
# 144 : 26 : }
# 145 : 1027 : }
# 146 : 268 : }
# 147 : :
# 148 [ + + ]: 163 : if (fFound)
# 149 : 52 : return true;
# 150 : :
# 151 [ + + ]: 111 : for (const CTxIn& txin : tx.vin)
# 152 : 175 : {
# 153 : : // Match if the filter contains an outpoint tx spends
# 154 [ + + ]: 175 : if (contains(txin.prevout))
# 155 : 8 : return true;
# 156 : :
# 157 : : // Match if the filter contains any arbitrary script data element in any scriptSig in tx
# 158 : 167 : CScript::const_iterator pc = txin.scriptSig.begin();
# 159 : 167 : std::vector<unsigned char> data;
# 160 [ + + ]: 433 : while (pc < txin.scriptSig.end())
# 161 : 270 : {
# 162 : 270 : opcodetype opcode;
# 163 [ - + ]: 270 : if (!txin.scriptSig.GetOp(pc, opcode, data))
# 164 : 0 : break;
# 165 [ + - ][ + + ]: 270 : if (data.size() != 0 && contains(data))
# 166 : 4 : return true;
# 167 : 270 : }
# 168 : 167 : }
# 169 : :
# 170 : 111 : return false;
# 171 : 111 : }
# 172 : :
# 173 : : CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const double fpRate)
# 174 : 5386 : {
# 175 : 5386 : 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 : 5386 : 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 : 5386 : nEntriesPerGeneration = (nElements + 1) / 2;
# 181 : 5386 : 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 : 5386 : uint32_t nFilterBits = (uint32_t)ceil(-1.0 * nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs)));
# 190 : 5386 : 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 : 5386 : data.resize(((nFilterBits + 63) / 64) << 1);
# 197 : 5386 : reset();
# 198 : 5386 : }
# 199 : :
# 200 : : /* Similar to CBloomFilter::Hash */
# 201 : 5765937 : static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, const std::vector<unsigned char>& vDataToHash) {
# 202 : 5765937 : return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
# 203 : 5765937 : }
# 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 : 5765932 : static inline uint32_t FastMod(uint32_t x, size_t n) {
# 210 : 5765932 : return ((uint64_t)x * (uint64_t)n) >> 32;
# 211 : 5765932 : }
# 212 : :
# 213 : : void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
# 214 : 257017 : {
# 215 [ + + ]: 257017 : if (nEntriesThisGeneration == nEntriesPerGeneration) {
# 216 : 74 : nEntriesThisGeneration = 0;
# 217 : 74 : nGeneration++;
# 218 [ + + ]: 74 : if (nGeneration == 4) {
# 219 : 22 : nGeneration = 1;
# 220 : 22 : }
# 221 : 74 : uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
# 222 : 74 : uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
# 223 : : /* Wipe old entries that used this generation number. */
# 224 [ + + ]: 15792 : for (uint32_t p = 0; p < data.size(); p += 2) {
# 225 : 15718 : uint64_t p1 = data[p], p2 = data[p + 1];
# 226 : 15718 : uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
# 227 : 15718 : data[p] = p1 & mask;
# 228 : 15718 : data[p + 1] = p2 & mask;
# 229 : 15718 : }
# 230 : 74 : }
# 231 : 257017 : nEntriesThisGeneration++;
# 232 : :
# 233 [ + + ]: 5280193 : for (int n = 0; n < nHashFuncs; n++) {
# 234 : 5023176 : uint32_t h = RollingBloomHash(n, nTweak, vKey);
# 235 : 5023176 : 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 : 5023176 : 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 : 5023176 : data[pos & ~1] = (data[pos & ~1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration & 1)) << bit;
# 240 : 5023176 : data[pos | 1] = (data[pos | 1] & ~(((uint64_t)1) << bit)) | ((uint64_t)(nGeneration >> 1)) << bit;
# 241 : 5023176 : }
# 242 : 257017 : }
# 243 : :
# 244 : : void CRollingBloomFilter::insert(const uint256& hash)
# 245 : 246373 : {
# 246 : 246373 : std::vector<unsigned char> vData(hash.begin(), hash.end());
# 247 : 246373 : insert(vData);
# 248 : 246373 : }
# 249 : :
# 250 : : bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
# 251 : 230177 : {
# 252 [ + + ]: 771613 : for (int n = 0; n < nHashFuncs; n++) {
# 253 : 742769 : uint32_t h = RollingBloomHash(n, nTweak, vKey);
# 254 : 742769 : int bit = h & 0x3F;
# 255 : 742769 : 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 [ + + ]: 742769 : if (!(((data[pos & ~1] | data[pos | 1]) >> bit) & 1)) {
# 258 : 201333 : return false;
# 259 : 201333 : }
# 260 : 742769 : }
# 261 : 230177 : return true;
# 262 : 230177 : }
# 263 : :
# 264 : : bool CRollingBloomFilter::contains(const uint256& hash) const
# 265 : 171883 : {
# 266 : 171883 : std::vector<unsigned char> vData(hash.begin(), hash.end());
# 267 : 171883 : return contains(vData);
# 268 : 171883 : }
# 269 : :
# 270 : : void CRollingBloomFilter::reset()
# 271 : 10322 : {
# 272 : 10322 : nTweak = GetRand(std::numeric_limits<unsigned int>::max());
# 273 : 10322 : nEntriesThisGeneration = 0;
# 274 : 10322 : nGeneration = 1;
# 275 : 10322 : std::fill(data.begin(), data.end(), 0);
# 276 : 10322 : }
|
