Bitcoin ABC 0.30.7
P2P Digital Currency
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
blockfilter.h
Go to the documentation of this file.
1// Copyright (c) 2018 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 <primitives/block.h>
10#include <serialize.h>
11#include <uint256.h>
12#include <undo.h>
13#include <util/bytevectorhash.h>
14
15#include <cstdint>
16#include <set>
17#include <string>
18#include <unordered_set>
19#include <vector>
20
25class GCSFilter {
26public:
27 typedef std::vector<uint8_t> Element;
28 typedef std::unordered_set<Element, ByteVectorHash> ElementSet;
29
30 struct Params {
31 uint64_t m_siphash_k0;
32 uint64_t m_siphash_k1;
33 uint8_t m_P;
34 uint32_t m_M;
35
36 Params(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0,
37 uint32_t M = 1)
38 : m_siphash_k0(siphash_k0), m_siphash_k1(siphash_k1), m_P(P),
39 m_M(M) {}
40 };
41
42private:
44 uint32_t m_N;
45 uint64_t m_F;
46 std::vector<uint8_t> m_encoded;
47
49 uint64_t HashToRange(const Element &element) const;
50
51 std::vector<uint64_t> BuildHashedSet(const ElementSet &elements) const;
52
54 bool MatchInternal(const uint64_t *sorted_element_hashes,
55 size_t size) const;
56
57public:
59 explicit GCSFilter(const Params &params = Params());
60
62 GCSFilter(const Params &params, std::vector<uint8_t> encoded_filter);
63
65 GCSFilter(const Params &params, const ElementSet &elements);
66
67 uint32_t GetN() const { return m_N; }
68 const Params &GetParams() const { return m_params; }
69 const std::vector<uint8_t> &GetEncoded() const { return m_encoded; }
70
75 bool Match(const Element &element) const;
76
82 bool MatchAny(const ElementSet &elements) const;
83};
84
85constexpr uint8_t BASIC_FILTER_P = 19;
86constexpr uint32_t BASIC_FILTER_M = 784931;
87
88enum class BlockFilterType : uint8_t {
89 BASIC = 0,
90 INVALID = 255,
91};
92
95const std::string &BlockFilterTypeName(BlockFilterType filter_type);
96
98bool BlockFilterTypeByName(const std::string &name,
99 BlockFilterType &filter_type);
100
102const std::set<BlockFilterType> &AllBlockFilterTypes();
103
105const std::string &ListBlockFilterTypes();
106
112private:
116
117 bool BuildParams(GCSFilter::Params &params) const;
118
119public:
120 BlockFilter() = default;
121
123 BlockFilter(BlockFilterType filter_type, const BlockHash &block_hash,
124 std::vector<uint8_t> filter);
125
127 BlockFilter(BlockFilterType filter_type, const CBlock &block,
128 const CBlockUndo &block_undo);
129
131 const BlockHash &GetBlockHash() const { return m_block_hash; }
132 const GCSFilter &GetFilter() const { return m_filter; }
133
134 const std::vector<uint8_t> &GetEncodedFilter() const {
135 return m_filter.GetEncoded();
136 }
137
139 uint256 GetHash() const;
140
142 uint256 ComputeHeader(const uint256 &prev_header) const;
143
144 template <typename Stream> void Serialize(Stream &s) const {
145 s << static_cast<uint8_t>(m_filter_type) << m_block_hash
146 << m_filter.GetEncoded();
147 }
148
149 template <typename Stream> void Unserialize(Stream &s) {
150 std::vector<uint8_t> encoded_filter;
151 uint8_t filter_type;
152
153 s >> filter_type >> m_block_hash >> encoded_filter;
154
155 m_filter_type = static_cast<BlockFilterType>(filter_type);
156
157 GCSFilter::Params params;
158 if (!BuildParams(params)) {
159 throw std::ios_base::failure("unknown filter_type");
160 }
161 m_filter = GCSFilter(params, std::move(encoded_filter));
162 }
163};
164
165#endif // BITCOIN_BLOCKFILTER_H
BlockFilterType
Definition: blockfilter.h:88
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:85
const std::string & BlockFilterTypeName(BlockFilterType filter_type)
Get the human-readable name for a filter type.
const std::set< BlockFilterType > & AllBlockFilterTypes()
Get a list of known filter types.
const std::string & ListBlockFilterTypes()
Get a comma-separated list of known filter type names.
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:86
bool BlockFilterTypeByName(const std::string &name, BlockFilterType &filter_type)
Find a filter type by its human-readable name.
const CChainParams & Params()
Return the currently selected parameters.
Definition: chainparams.cpp:19
Complete block filter struct as defined in BIP 157.
Definition: blockfilter.h:111
GCSFilter m_filter
Definition: blockfilter.h:115
void Serialize(Stream &s) const
Definition: blockfilter.h:144
bool BuildParams(GCSFilter::Params &params) const
uint256 ComputeHeader(const uint256 &prev_header) const
Compute the filter header given the previous one.
BlockFilterType GetFilterType() const
Definition: blockfilter.h:130
const BlockHash & GetBlockHash() const
Definition: blockfilter.h:131
const GCSFilter & GetFilter() const
Definition: blockfilter.h:132
BlockFilterType m_filter_type
Definition: blockfilter.h:113
BlockHash m_block_hash
Definition: blockfilter.h:114
BlockFilter()=default
uint256 GetHash() const
Compute the filter hash.
const std::vector< uint8_t > & GetEncodedFilter() const
Definition: blockfilter.h:134
void Unserialize(Stream &s)
Definition: blockfilter.h:149
Definition: block.h:60
Undo information for a CBlock.
Definition: undo.h:73
This implements a Golomb-coded set as defined in BIP 158.
Definition: blockfilter.h:25
uint64_t m_F
Range of element hashes, F = N * M.
Definition: blockfilter.h:45
bool MatchInternal(const uint64_t *sorted_element_hashes, size_t size) const
Helper method used to implement Match and MatchAny.
std::unordered_set< Element, ByteVectorHash > ElementSet
Definition: blockfilter.h:28
uint64_t HashToRange(const Element &element) const
Hash a data element to an integer in the range [0, N * M).
Definition: blockfilter.cpp:28
std::vector< uint8_t > Element
Definition: blockfilter.h:27
uint32_t m_N
Number of elements in the filter.
Definition: blockfilter.h:44
bool Match(const Element &element) const
Checks if the element may be in the set.
uint32_t GetN() const
Definition: blockfilter.h:67
GCSFilter(const Params &params=Params())
Constructs an empty filter.
Definition: blockfilter.cpp:46
bool MatchAny(const ElementSet &elements) const
Checks if any of the given elements may be in the set.
std::vector< uint64_t > BuildHashedSet(const ElementSet &elements) const
Definition: blockfilter.cpp:36
Params m_params
Definition: blockfilter.h:43
std::vector< uint8_t > m_encoded
Definition: blockfilter.h:46
const std::vector< uint8_t > & GetEncoded() const
Definition: blockfilter.h:69
const Params & GetParams() const
Definition: blockfilter.h:68
256-bit opaque blob.
Definition: uint256.h:129
static unsigned char elements[DATACOUNT][DATALEN]
Definition: tests_impl.h:36
const char * name
Definition: rest.cpp:47
A BlockHash is a unqiue identifier for a block.
Definition: blockhash.h:13
Params(uint64_t siphash_k0=0, uint64_t siphash_k1=0, uint8_t P=0, uint32_t M=1)
Definition: blockfilter.h:36
uint32_t m_M
Inverse false positive rate.
Definition: blockfilter.h:34
uint64_t m_siphash_k1
Definition: blockfilter.h:32
uint8_t m_P
Golomb-Rice coding parameter.
Definition: blockfilter.h:33
uint64_t m_siphash_k0
Definition: blockfilter.h:31