Bitcoin ABC  0.22.13
P2P Digital Currency
bloom.h
Go to the documentation of this file.
1 // Copyright (c) 2012-2016 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 
10 #include <cstdint>
11 #include <vector>
12 
13 class COutPoint;
14 class CTransaction;
15 class uint256;
16 
18 static const uint32_t MAX_BLOOM_FILTER_SIZE = 36000; // bytes
19 static const uint32_t MAX_HASH_FUNCS = 50;
20 
25 enum bloomflags {
28  // Only adds outpoints to the filter if the output is a
29  // pay-to-pubkey/pay-to-multisig script
32 };
33 
45 class CBloomFilter {
46 private:
47  std::vector<uint8_t> vData;
48  uint32_t nHashFuncs;
49  uint32_t nTweak;
50  uint8_t nFlags;
51 
52  uint32_t Hash(uint32_t nHashNum,
53  const std::vector<uint8_t> &vDataToHash) const;
54 
55 public:
67  CBloomFilter(const uint32_t nElements, const double nFPRate,
68  const uint32_t nTweak, uint8_t nFlagsIn);
69  CBloomFilter() : nHashFuncs(0), nTweak(0), nFlags(0) {}
70 
72 
73  template <typename Stream, typename Operation>
74  inline void SerializationOp(Stream &s, Operation ser_action) {
75  READWRITE(vData);
76  READWRITE(nHashFuncs);
77  READWRITE(nTweak);
78  READWRITE(nFlags);
79  }
80 
81  void insert(const std::vector<uint8_t> &vKey);
82  void insert(const COutPoint &outpoint);
83  void insert(const uint256 &hash);
84 
85  bool contains(const std::vector<uint8_t> &vKey) const;
86  bool contains(const COutPoint &outpoint) const;
87  bool contains(const uint256 &hash) const;
88 
92  bool IsWithinSizeConstraints() const;
93 
97  bool MatchAndInsertOutputs(const CTransaction &tx);
98 
101  bool MatchInputs(const CTransaction &tx);
102 
107  return MatchAndInsertOutputs(tx) || MatchInputs(tx);
108  }
109 };
110 
126 public:
127  CRollingBloomFilter(const uint32_t nElements, const double nFPRate);
128 
129  void insert(const std::vector<uint8_t> &vKey);
130  void insert(const uint256 &hash);
131  bool contains(const std::vector<uint8_t> &vKey) const;
132  bool contains(const uint256 &hash) const;
133 
134  void reset();
135 
136 private:
140  std::vector<uint64_t> data;
141  uint32_t nTweak;
143 };
144 
145 #endif // BITCOIN_BLOOM_H
uint32_t nHashFuncs
Definition: bloom.h:48
bloomflags
First two bits of nFlags control how much IsRelevantAndUpdate actually updates.
Definition: bloom.h:25
ADD_SERIALIZE_METHODS
Definition: bloom.h:71
bool IsRelevantAndUpdate(const CTransaction &tx)
Check if the transaction is relevant for any reason.
Definition: bloom.h:106
BloomFilter is a probabilistic filter which SPV clients provide so that we can filter the transaction...
Definition: bloom.h:45
bool contains(const std::vector< uint8_t > &vKey) const
Definition: bloom.cpp:78
RollingBloomFilter is a probabilistic "keep track of most recently inserted" set. ...
Definition: bloom.h:125
void insert(const std::vector< uint8_t > &vKey)
Definition: bloom.cpp:53
std::vector< uint8_t > vData
Definition: bloom.h:47
static const uint32_t MAX_HASH_FUNCS
Definition: bloom.h:19
uint32_t Hash(uint32_t nHashNum, const std::vector< uint8_t > &vDataToHash) const
Definition: bloom.cpp:45
uint32_t nTweak
Definition: bloom.h:141
uint8_t nFlags
Definition: bloom.h:50
bool MatchAndInsertOutputs(const CTransaction &tx)
Scans output scripts for matches and adds those outpoints to the filter for spend detection...
Definition: bloom.cpp:110
uint32_t nTweak
Definition: bloom.h:49
CBloomFilter()
Definition: bloom.h:69
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:22
std::vector< uint64_t > data
Definition: bloom.h:140
256-bit opaque blob.
Definition: uint256.h:120
int nEntriesThisGeneration
Definition: bloom.h:138
static const uint32_t MAX_BLOOM_FILTER_SIZE
20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
Definition: bloom.h:18
The basic transaction that is broadcasted on the network and contained in blocks. ...
Definition: transaction.h:211
bool MatchInputs(const CTransaction &tx)
Scan inputs to see if the spent outpoints are a match, or the input scripts contain matching elements...
Definition: bloom.cpp:159
#define READWRITE(...)
Definition: serialize.h:191
void SerializationOp(Stream &s, Operation ser_action)
Definition: bloom.h:74
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:105
int nEntriesPerGeneration
Definition: bloom.h:137