Line data Source code
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 22 : 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 66 : 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 66 : nHashFuncs(min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)),
39 : nTweak(nTweakIn),
40 132 : nFlags(nFlagsIn)
41 : {
42 22 : }
43 :
44 : // Private constructor used by CRollingBloomFilter
45 970 : CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn) :
46 970 : vData((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)) / 8),
47 : isFull(false),
48 : isEmpty(true),
49 1940 : nHashFuncs((unsigned int)(vData.size() * 8 / nElements * LN2)),
50 : nTweak(nTweakIn),
51 3880 : nFlags(BLOOM_UPDATE_NONE)
52 : {
53 970 : }
54 :
55 55564 : 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 111128 : return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8);
59 : }
60 :
61 4432 : void CBloomFilter::insert(const vector<unsigned char>& vKey)
62 : {
63 4432 : if (isFull)
64 4432 : return;
65 29400 : for (unsigned int i = 0; i < nHashFuncs; i++)
66 : {
67 29400 : unsigned int nIndex = Hash(i, vKey);
68 : // Sets bit nIndex of vData
69 58800 : vData[nIndex >> 3] |= (1 << (7 & nIndex));
70 : }
71 4432 : isEmpty = false;
72 : }
73 :
74 8 : void CBloomFilter::insert(const COutPoint& outpoint)
75 : {
76 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
77 : stream << outpoint;
78 16 : vector<unsigned char> data(stream.begin(), stream.end());
79 8 : insert(data);
80 8 : }
81 :
82 9 : void CBloomFilter::insert(const uint256& hash)
83 : {
84 36 : vector<unsigned char> data(hash.begin(), hash.end());
85 9 : insert(data);
86 9 : }
87 :
88 13179 : bool CBloomFilter::contains(const vector<unsigned char>& vKey) const
89 : {
90 13179 : if (isFull)
91 : return true;
92 13179 : if (isEmpty)
93 : return false;
94 15486 : for (unsigned int i = 0; i < nHashFuncs; i++)
95 : {
96 26164 : unsigned int nIndex = Hash(i, vKey);
97 : // Checks bit nIndex of vData
98 52328 : if (!(vData[nIndex >> 3] & (1 << (7 & nIndex))))
99 : return false;
100 : }
101 : return true;
102 : }
103 :
104 88 : bool CBloomFilter::contains(const COutPoint& outpoint) const
105 : {
106 : CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
107 : stream << outpoint;
108 176 : vector<unsigned char> data(stream.begin(), stream.end());
109 176 : return contains(data);
110 : }
111 :
112 76 : bool CBloomFilter::contains(const uint256& hash) const
113 : {
114 304 : vector<unsigned char> data(hash.begin(), hash.end());
115 152 : return contains(data);
116 : }
117 :
118 1307 : void CBloomFilter::clear()
119 : {
120 3921 : vData.assign(vData.size(),0);
121 1307 : isFull = false;
122 1307 : isEmpty = true;
123 1307 : }
124 :
125 0 : void CBloomFilter::reset(unsigned int nNewTweak)
126 : {
127 1286 : clear();
128 1286 : nTweak = nNewTweak;
129 0 : }
130 :
131 0 : bool CBloomFilter::IsWithinSizeConstraints() const
132 : {
133 0 : return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
134 : }
135 :
136 1662 : bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx)
137 : {
138 1662 : bool fFound = false;
139 : // Match if the filter contains the hash of tx
140 : // for finding tx when they appear in a block
141 1662 : if (isFull)
142 : return true;
143 76 : if (isEmpty)
144 : return false;
145 76 : const uint256& hash = tx.GetHash();
146 76 : if (contains(hash))
147 13 : fFound = true;
148 :
149 322 : for (unsigned int i = 0; i < tx.vout.size(); i++)
150 : {
151 246 : 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 246 : CScript::const_iterator pc = txout.scriptPubKey.begin();
157 : vector<unsigned char> data;
158 1809 : while (pc < txout.scriptPubKey.end())
159 : {
160 : opcodetype opcode;
161 980 : if (!txout.scriptPubKey.GetOp(pc, opcode, data))
162 : break;
163 980 : if (data.size() != 0 && contains(data))
164 : {
165 10 : fFound = true;
166 10 : if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL)
167 4 : insert(COutPoint(hash, i));
168 6 : else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY)
169 : {
170 : txnouttype type;
171 : vector<vector<unsigned char> > vSolutions;
172 4 : if (Solver(txout.scriptPubKey, type, vSolutions) &&
173 2 : (type == TX_PUBKEY || type == TX_MULTISIG))
174 1 : insert(COutPoint(hash, i));
175 : }
176 : break;
177 : }
178 : }
179 : }
180 :
181 76 : if (fFound)
182 : return true;
183 :
184 829 : BOOST_FOREACH(const CTxIn& txin, tx.vin)
185 : {
186 : // Match if the filter contains an outpoint tx spends
187 84 : if (contains(txin.prevout))
188 6 : return true;
189 :
190 : // Match if the filter contains any arbitrary script data element in any scriptSig in tx
191 160 : CScript::const_iterator pc = txin.scriptSig.begin();
192 : vector<unsigned char> data;
193 624 : while (pc < txin.scriptSig.end())
194 : {
195 : opcodetype opcode;
196 260 : if (!txin.scriptSig.GetOp(pc, opcode, data))
197 : break;
198 260 : if (data.size() != 0 && contains(data))
199 2 : return true;
200 : }
201 : }
202 :
203 47 : return false;
204 : }
205 :
206 0 : void CBloomFilter::UpdateEmptyFull()
207 : {
208 0 : bool full = true;
209 0 : bool empty = true;
210 0 : for (unsigned int i = 0; i < vData.size(); i++)
211 : {
212 0 : full &= vData[i] == 0xff;
213 0 : empty &= vData[i] == 0;
214 : }
215 0 : isFull = full;
216 0 : isEmpty = empty;
217 0 : }
218 :
219 485 : CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, double fpRate) :
220 485 : 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 485 : nInsertions = 0;
227 485 : nBloomSize = nElements * 2;
228 :
229 485 : reset();
230 485 : }
231 :
232 2197 : void CRollingBloomFilter::insert(const std::vector<unsigned char>& vKey)
233 : {
234 2197 : if (nInsertions == 0) {
235 11 : b1.clear();
236 2186 : } else if (nInsertions == nBloomSize / 2) {
237 9 : b2.clear();
238 : }
239 2197 : b1.insert(vKey);
240 2197 : b2.insert(vKey);
241 2197 : if (++nInsertions == nBloomSize) {
242 7 : nInsertions = 0;
243 : }
244 2197 : }
245 :
246 1 : void CRollingBloomFilter::insert(const uint256& hash)
247 : {
248 4 : vector<unsigned char> data(hash.begin(), hash.end());
249 1 : insert(data);
250 1 : }
251 :
252 12752 : bool CRollingBloomFilter::contains(const std::vector<unsigned char>& vKey) const
253 : {
254 12752 : if (nInsertions < nBloomSize / 2) {
255 2053 : return b2.contains(vKey);
256 : }
257 10699 : return b1.contains(vKey);
258 : }
259 :
260 1553 : bool CRollingBloomFilter::contains(const uint256& hash) const
261 : {
262 6212 : vector<unsigned char> data(hash.begin(), hash.end());
263 3106 : return contains(data);
264 : }
265 :
266 643 : void CRollingBloomFilter::reset()
267 : {
268 643 : unsigned int nNewTweak = GetRand(std::numeric_limits<unsigned int>::max());
269 643 : b1.reset(nNewTweak);
270 643 : b2.reset(nNewTweak);
271 643 : nInsertions = 0;
272 643 : }
|
