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