Bitcoin Core  0.20.99
P2P Digital Currency
blockfilter.h
Go to the documentation of this file.
1 // Copyright (c) 2018-2019 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_BLOCKFILTER_H
6 #define BITCOIN_BLOCKFILTER_H
7 
8 #include <stdint.h>
9 #include <string>
10 #include <set>
11 #include <unordered_set>
12 #include <vector>
13 
14 #include <primitives/block.h>
15 #include <serialize.h>
16 #include <uint256.h>
17 #include <undo.h>
18 #include <util/bytevectorhash.h>
19 
24 class GCSFilter
25 {
26 public:
27  typedef std::vector<unsigned char> Element;
28  typedef std::unordered_set<Element, ByteVectorHash> ElementSet;
29 
30  struct Params
31  {
32  uint64_t m_siphash_k0;
33  uint64_t m_siphash_k1;
34  uint8_t m_P;
35  uint32_t m_M;
36 
37  Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)
38  : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M)
39  {}
40  };
41 
42 private:
44  uint32_t m_N;
45  uint64_t m_F;
46  std::vector<unsigned char> m_encoded;
47 
49  uint64_t HashToRange(const Element& element) const;
50 
51  std::vector<uint64_t> BuildHashedSet(const ElementSet& elements) const;
52 
54  bool MatchInternal(const uint64_t* sorted_element_hashes, size_t size) const;
55 
56 public:
57 
59  explicit GCSFilter(const Params& params = Params());
60 
62  GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter);
63 
65  GCSFilter(const Params& params, const ElementSet& elements);
66 
67  uint32_t GetN() const { return m_N; }
68  const Params& GetParams() const { return m_params; }
69  const std::vector<unsigned char>& GetEncoded() const { return m_encoded; }
70 
75  bool Match(const Element& element) const;
76 
82  bool MatchAny(const ElementSet& elements) const;
83 };
84 
85 constexpr uint8_t BASIC_FILTER_P = 19;
86 constexpr uint32_t BASIC_FILTER_M = 784931;
87 
88 enum class BlockFilterType : uint8_t
89 {
90  BASIC = 0,
91  INVALID = 255,
92 };
93 
95 const std::string& BlockFilterTypeName(BlockFilterType filter_type);
96 
98 bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type);
99 
101 const std::set<BlockFilterType>& AllBlockFilterTypes();
102 
104 const std::string& ListBlockFilterTypes();
105 
111 {
112 private:
116 
117  bool BuildParams(GCSFilter::Params& params) const;
118 
119 public:
120 
121  BlockFilter() = default;
122 
124  BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
125  std::vector<unsigned char> filter);
126 
128  BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);
129 
130  BlockFilterType GetFilterType() const { return m_filter_type; }
131  const uint256& GetBlockHash() const { return m_block_hash; }
132  const GCSFilter& GetFilter() const { return m_filter; }
133 
134  const std::vector<unsigned char>& GetEncodedFilter() const
135  {
136  return m_filter.GetEncoded();
137  }
138 
140  uint256 GetHash() const;
141 
143  uint256 ComputeHeader(const uint256& prev_header) const;
144 
145  template <typename Stream>
146  void Serialize(Stream& s) const {
147  s << static_cast<uint8_t>(m_filter_type)
148  << m_block_hash
149  << m_filter.GetEncoded();
150  }
151 
152  template <typename Stream>
153  void Unserialize(Stream& s) {
154  std::vector<unsigned char> encoded_filter;
155  uint8_t filter_type;
156 
157  s >> filter_type
158  >> m_block_hash
159  >> encoded_filter;
160 
161  m_filter_type = static_cast<BlockFilterType>(filter_type);
162 
163  GCSFilter::Params params;
164  if (!BuildParams(params)) {
165  throw std::ios_base::failure("unknown filter_type");
166  }
167  m_filter = GCSFilter(params, std::move(encoded_filter));
168  }
169 };
170 
171 #endif // BITCOIN_BLOCKFILTER_H
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:86
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
Definition: block.h:62
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:85
const GCSFilter & GetFilter() const
Definition: blockfilter.h:132
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
Definition: blockfilter.cpp:66
GCSFilter m_filter
Definition: blockfilter.h:115
bool Match(const Element &element) const
Checks if the element may be in the set.
GCSFilter(const Params &params=Params())
Constructs an empty filter.
Definition: blockfilter.cpp:77
void Serialize(Stream &s) const
Definition: blockfilter.h:146
bool MatchInternal(const uint64_t *sorted_element_hashes, size_t size) const
Helper method used to implement Match and MatchAny.
BlockFilterType
Definition: blockfilter.h:88
const std::vector< unsigned char > & GetEncodedFilter() const
Definition: blockfilter.h:134
const char * name
Definition: rest.cpp:41
Complete block filter struct as defined in BIP 157.
Definition: blockfilter.h:110
const uint256 & GetBlockHash() const
Definition: blockfilter.h:131
uint64_t HashToRange(const Element &element) const
Hash a data element to an integer in the range [0, N * M).
Definition: blockfilter.cpp:58
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
This implements a Golomb-coded set as defined in BIP 158.
Definition: blockfilter.h:24
std::unordered_set< Element, ByteVectorHash > ElementSet
Definition: blockfilter.h:28
uint32_t m_M
Inverse false positive rate.
Definition: blockfilter.h:35
uint64_t m_siphash_k0
Definition: blockfilter.h:32
uint8_t m_P
Golomb-Rice coding parameter.
Definition: blockfilter.h:34
256-bit opaque blob.
Definition: uint256.h:124
Params(uint64_t siphash_k0=0, uint64_t siphash_k1=0, uint8_t P=0, uint32_t M=1)
Definition: blockfilter.h:37
Undo information for a CBlock.
Definition: undo.h:63
uint32_t GetN() const
Definition: blockfilter.h:67
uint256 m_block_hash
Definition: blockfilter.h:114
Params m_params
Definition: blockfilter.h:43
std::vector< unsigned char > Element
Definition: blockfilter.h:27
uint64_t m_siphash_k1
Definition: blockfilter.h:33
uint32_t m_N
Number of elements in the filter.
Definition: blockfilter.h:44
const Params & GetParams() const
Definition: blockfilter.h:68
BlockFilterType GetFilterType() const
Definition: blockfilter.h:130
uint64_t m_F
Range of element hashes, F = N * M.
Definition: blockfilter.h:45
std::vector< unsigned char > m_encoded
Definition: blockfilter.h:46
const std::vector< unsigned char > & GetEncoded() const
Definition: blockfilter.h:69
void Unserialize(Stream &s)
Definition: blockfilter.h:153