blockfilter.h raw
1 // Copyright (c) 2018-present 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 <string_view>
14 #include <unordered_set>
15 #include <utility>
16 #include <vector>
17
18 #include <attributes.h>
19 #include <uint256.h>
20 #include <util/bytevectorhash.h>
21
22 class CBlock;
23 class CBlockUndo;
24
25 /**
26 * This implements a Golomb-coded set as defined in BIP 158. It is a
27 * compact, probabilistic data structure for testing set membership.
28 */
29 class GCSFilter
30 {
31 public:
32 typedef std::vector<unsigned char> Element;
33 typedef std::unordered_set<Element, ByteVectorHash> ElementSet;
34
35 struct Params
36 {
37 uint64_t m_siphash_k0;
38 uint64_t m_siphash_k1;
39 uint8_t m_P; //!< Golomb-Rice coding parameter
40 uint32_t m_M; //!< Inverse false positive rate
41
42 Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)
43 : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M)
44 {}
45 };
46
47 private:
48 Params m_params;
49 uint32_t m_N; //!< Number of elements in the filter
50 uint64_t m_F; //!< Range of element hashes, F = N * M
51 std::vector<unsigned char> m_encoded;
52
53 /** Hash a data element to an integer in the range [0, N * M). */
54 uint64_t HashToRange(const Element& element) const;
55
56 std::vector<uint64_t> BuildHashedSet(const ElementSet& elements) const;
57
58 /** Helper method used to implement Match and MatchAny */
59 bool MatchInternal(const uint64_t* sorted_element_hashes, size_t size) const;
60
61 public:
62
63 /** Constructs an empty filter. */
64 explicit GCSFilter(const Params& params = Params());
65
66 /** Reconstructs an already-created filter from an encoding. */
67 GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check);
68
69 /** Builds a new filter from the params and set of elements. */
70 GCSFilter(const Params& params, const ElementSet& elements);
71
72 uint32_t GetN() const { return m_N; }
73 const Params& GetParams() const LIFETIMEBOUND { return m_params; }
74 const std::vector<unsigned char>& GetEncoded() const LIFETIMEBOUND { return m_encoded; }
75
76 /**
77 * Checks if the element may be in the set. False positives are possible
78 * with probability 1/M.
79 */
80 bool Match(const Element& element) const;
81
82 /**
83 * Checks if any of the given elements may be in the set. False positives
84 * are possible with probability 1/M per element checked. This is more
85 * efficient that checking Match on multiple elements separately.
86 */
87 bool MatchAny(const ElementSet& elements) const;
88 };
89
90 constexpr uint8_t BASIC_FILTER_P = 19;
91 constexpr uint32_t BASIC_FILTER_M = 784931;
92
93 enum class BlockFilterType : uint8_t
94 {
95 BASIC = 0,
96 INVALID = 255,
97 };
98
99 /** Get the human-readable name for a filter type. Returns empty string for unknown types. */
100 const std::string& BlockFilterTypeName(BlockFilterType filter_type);
101
102 /** Find a filter type by its human-readable name. */
103 bool BlockFilterTypeByName(std::string_view name, BlockFilterType& filter_type);
104
105 /** Get a list of known filter types. */
106 const std::set<BlockFilterType>& AllBlockFilterTypes();
107
108 /** Get a comma-separated list of known filter type names. */
109 const std::string& ListBlockFilterTypes();
110
111 /**
112 * Complete block filter struct as defined in BIP 157. Serialization matches
113 * payload of "cfilter" messages.
114 */
115 class BlockFilter
116 {
117 private:
118 BlockFilterType m_filter_type = BlockFilterType::INVALID;
119 uint256 m_block_hash;
120 GCSFilter m_filter;
121
122 bool BuildParams(GCSFilter::Params& params) const;
123
124 public:
125
126 BlockFilter() = default;
127
128 //! Reconstruct a BlockFilter from parts.
129 BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
130 std::vector<unsigned char> filter, bool skip_decode_check);
131
132 //! Construct a new BlockFilter of the specified type from a block.
133 BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);
134
135 BlockFilterType GetFilterType() const { return m_filter_type; }
136 const uint256& GetBlockHash() const LIFETIMEBOUND { return m_block_hash; }
137 const GCSFilter& GetFilter() const LIFETIMEBOUND { return m_filter; }
138
139 const std::vector<unsigned char>& GetEncodedFilter() const LIFETIMEBOUND
140 {
141 return m_filter.GetEncoded();
142 }
143
144 //! Compute the filter hash.
145 uint256 GetHash() const;
146
147 //! Compute the filter header given the previous one.
148 uint256 ComputeHeader(const uint256& prev_header) const;
149
150 template <typename Stream>
151 void Serialize(Stream& s) const {
152 s << static_cast<uint8_t>(m_filter_type)
153 << m_block_hash
154 << m_filter.GetEncoded();
155 }
156
157 template <typename Stream>
158 void Unserialize(Stream& s) {
159 std::vector<unsigned char> encoded_filter;
160 uint8_t filter_type;
161
162 s >> filter_type
163 >> m_block_hash
164 >> encoded_filter;
165
166 m_filter_type = static_cast<BlockFilterType>(filter_type);
167
168 GCSFilter::Params params;
169 if (!BuildParams(params)) {
170 throw std::ios_base::failure("unknown filter_type");
171 }
172 m_filter = GCSFilter(params, std::move(encoded_filter), /*skip_decode_check=*/false);
173 }
174 };
175
176 #endif // BITCOIN_BLOCKFILTER_H
177