src/bloom.cpp

   1 // Copyright (c) 2012-2014 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 <boost/foreach.hpp>
  18
  19 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455
  20 #define LN2 0.6931471805599453094172321214581765680755001343602552
  21
  22 using namespace std;
  23
  24 CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn, unsigned char nFlagsIn) :
  25     /**
  26      * The ideal size for a bloom filter with a given number of elements and false positive rate is:
  27      * - nElements * log(fp rate) / ln(2)^2
  28      * We ignore filter parameters which will create a bloom filter larger than the protocol limits
  29      */
  30     vData(min((unsigned int)(-1  / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
  31     /**
  32      * The ideal number of hash functions is filter size * ln(2) / number of elements
  33      * Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
  34      * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
  35      */
  36     isFull(false),
  37     isEmpty(false),
  38     nHashFuncs(min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
  39     nTweak(nTweakIn),
  40     nFlags(nFlagsIn)
  41 {
  42 }
  43
  44 // Private constructor used by CRollingBloomFilter
  45 CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn) :
  46     vData((unsigned int)(-1  / LN2SQUARED * nElements * log(nFPRate)) / 8),
  47     isFull(false),
  48     isEmpty(true),
  49     nHashFuncs((unsigned int)(vData.size() * 8 / nElements * LN2)),
  50     nTweak(nTweakIn),
  51     nFlags(BLOOM_UPDATE_NONE)
  52 {
  53 }
  54
  55 inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const
  56 {
  57     // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
  58     return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
  59 }
  60
  61 void CBloomFilter::insert(const vector<unsigned char>& vKey)
  62 {
  63     if (isFull)
  64         return;
  65     for (unsigned int i = 0; i < nHashFuncs; i++)
  66     {
  67         unsigned int nIndex = Hash(i, vKey);
  68         // Sets bit nIndex of vData
  69         vData[nIndex >> 3] |= (1 << (7 & nIndex));
  70     }
  71     isEmpty = false;
  72 }
  73
  74 void CBloomFilter::insert(const COutPoint& outpoint)
  75 {
  76     CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
  77     stream << outpoint;
  78     vector<unsigned char> data(stream.begin(), stream.end());
  79     insert(data);
  80 }
  81
  82 void CBloomFilter::insert(const uint256& hash)
  83 {
  84     vector<unsigned char> data(hash.begin(), hash.end());
  85     insert(data);
  86 }
  87
  88 bool CBloomFilter::contains(const vector<unsigned char>& vKey) const
  89 {
  90     if (isFull)
  91         return true;
  92     if (isEmpty)
  93         return false;
  94     for (unsigned int i = 0; i < nHashFuncs; i++)
  95     {
  96         unsigned int nIndex = Hash(i, vKey);
  97         // Checks bit nIndex of vData
  98         if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
  99             return false;
 100     }
 101     return true;
 102 }
 103
 104 bool CBloomFilter::contains(const COutPoint& outpoint) const
 105 {
 106     CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
 107     stream << outpoint;
 108     vector<unsigned char> data(stream.begin(), stream.end());
 109     return contains(data);
 110 }
 111
 112 bool CBloomFilter::contains(const uint256& hash) const
 113 {
 114     vector<unsigned char> data(hash.begin(), hash.end());
 115     return contains(data);
 116 }
 117
 118 void CBloomFilter::clear()
 119 {
 120     vData.assign(vData.size(),0);
 121     isFull = false;
 122     isEmpty = true;
 123 }
 124
 125 void CBloomFilter::reset(unsigned int nNewTweak)
 126 {
 127     clear();
 128     nTweak = nNewTweak;
 129 }
 130
 131 bool CBloomFilter::IsWithinSizeConstraints() const
 132 {
 133     return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
 134 }
 135
 136 bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
 137 {
 138     bool fFound = false;
 139     // Match if the filter contains the hash of tx
 140     //  for finding tx when they appear in a block
 141     if (isFull)
 142         return true;
 143     if (isEmpty)
 144         return false;
 145     const uint256& hash = tx.GetHash();
 146     if (contains(hash))
 147         fFound = true;
 148
 149     for (unsigned int i = 0; i < tx.vout.size(); i++)
 150     {
 151         const CTxOut& txout = tx.vout[i];
 152         // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx
 153         // If this matches, also add the specific output that was matched.
 154         // This means clients don't have to update the filter themselves when a new relevant tx
 155         // is discovered in order to find spending transactions, which avoids round-tripping and race conditions.
 156         CScript::const_iterator pc = txout.scriptPubKey.begin();
 157         vector<unsigned char> data;
 158         while (pc < txout.scriptPubKey.end())
 159         {
 160             opcodetype opcode;
 161             if (!txout.scriptPubKey.GetOp(pc, opcode, data))
 162                 break;
 163             if (data.size() != 0 && contains(data))
 164             {
 165                 fFound = true;
 166                 if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL)
 167                     insert(COutPoint(hash, i));
 168                 else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY)
 169                 {
 170                     txnouttype type;
 171                     vector<vector<unsigned char> > vSolutions;
 172                     if (Solver(txout.scriptPubKey, type, vSolutions) &&
 173                             (type == TX_PUBKEY || type == TX_MULTISIG))
 174                         insert(COutPoint(hash, i));
 175                 }
 176                 break;
 177             }
 178         }
 179     }
 180
 181     if (fFound)
 182         return true;
 183
 184     BOOST_FOREACH(const CTxIn& txin, tx.vin)
 185     {
 186         // Match if the filter contains an outpoint tx spends
 187         if (contains(txin.prevout))
 188             return true;
 189
 190         // Match if the filter contains any arbitrary script data element in any scriptSig in tx
 191         CScript::const_iterator pc = txin.scriptSig.begin();
 192         vector<unsigned char> data;
 193         while (pc < txin.scriptSig.end())
 194         {
 195             opcodetype opcode;
 196             if (!txin.scriptSig.GetOp(pc, opcode, data))
 197                 break;
 198             if (data.size() != 0 && contains(data))
 199                 return true;
 200         }
 201     }
 202
 203     return false;
 204 }
 205
 206 void CBloomFilter::UpdateEmptyFull()
 207 {
 208     bool full = true;
 209     bool empty = true;
 210     for (unsigned int i = 0; i < vData.size(); i++)
 211     {
 212         full &= vData[i] == 0xff;
 213         empty &= vData[i] == 0;
 214     }
 215     isFull = full;
 216     isEmpty = empty;
 217 }
 218
 219 CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, double fpRate) :
 220     b1(nElements * 2, fpRate, 0), b2(nElements * 2, fpRate, 0)
 221 {
 222     // Implemented using two bloom filters of 2 * nElements each.
 223     // We fill them up, and clear them, staggered, every nElements
 224     // inserted, so at least one always contains the last nElements
 225     // inserted.
 226     nInsertions = 0;
 227     nBloomSize = nElements * 2;
 228
 229     reset();
 230 }
 231
 232 void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
 233 {
 234     if (nInsertions == 0) {
 235         b1.clear();
 236     } else if (nInsertions == nBloomSize / 2) {
 237         b2.clear();
 238     }
 239     b1.insert(vKey);
 240     b2.insert(vKey);
 241     if (++nInsertions == nBloomSize) {
 242         nInsertions = 0;
 243     }
 244 }
 245
 246 void CRollingBloomFilter::insert(const uint256& hash)
 247 {
 248     vector<unsigned char> data(hash.begin(), hash.end());
 249     insert(data);
 250 }
 251
 252 bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
 253 {
 254     if (nInsertions < nBloomSize / 2) {
 255         return b2.contains(vKey);
 256     }
 257     return b1.contains(vKey);
 258 }
 259
 260 bool CRollingBloomFilter::contains(const uint256& hash) const
 261 {
 262     vector<unsigned char> data(hash.begin(), hash.end());
 263     return contains(data);
 264 }
 265
 266 void CRollingBloomFilter::reset()
 267 {
 268     unsigned int nNewTweak = GetRand(std::numeric_limits<unsigned int>::max());
 269     b1.reset(nNewTweak);
 270     b2.reset(nNewTweak);
 271     nInsertions = 0;
 272 }