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
|
// Copyright (c) 2018 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 <set>
#include <stdint.h>
#include <vector>
#include <primitives/block.h>
#include <serialize.h>
#include <uint256.h>
#include <undo.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::set<Element> ElementSet;
private:
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
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. */
GCSFilter(uint64_t siphash_k0 = 0, uint64_t siphash_k1 = 0, uint8_t P = 0, uint32_t M = 0);
/** Reconstructs an already-created filter from an encoding. */
GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, uint32_t M,
std::vector<unsigned char> encoded_filter);
/** Builds a new filter from the params and set of elements. */
GCSFilter(uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, uint32_t M,
const ElementSet& elements);
uint8_t GetP() const { return m_P; }
uint32_t GetN() const { return m_N; }
uint32_t GetM() const { return m_M; }
const std::vector<unsigned char>& GetEncoded() const { 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 BlockFilterType : uint8_t
{
BASIC = 0,
};
/**
* Complete block filter struct as defined in BIP 157.
*/
class BlockFilter
{
private:
BlockFilterType m_filter_type;
uint256 m_block_hash;
GCSFilter m_filter;
public:
// 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 GCSFilter& GetFilter() const { return m_filter; }
const std::vector<unsigned char>& GetEncodedFilter() const
{
return m_filter.GetEncoded();
}
};
#endif // BITCOIN_BLOCKFILTER_H
|
