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