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