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