Bitcoin Core  27.99.0
P2P Digital Currency
blockfilter.h
Go to the documentation of this file.
1 // Copyright (c) 2018-2022 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 <cstddef>
9 #include <cstdint>
10 #include <ios>
11 #include <set>
12 #include <string>
13 #include <unordered_set>
14 #include <utility>
15 #include <vector>
16 
17 #include <attributes.h>
18 #include <uint256.h>
19 #include <util/bytevectorhash.h>
20 
21 class CBlock;
22 class CBlockUndo;
23 
28 class GCSFilter
29 {
30 public:
31  typedef std::vector<unsigned char> Element;
32  typedef std::unordered_set<Element, ByteVectorHash> ElementSet;
33 
34  struct Params
35  {
36  uint64_t m_siphash_k0;
37  uint64_t m_siphash_k1;
38  uint8_t m_P;
39  uint32_t m_M;
40 
41  Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)
42  : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M)
43  {}
44  };
45 
46 private:
48  uint32_t m_N;
49  uint64_t m_F;
50  std::vector<unsigned char> m_encoded;
51 
53  uint64_t HashToRange(const Element& element) const;
54 
55  std::vector<uint64_t> BuildHashedSet(const ElementSet& elements) const;
56 
58  bool MatchInternal(const uint64_t* sorted_element_hashes, size_t size) const;
59 
60 public:
61 
63  explicit GCSFilter(const Params& params = Params());
64 
66  GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check);
67 
69  GCSFilter(const Params& params, const ElementSet& elements);
70 
71  uint32_t GetN() const { return m_N; }
72  const Params& GetParams() const LIFETIMEBOUND { return m_params; }
73  const std::vector<unsigned char>& GetEncoded() const LIFETIMEBOUND { return m_encoded; }
74 
79  bool Match(const Element& element) const;
80 
86  bool MatchAny(const ElementSet& elements) const;
87 };
88 
89 constexpr uint8_t BASIC_FILTER_P = 19;
90 constexpr uint32_t BASIC_FILTER_M = 784931;
91 
92 enum class BlockFilterType : uint8_t
93 {
94  BASIC = 0,
95  INVALID = 255,
96 };
97 
99 const std::string& BlockFilterTypeName(BlockFilterType filter_type);
100 
102 bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type);
103 
105 const std::set<BlockFilterType>& AllBlockFilterTypes();
106 
108 const std::string& ListBlockFilterTypes();
109 
115 {
116 private:
120 
121  bool BuildParams(GCSFilter::Params& params) const;
122 
123 public:
124 
125  BlockFilter() = default;
126 
128  BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
129  std::vector<unsigned char> filter, bool skip_decode_check);
130 
132  BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);
133 
135  const uint256& GetBlockHash() const LIFETIMEBOUND { return m_block_hash; }
136  const GCSFilter& GetFilter() const LIFETIMEBOUND { return m_filter; }
137 
138  const std::vector<unsigned char>& GetEncodedFilter() const LIFETIMEBOUND
139  {
140  return m_filter.GetEncoded();
141  }
142 
144  uint256 GetHash() const;
145 
147  uint256 ComputeHeader(const uint256& prev_header) const;
148 
149  template <typename Stream>
150  void Serialize(Stream& s) const {
151  s << static_cast<uint8_t>(m_filter_type)
152  << m_block_hash
153  << m_filter.GetEncoded();
154  }
155 
156  template <typename Stream>
157  void Unserialize(Stream& s) {
158  std::vector<unsigned char> encoded_filter;
159  uint8_t filter_type;
160 
161  s >> filter_type
162  >> m_block_hash
163  >> encoded_filter;
164 
165  m_filter_type = static_cast<BlockFilterType>(filter_type);
166 
167  GCSFilter::Params params;
168  if (!BuildParams(params)) {
169  throw std::ios_base::failure("unknown filter_type");
170  }
171  m_filter = GCSFilter(params, std::move(encoded_filter), /*skip_decode_check=*/false);
172  }
173 };
174 
175 #endif // BITCOIN_BLOCKFILTER_H
#define LIFETIMEBOUND
Definition: attributes.h:16
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
BlockFilterType
Definition: blockfilter.h:93
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:89
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:90
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
const CChainParams & Params()
Return the currently selected parameters.
Complete block filter struct as defined in BIP 157.
Definition: blockfilter.h:115
GCSFilter m_filter
Definition: blockfilter.h:119
const GCSFilter & GetFilter() const LIFETIMEBOUND
Definition: blockfilter.h:136
void Serialize(Stream &s) const
Definition: blockfilter.h:150
bool BuildParams(GCSFilter::Params &params) const
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
BlockFilterType GetFilterType() const
Definition: blockfilter.h:134
BlockFilterType m_filter_type
Definition: blockfilter.h:117
BlockFilter()=default
uint256 GetHash() const
Compute the filter hash.
void Unserialize(Stream &s)
Definition: blockfilter.h:157
uint256 m_block_hash
Definition: blockfilter.h:118
const uint256 & GetBlockHash() const LIFETIMEBOUND
Definition: blockfilter.h:135
const std::vector< unsigned char > & GetEncodedFilter() const LIFETIMEBOUND
Definition: blockfilter.h:138
Definition: block.h:69
Undo information for a CBlock.
Definition: undo.h:63
This implements a Golomb-coded set as defined in BIP 158.
Definition: blockfilter.h:29
std::vector< unsigned char > Element
Definition: blockfilter.h:31
uint64_t m_F
Range of element hashes, F = N * M.
Definition: blockfilter.h:49
bool MatchInternal(const uint64_t *sorted_element_hashes, size_t size) const
Helper method used to implement Match and MatchAny.
std::unordered_set< Element, ByteVectorHash > ElementSet
Definition: blockfilter.h:32
uint64_t HashToRange(const Element &element) const
Hash a data element to an integer in the range [0, N * M).
Definition: blockfilter.cpp:23
const std::vector< unsigned char > & GetEncoded() const LIFETIMEBOUND
Definition: blockfilter.h:73
uint32_t m_N
Number of elements in the filter.
Definition: blockfilter.h:48
bool Match(const Element &element) const
Checks if the element may be in the set.
uint32_t GetN() const
Definition: blockfilter.h:71
GCSFilter(const Params &params=Params())
Constructs an empty filter.
Definition: blockfilter.cpp:42
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
Definition: blockfilter.cpp:31
Params m_params
Definition: blockfilter.h:47
std::vector< unsigned char > m_encoded
Definition: blockfilter.h:50
const Params & GetParams() const LIFETIMEBOUND
Definition: blockfilter.h:72
256-bit opaque blob.
Definition: uint256.h:106
const char * name
Definition: rest.cpp:48
Params(uint64_t siphash_k0=0, uint64_t siphash_k1=0, uint8_t P=0, uint32_t M=1)
Definition: blockfilter.h:41
uint32_t m_M
Inverse false positive rate.
Definition: blockfilter.h:39
uint64_t m_siphash_k1
Definition: blockfilter.h:37
uint8_t m_P
Golomb-Rice coding parameter.
Definition: blockfilter.h:38
uint64_t m_siphash_k0
Definition: blockfilter.h:36