Changeset View
Changeset View
Standalone View
Standalone View
src/bloom.cpp
Show All 31 Lines | |||||
* See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these | * See https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these | ||||
* formulas. | * formulas. | ||||
*/ | */ | ||||
CBloomFilter::CBloomFilter(const uint32_t nElements, const double nFPRate, | CBloomFilter::CBloomFilter(const uint32_t nElements, const double nFPRate, | ||||
const uint32_t nTweakIn, uint8_t nFlagsIn) | const uint32_t nTweakIn, uint8_t nFlagsIn) | ||||
: vData(std::min<uint32_t>(-1 / LN2SQUARED * nElements * log(nFPRate), | : vData(std::min<uint32_t>(-1 / LN2SQUARED * nElements * log(nFPRate), | ||||
MAX_BLOOM_FILTER_SIZE * 8) / | MAX_BLOOM_FILTER_SIZE * 8) / | ||||
8), | 8), | ||||
isFull(false), isEmpty(true), | |||||
nHashFuncs(std::min<uint32_t>(vData.size() * 8 / nElements * LN2, | nHashFuncs(std::min<uint32_t>(vData.size() * 8 / nElements * LN2, | ||||
MAX_HASH_FUNCS)), | MAX_HASH_FUNCS)), | ||||
nTweak(nTweakIn), nFlags(nFlagsIn) {} | nTweak(nTweakIn), nFlags(nFlagsIn) {} | ||||
inline uint32_t | inline uint32_t | ||||
CBloomFilter::Hash(uint32_t nHashNum, | CBloomFilter::Hash(uint32_t nHashNum, | ||||
const std::vector<uint8_t> &vDataToHash) const { | const std::vector<uint8_t> &vDataToHash) const { | ||||
// 0xFBA4C795 chosen as it guarantees a reasonable bit difference between | // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between | ||||
// nHashNum values. | // nHashNum values. | ||||
return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % | return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % | ||||
(vData.size() * 8); | (vData.size() * 8); | ||||
} | } | ||||
void CBloomFilter::insert(const std::vector<uint8_t> &vKey) { | void CBloomFilter::insert(const std::vector<uint8_t> &vKey) { | ||||
if (isFull) { | if (vData.empty()) { | ||||
// Avoid divide-by-zero (CVE-2013-5700) | |||||
return; | return; | ||||
} | } | ||||
for (uint32_t i = 0; i < nHashFuncs; i++) { | for (uint32_t i = 0; i < nHashFuncs; i++) { | ||||
uint32_t nIndex = Hash(i, vKey); | uint32_t nIndex = Hash(i, vKey); | ||||
// Sets bit nIndex of vData | // Sets bit nIndex of vData | ||||
vData[nIndex >> 3] |= (1 << (7 & nIndex)); | vData[nIndex >> 3] |= (1 << (7 & nIndex)); | ||||
} | } | ||||
isEmpty = false; | |||||
} | } | ||||
void CBloomFilter::insert(const COutPoint &outpoint) { | void CBloomFilter::insert(const COutPoint &outpoint) { | ||||
CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); | CDataStream stream(SER_NETWORK, PROTOCOL_VERSION); | ||||
stream << outpoint; | stream << outpoint; | ||||
std::vector<uint8_t> data(stream.begin(), stream.end()); | std::vector<uint8_t> data(stream.begin(), stream.end()); | ||||
insert(data); | insert(data); | ||||
} | } | ||||
void CBloomFilter::insert(const uint256 &hash) { | void CBloomFilter::insert(const uint256 &hash) { | ||||
std::vector<uint8_t> data(hash.begin(), hash.end()); | std::vector<uint8_t> data(hash.begin(), hash.end()); | ||||
insert(data); | insert(data); | ||||
} | } | ||||
bool CBloomFilter::contains(const std::vector<uint8_t> &vKey) const { | bool CBloomFilter::contains(const std::vector<uint8_t> &vKey) const { | ||||
if (isFull) { | if (vData.empty()) { | ||||
// Avoid divide-by-zero (CVE-2013-5700) | |||||
return true; | return true; | ||||
} | } | ||||
if (isEmpty) { | |||||
return false; | |||||
} | |||||
for (uint32_t i = 0; i < nHashFuncs; i++) { | for (uint32_t i = 0; i < nHashFuncs; i++) { | ||||
uint32_t nIndex = Hash(i, vKey); | uint32_t nIndex = Hash(i, vKey); | ||||
// Checks bit nIndex of vData | // Checks bit nIndex of vData | ||||
if (!(vData[nIndex >> 3] & (1 << (7 & nIndex)))) { | if (!(vData[nIndex >> 3] & (1 << (7 & nIndex)))) { | ||||
return false; | return false; | ||||
} | } | ||||
} | } | ||||
return true; | return true; | ||||
Show All 15 Lines | bool CBloomFilter::IsWithinSizeConstraints() const { | ||||
return vData.size() <= MAX_BLOOM_FILTER_SIZE && | return vData.size() <= MAX_BLOOM_FILTER_SIZE && | ||||
nHashFuncs <= MAX_HASH_FUNCS; | nHashFuncs <= MAX_HASH_FUNCS; | ||||
} | } | ||||
bool CBloomFilter::MatchAndInsertOutputs(const CTransaction &tx) { | bool CBloomFilter::MatchAndInsertOutputs(const CTransaction &tx) { | ||||
bool fFound = false; | bool fFound = false; | ||||
// Match if the filter contains the hash of tx for finding tx when they | // Match if the filter contains the hash of tx for finding tx when they | ||||
// appear in a block | // appear in a block | ||||
if (isFull) { | if (vData.empty()) { | ||||
// zero-size = "match-all" filter | |||||
return true; | return true; | ||||
} | } | ||||
if (isEmpty) { | |||||
return false; | |||||
} | |||||
const TxId &txid = tx.GetId(); | const TxId &txid = tx.GetId(); | ||||
if (contains(txid)) { | if (contains(txid)) { | ||||
fFound = true; | fFound = true; | ||||
} | } | ||||
for (size_t i = 0; i < tx.vout.size(); i++) { | for (size_t i = 0; i < tx.vout.size(); i++) { | ||||
const CTxOut &txout = tx.vout[i]; | const CTxOut &txout = tx.vout[i]; | ||||
Show All 26 Lines | for (size_t i = 0; i < tx.vout.size(); i++) { | ||||
} | } | ||||
} | } | ||||
} | } | ||||
return fFound; | return fFound; | ||||
} | } | ||||
bool CBloomFilter::MatchInputs(const CTransaction &tx) { | bool CBloomFilter::MatchInputs(const CTransaction &tx) { | ||||
if (isEmpty) { | |||||
return false; | |||||
} | |||||
for (const CTxIn &txin : tx.vin) { | for (const CTxIn &txin : tx.vin) { | ||||
// Match if the filter contains an outpoint tx spends | // Match if the filter contains an outpoint tx spends | ||||
if (contains(txin.prevout)) { | if (contains(txin.prevout)) { | ||||
return true; | return true; | ||||
} | } | ||||
// Match if the filter contains any arbitrary script data element in any | // Match if the filter contains any arbitrary script data element in any | ||||
// scriptSig in tx | // scriptSig in tx | ||||
CScript::const_iterator pc = txin.scriptSig.begin(); | CScript::const_iterator pc = txin.scriptSig.begin(); | ||||
std::vector<uint8_t> data; | std::vector<uint8_t> data; | ||||
while (pc < txin.scriptSig.end()) { | while (pc < txin.scriptSig.end()) { | ||||
opcodetype opcode; | opcodetype opcode; | ||||
if (!txin.scriptSig.GetOp(pc, opcode, data)) { | if (!txin.scriptSig.GetOp(pc, opcode, data)) { | ||||
break; | break; | ||||
} | } | ||||
if (data.size() != 0 && contains(data)) { | if (data.size() != 0 && contains(data)) { | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
void CBloomFilter::UpdateEmptyFull() { | |||||
bool full = true; | |||||
bool empty = true; | |||||
for (const auto d : vData) { | |||||
full &= (d == 0xff); | |||||
empty &= (d == 0); | |||||
} | |||||
isFull = full; | |||||
isEmpty = empty; | |||||
} | |||||
CRollingBloomFilter::CRollingBloomFilter(const uint32_t nElements, | CRollingBloomFilter::CRollingBloomFilter(const uint32_t nElements, | ||||
const double fpRate) { | const double fpRate) { | ||||
double logFpRate = log(fpRate); | double logFpRate = log(fpRate); | ||||
/* The optimal number of hash functions is log(fpRate) / log(0.5), but | /* The optimal number of hash functions is log(fpRate) / log(0.5), but | ||||
* restrict it to the range 1-50. */ | * restrict it to the range 1-50. */ | ||||
nHashFuncs = std::max(1, std::min<int>(round(logFpRate / log(0.5)), 50)); | nHashFuncs = std::max(1, std::min<int>(round(logFpRate / log(0.5)), 50)); | ||||
/* In this rolling bloom filter, we'll store between 2 and 3 generations of | /* In this rolling bloom filter, we'll store between 2 and 3 generations of | ||||
* nElements / 2 entries. */ | * nElements / 2 entries. */ | ||||
▲ Show 20 Lines • Show All 107 Lines • Show Last 20 Lines |