Bitcoin Core  0.15.99
P2P Digital Currency
Public Member Functions | Public Attributes | Private Member Functions | Private Attributes | Friends | List of all members
CBloomFilter Class Reference

BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transactions we send them. More...

#include <bloom.h>

Public Member Functions

 CBloomFilter (const unsigned int nElements, const double nFPRate, const unsigned int nTweak, unsigned char nFlagsIn)
 Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements Note that if the given parameters will result in a filter outside the bounds of the protocol limits, the filter created will be as close to the given parameters as possible within the protocol limits. More...
 
 CBloomFilter ()
 
template<typename Stream , typename Operation >
void SerializationOp (Stream &s, Operation ser_action)
 
void insert (const std::vector< unsigned char > &vKey)
 
void insert (const COutPoint &outpoint)
 
void insert (const uint256 &hash)
 
bool contains (const std::vector< unsigned char > &vKey) const
 
bool contains (const COutPoint &outpoint) const
 
bool contains (const uint256 &hash) const
 
void clear ()
 
void reset (const unsigned int nNewTweak)
 
bool IsWithinSizeConstraints () const
 True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (catch a filter which was just deserialized which was too big) More...
 
bool IsRelevantAndUpdate (const CTransaction &tx)
 Also adds any outputs which match the filter to the filter (to match their spending txes) More...
 
void UpdateEmptyFull ()
 Checks for empty and full filters to avoid wasting cpu. More...
 

Public Attributes

 ADD_SERIALIZE_METHODS
 

Private Member Functions

unsigned int Hash (unsigned int nHashNum, const std::vector< unsigned char > &vDataToHash) const
 
 CBloomFilter (const unsigned int nElements, const double nFPRate, const unsigned int nTweak)
 

Private Attributes

std::vector< unsigned char > vData
 
bool isFull
 
bool isEmpty
 
unsigned int nHashFuncs
 
unsigned int nTweak
 
unsigned char nFlags
 

Friends

class CRollingBloomFilter
 

Detailed Description

BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transactions we send them.

This allows for significantly more efficient transaction and block downloads.

Because bloom filters are probabilistic, a SPV node can increase the false- positive rate, making us send it transactions which aren't actually its, allowing clients to trade more bandwidth for more privacy by obfuscating which keys are controlled by them.

Definition at line 44 of file bloom.h.

Constructor & Destructor Documentation

CBloomFilter::CBloomFilter ( const unsigned int  nElements,
const double  nFPRate,
const unsigned int  nTweak 
)
private

Definition at line 42 of file bloom.cpp.

CBloomFilter::CBloomFilter ( const unsigned int  nElements,
const double  nFPRate,
const unsigned int  nTweakIn,
unsigned char  nFlagsIn 
)

Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements Note that if the given parameters will result in a filter outside the bounds of the protocol limits, the filter created will be as close to the given parameters as possible within the protocol limits.

The ideal size for a bloom filter with a given number of elements and false positive rate is:

This will apply if nFPRate is very low or nElements is unreasonably high. nTweak is a constant which is added to the seed value passed to the hash function It should generally always be a random value (and is largely only exposed for unit testing) nFlags should be one of the BLOOM_UPDATE_* enums (not _MASK)

  • nElements * log(fp rate) / ln(2)^2 We ignore filter parameters which will create a bloom filter larger than the protocol limits 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 https://en.wikipedia.org/wiki/Bloom_filter for an explanation of these formulas

Definition at line 21 of file bloom.cpp.

CBloomFilter::CBloomFilter ( )
inline

Definition at line 71 of file bloom.h.

Member Function Documentation

void CBloomFilter::clear ( )

Definition at line 115 of file bloom.cpp.

Here is the caller graph for this function:

bool CBloomFilter::contains ( const std::vector< unsigned char > &  vKey) const

Definition at line 85 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool CBloomFilter::contains ( const COutPoint outpoint) const

Definition at line 101 of file bloom.cpp.

Here is the call graph for this function:

bool CBloomFilter::contains ( const uint256 hash) const

Definition at line 109 of file bloom.cpp.

Here is the call graph for this function:

unsigned int CBloomFilter::Hash ( unsigned int  nHashNum,
const std::vector< unsigned char > &  vDataToHash 
) const
inlineprivate

Definition at line 52 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void CBloomFilter::insert ( const std::vector< unsigned char > &  vKey)

Definition at line 58 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void CBloomFilter::insert ( const COutPoint outpoint)

Definition at line 71 of file bloom.cpp.

Here is the call graph for this function:

void CBloomFilter::insert ( const uint256 hash)

Definition at line 79 of file bloom.cpp.

Here is the call graph for this function:

bool CBloomFilter::IsRelevantAndUpdate ( const CTransaction tx)

Also adds any outputs which match the filter to the filter (to match their spending txes)

Definition at line 133 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool CBloomFilter::IsWithinSizeConstraints ( ) const

True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (catch a filter which was just deserialized which was too big)

Definition at line 128 of file bloom.cpp.

Here is the caller graph for this function:

void CBloomFilter::reset ( const unsigned int  nNewTweak)

Definition at line 122 of file bloom.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename Stream , typename Operation >
void CBloomFilter::SerializationOp ( Stream &  s,
Operation  ser_action 
)
inline

Definition at line 76 of file bloom.h.

Here is the call graph for this function:

void CBloomFilter::UpdateEmptyFull ( )

Checks for empty and full filters to avoid wasting cpu.

Definition at line 203 of file bloom.cpp.

Here is the caller graph for this function:

Friends And Related Function Documentation

friend class CRollingBloomFilter
friend

Definition at line 58 of file bloom.h.

Member Data Documentation

CBloomFilter::ADD_SERIALIZE_METHODS

Definition at line 73 of file bloom.h.

bool CBloomFilter::isEmpty
private

Definition at line 49 of file bloom.h.

bool CBloomFilter::isFull
private

Definition at line 48 of file bloom.h.

unsigned char CBloomFilter::nFlags
private

Definition at line 52 of file bloom.h.

unsigned int CBloomFilter::nHashFuncs
private

Definition at line 50 of file bloom.h.

unsigned int CBloomFilter::nTweak
private

Definition at line 51 of file bloom.h.

std::vector<unsigned char> CBloomFilter::vData
private

Definition at line 47 of file bloom.h.


The documentation for this class was generated from the following files: