Branch data Line data Source code
# 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>
# 8 : : #include <primitives/transaction.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) :
# 26 : : /**
# 27 : : * The ideal size for a bloom filter with a given number of elements and false positive rate is:
# 28 : : * - nElements * log(fp rate) / ln(2)^2
# 29 : : * We ignore filter parameters which will create a bloom filter larger than the protocol limits
# 30 : : */
# 31 : : vData(std::min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
# 32 : : /**
# 33 : : * The ideal number of hash functions is filter size * ln(2) / number of elements
# 34 : : * Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
# 35 : : * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
# 36 : : */
# 37 : : nHashFuncs(std::min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
# 38 : : nTweak(nTweakIn),
# 39 : : nFlags(nFlagsIn)
# 40 : 44 : {
# 41 : 44 : }
# 42 : :
# 43 : : inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const
# 44 : 3570 : {
# 45 : : // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
# 46 : 3570 : return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
# 47 : 3570 : }
# 48 : :
# 49 : : void CBloomFilter::insert(Span<const unsigned char> vKey)
# 50 : 84 : {
# 51 [ + + ]: 84 : if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
# 52 : 2 : return;
# 53 [ + + ]: 1459 : for (unsigned int i = 0; i < nHashFuncs; i++)
# 54 : 1377 : {
# 55 : 1377 : unsigned int nIndex = Hash(i, vKey);
# 56 : : // Sets bit nIndex of vData
# 57 : 1377 : vData[nIndex >> 3] |= (1 << (7 & nIndex));
# 58 : 1377 : }
# 59 : 82 : }
# 60 : :
# 61 : : void CBloomFilter::insert(const COutPoint& outpoint)
# 62 : 21 : {
# 63 : 21 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
# 64 : 21 : stream << outpoint;
# 65 : 21 : insert(MakeUCharSpan(stream));
# 66 : 21 : }
# 67 : :
# 68 : : bool CBloomFilter::contains(Span<const unsigned char> vKey) const
# 69 : 887 : {
# 70 [ - + ]: 887 : if (vData.empty()) // Avoid divide-by-zero (CVE-2013-5700)
# 71 : 0 : return true;
# 72 [ + + ]: 2272 : for (unsigned int i = 0; i < nHashFuncs; i++)
# 73 : 2193 : {
# 74 : 2193 : unsigned int nIndex = Hash(i, vKey);
# 75 : : // Checks bit nIndex of vData
# 76 [ + + ]: 2193 : if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
# 77 : 808 : return false;
# 78 : 2193 : }
# 79 : 79 : return true;
# 80 : 887 : }
# 81 : :
# 82 : : bool CBloomFilter::contains(const COutPoint& outpoint) const
# 83 : 180 : {
# 84 : 180 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
# 85 : 180 : stream << outpoint;
# 86 : 180 : return contains(MakeUCharSpan(stream));
# 87 : 180 : }
# 88 : :
# 89 : : bool CBloomFilter::IsWithinSizeConstraints() const
# 90 : 9 : {
# 91 [ + + ][ + + ]: 9 : return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
# 92 : 9 : }
# 93 : :
# 94 : : bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
# 95 : 161 : {
# 96 : 161 : bool fFound = false;
# 97 : : // Match if the filter contains the hash of tx
# 98 : : // for finding tx when they appear in a block
# 99 [ - + ]: 161 : if (vData.empty()) // zero-size = "match-all" filter
# 100 : 0 : return true;
# 101 : 161 : const uint256& hash = tx.GetHash();
# 102 [ + + ]: 161 : if (contains(hash))
# 103 : 26 : fFound = true;
# 104 : :
# 105 [ + + ]: 425 : for (unsigned int i = 0; i < tx.vout.size(); i++)
# 106 : 264 : {
# 107 : 264 : 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.
# 112 : 264 : CScript::const_iterator pc = txout.scriptPubKey.begin();
# 113 : 264 : std::vector<unsigned char> data;
# 114 [ + + ]: 1255 : while (pc < txout.scriptPubKey.end())
# 115 : 1016 : {
# 116 : 1016 : opcodetype opcode;
# 117 [ - + ]: 1016 : if (!txout.scriptPubKey.GetOp(pc, opcode, data))
# 118 : 0 : break;
# 119 [ + + ][ + + ]: 1016 : if (data.size() != 0 && contains(data))
# 120 : 25 : {
# 121 : 25 : fFound = true;
# 122 [ + + ]: 25 : if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL)
# 123 : 13 : insert(COutPoint(hash, i));
# 124 [ + + ]: 12 : else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY)
# 125 : 4 : {
# 126 : 4 : std::vector<std::vector<unsigned char> > vSolutions;
# 127 : 4 : TxoutType type = Solver(txout.scriptPubKey, vSolutions);
# 128 [ + + ][ - + ]: 4 : if (type == TxoutType::PUBKEY || type == TxoutType::MULTISIG) {
# 129 : 2 : insert(COutPoint(hash, i));
# 130 : 2 : }
# 131 : 4 : }
# 132 : 25 : break;
# 133 : 25 : }
# 134 : 1016 : }
# 135 : 264 : }
# 136 : :
# 137 [ + + ]: 161 : if (fFound)
# 138 : 51 : return true;
# 139 : :
# 140 [ + + ]: 110 : for (const CTxIn& txin : tx.vin)
# 141 : 172 : {
# 142 : : // Match if the filter contains an outpoint tx spends
# 143 [ + + ]: 172 : if (contains(txin.prevout))
# 144 : 8 : return true;
# 145 : :
# 146 : : // Match if the filter contains any arbitrary script data element in any scriptSig in tx
# 147 : 164 : CScript::const_iterator pc = txin.scriptSig.begin();
# 148 : 164 : std::vector<unsigned char> data;
# 149 [ + + ]: 424 : while (pc < txin.scriptSig.end())
# 150 : 264 : {
# 151 : 264 : opcodetype opcode;
# 152 [ - + ]: 264 : if (!txin.scriptSig.GetOp(pc, opcode, data))
# 153 : 0 : break;
# 154 [ + + ][ + + ]: 264 : if (data.size() != 0 && contains(data))
# 155 : 4 : return true;
# 156 : 264 : }
# 157 : 164 : }
# 158 : :
# 159 : 98 : return false;
# 160 : 110 : }
# 161 : :
# 162 : : CRollingBloomFilter::CRollingBloomFilter(const unsigned int nElements, const double fpRate)
# 163 : 6225 : {
# 164 : 6225 : 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 : 6225 : 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 : 6225 : nEntriesPerGeneration = (nElements + 1) / 2;
# 170 : 6225 : 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 : 6225 : uint32_t nFilterBits = (uint32_t)ceil(-1.0 * nHashFuncs * nMaxElements / log(1.0 - exp(logFpRate / nHashFuncs)));
# 179 : 6225 : 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 : 6225 : data.resize(((nFilterBits + 63) / 64) << 1);
# 186 : 6225 : reset();
# 187 : 6225 : }
# 188 : :
# 189 : : /* Similar to CBloomFilter::Hash */
# 190 : : static inline uint32_t RollingBloomHash(unsigned int nHashNum, uint32_t nTweak, Span<const unsigned char> vDataToHash)
# 191 : 6001087 : {
# 192 : 6001087 : return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash);
# 193 : 6001087 : }
# 194 : :
# 195 : : void CRollingBloomFilter::insert(Span<const unsigned char> vKey)
# 196 : 268276 : {
# 197 [ + + ]: 268276 : if (nEntriesThisGeneration == nEntriesPerGeneration) {
# 198 : 74 : nEntriesThisGeneration = 0;
# 199 : 74 : nGeneration++;
# 200 [ + + ]: 74 : if (nGeneration == 4) {
# 201 : 22 : nGeneration = 1;
# 202 : 22 : }
# 203 : 74 : uint64_t nGenerationMask1 = 0 - (uint64_t)(nGeneration & 1);
# 204 : 74 : uint64_t nGenerationMask2 = 0 - (uint64_t)(nGeneration >> 1);
# 205 : : /* Wipe old entries that used this generation number. */
# 206 [ + + ]: 15792 : for (uint32_t p = 0; p < data.size(); p += 2) {
# 207 : 15718 : uint64_t p1 = data[p], p2 = data[p + 1];
# 208 : 15718 : uint64_t mask = (p1 ^ nGenerationMask1) | (p2 ^ nGenerationMask2);
# 209 : 15718 : data[p] = p1 & mask;
# 210 : 15718 : data[p + 1] = p2 & mask;
# 211 : 15718 : }
# 212 : 74 : }
# 213 : 268276 : nEntriesThisGeneration++;
# 214 : :
# 215 [ + + ]: 5498634 : for (int n = 0; n < nHashFuncs; n++) {
# 216 : 5230358 : uint32_t h = RollingBloomHash(n, nTweak, vKey);
# 217 : 5230358 : 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 : 5230358 : 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 : 5230358 : data[pos & ~1U] = (data[pos & ~1U] & ~(uint64_t{1} << bit)) | (uint64_t(nGeneration & 1)) << bit;
# 222 : 5230358 : data[pos | 1] = (data[pos | 1] & ~(uint64_t{1} << bit)) | (uint64_t(nGeneration >> 1)) << bit;
# 223 : 5230358 : }
# 224 : 268276 : }
# 225 : :
# 226 : : bool CRollingBloomFilter::contains(Span<const unsigned char> vKey) const
# 227 : 238729 : {
# 228 [ + + ]: 800585 : for (int n = 0; n < nHashFuncs; n++) {
# 229 : 770730 : uint32_t h = RollingBloomHash(n, nTweak, vKey);
# 230 : 770730 : int bit = h & 0x3F;
# 231 : 770730 : 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 [ + + ]: 770730 : if (!(((data[pos & ~1U] | data[pos | 1]) >> bit) & 1)) {
# 234 : 208874 : return false;
# 235 : 208874 : }
# 236 : 770730 : }
# 237 : 29855 : return true;
# 238 : 238729 : }
# 239 : :
# 240 : : void CRollingBloomFilter::reset()
# 241 : 10389 : {
# 242 : 10389 : nTweak = GetRand(std::numeric_limits<unsigned int>::max());
# 243 : 10389 : nEntriesThisGeneration = 0;
# 244 : 10389 : nGeneration = 1;
# 245 : 10389 : std::fill(data.begin(), data.end(), 0);
# 246 : 10389 : }
|
