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