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
20using util::Join;
21
22static const std::map<BlockFilterType, std::string> g_filter_types = {
23    {BlockFilterType::BASIC, "basic"},
24};
25
26uint64_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
34std::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
45GCSFilter::GCSFilter(const Params& params)
46    : m_params(params), m_N(0), m_F(0), m_encoded{0}
47{}
48
49GCSFilter::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
74GCSFilter::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
104bool 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
136bool GCSFilter::Match(const Element& element) const
137{
138    uint64_t query = HashToRange(element);
139    return MatchInternal(&query, 1);
140}
141
142bool 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
148const 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
155bool 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
166const 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
180const 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
187static 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
211BlockFilter::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
222BlockFilter::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
232bool 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
248uint256 BlockFilter::GetHash() const
249{
250    return Hash(GetEncodedFilter());