From bd21612c37cf4f2df3a6926beff8a7f89714235e Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 13 Aug 2012 05:26:27 +0200 Subject: Add a CBloomFilter class for use as a transaction filter. --- src/bloom.cpp | 133 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 133 insertions(+) create mode 100644 src/bloom.cpp (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp new file mode 100644 index 000000000..5fac1d06a --- /dev/null +++ b/src/bloom.cpp @@ -0,0 +1,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 +#include + +#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& 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& 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 data(stream.begin(), stream.end()); + insert(data); +} + +void CBloomFilter::insert(const uint256& hash) +{ + vector data(hash.begin(), hash.end()); + insert(data); +} + +bool CBloomFilter::contains(const vector& 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 data(stream.begin(), stream.end()); + return contains(data); +} + +bool CBloomFilter::contains(const uint256& hash) const +{ + vector 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 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 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; +} -- cgit v1.2.3 From 269d9c6492dc275650d2137d53f4afdca88e3216 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Mon, 13 Aug 2012 05:26:30 +0200 Subject: Replace RelayMessage with RelayTransaction. --- src/bloom.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index 5fac1d06a..73b04aa3d 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -88,11 +88,11 @@ bool CBloomFilter::IsWithinSizeConstraints() const return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS; } -bool CBloomFilter::IsTransactionRelevantToFilter(const CTransaction& tx) const +bool CBloomFilter::IsTransactionRelevantToFilter(const CTransaction& tx, const uint256& hash) const { // Match if the filter contains the hash of tx // for finding tx when they appear in a block - if (contains(tx.GetHash())) + if (contains(hash)) return true; BOOST_FOREACH(const CTxOut& txout, tx.vout) -- cgit v1.2.3 From d3b26f7077f58ebfcfccc5f0b16f8c29be5dc6b5 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Sat, 18 Aug 2012 23:38:28 -0400 Subject: Automatically add any matching outputs to a filter during matching. --- src/bloom.cpp | 20 ++++++++++++++++---- 1 file changed, 16 insertions(+), 4 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index 73b04aa3d..e773bbbbd 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -88,16 +88,21 @@ bool CBloomFilter::IsWithinSizeConstraints() const return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS; } -bool CBloomFilter::IsTransactionRelevantToFilter(const CTransaction& tx, const uint256& hash) const +bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx, const uint256& hash) { + bool fFound = false; // Match if the filter contains the hash of tx // for finding tx when they appear in a block if (contains(hash)) - return true; + fFound = true; - BOOST_FOREACH(const CTxOut& txout, tx.vout) + for (unsigned int i = 0; i < tx.vout.size(); i++) { + const CTxOut& txout = tx.vout[i]; // Match if the filter contains any arbitrary script data element in any scriptPubKey in tx + // If this matches, also add the specific output that was matched. + // This means clients don't have to update the filter themselves when a new relevant tx + // is discovered in order to find spending transactions, which avoids round-tripping and race conditions. CScript::const_iterator pc = txout.scriptPubKey.begin(); vector data; while (pc < txout.scriptPubKey.end()) @@ -106,10 +111,17 @@ bool CBloomFilter::IsTransactionRelevantToFilter(const CTransaction& tx, const u if (!txout.scriptPubKey.GetOp(pc, opcode, data)) break; if (data.size() != 0 && contains(data)) - return true; + { + fFound = true; + insert(COutPoint(hash, i)); + break; + } } } + if (fFound) + return true; + BOOST_FOREACH(const CTxIn& txin, tx.vin) { // Match if the filter contains an outpoint tx spends -- cgit v1.2.3 From b1f99bed6f0fbbe94e6a3161b49b3f225dec8374 Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Fri, 2 Nov 2012 18:33:50 -0400 Subject: Add a nTweak to bloom filters to tweak the seed. --- src/bloom.cpp | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index e773bbbbd..65f9b021b 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -15,7 +15,7 @@ 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) : +CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn) : // 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 @@ -23,14 +23,15 @@ vData(min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM // 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)) +nHashFuncs(min((unsigned int)(vData.size() * 8 / nElements * LN2), MAX_HASH_FUNCS)), +nTweak(nTweakIn) { } inline unsigned int CBloomFilter::Hash(unsigned int nHashNum, const std::vector& vDataToHash) const { // 0xFBA4C795 chosen as it guarantees a reasonable bit difference between nHashNum values. - return MurmurHash3(nHashNum * 0xFBA4C795, vDataToHash) % (vData.size() * 8); + return MurmurHash3(nHashNum * 0xFBA4C795 + nTweak, vDataToHash) % (vData.size() * 8); } void CBloomFilter::insert(const vector& vKey) -- cgit v1.2.3 From e1a4f3778cb90ba9f0d4e736752f78dad1703caa Mon Sep 17 00:00:00 2001 From: Matt Corallo Date: Thu, 10 Jan 2013 20:23:28 -0500 Subject: Add nFlags to CBloomFilter to make filter updating optional. --- src/bloom.cpp | 16 +++++++++++++--- 1 file changed, 13 insertions(+), 3 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index 65f9b021b..36f5e5013 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -15,7 +15,7 @@ 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, unsigned int nTweakIn) : +CBloomFilter::CBloomFilter(unsigned int nElements, double nFPRate, unsigned int nTweakIn, unsigned char nFlagsIn) : // 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 @@ -24,7 +24,8 @@ vData(min((unsigned int)(-1 / LN2SQUARED * nElements * log(nFPRate)), MAX_BLOOM // 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)), -nTweak(nTweakIn) +nTweak(nTweakIn), +nFlags(nFlagsIn) { } @@ -114,7 +115,16 @@ bool CBloomFilter::IsRelevantAndUpdate(const CTransaction& tx, const uint256& ha if (data.size() != 0 && contains(data)) { fFound = true; - insert(COutPoint(hash, i)); + if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_ALL) + insert(COutPoint(hash, i)); + else if ((nFlags & BLOOM_UPDATE_MASK) == BLOOM_UPDATE_P2PUBKEY_ONLY) + { + txnouttype type; + vector > vSolutions; + if (Solver(txout.scriptPubKey, type, vSolutions) && + (type == TX_PUBKEY || type == TX_MULTISIG)) + insert(COutPoint(hash, i)); + } break; } } -- cgit v1.2.3