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 
20 /**
21  * This implements a Golomb-coded set as defined in BIP 158. It is a
22  * compact, probabilistic data structure for testing set membership.
23  */
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;  //!< Golomb-Rice coding parameter
35         uint32_t m_M;  //!< Inverse false positive rate
36 
37         Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 1)
m_siphash_k0Params38             : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P), m_M(M)
39         {}
40     };
41 
42 private:
43     Params m_params;
44     uint32_t m_N;  //!< Number of elements in the filter
45     uint64_t m_F;  //!< Range of element hashes, F = N * M
46     std::vector<unsigned char> m_encoded;
47 
48     /** Hash a data element to an integer in the range [0, N * M). */
49     uint64_t HashToRange(const Element& element) const;
50 
51     std::vector<uint64_t> BuildHashedSet(const ElementSet& elements) const;
52 
53     /** Helper method used to implement Match and MatchAny */
54     bool MatchInternal(const uint64_t* sorted_element_hashes, size_t size) const;
55 
56 public:
57 
58     /** Constructs an empty filter. */
59     explicit GCSFilter(const Params& params = Params());
60 
61     /** Reconstructs an already-created filter from an encoding. */
62     GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter);
63 
64     /** Builds a new filter from the params and set of elements. */
65     GCSFilter(const Params& params, const ElementSet& elements);
66 
GetN()67     uint32_t GetN() const { return m_N; }
GetParams()68     const Params& GetParams() const { return m_params; }
GetEncoded()69     const std::vector<unsigned char>& GetEncoded() const { return m_encoded; }
70 
71     /**
72      * Checks if the element may be in the set. False positives are possible
73      * with probability 1/M.
74      */
75     bool Match(const Element& element) const;
76 
77     /**
78      * Checks if any of the given elements may be in the set. False positives
79      * are possible with probability 1/M per element checked. This is more
80      * efficient that checking Match on multiple elements separately.
81      */
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 
94 /** Get the human-readable name for a filter type. Returns empty string for unknown types. */
95 const std::string& BlockFilterTypeName(BlockFilterType filter_type);
96 
97 /** Find a filter type by its human-readable name. */
98 bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type);
99 
100 /** Get a list of known filter types. */
101 const std::set<BlockFilterType>& AllBlockFilterTypes();
102 
103 /** Get a comma-separated list of known filter type names. */
104 const std::string& ListBlockFilterTypes();
105 
106 /**
107  * Complete block filter struct as defined in BIP 157. Serialization matches
108  * payload of "cfilter" messages.
109  */
110 class BlockFilter
111 {
112 private:
113     BlockFilterType m_filter_type = BlockFilterType::INVALID;
114     uint256 m_block_hash;
115     GCSFilter m_filter;
116 
117     bool BuildParams(GCSFilter::Params& params) const;
118 
119 public:
120 
121     BlockFilter() = default;
122 
123     //! Reconstruct a BlockFilter from parts.
124     BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
125                 std::vector<unsigned char> filter);
126 
127     //! Construct a new BlockFilter of the specified type from a block.
128     BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo);
129 
GetFilterType()130     BlockFilterType GetFilterType() const { return m_filter_type; }
GetBlockHash()131     const uint256& GetBlockHash() const { return m_block_hash; }
GetFilter()132     const GCSFilter& GetFilter() const { return m_filter; }
133 
GetEncodedFilter()134     const std::vector<unsigned char>& GetEncodedFilter() const
135     {
136         return m_filter.GetEncoded();
137     }
138 
139     //! Compute the filter hash.
140     uint256 GetHash() const;
141 
142     //! Compute the filter header given the previous one.
143     uint256 ComputeHeader(const uint256& prev_header) const;
144 
145     template <typename Stream>
Serialize(Stream & s)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>
Unserialize(Stream & s)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
172