Branch data Line data Source code
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 <private_broadcast.h>
6 : :
7 : : #include <consensus/tx_check.h>
8 : : #include <consensus/validation.h>
9 : : #include <net.h>
10 : : #include <primitives/transaction.h>
11 : : #include <test/fuzz/FuzzedDataProvider.h>
12 : : #include <test/fuzz/fuzz.h>
13 : : #include <test/fuzz/util.h>
14 : : #include <test/fuzz/util/net.h>
15 : : #include <test/util/setup_common.h>
16 : : #include <test/util/time.h>
17 : : #include <util/check.h>
18 : : #include <util/overflow.h>
19 : : #include <util/time.h>
20 : :
21 : : #include <algorithm>
22 : : #include <optional>
23 : : #include <ranges>
24 : : #include <unordered_map>
25 : : #include <unordered_set>
26 : :
27 : : struct CTransactionRefHash {
28 : 27759 : size_t operator()(const CTransactionRef& tx) const
29 : : {
30 [ + - + + : 27759 : return static_cast<size_t>(tx->GetWitnessHash().ToUint256().GetUint64(0));
+ + ]
31 : : }
32 : : };
33 : :
34 : : struct CTransactionRefComp {
35 : 18149 : bool operator()(const CTransactionRef& a, const CTransactionRef& b) const
36 : : {
37 : 16612 : return a->GetWitnessHash() == b->GetWitnessHash();
[ - + - +
- + - - -
- - - ]
38 : : }
39 : : };
40 : :
41 [ + - ]: 1123 : FUZZ_TARGET(private_broadcast)
42 : : {
43 : 647 : FuzzedDataProvider fdp(buffer.data(), buffer.size());
44 : 647 : FakeNodeClock clock_ctx{ConsumeTime(fdp)};
45 : :
46 : 647 : const size_t cap{fdp.ConsumeIntegralInRange<size_t>(1, 12)};
47 : 647 : const size_t max_send_attempts{fdp.ConsumeIntegralInRange<size_t>(1, 12)};
48 : 647 : PrivateBroadcast pb{cap, max_send_attempts};
49 : :
50 : : // Random transactions that the test generated and passed to Add(). Trimmed by Remove() and Add() cleanup.
51 : : // The values are the number of times a transaction was picked for sending.
52 : 647 : std::unordered_map<CTransactionRef, size_t, CTransactionRefHash, CTransactionRefComp> transactions;
53 : : // The values are the number of times a transaction is planned to be sent.
54 : 647 : std::unordered_map<CTransactionRef, size_t, CTransactionRefHash, CTransactionRefComp> planned_sends;
55 : 647 : std::unordered_set<CTransactionRef, CTransactionRefHash, CTransactionRefComp> resolved_transactions;
56 : : // When each transaction was added, or reset by adding it again.
57 : 647 : std::unordered_map<CTransactionRef, NodeClock::time_point, CTransactionRefHash, CTransactionRefComp> time_added;
58 : : // When each node confirmed reception. Only looked up through nodes_sent_to.
59 : 647 : std::unordered_map<NodeId, NodeClock::time_point> confirmed_at;
60 : :
61 : : // Transactions passed to PickTxForSend(), indexed by node id. Trimmed when
62 : : // Remove() is called or a transaction is reset or cleaned up by Add().
63 : 647 : std::unordered_map<NodeId, CTransactionRef> nodes_sent_to;
64 : 647 : std::unordered_set<NodeId> disconnected_nodes;
65 : :
66 : 647 : NodeId next_nodeid{0}; // Generate unique node ids.
67 : :
68 : 6224 : const auto is_pending{[&](const auto& entry) {
69 [ + + ]: 5577 : return entry.second < std::min(planned_sends.at(entry.first), max_send_attempts);
70 : 647 : }};
71 : :
72 : 2186 : const auto ExistentOrNewNodeId = [&next_nodeid, &fdp](){
73 [ + + + + ]: 1539 : if (next_nodeid == 0 || fdp.ConsumeBool()) {
74 : 1429 : return next_nodeid++;
75 : : }
76 : 110 : return fdp.ConsumeIntegralInRange<NodeId>(0, next_nodeid - 1);
77 : 647 : };
78 : :
79 [ + + + - ]: 18414 : LIMITED_WHILE (fdp.ConsumeBool(), 10000) {
80 [ + - ]: 17767 : CallOneOf(
81 : : fdp,
82 : 1712 : [&] { // Add()
83 : 1712 : CTransactionRef tx;
84 [ + + + + ]: 1712 : if (transactions.empty() || fdp.ConsumeBool()) {
85 [ + - - + ]: 3876 : tx = MakeTransactionRef(ConsumeTransaction(fdp, std::nullopt));
86 : : } else {
87 : 420 : tx = PickIterator(fdp, transactions)->first;
88 : : }
89 : :
90 [ + - ]: 1712 : auto cleanup_candidates{resolved_transactions};
91 [ + + ]: 2432 : for (const auto& [nodeid, sent_tx] : nodes_sent_to) {
92 [ + + ]: 720 : if (!disconnected_nodes.contains(nodeid)) cleanup_candidates.erase(sent_tx);
93 : : }
94 [ + - ]: 1712 : std::erase_if(transactions, [&](const auto& entry) {
95 [ + + + - ]: 1701 : if (!cleanup_candidates.contains(entry.first) || is_pending(entry)) return false;
96 : 0 : planned_sends.erase(entry.first);
97 : 0 : resolved_transactions.erase(entry.first);
98 : 0 : return true;
99 : : });
100 : 2432 : std::erase_if(nodes_sent_to, [&](const auto& entry) { return !transactions.contains(entry.second); });
101 : :
102 : 1712 : const bool present_before{transactions.contains(tx)};
103 [ + - ]: 1712 : const auto res{pb.Add(tx)};
104 [ + + ]: 1712 : if (present_before) {
105 : 460 : auto tx_it{transactions.find(tx)};
106 [ + - + - ]: 920 : Assert(tx_it != transactions.end());
107 [ + + ]: 460 : if (tx_it->second < max_send_attempts) {
108 [ + - ]: 449 : Assert(res == PrivateBroadcast::AddResult::AlreadyPresent);
109 : : } else {
110 [ + - ]: 11 : Assert(res == PrivateBroadcast::AddResult::Added);
111 [ + - ]: 11 : tx_it->second = 0;
112 [ + - ]: 11 : planned_sends[tx] = PrivateBroadcast::INITIAL_CONNECTION_COUNT;
113 [ + - ]: 11 : time_added[tx] = NodeClock::now();
114 : 11 : resolved_transactions.erase(tx);
115 [ + + ]: 34 : std::erase_if(nodes_sent_to, [&](const auto& entry) { return CTransactionRefComp{}(entry.second, tx); });
116 : : }
117 [ + + ]: 1252 : } else if (transactions.size() >= cap) {
118 [ + - ]: 199 : Assert(res == PrivateBroadcast::AddResult::QueueFull);
119 : : } else {
120 [ + - ]: 1053 : Assert(res == PrivateBroadcast::AddResult::Added);
121 [ + - ]: 1053 : transactions.emplace(tx, 0);
122 [ + - ]: 1053 : planned_sends.emplace(tx, PrivateBroadcast::INITIAL_CONNECTION_COUNT);
123 [ + - ]: 1053 : time_added[tx] = NodeClock::now();
124 : : }
125 [ + - ]: 3424 : },
126 : 1597 : [&] { // Remove()
127 [ + + ]: 1597 : if (transactions.empty()) {
128 : : return;
129 : : }
130 : 482 : const auto transactions_it{PickIterator(fdp, transactions)};
131 : 482 : const CTransactionRef& tx{transactions_it->first};
132 : :
133 : : // Remove relevant entries from nodes_sent_to[] if any.
134 [ + + ]: 638 : std::erase_if(nodes_sent_to, [&](const auto& entry) { return CTransactionRefComp{}(entry.second, tx); });
135 : :
136 : 482 : const auto remaining_sends{pb.Remove(tx)};
137 : :
138 : 482 : Assert(remaining_sends.has_value());
139 [ + - + + ]: 834 : Assert(remaining_sends.value() == std::min(planned_sends.at(tx), max_send_attempts) - transactions_it->second);
140 : 482 : Assert(!pb.Remove(tx).has_value());
141 : 482 : planned_sends.erase(tx);
142 : 482 : resolved_transactions.erase(tx);
143 : 482 : transactions.erase(transactions_it);
144 : : },
145 : 228 : [&] { // MarkResolved()
146 [ + + + + ]: 228 : const CTransactionRef tx{transactions.empty() || fdp.ConsumeBool() ?
147 [ + + ]: 608 : MakeTransactionRef(ConsumeTransaction(fdp, std::nullopt)) :
148 [ + - + - : 646 : PickIterator(fdp, transactions)->first};
+ + ]
149 [ + - + - ]: 228 : Assert(pb.MarkResolved(tx) == transactions.contains(tx));
150 [ + + + - ]: 228 : if (transactions.contains(tx)) resolved_transactions.insert(tx);
151 : 228 : },
152 : 2816 : [&] { // PickTxForSend()
153 : : // Only give pristine node ids to PickTxForSend() as required.
154 : 2816 : const NodeId will_send_to_nodeid{next_nodeid++};
155 : 2816 : const CService will_send_to_address{ConsumeService(fdp)};
156 : :
157 [ + - ]: 2816 : const auto opt_tx{pb.PickTxForSend(will_send_to_nodeid, will_send_to_address)};
158 : :
159 [ + + ]: 2816 : if (opt_tx.has_value()) {
160 [ + - ]: 469 : Assert(transactions.contains(opt_tx.value()));
161 : :
162 : : // "Number of times picked for sending" is the primary key in Priority's comparison
163 : : // (fewest sends = highest priority), so PickTxForSend() must return a transaction
164 : : // with the minimum send count of any in the queue. Ties are broken by state we
165 : : // don't model, so only check this key.
166 [ + - ]: 469 : auto pending_transactions{transactions | std::views::filter(is_pending)};
167 [ + - ]: 469 : const size_t min_picked{std::ranges::min_element(
168 [ + + + - ]: 763 : pending_transactions, {}, [](const auto& el) { return el.second; })->second};
169 [ + - ]: 469 : const auto picked_it{transactions.find(opt_tx.value())};
170 [ + - + - ]: 938 : Assert(picked_it != transactions.end());
171 [ + - ]: 469 : Assert(picked_it->second == min_picked); // picked the least-sent transaction
172 [ + - ]: 469 : ++picked_it->second; // PickTxForSend() recorded exactly one send
173 : :
174 [ + - + - : 469 : const auto& [_, inserted]{nodes_sent_to.emplace(will_send_to_nodeid, opt_tx.value())};
+ - ]
175 [ + - ]: 469 : Assert(inserted);
176 : : } else {
177 [ + - + - ]: 2347 : Assert(std::ranges::none_of(transactions, is_pending));
178 : : }
179 : 2816 : },
180 : 154 : [&] { // GetTxForNode()
181 : 154 : const NodeId nodeid{ExistentOrNewNodeId()};
182 : :
183 : 154 : const auto opt_tx{pb.GetTxForNode(nodeid)};
184 : :
185 [ + + ]: 154 : if (nodes_sent_to.contains(nodeid)) {
186 [ + - ]: 6 : Assert(opt_tx.has_value());
187 [ + - + - ]: 6 : Assert(transactions.contains(opt_tx.value()));
188 [ + - + - : 6 : Assert(opt_tx.value() == nodes_sent_to.at(nodeid));
+ - ]
189 : : } else {
190 [ + - ]: 148 : Assert(!opt_tx.has_value());
191 : : }
192 : 154 : },
193 : 1171 : [&] { // NodeConfirmedReception()
194 : 1171 : const NodeId nodeid{ExistentOrNewNodeId()};
195 : :
196 : 1171 : pb.NodeConfirmedReception(nodeid);
197 [ + + ]: 1171 : if (nodes_sent_to.contains(nodeid)) confirmed_at[nodeid] = NodeClock::now();
198 : 1171 : },
199 : 214 : [&] { // NodeDisconnected()
200 : 214 : const NodeId nodeid{ExistentOrNewNodeId()};
201 : 214 : pb.NodeDisconnected(nodeid);
202 [ + + ]: 214 : if (nodes_sent_to.contains(nodeid)) disconnected_nodes.insert(nodeid);
203 : 214 : },
204 : 4436 : [&] { // HavePendingTransactions()
205 [ + + ]: 4436 : if (std::ranges::any_of(transactions, is_pending)) {
206 : 1296 : Assert(pb.HavePendingTransactions());
207 : : } else {
208 : 3140 : Assert(!pb.HavePendingTransactions());
209 : : }
210 : 4436 : },
211 : 109 : [&] { // TryGrantRetry()
212 [ + + ]: 109 : if (transactions.empty()) return;
213 : 74 : const auto tx_it{PickIterator(fdp, transactions)};
214 : 74 : auto& count{planned_sends.at(tx_it->first)};
215 [ + + + + : 74 : const bool can_retry{!resolved_transactions.contains(tx_it->first) && !is_pending(*tx_it) && count < max_send_attempts};
+ + ]
216 : 74 : Assert(pb.TryGrantRetry(tx_it->first) == can_retry);
217 [ + + ]: 74 : if (can_retry) ++count;
218 : : },
219 : 5011 : [&] { // GetStale()
220 : 5011 : const auto stale{pb.GetStale()};
221 : :
222 [ - + + - ]: 5011 : Assert(stale.size() <= transactions.size());
223 : :
224 [ + + ]: 5119 : for (const auto& stale_tx : stale) {
225 : 108 : const auto it{transactions.find(stale_tx)};
226 [ + - + - ]: 216 : Assert(it != transactions.end());
227 [ + - ]: 108 : Assert(!resolved_transactions.contains(stale_tx));
228 [ + - + - ]: 108 : Assert(planned_sends.at(stale_tx) < max_send_attempts);
229 : : }
230 : :
231 : : // Every transaction that should be stale must be returned, not only a subset.
232 : 5011 : const auto now{NodeClock::now()};
233 : 5011 : std::unordered_set<CTransactionRef, CTransactionRefHash, CTransactionRefComp> expected;
234 [ + + ]: 8389 : for (const auto& [tx, num_picked] : transactions) {
235 [ + - + + : 3378 : if (resolved_transactions.contains(tx) || planned_sends.at(tx) >= max_send_attempts) continue;
+ + ]
236 : 3231 : std::optional<NodeClock::time_point> last_confirmed;
237 [ + + + + ]: 4589 : for (const auto& [nodeid, sent_tx] : nodes_sent_to) {
238 [ + + ]: 1358 : if (!CTransactionRefComp{}(sent_tx, tx)) continue;
239 [ + + ]: 1325 : if (const auto c{confirmed_at.find(nodeid)}; c != confirmed_at.end()) {
240 [ - + - + ]: 1372 : last_confirmed = std::max(last_confirmed.value_or(c->second), c->second);
241 : : }
242 : : }
243 [ + + ]: 3231 : const bool is_stale{last_confirmed ? *last_confirmed < now - PrivateBroadcast::STALE_DURATION :
244 [ + - ]: 3231 : time_added.at(tx) < now - PrivateBroadcast::INITIAL_STALE_DURATION};
245 [ + + + - ]: 3231 : if (is_stale) expected.insert(tx);
246 : : }
247 [ - + + - ]: 5011 : Assert(stale.size() == expected.size());
248 [ + - + + ]: 5119 : for (const auto& stale_tx : stale) Assert(expected.erase(stale_tx) == 1);
249 : 5011 : },
250 : 72 : [&] { // GetBroadcastInfo()
251 : 72 : const auto all_broadcast_info{pb.GetBroadcastInfo()};
252 : :
253 [ - + + - ]: 72 : Assert(all_broadcast_info.size() == transactions.size() - resolved_transactions.size());
254 : :
255 [ + + ]: 156 : for (const auto& info : all_broadcast_info) {
256 : 84 : const auto it{transactions.find(info.tx)};
257 [ + - + - ]: 168 : Assert(it != transactions.end());
258 [ + - ]: 84 : Assert(!resolved_transactions.contains(info.tx));
259 [ - + + - ]: 84 : Assert(info.peers.size() == it->second); // exactly the sends we recorded
260 [ + - ]: 84 : Assert(info.attempts_remaining == max_send_attempts - it->second);
261 : : }
262 : 72 : },
263 : 247 : [&] {
264 : 247 : clock_ctx.set(ConsumeTime(fdp));
265 : 247 : });
266 : : }
267 : 647 : }
|