Branch data Line data Source code
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 <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 : 2580 : 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 : 1590 : Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)
43 [ + - ]: 1021 : : 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 [ + - ]: 1 : uint32_t GetN() const { return m_N; }
73 : : const Params& GetParams() const LIFETIMEBOUND { return m_params; }
74 [ + - ]: 1034 : 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 [ + - ]: 902 : 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 : 451 : 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 [ + - + - ]: 112 : BlockFilterType GetFilterType() const { return m_filter_type; }
[ - + ]
136 [ + - + - ]: 112 : const uint256& GetBlockHash() const LIFETIMEBOUND { return m_block_hash; }
[ # # ]
137 [ # # ]: 0 : const GCSFilter& GetFilter() const LIFETIMEBOUND { return m_filter; }
138 : :
139 : 1026 : const std::vector<unsigned char>& GetEncodedFilter() const LIFETIMEBOUND
140 : : {
141 [ + - + - ]: 1136 : 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 : 1 : void Serialize(Stream& s) const {
152 : 1 : s << static_cast<uint8_t>(m_filter_type)
153 : 1 : << m_block_hash
154 : 1 : << m_filter.GetEncoded();
155 : 1 : }
156 : :
157 : : template <typename Stream>
158 : 1 : void Unserialize(Stream& s) {
159 [ + - ]: 1 : std::vector<unsigned char> encoded_filter;
160 : : uint8_t filter_type;
161 : :
162 : 1 : s >> filter_type
163 [ + - + - ]: 1 : >> m_block_hash
164 : 1 : >> encoded_filter;
165 : :
166 : 1 : m_filter_type = static_cast<BlockFilterType>(filter_type);
167 : :
168 : 1 : GCSFilter::Params params;
169 [ + - - + ]: 1 : if (!BuildParams(params)) {
170 [ # # ]: 0 : throw std::ios_base::failure("unknown filter_type");
171 : : }
172 [ + - ]: 1 : m_filter = GCSFilter(params, std::move(encoded_filter), /*skip_decode_check=*/false);
173 : 1 : }
174 : : };
175 : :
176 : : #endif // BITCOIN_BLOCKFILTER_H
|
