/bitcoin/src/blockfilter.cpp

Source
// Copyright (c) 2018-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.

#include <mutex>
#include <set>

#include <blockfilter.h>
#include <crypto/siphash.h>
#include <hash.h>
#include <primitives/block.h>
#include <primitives/transaction.h>
#include <script/script.h>
#include <streams.h>
#include <undo.h>
#include <util/golombrice.h>
#include <util/string.h>

using util::Join;

static const std::map<BlockFilterType, std::string> g_filter_types = {
    {BlockFilterType::BASIC, "basic"},
};

uint64_t GCSFilter::HashToRange(const Element& element) const
{
    uint64_t hash = CSipHasher(m_params.m_siphash_k0, m_params.m_siphash_k1)
        .Write(element)
        .Finalize();
    return FastRange64(hash, m_F);
}

std::vector<uint64_t> GCSFilter::BuildHashedSet(const ElementSet& elements) const
{
    std::vector<uint64_t> hashed_elements;
    hashed_elements.reserve(elements.size());
    for (const Element& element : elements) {
        hashed_elements.push_back(HashToRange(element));
    }
    std::sort(hashed_elements.begin(), hashed_elements.end());
    return hashed_elements;
}

GCSFilter::GCSFilter(const Params& params)
    : m_params(params), m_N(0), m_F(0), m_encoded{0}
{}

GCSFilter::GCSFilter(const Params& params, std::vector<unsigned char> encoded_filter, bool skip_decode_check)
    : m_params(params), m_encoded(std::move(encoded_filter))
{
    SpanReader stream{m_encoded};

    uint64_t N = ReadCompactSize(stream);
    m_N = static_cast<uint32_t>(N);
    if (m_N != N) {
        throw std::ios_base::failure("N must be <2^32");
    }
    m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);

    if (skip_decode_check) return;

    // Verify that the encoded filter contains exactly N elements. If it has too much or too little
    // data, a std::ios_base::failure exception will be raised.
    BitStreamReader bitreader{stream};
    for (uint64_t i = 0; i < m_N; ++i) {
        GolombRiceDecode(bitreader, m_params.m_P);
    }
    if (!stream.empty()) {
        throw std::ios_base::failure("encoded_filter contains excess data");
    }
}

GCSFilter::GCSFilter(const Params& params, const ElementSet& elements)
    : m_params(params)
{
    size_t N = elements.size();
    m_N = static_cast<uint32_t>(N);
    if (m_N != N) {
        throw std::invalid_argument("N must be <2^32");
    }
    m_F = static_cast<uint64_t>(m_N) * static_cast<uint64_t>(m_params.m_M);

    VectorWriter stream{m_encoded, 0};

    WriteCompactSize(stream, m_N);

    if (elements.empty()) {
        return;
    }

    BitStreamWriter bitwriter{stream};

    uint64_t last_value = 0;
    for (uint64_t value : BuildHashedSet(elements)) {
        uint64_t delta = value - last_value;
        GolombRiceEncode(bitwriter, m_params.m_P, delta);
        last_value = value;
    }

    bitwriter.Flush();
}

bool GCSFilter::MatchInternal(const uint64_t* element_hashes, size_t size) const
{
    SpanReader stream{m_encoded};

    // Seek forward by size of N
    uint64_t N = ReadCompactSize(stream);
    assert(N == m_N);

    BitStreamReader bitreader{stream};

    uint64_t value = 0;
    size_t hashes_index = 0;
    for (uint32_t i = 0; i < m_N; ++i) {
        uint64_t delta = GolombRiceDecode(bitreader, m_params.m_P);
        value += delta;

        while (true) {
            if (hashes_index == size) {
                return false;
            } else if (element_hashes[hashes_index] == value) {
                return true;
            } else if (element_hashes[hashes_index] > value) {
                break;
            }

            hashes_index++;
        }
    }

    return false;
}

bool GCSFilter::Match(const Element& element) const
{
    uint64_t query = HashToRange(element);
    return MatchInternal(&query, 1);
}

bool GCSFilter::MatchAny(const ElementSet& elements) const
{
    const std::vector<uint64_t> queries = BuildHashedSet(elements);
    return MatchInternal(queries.data(), queries.size());
}

const std::string& BlockFilterTypeName(BlockFilterType filter_type)
{
    static std::string unknown_retval;
    auto it = g_filter_types.find(filter_type);
    return it != g_filter_types.end() ? it->second : unknown_retval;
}

bool BlockFilterTypeByName(const std::string& name, BlockFilterType& filter_type) {
    for (const auto& entry : g_filter_types) {
        if (entry.second == name) {
            filter_type = entry.first;
            return true;
        }
    }
    return false;
}

const std::set<BlockFilterType>& AllBlockFilterTypes()
{
    static std::set<BlockFilterType> types;

    static std::once_flag flag;
    std::call_once(flag, []() {
            for (const auto& entry : g_filter_types) {
                types.insert(entry.first);
            }
        });

    return types;
}

const std::string& ListBlockFilterTypes()
{
    static std::string type_list{Join(g_filter_types, ", ", [](const auto& entry) { return entry.second; })};

    return type_list;
}

static GCSFilter::ElementSet BasicFilterElements(const CBlock& block,
                                                 const CBlockUndo& block_undo)
{
    GCSFilter::ElementSet elements;

    for (const CTransactionRef& tx : block.vtx) {
        for (const CTxOut& txout : tx->vout) {
            const CScript& script = txout.scriptPubKey;
            if (script.empty() || script[0] == OP_RETURN) continue;
            elements.emplace(script.begin(), script.end());
        }
    }

    for (const CTxUndo& tx_undo : block_undo.vtxundo) {
        for (const Coin& prevout : tx_undo.vprevout) {
            const CScript& script = prevout.out.scriptPubKey;
            if (script.empty()) continue;
            elements.emplace(script.begin(), script.end());
        }
    }

    return elements;
}

BlockFilter::BlockFilter(BlockFilterType filter_type, const uint256& block_hash,
                         std::vector<unsigned char> filter, bool skip_decode_check)
    : m_filter_type(filter_type), m_block_hash(block_hash)
{
    GCSFilter::Params params;
    if (!BuildParams(params)) {
        throw std::invalid_argument("unknown filter_type");
    }
    m_filter = GCSFilter(params, std::move(filter), skip_decode_check);
}

BlockFilter::BlockFilter(BlockFilterType filter_type, const CBlock& block, const CBlockUndo& block_undo)
    : m_filter_type(filter_type), m_block_hash(block.GetHash())
{
    GCSFilter::Params params;
    if (!BuildParams(params)) {
        throw std::invalid_argument("unknown filter_type");
    }
    m_filter = GCSFilter(params, BasicFilterElements(block, block_undo));
}

bool BlockFilter::BuildParams(GCSFilter::Params& params) const
{
    switch (m_filter_type) {
    case BlockFilterType::BASIC:
        params.m_siphash_k0 = m_block_hash.GetUint64(0);
        params.m_siphash_k1 = m_block_hash.GetUint64(1);
        params.m_P = BASIC_FILTER_P;
        params.m_M = BASIC_FILTER_M;
        return true;
    case BlockFilterType::INVALID:
        return false;
    }

    return false;
}

uint256 BlockFilter::GetHash() const
{
    return Hash(GetEncodedFilter());
}

uint256 BlockFilter::ComputeHeader(const uint256& prev_header) const
{
    return Hash(GetHash(), prev_header);
}

Coverage Report

Created: 2025-06-10 13:21

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