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