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 <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 <algorithm>
20 : : #include <ranges>
21 : : #include <unordered_map>
22 : : #include <unordered_set>
23 : :
24 : : struct CTransactionRefHash {
25 : 102864 : size_t operator()(const CTransactionRef& tx) const
26 : : {
27 [ + + ]: 102864 : return static_cast<size_t>(tx->GetWitnessHash().ToUint256().GetUint64(0));
28 : : }
29 : : };
30 : :
31 : : struct CTransactionRefComp {
32 : 177007 : bool operator()(const CTransactionRef& a, const CTransactionRef& b) const
33 : : {
34 [ - + - - : 114493 : return a->GetWitnessHash() == b->GetWitnessHash();
+ + ]
35 : : }
36 : : };
37 : :
38 [ + - ]: 1411 : FUZZ_TARGET(private_broadcast)
39 : : {
40 : 935 : SeedRandomStateForTest(SeedRand::ZEROS);
41 : 935 : FuzzedDataProvider fdp(buffer.data(), buffer.size());
42 : 935 : FakeNodeClock clock_ctx{ConsumeTime(fdp)};
43 : :
44 : 935 : const size_t cap{fdp.ConsumeIntegralInRange<size_t>(1, 12)};
45 : 935 : const size_t max_send_attempts{fdp.ConsumeIntegralInRange<size_t>(1, 12)};
46 : 935 : PrivateBroadcast pb{cap, max_send_attempts};
47 : :
48 : : // Random transaction that the test generated and passed to Add(). Trimmed when Remove() is called.
49 : : // The values are the number of times a transaction was picked for sending.
50 : 935 : std::unordered_map<CTransactionRef, size_t, CTransactionRefHash, CTransactionRefComp> transactions;
51 : :
52 : : // Transactions passed to PickTxForSend(), indexed by node id. Trimmed when
53 : : // Remove() is called or a transaction is reset by Add().
54 : 935 : std::unordered_map<NodeId, CTransactionRef> nodes_sent_to;
55 : :
56 : : // A subset of `nodes_sent_to`, node ids passed to NodeConfirmedReception().
57 : : // Trimmed when Remove() is called or a transaction is reset by Add().
58 : 935 : std::unordered_set<NodeId> nodes_that_confirmed_reception;
59 : :
60 : 935 : NodeId next_nodeid{0}; // Generate unique node ids.
61 : :
62 : 136980 : const auto is_pending{[max_send_attempts](const auto& entry) {
63 : 201165 : return entry.second < max_send_attempts;
[ + + + -
+ + + + -
+ + + ]
64 : 935 : }};
65 : :
66 : 115097 : const auto ExistentOrNewNodeId = [&next_nodeid, &fdp](){
67 [ + + + + ]: 114162 : if (next_nodeid == 0 || fdp.ConsumeBool()) {
68 : 96807 : return next_nodeid++;
69 : : }
70 : 17355 : return fdp.ConsumeIntegralInRange<NodeId>(0, next_nodeid - 1);
71 : 935 : };
72 : :
73 [ + + + + ]: 277804 : LIMITED_WHILE (fdp.ConsumeBool(), 10000) {
74 [ + - ]: 276869 : CallOneOf(
75 : : fdp,
76 : 16147 : [&] { // Add()
77 : 16147 : CTransactionRef tx;
78 [ + + + + ]: 16147 : if (transactions.empty() || fdp.ConsumeBool()) {
79 [ + - - + ]: 36369 : tx = MakeTransactionRef(ConsumeTransaction(fdp, std::nullopt));
80 : : } else {
81 : 4024 : tx = PickIterator(fdp, transactions)->first;
82 : : }
83 : :
84 : 16147 : const bool present_before{transactions.contains(tx)};
85 [ + - ]: 16147 : const auto res{pb.Add(tx)};
86 [ + + ]: 16147 : if (present_before) {
87 : 6567 : auto tx_it{transactions.find(tx)};
88 [ + - - + ]: 13134 : Assert(tx_it != transactions.end());
89 [ + + ]: 6567 : if (is_pending(*tx_it)) {
90 [ - + ]: 5092 : Assert(res == PrivateBroadcast::AddResult::AlreadyPresent);
91 : : } else {
92 [ - + ]: 1475 : Assert(res == PrivateBroadcast::AddResult::Added);
93 : 1475 : tx_it->second = 0;
94 [ + + ]: 29867 : for (auto it = nodes_sent_to.begin(); it != nodes_sent_to.end();) {
95 [ + + ]: 28392 : if (CTransactionRefComp{}(it->second, tx)) {
96 : 7860 : nodes_that_confirmed_reception.erase(it->first);
97 : 7860 : it = nodes_sent_to.erase(it);
98 : : } else {
99 : 20532 : ++it;
100 : : }
101 : : }
102 : : }
103 [ + + ]: 9580 : } else if (transactions.size() >= cap) {
104 [ - + + - ]: 16147 : Assert(res == PrivateBroadcast::AddResult::QueueFull);
105 : : } else {
106 [ - + ]: 7183 : Assert(res == PrivateBroadcast::AddResult::Added);
107 [ + - ]: 7183 : transactions.emplace(tx, 0);
108 : : }
109 : 16147 : },
110 : 50060 : [&] { // Remove()
111 [ + + ]: 50060 : if (transactions.empty()) {
112 : : return;
113 : : }
114 : 6129 : const auto transactions_it{PickIterator(fdp, transactions)};
115 : 6129 : const CTransactionRef& tx{transactions_it->first};
116 : :
117 : 6129 : size_t num_nodes_that_confirmed_tx{0};
118 : :
119 : : // Remove relevant entries from nodes_sent_to[] and nodes_that_confirmed_reception[] if any.
120 [ + + ]: 68643 : for (auto it = nodes_sent_to.begin(); it != nodes_sent_to.end();) {
121 [ + + ]: 62514 : const NodeId nodeid{it->first};
122 [ + + ]: 62514 : if (CTransactionRefComp{}(it->second, tx)) {
123 : 11244 : it = nodes_sent_to.erase(it);
124 [ + + ]: 11244 : if (nodes_that_confirmed_reception.erase(nodeid) > 0) {
125 : 646 : ++num_nodes_that_confirmed_tx;
126 : : }
127 : : } else {
128 : 51270 : ++it;
129 : : }
130 : : }
131 : :
132 : 6129 : const auto opt_num_confirmed{pb.Remove(tx)};
133 : :
134 [ - + ]: 6129 : Assert(opt_num_confirmed.has_value());
135 [ - + ]: 6129 : Assert(opt_num_confirmed.value() == num_nodes_that_confirmed_tx);
136 [ - + ]: 6129 : Assert(!pb.Remove(tx).has_value());
137 : 6129 : transactions.erase(transactions_it);
138 : : },
139 : 52210 : [&] { // PickTxForSend()
140 : : // Only give pristine node ids to PickTxForSend() as required.
141 : 52210 : const NodeId will_send_to_nodeid{next_nodeid++};
142 : 52210 : const CService will_send_to_address{ConsumeService(fdp)};
143 : :
144 [ + - ]: 52210 : const auto opt_tx{pb.PickTxForSend(will_send_to_nodeid, will_send_to_address)};
145 : :
146 [ + + ]: 52210 : if (opt_tx.has_value()) {
147 [ - + ]: 22374 : Assert(transactions.contains(opt_tx.value()));
148 : :
149 : : // "Number of times picked for sending" is the primary key in Priority's comparison
150 : : // (fewest sends = highest priority), so PickTxForSend() must return a transaction
151 : : // with the minimum send count of any in the queue. Ties are broken by state we
152 : : // don't model, so only check this key.
153 : 22374 : auto pending_transactions{transactions | std::views::filter(is_pending)};
154 [ + - ]: 22374 : const size_t min_picked{std::ranges::min_element(
155 [ + + + - ]: 88151 : pending_transactions, {}, [](const auto& el) { return el.second; })->second};
156 [ + - ]: 22374 : const auto picked_it{transactions.find(opt_tx.value())};
157 [ + - - + ]: 44748 : Assert(picked_it != transactions.end());
158 [ - + ]: 22374 : Assert(picked_it->second == min_picked); // picked the least-sent transaction
159 [ + - ]: 22374 : ++picked_it->second; // PickTxForSend() recorded exactly one send
160 : :
161 [ + - - + ]: 22374 : const auto& [_, inserted]{nodes_sent_to.emplace(will_send_to_nodeid, opt_tx.value())};
162 [ - + ]: 22374 : Assert(inserted);
163 : : } else {
164 [ - + ]: 52210 : Assert(std::ranges::none_of(transactions, is_pending));
165 : : }
166 : 52210 : },
167 : 37062 : [&] { // GetTxForNode()
168 : 37062 : const NodeId nodeid{ExistentOrNewNodeId()};
169 : :
170 : 37062 : const auto opt_tx{pb.GetTxForNode(nodeid)};
171 : :
172 [ + + ]: 37062 : if (nodes_sent_to.contains(nodeid)) {
173 [ - + ]: 790 : Assert(opt_tx.has_value());
174 [ - + ]: 790 : Assert(transactions.contains(opt_tx.value()));
175 [ + - + - : 790 : Assert(opt_tx.value() == nodes_sent_to.at(nodeid));
- + ]
176 : : } else {
177 [ - + ]: 37062 : Assert(!opt_tx.has_value());
178 : : }
179 : 37062 : },
180 : 11112 : [&] { // NodeConfirmedReception()
181 : 11112 : const NodeId nodeid{ExistentOrNewNodeId()};
182 : :
183 : 11112 : pb.NodeConfirmedReception(nodeid);
184 : :
185 [ + + ]: 11112 : if (nodes_sent_to.contains(nodeid)) {
186 : : // nodeid was previously passed to PickTxForSend(), so NodeConfirmedReception()
187 : : // must have changed the internal state. Remember this to later check that
188 : : // DidNodeConfirmReception() works correctly.
189 : 3140 : nodes_that_confirmed_reception.emplace(nodeid);
190 : : }
191 : 11112 : },
192 : 65988 : [&] { // DidNodeConfirmReception()
193 : 65988 : const NodeId nodeid{ExistentOrNewNodeId()};
194 : :
195 : 65988 : const bool confirmed{pb.DidNodeConfirmReception(nodeid)};
196 : :
197 [ + + ]: 65988 : if (nodes_that_confirmed_reception.contains(nodeid)) {
198 [ - + ]: 524 : Assert(confirmed);
199 : : } else {
200 [ - + ]: 65464 : Assert(!confirmed);
201 : : }
202 : 65988 : },
203 : 6496 : [&] { // HavePendingTransactions()
204 [ + + ]: 6496 : if (std::ranges::any_of(transactions, is_pending)) {
205 [ - + ]: 2787 : Assert(pb.HavePendingTransactions());
206 : : } else {
207 [ - + ]: 3709 : Assert(!pb.HavePendingTransactions());
208 : : }
209 : 6496 : },
210 : 15147 : [&] { // GetStale()
211 : 15147 : const auto stale{pb.GetStale()};
212 : :
213 [ - + - + ]: 15147 : Assert(stale.size() <= transactions.size());
214 : :
215 [ + + ]: 35575 : for (const auto& stale_tx : stale) {
216 : 20428 : const auto it{transactions.find(stale_tx)};
217 [ + - - + ]: 40856 : Assert(it != transactions.end());
218 [ - + ]: 20428 : Assert(is_pending(*it));
219 : : }
220 : 15147 : },
221 : 2229 : [&] { // GetBroadcastInfo()
222 : 2229 : const auto all_broadcast_info{pb.GetBroadcastInfo()};
223 : :
224 [ - + - + ]: 2229 : Assert(all_broadcast_info.size() == transactions.size());
225 : :
226 [ + + ]: 9230 : for (const auto& info : all_broadcast_info) {
227 : 7001 : const auto it{transactions.find(info.tx)};
228 [ + - - + ]: 14002 : Assert(it != transactions.end());
229 [ - + - + ]: 7001 : Assert(info.peers.size() == it->second); // exactly the sends we recorded
230 [ - + ]: 7001 : Assert(info.attempts_remaining == max_send_attempts - it->second);
231 : : }
232 : 2229 : },
233 : 20418 : [&] {
234 : 20418 : clock_ctx.set(ConsumeTime(fdp));
235 : 20418 : });
236 : : }
237 : 935 : }
|
