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 : : #include <mutex>
6 : : #include <set>
7 : :
8 : : #include <blockfilter.h>
9 : : #include <crypto/siphash.h>
10 : : #include <hash.h>
11 : : #include <primitives/block.h>
12 : : #include <primitives/transaction.h>
13 : : #include <script/script.h>
14 : : #include <streams.h>
15 : : #include <undo.h>
16 : : #include <util/golombrice.h>
17 : : #include <util/string.h>
18 : :
19 [ + - ]: 2 : static const std::map<BlockFilterType, std::string> g_filter_types = {
20 [ + - ]: 2 : {BlockFilterType::BASIC, "basic"},
21 : : };
22 : :
23 : 0 : uint64_t GCSFilter::HashToRange(const Element& element) const
24 : : {
25 : 0 : uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
26 : 0 : .Write(element)
27 : 0 : .Finalize();
28 : 0 : return FastRange64(hash, m_F);
29 : : }
30 : :
31 : 0 : std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
32 : : {
33 : 0 : std::vector<uint64_t> hashed_elements;
34 [ # # ]: 0 : hashed_elements.reserve(elements.size());
35 [ # # ]: 0 : for (const Element& element : elements) {
36 [ # # ][ # # ]: 0 : hashed_elements.push_back(HashToRange(element));
37 : : }
38 [ # # ]: 0 : std::sort(hashed_elements.begin(), hashed_elements.end());
39 : 0 : return hashed_elements;
40 [ # # ]: 0 : }
41 : :
42 : 0 : GCSFilter::GCSFilter(const Params& params)
43 [ # # ]: 0 : : m_params(params), m_N(0), m_F(0), m_encoded{0}
44 : 0 : {}
45 : :
46 : 0 : GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check)
47 : 0 : : m_params(params), m_encoded(std::move(encoded_filter))
48 : : {
49 [ # # ][ # # ]: 0 : SpanReader stream{m_encoded};
50 : :
51 [ # # ]: 0 : uint64_t N = ReadCompactSize(stream);
52 : 0 : m_N = static_cast<uint32_t>(N);
53 [ # # ]: 0 : if (m_N != N) {
54 [ # # ]: 0 : throw std::ios_base::failure("N must be <2^32");
55 : : }
56 : 0 : m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
57 : :
58 [ # # ]: 0 : if (skip_decode_check) return;
59 : :
60 : : // Verify that the encoded filter contains exactly N elements. If it has too much or too little
61 : : // data, a std::ios_base::failure exception will be raised.
62 [ # # ]: 0 : BitStreamReader bitreader{stream};
63 [ # # ]: 0 : for (uint64_t i = 0; i < m_N; ++i) {
64 [ # # ]: 0 : GolombRiceDecode(bitreader, m_params.m_P);
65 : 0 : }
66 [ # # ][ # # ]: 0 : if (!stream.empty()) {
67 [ # # ]: 0 : throw std::ios_base::failure("encoded_filter contains excess data");
68 : : }
69 : 0 : }
70 : :
71 : 0 : GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
72 : 0 : : m_params(params)
73 : : {
74 : 0 : size_t N = elements.size();
75 : 0 : m_N = static_cast<uint32_t>(N);
76 [ # # ]: 0 : if (m_N != N) {
77 [ # # ][ # # ]: 0 : throw std::invalid_argument("N must be <2^32");
78 : : }
79 : 0 : m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
80 : :
81 [ # # ]: 0 : VectorWriter stream{m_encoded, 0};
82 : :
83 [ # # ]: 0 : WriteCompactSize(stream, m_N);
84 : :
85 [ # # ]: 0 : if (elements.empty()) {
86 : 0 : return;
87 : : }
88 : :
89 [ # # ]: 0 : BitStreamWriter bitwriter{stream};
90 : :
91 : 0 : uint64_t last_value = 0;
92 [ # # ][ # # ]: 0 : for (uint64_t value : BuildHashedSet(elements)) {
93 : 0 : uint64_t delta = value - last_value;
94 [ # # ]: 0 : GolombRiceEncode(bitwriter, m_params.m_P, delta);
95 : 0 : last_value = value;
96 : : }
97 : :
98 [ # # ]: 0 : bitwriter.Flush();
99 : 0 : }
100 : :
101 : 0 : bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
102 : : {
103 : 0 : SpanReader stream{m_encoded};
104 : :
105 : : // Seek forward by size of N
106 : 0 : uint64_t N = ReadCompactSize(stream);
107 [ # # ]: 0 : assert(N == m_N);
108 : :
109 : 0 : BitStreamReader bitreader{stream};
110 : :
111 : 0 : uint64_t value = 0;
112 : 0 : size_t hashes_index = 0;
113 [ # # ]: 0 : for (uint32_t i = 0; i < m_N; ++i) {
114 : 0 : uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
115 : 0 : value += delta;
116 : :
117 : 0 : while (true) {
118 [ # # ]: 0 : if (hashes_index == size) {
119 : 0 : return false;
120 [ # # ]: 0 : } else if (element_hashes[hashes_index] == value) {
121 : 0 : return true;
122 [ # # ]: 0 : } else if (element_hashes[hashes_index] > value) {
123 : 0 : break;
124 : : }
125 : :
126 : 0 : hashes_index++;
127 : : }
128 : 0 : }
129 : :
130 : 0 : return false;
131 : 0 : }
132 : :
133 : 0 : bool GCSFilter::Match(const Element& element) const
134 : : {
135 : 0 : uint64_t query = HashToRange(element);
136 : 0 : return MatchInternal(&query, 1);
137 : : }
138 : :
139 : 0 : bool GCSFilter::MatchAny(const ElementSet& elements) const
140 : : {
141 : 0 : const std::vector<uint64_t> queries = BuildHashedSet(elements);
142 [ # # ]: 0 : return MatchInternal(queries.data(), queries.size());
143 : 0 : }
144 : :
145 : 0 : const std::string& BlockFilterTypeName(BlockFilterType filter_type)
146 : : {
147 [ # # ][ # # ]: 0 : static std::string unknown_retval;
148 : 0 : auto it = g_filter_types.find(filter_type);
149 [ # # ]: 0 : return it != g_filter_types.end() ? it->second : unknown_retval;
150 : : }
151 : :
152 : 0 : bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
153 [ # # ]: 0 : for (const auto& entry : g_filter_types) {
154 [ # # ]: 0 : if (entry.second == name) {
155 : 0 : filter_type = entry.first;
156 : 0 : return true;
157 : : }
158 : : }
159 : 0 : return false;
160 : 0 : }
161 : :
162 : 0 : const std::set<BlockFilterType>& AllBlockFilterTypes()
163 : : {
164 [ # # ][ # # ]: 0 : static std::set<BlockFilterType> types;
165 : :
166 : : static std::once_flag flag;
167 : 0 : std::call_once(flag, []() {
168 [ # # ]: 0 : for (const auto& entry : g_filter_types) {
169 : 0 : types.insert(entry.first);
170 : : }
171 : 0 : });
172 : :
173 : 0 : return types;
174 : : }
175 : :
176 : 0 : const std::string& ListBlockFilterTypes()
177 : : {
178 [ # # ][ # # ]: 0 : static std::string type_list{Join(g_filter_types, ", ", [](const auto& entry) { return entry.second; })};
[ # # ]
179 : :
180 : 0 : return type_list;
181 : 0 : }
182 : :
183 : 0 : static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
184 : : const CBlockUndo& block_undo)
185 : : {
186 : 0 : GCSFilter::ElementSet elements;
187 : :
188 [ # # ]: 0 : for (const CTransactionRef& tx : block.vtx) {
189 [ # # ]: 0 : for (const CTxOut& txout : tx->vout) {
190 : 0 : const CScript& script = txout.scriptPubKey;
191 [ # # ][ # # ]: 0 : if (script.empty() || script[0] == OP_RETURN) continue;
[ # # ][ # # ]
192 [ # # ][ # # ]: 0 : elements.emplace(script.begin(), script.end());
[ # # ]
193 : : }
194 : : }
195 : :
196 [ # # ]: 0 : for (const CTxUndo& tx_undo : block_undo.vtxundo) {
197 [ # # ]: 0 : for (const Coin& prevout : tx_undo.vprevout) {
198 : 0 : const CScript& script = prevout.out.scriptPubKey;
199 [ # # ][ # # ]: 0 : if (script.empty()) continue;
200 [ # # ][ # # ]: 0 : elements.emplace(script.begin(), script.end());
[ # # ]
201 : : }
202 : : }
203 : :
204 : 0 : return elements;
205 [ # # ]: 0 : }
206 : :
207 : 0 : BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
208 : : std::vector<unsigned char> filter, bool skip_decode_check)
209 : 0 : : m_filter_type(filter_type), m_block_hash(block_hash)
210 : : {
211 [ # # ]: 0 : GCSFilter::Params params;
212 [ # # ][ # # ]: 0 : if (!BuildParams(params)) {
213 [ # # ][ # # ]: 0 : throw std::invalid_argument("unknown filter_type");
214 : : }
215 [ # # ]: 0 : m_filter = GCSFilter(params, std::move(filter), skip_decode_check);
216 : 0 : }
217 : :
218 : 0 : BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
219 : 0 : : m_filter_type(filter_type), m_block_hash(block.GetHash())
220 : : {
221 [ # # ]: 0 : GCSFilter::Params params;
222 [ # # ][ # # ]: 0 : if (!BuildParams(params)) {
223 [ # # ][ # # ]: 0 : throw std::invalid_argument("unknown filter_type");
224 : : }
225 [ # # ][ # # ]: 0 : m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
226 : 0 : }
227 : :
228 : 0 : bool BlockFilter::BuildParams(GCSFilter::Params& params) const
229 : : {
230 [ # # # ]: 0 : switch (m_filter_type) {
231 : : case BlockFilterType::BASIC:
232 : 0 : params.m_siphash_k0 = m_block_hash.GetUint64(0);
233 : 0 : params.m_siphash_k1 = m_block_hash.GetUint64(1);
234 : 0 : params.m_P = BASIC_FILTER_P;
235 : 0 : params.m_M = BASIC_FILTER_M;
236 : 0 : return true;
237 : : case BlockFilterType::INVALID:
238 : 0 : return false;
239 : : }
240 : :
241 : 0 : return false;
242 : 0 : }
243 : :
244 : 0 : uint256 BlockFilter::GetHash() const
245 : : {
246 : 0 : return Hash(GetEncodedFilter());
247 : : }
248 : :
249 : 0 : uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
250 : : {
251 : 0 : return Hash(GetHash(), prev_header);
252 : : }
|
