Bitcoin Core  22.99.0
P2P Digital Currency
bloom.h
Go to the documentation of this file.
1 // Copyright (c) 2012-2020 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_BLOOM_H
6 #define BITCOIN_BLOOM_H
7 
8 #include <serialize.h>
9 #include <span.h>
10 
11 #include <vector>
12 
13 class COutPoint;
14 class CTransaction;
15 
17 static constexpr unsigned int MAX_BLOOM_FILTER_SIZE = 36000; // bytes
18 static constexpr unsigned int MAX_HASH_FUNCS = 50;
19 
25 {
28  // Only adds outpoints to the filter if the output is a pay-to-pubkey/pay-to-multisig script
31 };
32 
45 {
46 private:
47  std::vector<unsigned char> vData;
48  unsigned int nHashFuncs;
49  unsigned int nTweak;
50  unsigned char nFlags;
51 
52  unsigned int Hash(unsigned int nHashNum, Span<const unsigned char> vDataToHash) const;
53 
54 public:
64  CBloomFilter(const unsigned int nElements, const double nFPRate, const unsigned int nTweak, unsigned char nFlagsIn);
66 
67  SERIALIZE_METHODS(CBloomFilter, obj) { READWRITE(obj.vData, obj.nHashFuncs, obj.nTweak, obj.nFlags); }
68 
70  void insert(const COutPoint& outpoint);
71 
72  bool contains(Span<const unsigned char> vKey) const;
73  bool contains(const COutPoint& outpoint) const;
74 
77  bool IsWithinSizeConstraints() const;
78 
80  bool IsRelevantAndUpdate(const CTransaction& tx);
81 };
82 
109 {
110 public:
111  CRollingBloomFilter(const unsigned int nElements, const double nFPRate);
112 
114  bool contains(Span<const unsigned char> vKey) const;
115 
116  void reset();
117 
118 private:
122  std::vector<uint64_t> data;
123  unsigned int nTweak;
125 };
126 
127 #endif // BITCOIN_BLOOM_H
CRollingBloomFilter::insert
void insert(Span< const unsigned char > vKey)
Definition: bloom.cpp:202
CRollingBloomFilter::nGeneration
int nGeneration
Definition: bloom.h:121
CBloomFilter::contains
bool contains(Span< const unsigned char > vKey) const
Definition: bloom.cpp:67
CBloomFilter::IsWithinSizeConstraints
bool IsWithinSizeConstraints() const
True if the size is <= MAX_BLOOM_FILTER_SIZE and the number of hash functions is <= MAX_HASH_FUNCS (c...
Definition: bloom.cpp:88
CBloomFilter
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:44
CBloomFilter::nTweak
unsigned int nTweak
Definition: bloom.h:49
CRollingBloomFilter::CRollingBloomFilter
CRollingBloomFilter(const unsigned int nElements, const double nFPRate)
Definition: bloom.cpp:161
CRollingBloomFilter::nTweak
unsigned int nTweak
Definition: bloom.h:123
BLOOM_UPDATE_P2PUBKEY_ONLY
@ BLOOM_UPDATE_P2PUBKEY_ONLY
Definition: bloom.h:29
MAX_HASH_FUNCS
static constexpr unsigned int MAX_HASH_FUNCS
Definition: bloom.h:18
CBloomFilter::vData
std::vector< unsigned char > vData
Definition: bloom.h:47
CTransaction
The basic transaction that is broadcasted on the network and contained in blocks.
Definition: transaction.h:259
Span
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:92
span.h
CRollingBloomFilter::reset
void reset()
Definition: bloom.cpp:247
CBloomFilter::CBloomFilter
CBloomFilter()
Definition: bloom.h:65
READWRITE
#define READWRITE(...)
Definition: serialize.h:147
CBloomFilter::SERIALIZE_METHODS
SERIALIZE_METHODS(CBloomFilter, obj)
Definition: bloom.h:67
bloomflags
bloomflags
First two bits of nFlags control how much IsRelevantAndUpdate actually updates The remaining bits are...
Definition: bloom.h:24
BLOOM_UPDATE_MASK
@ BLOOM_UPDATE_MASK
Definition: bloom.h:30
CRollingBloomFilter::nHashFuncs
int nHashFuncs
Definition: bloom.h:124
CRollingBloomFilter::nEntriesThisGeneration
int nEntriesThisGeneration
Definition: bloom.h:120
CRollingBloomFilter::data
std::vector< uint64_t > data
Definition: bloom.h:122
CBloomFilter::insert
void insert(Span< const unsigned char > vKey)
Definition: bloom.cpp:48
CBloomFilter::nFlags
unsigned char nFlags
Definition: bloom.h:50
BLOOM_UPDATE_ALL
@ BLOOM_UPDATE_ALL
Definition: bloom.h:27
CBloomFilter::nHashFuncs
unsigned int nHashFuncs
Definition: bloom.h:48
serialize.h
COutPoint
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:26
CBloomFilter::IsRelevantAndUpdate
bool IsRelevantAndUpdate(const CTransaction &tx)
Also adds any outputs which match the filter to the filter (to match their spending txes)
Definition: bloom.cpp:93
CRollingBloomFilter
RollingBloomFilter is a probabilistic "keep track of most recently inserted" set.
Definition: bloom.h:108
BLOOM_UPDATE_NONE
@ BLOOM_UPDATE_NONE
Definition: bloom.h:26
CRollingBloomFilter::nEntriesPerGeneration
int nEntriesPerGeneration
Definition: bloom.h:119
CRollingBloomFilter::contains
bool contains(Span< const unsigned char > vKey) const
Definition: bloom.cpp:233
CBloomFilter::Hash
unsigned int Hash(unsigned int nHashNum, Span< const unsigned char > vDataToHash) const
Definition: bloom.cpp:42
MAX_BLOOM_FILTER_SIZE
static constexpr unsigned int MAX_BLOOM_FILTER_SIZE
20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
Definition: bloom.h:17