From bbe41088c61f2ad328766e851ffe6169aa80935a Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Fri, 17 Jul 2015 06:42:43 -0400 Subject: Add uint256 support to CRollingBloomFilter --- src/bloom.cpp | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index 36cba491c..e15bc32f9 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -234,6 +234,20 @@ void CRollingBloomFilter::insert(const std::vector& vKey) } } +void CRollingBloomFilter::insert(const uint256& hash) +{ + if (nInsertions == 0) { + b1.clear(); + } else if (nInsertions == nBloomSize / 2) { + b2.clear(); + } + b1.insert(hash); + b2.insert(hash); + if (++nInsertions == nBloomSize) { + nInsertions = 0; + } +} + bool CRollingBloomFilter::contains(const std::vector& vKey) const { if (nInsertions < nBloomSize / 2) { @@ -242,6 +256,14 @@ bool CRollingBloomFilter::contains(const std::vector& vKey) const return b1.contains(vKey); } +bool CRollingBloomFilter::contains(const uint256& hash) const +{ + if (nInsertions < nBloomSize / 2) { + return b2.contains(hash); + } + return b1.contains(hash); +} + void CRollingBloomFilter::clear() { b1.clear(); -- cgit v1.2.3 From a3d65fedaa18686f0cc007d0a13dba6545250300 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 27 Jul 2015 18:38:45 +0200 Subject: Reuse vector hashing code for uint256 --- src/bloom.cpp | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index e15bc32f9..3f50b1da9 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -236,16 +236,8 @@ void CRollingBloomFilter::insert(const std::vector& vKey) void CRollingBloomFilter::insert(const uint256& hash) { - if (nInsertions == 0) { - b1.clear(); - } else if (nInsertions == nBloomSize / 2) { - b2.clear(); - } - b1.insert(hash); - b2.insert(hash); - if (++nInsertions == nBloomSize) { - nInsertions = 0; - } + vector data(hash.begin(), hash.end()); + insert(data); } bool CRollingBloomFilter::contains(const std::vector& vKey) const @@ -258,10 +250,8 @@ bool CRollingBloomFilter::contains(const std::vector& vKey) const bool CRollingBloomFilter::contains(const uint256& hash) const { - if (nInsertions < nBloomSize / 2) { - return b2.contains(hash); - } - return b1.contains(hash); + vector data(hash.begin(), hash.end()); + return contains(data); } void CRollingBloomFilter::clear() -- cgit v1.2.3 From d2d7ee0e863b286e1c9f9c54659d494fb0a7712d Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Mon, 20 Jul 2015 04:43:34 +0900 Subject: Make CRollingBloomFilter set nTweak for you While CBloomFilter is usually used with an explicitly set nTweak, CRollingBloomFilter is only used internally. Requiring every caller to set nTweak is error-prone and redundant; better to have the class handle that for you with a high-quality randomness source. Additionally when clearing the filter it makes sense to change nTweak as well to recover from a bad setting, e.g. due to insufficient randomness at initialization, so the clear() method is replaced by a reset() method that sets a new, random, nTweak value. --- src/bloom.cpp | 19 +++++++++++++++---- 1 file changed, 15 insertions(+), 4 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index 3f50b1da9..89959d732 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -8,6 +8,7 @@ #include "hash.h" #include "script/script.h" #include "script/standard.h" +#include "random.h" #include "streams.h" #include @@ -121,6 +122,12 @@ void CBloomFilter::clear() isEmpty = true; } +void CBloomFilter::reset(unsigned int nNewTweak) +{ + clear(); + nTweak = nNewTweak; +} + bool CBloomFilter::IsWithinSizeConstraints() const { return vData.size() <= MAX_BLOOM_FILTER_SIZE && nHashFuncs <= MAX_HASH_FUNCS; @@ -217,7 +224,8 @@ CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, double fpRate, // inserted, so at least one always contains the last nElements // inserted. nBloomSize = nElements * 2; - nInsertions = 0; + + reset(nTweak); } void CRollingBloomFilter::insert(const std::vector& vKey) @@ -254,9 +262,12 @@ bool CRollingBloomFilter::contains(const uint256& hash) const return contains(data); } -void CRollingBloomFilter::clear() +void CRollingBloomFilter::reset(unsigned int nNewTweak) { - b1.clear(); - b2.clear(); + if (!nNewTweak) + nNewTweak = GetRand(std::numeric_limits::max()); + + b1.reset(nNewTweak); + b2.reset(nNewTweak); nInsertions = 0; } -- cgit v1.2.3 From d741371d7d27e228aa64c618c50b23fb5449c3e1 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 27 Jul 2015 18:58:00 +0200 Subject: Only use randomly created nonces in CRollingBloomFilter. --- src/bloom.cpp | 13 ++++++------- 1 file changed, 6 insertions(+), 7 deletions(-) (limited to 'src/bloom.cpp') diff --git a/src/bloom.cpp b/src/bloom.cpp index 89959d732..de8720659 100644 --- a/src/bloom.cpp +++ b/src/bloom.cpp @@ -216,16 +216,17 @@ void CBloomFilter::UpdateEmptyFull() isEmpty = empty; } -CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, double fpRate, unsigned int nTweak) : - b1(nElements * 2, fpRate, nTweak), b2(nElements * 2, fpRate, nTweak) +CRollingBloomFilter::CRollingBloomFilter(unsigned int nElements, double fpRate) : + b1(nElements * 2, fpRate, 0), b2(nElements * 2, fpRate, 0) { // Implemented using two bloom filters of 2 * nElements each. // We fill them up, and clear them, staggered, every nElements // inserted, so at least one always contains the last nElements // inserted. + nInsertions = 0; nBloomSize = nElements * 2; - reset(nTweak); + reset(); } void CRollingBloomFilter::insert(const std::vector& vKey) @@ -262,11 +263,9 @@ bool CRollingBloomFilter::contains(const uint256& hash) const return contains(data); } -void CRollingBloomFilter::reset(unsigned int nNewTweak) +void CRollingBloomFilter::reset() { - if (!nNewTweak) - nNewTweak = GetRand(std::numeric_limits::max()); - + unsigned int nNewTweak = GetRand(std::numeric_limits::max()); b1.reset(nNewTweak); b2.reset(nNewTweak); nInsertions = 0; -- cgit v1.2.3