private_broadcast.cpp raw
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 const size_t cap{fdp.ConsumeIntegralInRange<size_t>(1, 12)};
42 PrivateBroadcast pb{cap};
43
44 // Random transaction that the test generated and passed to Add(). Trimmed when Remove() is called.
45 // The values are the number of times a transaction was picked for sending.
46 std::unordered_map<CTransactionRef, size_t, CTransactionRefHash, CTransactionRefComp> transactions;
47
48 // Ids of nodes that were passed to PickTxForSend(). Trimmed when Remove() is called.
49 std::unordered_set<NodeId> nodes_sent_to;
50
51 // A subset of `nodes_sent_to`, node ids passed to NodeConfirmedReception(). Trimmed when Remove() is called.
52 std::unordered_set<NodeId> nodes_that_confirmed_reception;
53
54 NodeId next_nodeid{0}; // Generate unique node ids.
55
56 const auto ExistentOrNewNodeId = [&next_nodeid, &fdp](){
57 if (next_nodeid == 0 || fdp.ConsumeBool()) {
58 return next_nodeid++;
59 }
60 return fdp.ConsumeIntegralInRange<NodeId>(0, next_nodeid - 1);
61 };
62
63 LIMITED_WHILE(fdp.ConsumeBool(), 10000) {
64 CallOneOf(
65 fdp,
66 [&] { // Add()
67 CTransactionRef tx;
68 if (transactions.empty() || fdp.ConsumeBool()) {
69 tx = MakeTransactionRef(ConsumeTransaction(fdp, std::nullopt));
70 } else {
71 tx = PickIterator(fdp, transactions)->first;
72 }
73
74 const bool present_before{transactions.contains(tx)};
75 const auto res{pb.Add(tx)};
76 if (present_before) {
77 Assert(res == PrivateBroadcast::AddResult::AlreadyPresent);
78 } else if (transactions.size() >= cap) {
79 Assert(res == PrivateBroadcast::AddResult::QueueFull);
80 } else {
81 Assert(res == PrivateBroadcast::AddResult::Added);
82 transactions.emplace(tx, 0);
83 }
84 },
85 [&] { // Remove()
86 if (transactions.empty()) {
87 return;
88 }
89 const auto transactions_it{PickIterator(fdp, transactions)};
90 const CTransactionRef& tx{transactions_it->first};
91
92 size_t num_nodes_that_confirmed_tx{0};
93
94 // Remove relevant entries from nodes_sent_to[] and nodes_that_confirmed_reception[] if any.
95 for (auto it = nodes_sent_to.begin(); it != nodes_sent_to.end();) {
96 const NodeId nodeid{*it};
97 const auto opt_tx_for_node{pb.GetTxForNode(nodeid)};
98 if (opt_tx_for_node.has_value() && opt_tx_for_node.value() == tx) {
99 it = nodes_sent_to.erase(it);
100 if (nodes_that_confirmed_reception.erase(nodeid) > 0) {
101 ++num_nodes_that_confirmed_tx;
102 }
103 } else {
104 ++it;
105 }
106 }
107
108 const auto opt_num_confirmed{pb.Remove(tx)};
109
110 Assert(opt_num_confirmed.has_value());
111 Assert(opt_num_confirmed.value() == num_nodes_that_confirmed_tx);
112 Assert(!pb.Remove(tx).has_value());
113 transactions.erase(transactions_it);
114 },
115 [&] { // PickTxForSend()
116 // Only give pristine node ids to PickTxForSend() as required.
117 const NodeId will_send_to_nodeid{next_nodeid++};
118 const CService will_send_to_address{ConsumeService(fdp)};
119
120 const auto opt_tx{pb.PickTxForSend(will_send_to_nodeid, will_send_to_address)};
121
122 if (opt_tx.has_value()) {
123 Assert(transactions.contains(opt_tx.value()));
124
125 // "Number of times picked for sending" is the primary key in Priority's comparison
126 // (fewest sends = highest priority), so PickTxForSend() must return a transaction
127 // with the minimum send count of any in the queue. Ties are broken by state we
128 // don't model, so only check this key.
129 const size_t min_picked{std::ranges::min_element(
130 transactions, {}, [](const auto& el) { return el.second; })->second};
131 const auto picked_it{transactions.find(opt_tx.value())};
132 Assert(picked_it != transactions.end());
133 Assert(picked_it->second == min_picked); // picked the least-sent transaction
134 ++picked_it->second; // PickTxForSend() recorded exactly one send
135
136 const auto& [_, inserted]{nodes_sent_to.emplace(will_send_to_nodeid)};
137 Assert(inserted);
138 } else {
139 Assert(transactions.empty());
140 }
141 },
142 [&] { // GetTxForNode()
143 const NodeId nodeid{ExistentOrNewNodeId()};
144
145 const auto opt_tx{pb.GetTxForNode(nodeid)};
146
147 if (nodes_sent_to.contains(nodeid)) {
148 Assert(opt_tx.has_value());
149 Assert(transactions.contains(opt_tx.value()));
150 } else {
151 Assert(!opt_tx.has_value());
152 }
153 },
154 [&] { // NodeConfirmedReception()
155 const NodeId nodeid{ExistentOrNewNodeId()};
156
157 pb.NodeConfirmedReception(nodeid);
158
159 if (nodes_sent_to.contains(nodeid)) {
160 // nodeid was previously passed to PickTxForSend(), so NodeConfirmedReception()
161 // must have changed the internal state. Remember this to later check that
162 // DidNodeConfirmReception() works correctly.
163 nodes_that_confirmed_reception.emplace(nodeid);
164 }
165 },
166 [&] { // DidNodeConfirmReception()
167 const NodeId nodeid{ExistentOrNewNodeId()};
168
169 const bool confirmed{pb.DidNodeConfirmReception(nodeid)};
170
171 if (nodes_that_confirmed_reception.contains(nodeid)) {
172 Assert(confirmed);
173 } else {
174 Assert(!confirmed);
175 }
176 },
177 [&] { // HavePendingTransactions()
178 if (pb.HavePendingTransactions()) {
179 Assert(!transactions.empty());
180 } else {
181 Assert(transactions.empty());
182 }
183 },
184 [&] { // GetStale()
185 const auto stale{pb.GetStale()};
186
187 Assert(stale.size() <= transactions.size());
188
189 for (const auto& stale_tx : stale) {
190 Assert(transactions.contains(stale_tx));
191 }
192 },
193 [&] { // GetBroadcastInfo()
194 const auto all_broadcast_info{pb.GetBroadcastInfo()};
195
196 Assert(all_broadcast_info.size() == transactions.size());
197
198 for (const auto& info : all_broadcast_info) {
199 const auto it{transactions.find(info.tx)};
200 Assert(it != transactions.end());
201 Assert(info.peers.size() == it->second); // exactly the sends we recorded
202 }
203 },
204 [&] {
205 clock_ctx.set(ConsumeTime(fdp));
206 });
207 }
208 }
209