Skip to content

Commit 2ee4faf

Browse files
kevkevinpalinstagibbsvasild
committed
test: add fuzz test for private broadcast
Co-authored-by: Greg Sanders <gsanders87@gmail.com> Co-authored-by: Vasil Dimov <vd@FreeBSD.org>
1 parent 08b7c61 commit 2ee4faf

3 files changed

Lines changed: 212 additions & 5 deletions

File tree

‎src/test/fuzz/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,7 @@ add_executable(fuzz
9494
pow.cpp
9595
prevector.cpp
9696
primitives_transaction.cpp
97+
private_broadcast.cpp
9798
process_message.cpp
9899
process_messages.cpp
99100
protocol.cpp

‎src/test/fuzz/private_broadcast.cpp‎

Lines changed: 202 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,202 @@
1+
// Copyright (c) 2025-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 <consensus/tx_check.h>
6+
#include <consensus/validation.h>
7+
#include <net.h>
8+
#include <primitives/transaction.h>
9+
#include <private_broadcast.h>
10+
#include <test/fuzz/FuzzedDataProvider.h>
11+
#include <test/fuzz/fuzz.h>
12+
#include <test/fuzz/util.h>
13+
#include <test/fuzz/util/net.h>
14+
#include <test/util/setup_common.h>
15+
#include <test/util/time.h>
16+
#include <util/overflow.h>
17+
#include <util/time.h>
18+
19+
#include <unordered_set>
20+
21+
struct CTransactionRefHash {
22+
size_t operator()(const CTransactionRef& tx) const
23+
{
24+
return static_cast<size_t>(tx->GetWitnessHash().ToUint256().GetUint64(0));
25+
}
26+
};
27+
28+
struct CTransactionRefComp {
29+
bool operator()(const CTransactionRef& a, const CTransactionRef& b) const
30+
{
31+
return a->GetWitnessHash() == b->GetWitnessHash();
32+
}
33+
};
34+
35+
FUZZ_TARGET(private_broadcast)
36+
{
37+
SeedRandomStateForTest(SeedRand::ZEROS);
38+
FuzzedDataProvider fdp(buffer.data(), buffer.size());
39+
FakeNodeClock clock_ctx{ConsumeTime(fdp)};
40+
41+
PrivateBroadcast pb;
42+
43+
// Random transaction that the test generated and passed to Add(). Trimmed when Remove() is called.
44+
// The values are the number of times a transaction was picked for sending.
45+
std::unordered_map<CTransactionRef, size_t, CTransactionRefHash, CTransactionRefComp> transactions;
46+
47+
// Ids of nodes that were passed to PickTxForSend(). Trimmed when Remove() is called.
48+
std::unordered_set<NodeId> nodes_sent_to;
49+
50+
// A subset of `nodes_sent_to`, node ids passed to NodeConfirmedReception(). Trimmed when Remove() is called.
51+
std::unordered_set<NodeId> nodes_that_confirmed_reception;
52+
53+
NodeId next_nodeid{0}; // Generate unique node ids.
54+
55+
const auto ExistentOrNewNodeId = [&next_nodeid, &fdp](){
56+
if (next_nodeid == 0 || fdp.ConsumeBool()) {
57+
return next_nodeid++;
58+
}
59+
return fdp.ConsumeIntegralInRange<NodeId>(0, next_nodeid - 1);
60+
};
61+
62+
LIMITED_WHILE(fdp.ConsumeBool(), 10000) {
63+
CallOneOf(
64+
fdp,
65+
[&] { // Add()
66+
CTransactionRef tx;
67+
bool from_transactions{false};
68+
if (transactions.empty() || fdp.ConsumeBool()) {
69+
tx = MakeTransactionRef(ConsumeTransaction(fdp, std::nullopt));
70+
} else {
71+
tx = PickIterator(fdp, transactions)->first;
72+
from_transactions = true;
73+
}
74+
if (pb.Add(tx)) {
75+
Assert(!from_transactions);
76+
transactions.emplace(tx, 0);
77+
}
78+
},
79+
[&] { // Remove()
80+
if (transactions.empty()) {
81+
return;
82+
}
83+
const auto transactions_it{PickIterator(fdp, transactions)};
84+
const CTransactionRef& tx{transactions_it->first};
85+
86+
size_t num_nodes_that_confirmed_tx{0};
87+
88+
// Remove relevant entries from nodes_sent_to[] and nodes_that_confirmed_reception[] if any.
89+
for (auto it = nodes_sent_to.begin(); it != nodes_sent_to.end();) {
90+
const NodeId nodeid{*it};
91+
const auto opt_tx_for_node{pb.GetTxForNode(nodeid)};
92+
if (opt_tx_for_node.has_value() && opt_tx_for_node.value() == tx) {
93+
it = nodes_sent_to.erase(it);
94+
if (nodes_that_confirmed_reception.erase(nodeid) > 0) {
95+
++num_nodes_that_confirmed_tx;
96+
}
97+
} else {
98+
++it;
99+
}
100+
}
101+
102+
const auto opt_num_confirmed{pb.Remove(tx)};
103+
104+
Assert(opt_num_confirmed.has_value());
105+
Assert(opt_num_confirmed.value() == num_nodes_that_confirmed_tx);
106+
Assert(!pb.Remove(tx).has_value());
107+
transactions.erase(transactions_it);
108+
},
109+
[&] { // PickTxForSend()
110+
// Only give pristine node ids to PickTxForSend() as required.
111+
const NodeId will_send_to_nodeid{next_nodeid++};
112+
const CService will_send_to_address{ConsumeService(fdp)};
113+
114+
const auto opt_tx{pb.PickTxForSend(will_send_to_nodeid, will_send_to_address)};
115+
116+
if (opt_tx.has_value()) {
117+
Assert(transactions.contains(opt_tx.value()));
118+
119+
// "Number of times picked for sending" is the primary key in Priority's comparison
120+
// (fewest sends = highest priority), so PickTxForSend() must return a transaction
121+
// with the minimum send count of any in the queue. Ties are broken by state we
122+
// don't model, so only check this key.
123+
const size_t min_picked{std::ranges::min_element(
124+
transactions, {}, [](const auto& el) { return el.second; })->second};
125+
const auto picked_it{transactions.find(opt_tx.value())};
126+
Assert(picked_it != transactions.end());
127+
Assert(picked_it->second == min_picked); // picked the least-sent transaction
128+
++picked_it->second; // PickTxForSend() recorded exactly one send
129+
130+
const auto& [_, inserted]{nodes_sent_to.emplace(will_send_to_nodeid)};
131+
Assert(inserted);
132+
} else {
133+
Assert(transactions.empty());
134+
}
135+
},
136+
[&] { // GetTxForNode()
137+
const NodeId nodeid{ExistentOrNewNodeId()};
138+
139+
const auto opt_tx{pb.GetTxForNode(nodeid)};
140+
141+
if (nodes_sent_to.contains(nodeid)) {
142+
Assert(opt_tx.has_value());
143+
Assert(transactions.contains(opt_tx.value()));
144+
} else {
145+
Assert(!opt_tx.has_value());
146+
}
147+
},
148+
[&] { // NodeConfirmedReception()
149+
const NodeId nodeid{ExistentOrNewNodeId()};
150+
151+
pb.NodeConfirmedReception(nodeid);
152+
153+
if (nodes_sent_to.contains(nodeid)) {
154+
// nodeid was previously passed to PickTxForSend(), so NodeConfirmedReception()
155+
// must have changed the internal state. Remember this to later check that
156+
// DidNodeConfirmReception() works correctly.
157+
nodes_that_confirmed_reception.emplace(nodeid);
158+
}
159+
},
160+
[&] { // DidNodeConfirmReception()
161+
const NodeId nodeid{ExistentOrNewNodeId()};
162+
163+
const bool confirmed{pb.DidNodeConfirmReception(nodeid)};
164+
165+
if (nodes_that_confirmed_reception.contains(nodeid)) {
166+
Assert(confirmed);
167+
} else {
168+
Assert(!confirmed);
169+
}
170+
},
171+
[&] { // HavePendingTransactions()
172+
if (pb.HavePendingTransactions()) {
173+
Assert(!transactions.empty());
174+
} else {
175+
Assert(transactions.empty());
176+
}
177+
},
178+
[&] { // GetStale()
179+
const auto stale{pb.GetStale()};
180+
181+
Assert(stale.size() <= transactions.size());
182+
183+
for (const auto& stale_tx : stale) {
184+
Assert(transactions.contains(stale_tx));
185+
}
186+
},
187+
[&] { // GetBroadcastInfo()
188+
const auto all_broadcast_info{pb.GetBroadcastInfo()};
189+
190+
Assert(all_broadcast_info.size() == transactions.size());
191+
192+
for (const auto& info : all_broadcast_info) {
193+
const auto it{transactions.find(info.tx)};
194+
Assert(it != transactions.end());
195+
Assert(info.peers.size() == it->second); // exactly the sends we recorded
196+
}
197+
},
198+
[&] {
199+
clock_ctx.set(ConsumeTime(fdp));
200+
});
201+
}
202+
}

‎src/test/fuzz/util.h‎

Lines changed: 9 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -46,13 +46,17 @@ size_t CallOneOf(FuzzedDataProvider& fuzzed_data_provider, Callables... callable
4646
}
4747

4848
template <typename Collection>
49-
auto& PickValue(FuzzedDataProvider& fuzzed_data_provider, Collection& col)
49+
auto PickIterator(FuzzedDataProvider& fuzzed_data_provider, Collection& col)
5050
{
51-
auto sz{col.size()};
51+
const auto sz{col.size()};
5252
assert(sz >= 1);
53-
auto it = col.begin();
54-
std::advance(it, fuzzed_data_provider.ConsumeIntegralInRange<decltype(sz)>(0, sz - 1));
55-
return *it;
53+
return std::next(col.begin(), fuzzed_data_provider.ConsumeIntegralInRange<decltype(sz)>(0, sz - 1));
54+
}
55+
56+
template <typename Collection>
57+
auto& PickValue(FuzzedDataProvider& fuzzed_data_provider, Collection& col)
58+
{
59+
return *PickIterator(fuzzed_data_provider, col);
5660
}
5761

5862
template<typename B = uint8_t>

0 commit comments

Comments
 (0)