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.
7 #include "primitives/transaction.h"
9 #include "script/script.h"
10 #include "script/standard.h"
16 #include <boost/foreach.hpp>
18 #define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455
19 #define LN2 0.6931471805599453094172321214581765680755001343602552
23 CBloomFilter::CBloomFilter(unsigned int nElements
, double nFPRate
, unsigned int nTweakIn
, unsigned char nFlagsIn
) :
25 * The ideal size for a bloom filter with a given number of elements and false positive rate is:
26 * - nElements * log(fp rate) / ln(2)^2
27 * We ignore filter parameters which will create a bloom filter larger than the protocol limits
29 vData(min((unsigned int)(-1 / LN2SQUARED
* nElements
* log(nFPRate
)), MAX_BLOOM_FILTER_SIZE
* 8) / 8),
31 * The ideal number of hash functions is filter size * ln(2) / number of elements
32 * Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
33 * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
37 nHashFuncs(min((unsigned int)(vData
.size() * 8 / nElements
* LN2
), MAX_HASH_FUNCS
)),
43 inline unsigned int CBloomFilter::Hash(unsigned int nHashNum
, const std::vector
<unsigned char>& vDataToHash
) const
45 // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
46 return MurmurHash3(nHashNum
* 0xFBA4C795 + nTweak
, vDataToHash
) % (vData
.size() * 8);
49 void CBloomFilter::insert(const vector
<unsigned char>& vKey
)
53 for (unsigned int i
= 0; i
< nHashFuncs
; i
++)
55 unsigned int nIndex
= Hash(i
, vKey
);
56 // Sets bit nIndex of vData
57 vData
[nIndex
>> 3] |= (1 << (7 & nIndex
));
62 void CBloomFilter::insert(const COutPoint
& outpoint
)
64 CDataStream
stream(SER_NETWORK
, PROTOCOL_VERSION
);
66 vector
<unsigned char> data(stream
.begin(), stream
.end());
70 void CBloomFilter::insert(const uint256
& hash
)
72 vector
<unsigned char> data(hash
.begin(), hash
.end());
76 bool CBloomFilter::contains(const vector
<unsigned char>& vKey
) const
82 for (unsigned int i
= 0; i
< nHashFuncs
; i
++)
84 unsigned int nIndex
= Hash(i
, vKey
);
85 // Checks bit nIndex of vData
86 if (!(vData
[nIndex
>> 3] & (1 << (7 & nIndex
))))
92 bool CBloomFilter::contains(const COutPoint
& outpoint
) const
94 CDataStream
stream(SER_NETWORK
, PROTOCOL_VERSION
);
96 vector
<unsigned char> data(stream
.begin(), stream
.end());
97 return contains(data
);
100 bool CBloomFilter::contains(const uint256
& hash
) const
102 vector
<unsigned char> data(hash
.begin(), hash
.end());
103 return contains(data
);
106 void CBloomFilter::clear()
108 vData
.assign(vData
.size(),0);
113 bool CBloomFilter::IsWithinSizeConstraints() const
115 return vData
.size() <= MAX_BLOOM_FILTER_SIZE
&& nHashFuncs
<= MAX_HASH_FUNCS
;
118 bool CBloomFilter::IsRelevantAndUpdate(const CTransaction
& tx
)
121 // Match if the filter contains the hash of tx
122 // for finding tx when they appear in a block
127 const uint256
& hash
= tx
.GetHash();
131 for (unsigned int i
= 0; i
< tx
.vout
.size(); i
++)
133 const CTxOut
& txout
= tx
.vout
[i
];
134 // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx
135 // If this matches, also add the specific output that was matched.
136 // This means clients don't have to update the filter themselves when a new relevant tx
137 // is discovered in order to find spending transactions, which avoids round-tripping and race conditions.
138 CScript::const_iterator pc
= txout
.scriptPubKey
.begin();
139 vector
<unsigned char> data
;
140 while (pc
< txout
.scriptPubKey
.end())
143 if (!txout
.scriptPubKey
.GetOp(pc
, opcode
, data
))
145 if (data
.size() != 0 && contains(data
))
148 if ((nFlags
& BLOOM_UPDATE_MASK
) == BLOOM_UPDATE_ALL
)
149 insert(COutPoint(hash
, i
));
150 else if ((nFlags
& BLOOM_UPDATE_MASK
) == BLOOM_UPDATE_P2PUBKEY_ONLY
)
153 vector
<vector
<unsigned char> > vSolutions
;
154 if (Solver(txout
.scriptPubKey
, type
, vSolutions
) &&
155 (type
== TX_PUBKEY
|| type
== TX_MULTISIG
))
156 insert(COutPoint(hash
, i
));
166 BOOST_FOREACH(const CTxIn
& txin
, tx
.vin
)
168 // Match if the filter contains an outpoint tx spends
169 if (contains(txin
.prevout
))
172 // Match if the filter contains any arbitrary script data element in any scriptSig in tx
173 CScript::const_iterator pc
= txin
.scriptSig
.begin();
174 vector
<unsigned char> data
;
175 while (pc
< txin
.scriptSig
.end())
178 if (!txin
.scriptSig
.GetOp(pc
, opcode
, data
))
180 if (data
.size() != 0 && contains(data
))
188 void CBloomFilter::UpdateEmptyFull()
192 for (unsigned int i
= 0; i
< vData
.size(); i
++)
194 full
&= vData
[i
] == 0xff;
195 empty
&= vData
[i
] == 0;