blockfilter.cpp raw
1 // Copyright (c) 2018-present 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 #include <string_view>
8
9 #include <blockfilter.h>
10 #include <crypto/siphash.h>
11 #include <hash.h>
12 #include <primitives/block.h>
13 #include <primitives/transaction.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 };
25
26 uint64_t GCSFilter::HashToRange(const Element& element) const
27 {
28 uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
29 .Write(element)
30 .Finalize();
31 return FastRange64(hash, m_F);
32 }
33
34 std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
35 {
36 std::vector<uint64_t> hashed_elements;
37 hashed_elements.reserve(elements.size());
38 for (const Element& element : elements) {
39 hashed_elements.push_back(HashToRange(element));
40 }
41 std::sort(hashed_elements.begin(), hashed_elements.end());
42 return hashed_elements;
43 }
44
45 GCSFilter::GCSFilter(const Params& params)
46 : m_params(params), m_N(0), m_F(0), m_encoded{0}
47 {}
48
49 GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check)
50 : m_params(params), m_encoded(std::move(encoded_filter))
51 {
52 SpanReader stream{m_encoded};
53
54 uint64_t N = ReadCompactSize(stream);
55 m_N = static_cast<uint32_t>(N);
56 if (m_N != N) {
57 throw std::ios_base::failure("N must be <2^32");
58 }
59 m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
60
61 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 BitStreamReader bitreader{stream};
66 for (uint64_t i = 0; i < m_N; ++i) {
67 GolombRiceDecode(bitreader, m_params.m_P);
68 }
69 if (!stream.empty()) {
70 throw std::ios_base::failure("encoded_filter contains excess data");
71 }
72 }
73
74 GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
75 : m_params(params)
76 {
77 size_t N = elements.size();
78 m_N = static_cast<uint32_t>(N);
79 if (m_N != N) {
80 throw std::invalid_argument("N must be <2^32");
81 }
82 m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);
83
84 VectorWriter stream{m_encoded, 0};
85
86 WriteCompactSize(stream, m_N);
87
88 if (elements.empty()) {
89 return;
90 }
91
92 BitStreamWriter bitwriter{stream};
93
94 uint64_t last_value = 0;
95 for (uint64_t value : BuildHashedSet(elements)) {
96 uint64_t delta = value - last_value;
97 GolombRiceEncode(bitwriter, m_params.m_P, delta);
98 last_value = value;
99 }
100
101 bitwriter.Flush();
102 }
103
104 bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
105 {
106 SpanReader stream{m_encoded};
107
108 // Seek forward by size of N
109 uint64_t N = ReadCompactSize(stream);
110 assert(N == m_N);
111
112 BitStreamReader bitreader{stream};
113
114 uint64_t value = 0;
115 size_t hashes_index = 0;
116 for (uint32_t i = 0; i < m_N; ++i) {
117 uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
118 value += delta;
119
120 while (true) {
121 if (hashes_index == size) {
122 return false;
123 } else if (element_hashes[hashes_index] == value) {
124 return true;
125 } else if (element_hashes[hashes_index] > value) {
126 break;
127 }
128
129 hashes_index++;
130 }
131 }
132
133 return false;
134 }
135
136 bool GCSFilter::Match(const Element& element) const
137 {
138 uint64_t query = HashToRange(element);
139 return MatchInternal(&query, 1);
140 }
141
142 bool GCSFilter::MatchAny(const ElementSet& elements) const
143 {
144 const std::vector<uint64_t> queries = BuildHashedSet(elements);
145 return MatchInternal(queries.data(), queries.size());
146 }
147
148 const std::string& BlockFilterTypeName(BlockFilterType filter_type)
149 {
150 static std::string unknown_retval;
151 auto it = g_filter_types.find(filter_type);
152 return it != g_filter_types.end() ? it->second : unknown_retval;
153 }
154
155 bool BlockFilterTypeByName(std::string_view name, BlockFilterType& filter_type)
156 {
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 BasicFilterElements(const CBlock& block,
188 const CBlockUndo& block_undo)
189 {
190 GCSFilter::ElementSet elements;
191
192 for (const CTransactionRef& tx : block.vtx) {
193 for (const CTxOut& txout : tx->vout) {
194 const CScript& script = txout.scriptPubKey;
195 if (script.empty() || script[0] == OP_RETURN) continue;
196 elements.emplace(script.begin(), script.end());
197 }
198 }
199
200 for (const CTxUndo& tx_undo : block_undo.vtxundo) {
201 for (const Coin& prevout : tx_undo.vprevout) {
202 const CScript& script = prevout.out.scriptPubKey;
203 if (script.empty()) continue;
204 elements.emplace(script.begin(), script.end());
205 }
206 }
207
208 return elements;
209 }
210
211 BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
212 std::vector<unsigned char> filter, bool skip_decode_check)
213 : m_filter_type(filter_type), m_block_hash(block_hash)
214 {
215 GCSFilter::Params params;
216 if (!BuildParams(params)) {
217 throw std::invalid_argument("unknown filter_type");
218 }
219 m_filter = GCSFilter(params, std::move(filter), skip_decode_check);
220 }
221
222 BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
223 : m_filter_type(filter_type), m_block_hash(block.GetHash())
224 {
225 GCSFilter::Params params;
226 if (!BuildParams(params)) {
227 throw std::invalid_argument("unknown filter_type");
228 }
229 m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
230 }
231
232 bool BlockFilter::BuildParams(GCSFilter::Params& params) const
233 {
234 switch (m_filter_type) {
235 case BlockFilterType::BASIC:
236 params.m_siphash_k0 = m_block_hash.GetUint64(0);
237 params.m_siphash_k1 = m_block_hash.GetUint64(1);
238 params.m_P = BASIC_FILTER_P;
239 params.m_M = BASIC_FILTER_M;
240 return true;
241 case BlockFilterType::INVALID:
242 return false;
243 }
244
245 return false;
246 }
247
248 uint256 BlockFilter::GetHash() const
249 {
250 return Hash(GetEncodedFilter());
251 }
252
253 uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
254 {
255 return Hash(GetHash(), prev_header);
256 }
257