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