1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
// Copyright (c) 2012 The Bitcoin developers
// Distributed under the MIT/X11 software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <math.h>
#include <stdlib.h>
#include "bloom.h"
#include "main.h"
#include "script.h"
#define LN2SQUARED 0.4804530139182014246671025263266649717305529515945455
#define LN2 0.6931471805599453094172321214581765680755001343602552
using namespace std;
static const unsigned char bit_mask[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate) :
// The ideal size for a bloom filter with a given number of elements and false positive rate is:
// - nElements * log(fp rate) / ln(2)^2
// We ignore filter parameters which will create a bloom filter larger than the protocol limits
vData(min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM_FILTER_SIZE * 8) / 8),
// The ideal number of hash functions is filter size * ln(2) / number of elements
// Again, we ignore filter parameters which will create a bloom filter with more hash functions than the protocol limits
// See http://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas
nHashFuncs(min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS))
{
}
inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector<unsigned char>& vDataToHash) const
{
// 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values.
return MurmurHash3(nHashNum * 0xFBA4C795, vDataToHash) % (vData.size() * 8);
}
void CBloomFilter::insert(const vector<unsigned char>& vKey)
{
for (unsigned int i = 0; i < nHashFuncs; i++)
{
unsigned int nIndex = Hash(i, vKey);
// Sets bit nIndex of vData
vData[nIndex >> 3] |= bit_mask[7 & nIndex];
}
}
void CBloomFilter::insert(const COutPoint& outpoint)
{
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
stream << outpoint;
vector<unsigned char> data(stream.begin(), stream.end());
insert(data);
}
void CBloomFilter::insert(const uint256& hash)
{
vector<unsigned char> data(hash.begin(), hash.end());
insert(data);
}
bool CBloomFilter::contains(const vector<unsigned char>& vKey) const
{
for (unsigned int i = 0; i < nHashFuncs; i++)
{
unsigned int nIndex = Hash(i, vKey);
// Checks bit nIndex of vData
if (!(vData[nIndex >> 3] & bit_mask[7 & nIndex]))
return false;
}
return true;
}
bool CBloomFilter::contains(const COutPoint& outpoint) const
{
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION);
stream << outpoint;
vector<unsigned char> data(stream.begin(), stream.end());
return contains(data);
}
bool CBloomFilter::contains(const uint256& hash) const
{
vector<unsigned char> data(hash.begin(), hash.end());
return contains(data);
}
bool CBloomFilter::IsWithinSizeConstraints() const
{
return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS;
}
bool CBloomFilter::IsTransactionRelevantToFilter(const CTransaction& tx) const
{
// Match if the filter contains the hash of tx
// for finding tx when they appear in a block
if (contains(tx.GetHash()))
return true;
BOOST_FOREACH(const CTxOut& txout, tx.vout)
{
// Match if the filter contains any arbitrary script data element in any scriptPubKey in tx
CScript::const_iterator pc = txout.scriptPubKey.begin();
vector<unsigned char> data;
while (pc < txout.scriptPubKey.end())
{
opcodetype opcode;
if (!txout.scriptPubKey.GetOp(pc, opcode, data))
break;
if (data.size() != 0 && contains(data))
return true;
}
}
BOOST_FOREACH(const CTxIn& txin, tx.vin)
{
// Match if the filter contains an outpoint tx spends
if (contains(txin.prevout))
return true;
// Match if the filter contains any arbitrary script data element in any scriptSig in tx
CScript::const_iterator pc = txin.scriptSig.begin();
vector<unsigned char> data;
while (pc < txin.scriptSig.end())
{
opcodetype opcode;
if (!txin.scriptSig.GetOp(pc, opcode, data))
break;
if (data.size() != 0 && contains(data))
return true;
}
}
return false;
}
|
