Line data Source code
1 : // Copyright (c) 2018-2019 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 <sstream>
7 : #include <set>
8 :
9 : #include <blockfilter.h>
10 : #include <crypto/siphash.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 :
17 : /// SerType used to serialize parameters in GCS filter encoding.
18 : static constexpr int GCS_SER_TYPE = SER_NETWORK;
19 :
20 : /// Protocol version used to serialize parameters in GCS filter encoding.
21 : static constexpr int GCS_SER_VERSION = 0;
22 :
23 640 : static const std::map<BlockFilterType, std::string> g_filter_types = {
24 640 : {BlockFilterType::BASIC, "basic"},
25 : };
26 :
27 : // Map a value x that is uniformly distributed in the range [0, 2^64) to a
28 : // value uniformly distributed in [0, n) by returning the upper 64 bits of
29 : // x * n.
30 : //
31 : // See: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
32 134778 : static uint64_t MapIntoRange(uint64_t x, uint64_t n)
33 : {
34 : #ifdef __SIZEOF_INT128__
35 134778 : return (static_cast<unsigned __int128>(x) * static_cast<unsigned __int128>(n)) >> 64;
36 : #else
37 : // To perform the calculation on 64-bit numbers without losing the
38 : // result to overflow, split the numbers into the most significant and
39 : // least significant 32 bits and perform multiplication piece-wise.
40 : //
41 : // See: https://stackoverflow.com/a/26855440
42 : uint64_t x_hi = x >> 32;
43 : uint64_t x_lo = x & 0xFFFFFFFF;
44 : uint64_t n_hi = n >> 32;
45 : uint64_t n_lo = n & 0xFFFFFFFF;
46 :
47 : uint64_t ac = x_hi * n_hi;
48 : uint64_t ad = x_hi * n_lo;
49 : uint64_t bc = x_lo * n_hi;
50 : uint64_t bd = x_lo * n_lo;
51 :
52 : uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
53 : uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
54 : return upper64;
55 : #endif
56 : }
57 :
58 134778 : uint64_t GCSFilter::HashToRange(const Element& element) const
59 : {
60 134778 : uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
61 134778 : .Write(element.data(), element.size())
62 134778 : .Finalize();
63 134778 : return MapIntoRange(hash, m_F);
64 : }
65 :
66 4559 : std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
67 : {
68 4559 : std::vector<uint64_t> hashed_elements;
69 4559 : hashed_elements.reserve(elements.size());
70 139217 : for (const Element& element : elements) {
71 134658 : hashed_elements.push_back(HashToRange(element));
72 0 : }
73 4559 : std::sort(hashed_elements.begin(), hashed_elements.end());
74 : return hashed_elements;
75 4559 : }
76 :
77 10552 : GCSFilter::GCSFilter(const Params& params)
78 5276 : : m_params(params), m_N(0), m_F(0), m_encoded{0}
79 10552 : {}
80 :
81 712 : GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter)
82 356 : : m_params(params), m_encoded(std::move(encoded_filter))
83 356 : {
84 356 : VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
85 :
86 356 : uint64_t N = ReadCompactSize(stream);
87 356 : m_N = static_cast<uint32_t>(N);
88 356 : if (m_N != N) {
89 0 : throw std::ios_base::failure("N must be <2^32");
90 : }
91 356 : m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
92 :
93 : // Verify that the encoded filter contains exactly N elements. If it has too much or too little
94 : // data, a std::ios_base::failure exception will be raised.
95 356 : BitStreamReader<VectorReader> bitreader(stream);
96 716 : for (uint64_t i = 0; i < m_N; ++i) {
97 360 : GolombRiceDecode(bitreader, m_params.m_P);
98 : }
99 356 : if (!stream.empty()) {
100 0 : throw std::ios_base::failure("encoded_filter contains excess data");
101 : }
102 712 : }
103 :
104 8920 : GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
105 4460 : : m_params(params)
106 4460 : {
107 4460 : size_t N = elements.size();
108 4460 : m_N = static_cast<uint32_t>(N);
109 4460 : if (m_N != N) {
110 0 : throw std::invalid_argument("N must be <2^32");
111 : }
112 4460 : m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
113 :
114 4460 : CVectorWriter stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
115 :
116 4460 : WriteCompactSize(stream, m_N);
117 :
118 4460 : if (elements.empty()) {
119 1 : return;
120 : }
121 :
122 4459 : BitStreamWriter<CVectorWriter> bitwriter(stream);
123 :
124 : uint64_t last_value = 0;
125 129040 : for (uint64_t value : BuildHashedSet(elements)) {
126 124581 : uint64_t delta = value - last_value;
127 124581 : GolombRiceEncode(bitwriter, m_params.m_P, delta);
128 : last_value = value;
129 : }
130 :
131 4459 : bitwriter.Flush();
132 8920 : }
133 :
134 220 : bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
135 : {
136 220 : VectorReader stream(GCS_SER_TYPE, GCS_SER_VERSION, m_encoded, 0);
137 :
138 : // Seek forward by size of N
139 220 : uint64_t N = ReadCompactSize(stream);
140 220 : assert(N == m_N);
141 :
142 220 : BitStreamReader<VectorReader> bitreader(stream);
143 :
144 : uint64_t value = 0;
145 21624 : size_t hashes_index = 0;
146 21624 : for (uint32_t i = 0; i < m_N; ++i) {
147 21623 : uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
148 21623 : value += delta;
149 :
150 25608 : while (true) {
151 25608 : if (hashes_index == size) {
152 14 : return false;
153 25594 : } else if (element_hashes[hashes_index] == value) {
154 205 : return true;
155 25389 : } else if (element_hashes[hashes_index] > value) {
156 : break;
157 : }
158 :
159 3985 : hashes_index++;
160 : }
161 21404 : }
162 :
163 1 : return false;
164 220 : }
165 :
166 120 : bool GCSFilter::Match(const Element& element) const
167 : {
168 120 : uint64_t query = HashToRange(element);
169 240 : return MatchInternal(&query, 1);
170 120 : }
171 :
172 100 : bool GCSFilter::MatchAny(const ElementSet& elements) const
173 : {
174 100 : const std::vector<uint64_t> queries = BuildHashedSet(elements);
175 100 : return MatchInternal(queries.data(), queries.size());
176 100 : }
177 :
178 14 : const std::string& BlockFilterTypeName(BlockFilterType filter_type)
179 : {
180 14 : static std::string unknown_retval = "";
181 14 : auto it = g_filter_types.find(filter_type);
182 14 : return it != g_filter_types.end() ? it->second : unknown_retval;
183 14 : }
184 :
185 15 : bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
186 30 : for (const auto& entry : g_filter_types) {
187 15 : if (entry.second == name) {
188 13 : filter_type = entry.first;
189 13 : return true;
190 : }
191 2 : }
192 2 : return false;
193 15 : }
194 :
195 4 : const std::set<BlockFilterType>& AllBlockFilterTypes()
196 : {
197 4 : static std::set<BlockFilterType> types;
198 :
199 : static std::once_flag flag;
200 8 : std::call_once(flag, []() {
201 8 : for (auto entry : g_filter_types) {
202 4 : types.insert(entry.first);
203 4 : }
204 4 : });
205 :
206 4 : return types;
207 : }
208 :
209 1010 : const std::string& ListBlockFilterTypes()
210 : {
211 1010 : static std::string type_list;
212 :
213 : static std::once_flag flag;
214 1646 : std::call_once(flag, []() {
215 636 : std::stringstream ret;
216 : bool first = true;
217 1272 : for (auto entry : g_filter_types) {
218 636 : if (!first) ret << ", ";
219 636 : ret << entry.second;
220 : first = false;
221 636 : }
222 636 : type_list = ret.str();
223 636 : });
224 :
225 1010 : return type_list;
226 : }
227 :
228 4447 : static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
229 : const CBlockUndo& block_undo)
230 : {
231 4447 : GCSFilter::ElementSet elements;
232 :
233 8905 : for (const CTransactionRef& tx : block.vtx) {
234 13360 : for (const CTxOut& txout : tx->vout) {
235 8902 : const CScript& script = txout.scriptPubKey;
236 8902 : if (script.empty() || script[0] == OP_RETURN) continue;
237 4465 : elements.emplace(script.begin(), script.end());
238 8930 : }
239 : }
240 :
241 4458 : for (const CTxUndo& tx_undo : block_undo.vtxundo) {
242 39 : for (const Coin& prevout : tx_undo.vprevout) {
243 28 : const CScript& script = prevout.out.scriptPubKey;
244 28 : if (script.empty()) continue;
245 24 : elements.emplace(script.begin(), script.end());
246 48 : }
247 : }
248 :
249 : return elements;
250 4447 : }
251 :
252 710 : BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
253 : std::vector<unsigned char> filter)
254 355 : : m_filter_type(filter_type), m_block_hash(block_hash)
255 355 : {
256 355 : GCSFilter::Params params;
257 355 : if (!BuildParams(params)) {
258 0 : throw std::invalid_argument("unknown filter_type");
259 : }
260 355 : m_filter = GCSFilter(params, std::move(filter));
261 710 : }
262 :
263 8894 : BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
264 4447 : : m_filter_type(filter_type), m_block_hash(block.GetHash())
265 4447 : {
266 4447 : GCSFilter::Params params;
267 4447 : if (!BuildParams(params)) {
268 0 : throw std::invalid_argument("unknown filter_type");
269 : }
270 4447 : m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
271 8894 : }
272 :
273 4803 : bool BlockFilter::BuildParams(GCSFilter::Params& params) const
274 : {
275 4803 : switch (m_filter_type) {
276 : case BlockFilterType::BASIC:
277 4803 : params.m_siphash_k0 = m_block_hash.GetUint64(0);
278 4803 : params.m_siphash_k1 = m_block_hash.GetUint64(1);
279 4803 : params.m_P = BASIC_FILTER_P;
280 4803 : params.m_M = BASIC_FILTER_M;
281 4803 : return true;
282 : case BlockFilterType::INVALID:
283 0 : return false;
284 : }
285 :
286 0 : return false;
287 4803 : }
288 :
289 9338 : uint256 BlockFilter::GetHash() const
290 : {
291 9338 : const std::vector<unsigned char>& data = GetEncodedFilter();
292 :
293 9338 : uint256 result;
294 9338 : CHash256().Write(data).Finalize(result);
295 : return result;
296 9338 : }
297 :
298 4446 : uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
299 : {
300 4446 : const uint256& filter_hash = GetHash();
301 :
302 4446 : uint256 result;
303 8892 : CHash256()
304 4446 : .Write(filter_hash)
305 4446 : .Write(prev_header)
306 4446 : .Finalize(result);
307 : return result;
308 4446 : }
|
