LCOV - code coverage report
Current view: top level - src/test/fuzz - private_broadcast.cpp (source / functions) Coverage Total Hit
Test: fuzz_coverage.info Lines: 98.2 % 166 163
Test Date: 2026-11-21 05:38:30 Functions: 100.0 % 19 19
Branches: 66.9 % 254 170

             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 : }
        

Generated by: LCOV version 2.5.0-full