Bitcoin ABC  0.28.12
P2P Digital Currency
Public Member Functions | Private Member Functions | Private Attributes | 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 uint32_t nElements, const double nFPRate, const uint32_t nTweak, uint8_t nFlagsIn)
 Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements. More...
 
 CBloomFilter ()
 
 SERIALIZE_METHODS (CBloomFilter, obj)
 
void insert (const std::vector< uint8_t > &vKey)
 
void insert (const COutPoint &outpoint)
 
void insert (const uint256 &hash)
 
bool contains (const std::vector< uint8_t > &vKey) const
 
bool contains (const COutPoint &outpoint) const
 
bool contains (const uint256 &hash) const
 
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 MatchAndInsertOutputs (const CTransaction &tx)
 Scans output scripts for matches and adds those outpoints to the filter for spend detection. More...
 
bool MatchInputs (const CTransaction &tx)
 Scan inputs to see if the spent outpoints are a match, or the input scripts contain matching elements. More...
 
bool IsRelevantAndUpdate (const CTransaction &tx)
 Check if the transaction is relevant for any reason. More...
 

Private Member Functions

uint32_t Hash (uint32_t nHashNum, const std::vector< uint8_t > &vDataToHash) const
 

Private Attributes

std::vector< uint8_t > vData
 
uint32_t nHashFuncs
 
uint32_t nTweak
 
uint8_t nFlags
 

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 45 of file bloom.h.

Constructor & Destructor Documentation

◆ CBloomFilter() [1/2]

CBloomFilter::CBloomFilter ( const uint32_t  nElements,
const double  nFPRate,
const uint32_t  nTweakIn,
uint8_t  nFlagsIn 
)

Creates a new bloom filter which will provide the given fp rate when filled with the given number of elements.

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

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. 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 36 of file bloom.cpp.

◆ CBloomFilter() [2/2]

CBloomFilter::CBloomFilter ( )
inline

Definition at line 69 of file bloom.h.

Member Function Documentation

◆ contains() [1/3]

bool CBloomFilter::contains ( const COutPoint outpoint) const

Definition at line 94 of file bloom.cpp.

Here is the call graph for this function:

◆ contains() [2/3]

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

Definition at line 79 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ contains() [3/3]

bool CBloomFilter::contains ( const uint256 hash) const

Definition at line 101 of file bloom.cpp.

Here is the call graph for this function:

◆ Hash()

uint32_t CBloomFilter::Hash ( uint32_t  nHashNum,
const std::vector< uint8_t > &  vDataToHash 
) const
inlineprivate

Definition at line 46 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert() [1/3]

void CBloomFilter::insert ( const COutPoint outpoint)

Definition at line 67 of file bloom.cpp.

Here is the call graph for this function:

◆ insert() [2/3]

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

Definition at line 54 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert() [3/3]

void CBloomFilter::insert ( const uint256 hash)

Definition at line 74 of file bloom.cpp.

Here is the call graph for this function:

◆ IsRelevantAndUpdate()

bool CBloomFilter::IsRelevantAndUpdate ( const CTransaction tx)
inline

Check if the transaction is relevant for any reason.

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

Definition at line 100 of file bloom.h.

Here is the call graph for this function:

◆ IsWithinSizeConstraints()

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 106 of file bloom.cpp.

◆ MatchAndInsertOutputs()

bool CBloomFilter::MatchAndInsertOutputs ( const CTransaction tx)

Scans output scripts for matches and adds those outpoints to the filter for spend detection.

Returns true if any output matched, or the txid matches.

Definition at line 111 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ MatchInputs()

bool CBloomFilter::MatchInputs ( const CTransaction tx)

Scan inputs to see if the spent outpoints are a match, or the input scripts contain matching elements.

Definition at line 161 of file bloom.cpp.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ SERIALIZE_METHODS()

CBloomFilter::SERIALIZE_METHODS ( CBloomFilter  ,
obj   
)
inline

Definition at line 71 of file bloom.h.

Member Data Documentation

◆ nFlags

uint8_t CBloomFilter::nFlags
private

Definition at line 50 of file bloom.h.

◆ nHashFuncs

uint32_t CBloomFilter::nHashFuncs
private

Definition at line 48 of file bloom.h.

◆ nTweak

uint32_t CBloomFilter::nTweak
private

Definition at line 49 of file bloom.h.

◆ vData

std::vector<uint8_t> CBloomFilter::vData
private

Definition at line 47 of file bloom.h.


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