LCOV - code coverage report
Current view: top level - src/wallet/test/fuzz - coinselection.cpp (source / functions) Hit Total Coverage
Test: fuzz_coverage.info Lines: 5 128 3.9 %
Date: 2023-11-06 23:13:05 Functions: 1 11 9.1 %
Branches: 5 284 1.8 %

           Branch data     Line data    Source code
       1                 :            : // Copyright (c) 2022 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 <policy/feerate.h>
       6                 :            : #include <policy/policy.h>
       7                 :            : #include <primitives/transaction.h>
       8                 :            : #include <test/fuzz/FuzzedDataProvider.h>
       9                 :            : #include <test/fuzz/fuzz.h>
      10                 :            : #include <test/fuzz/util.h>
      11                 :            : #include <test/util/setup_common.h>
      12                 :            : #include <wallet/coinselection.h>
      13                 :            : 
      14                 :            : #include <vector>
      15                 :            : 
      16                 :            : namespace wallet {
      17         [ +  - ]:          2 : 
      18         [ +  - ]:          2 : static void AddCoin(const CAmount& value, int n_input, int n_input_bytes, int locktime, std::vector<COutput>& coins, CFeeRate fee_rate)
      19                 :            : {
      20                 :          0 :     CMutableTransaction tx;
      21         [ #  # ]:          0 :     tx.vout.resize(n_input + 1);
      22                 :          0 :     tx.vout[n_input].nValue = value;
      23                 :          0 :     tx.nLockTime = locktime; // all transactions get different hashes
      24 [ #  # ][ #  # ]:          0 :     coins.emplace_back(COutPoint(tx.GetHash(), n_input), tx.vout.at(n_input), /*depth=*/0, n_input_bytes, /*spendable=*/true, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, fee_rate);
         [ #  # ][ #  # ]
      25                 :          2 : }
      26                 :            : 
      27                 :            : // Randomly distribute coins to instances of OutputGroup
      28                 :          0 : static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vector<COutput>& coins, const CoinSelectionParams& coin_params, bool positive_only, std::vector<OutputGroup>& output_groups)
      29                 :            : {
      30                 :          0 :     auto output_group = OutputGroup(coin_params);
      31                 :          0 :     bool valid_outputgroup{false};
      32         [ #  # ]:          0 :     for (auto& coin : coins) {
      33 [ #  # ][ #  # ]:          0 :         if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
         [ #  # ][ #  # ]
      34 [ #  # ][ #  # ]:          0 :             output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*descendants=*/0);
      35                 :          0 :         }
      36                 :            :         // If positive_only was specified, nothing was inserted, leading to an empty output group
      37                 :            :         // that would be invalid for the BnB algorithm
      38 [ #  # ][ #  # ]:          0 :         valid_outputgroup = !positive_only || output_group.GetSelectionAmount() > 0;
      39 [ #  # ][ #  # ]:          0 :         if (valid_outputgroup && fuzzed_data_provider.ConsumeBool()) {
                 [ #  # ]
      40         [ #  # ]:          0 :             output_groups.push_back(output_group);
      41         [ #  # ]:          0 :             output_group = OutputGroup(coin_params);
      42                 :          0 :             valid_outputgroup = false;
      43                 :          0 :         }
      44                 :            :     }
      45 [ #  # ][ #  # ]:          0 :     if (valid_outputgroup) output_groups.push_back(output_group);
      46                 :          0 : }
      47                 :            : 
      48                 :          0 : static CAmount CreateCoins(FuzzedDataProvider& fuzzed_data_provider, std::vector<COutput>& utxo_pool, CoinSelectionParams& coin_params, int& next_locktime)
      49                 :            : {
      50                 :          0 :     CAmount total_balance{0};
      51 [ #  # ][ #  # ]:          0 :     LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
      52                 :            :     {
      53                 :          0 :         const int n_input{fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 10)};
      54                 :          0 :         const int n_input_bytes{fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 10000)};
      55                 :          0 :         const CAmount amount{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
      56         [ #  # ]:          0 :         if (total_balance + amount >= MAX_MONEY) {
      57                 :          0 :             break;
      58                 :            :         }
      59                 :          0 :         AddCoin(amount, n_input, n_input_bytes, ++next_locktime, utxo_pool, coin_params.m_effective_feerate);
      60                 :          0 :         total_balance += amount;
      61                 :          0 :     }
      62                 :            : 
      63                 :          0 :     return total_balance;
      64                 :            : }
      65                 :            : 
      66                 :          0 : static SelectionResult ManualSelection(std::vector<COutput>& utxos, const CAmount& total_amount, const bool& subtract_fee_outputs)
      67                 :            : {
      68                 :          0 :     SelectionResult result(total_amount, SelectionAlgorithm::MANUAL);
      69                 :          0 :     std::set<std::shared_ptr<COutput>> utxo_pool;
      70         [ #  # ]:          0 :     for (const auto& utxo : utxos) {
      71 [ #  # ][ #  # ]:          0 :         utxo_pool.insert(std::make_shared<COutput>(utxo));
      72                 :            :     }
      73         [ #  # ]:          0 :     result.AddInputs(utxo_pool, subtract_fee_outputs);
      74                 :          0 :     return result;
      75         [ #  # ]:          0 : }
      76                 :            : 
      77                 :            : // Returns true if the result contains an error and the message is not empty
      78         [ #  # ]:          0 : static bool HasErrorMsg(const util::Result<SelectionResult>& res) { return !util::ErrorString(res).empty(); }
      79                 :            : 
      80 [ +  - ][ +  - ]:          6 : FUZZ_TARGET(coinselection)
      81                 :            : {
      82                 :          0 :     FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
      83         [ +  - ]:          2 :     std::vector<COutput> utxo_pool;
      84                 :            : 
      85         [ #  # ]:          0 :     const CFeeRate long_term_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
      86         [ #  # ]:          0 :     const CFeeRate effective_fee_rate{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
      87                 :            :     // Discard feerate must be at least dust relay feerate
      88 [ #  # ][ #  # ]:          0 :     const CFeeRate discard_fee_rate{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(DUST_RELAY_TX_FEE, COIN)};
      89                 :          0 :     const CAmount min_viable_change{ConsumeMoney(fuzzed_data_provider, /*max=*/COIN)};
      90         [ #  # ]:          0 :     const CAmount target{fuzzed_data_provider.ConsumeIntegralInRange<CAmount>(1, MAX_MONEY)};
      91         [ #  # ]:          0 :     const bool subtract_fee_outputs{fuzzed_data_provider.ConsumeBool()};
      92                 :            : 
      93                 :          0 :     FastRandomContext fast_random_context{ConsumeUInt256(fuzzed_data_provider)};
      94         [ #  # ]:          0 :     CoinSelectionParams coin_params{fast_random_context};
      95                 :          0 :     coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
      96                 :          0 :     coin_params.m_long_term_feerate = long_term_fee_rate;
      97                 :          0 :     coin_params.m_effective_feerate = effective_fee_rate;
      98                 :          0 :     coin_params.min_viable_change = min_viable_change;
      99         [ #  # ]:          0 :     coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
     100         [ #  # ]:          0 :     coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
     101                 :          0 :     coin_params.m_discard_feerate = discard_fee_rate;
     102         [ #  # ]:          0 :     coin_params.change_spend_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(41, 1000);
     103         [ #  # ]:          0 :     coin_params.m_cost_of_change = coin_params.m_change_fee + coin_params.m_discard_feerate.GetFee(coin_params.change_spend_size);
     104                 :            : 
     105                 :          0 :     int next_locktime{0};
     106         [ #  # ]:          0 :     CAmount total_balance{CreateCoins(fuzzed_data_provider, utxo_pool, coin_params, next_locktime)};
     107                 :            : 
     108                 :          0 :     std::vector<OutputGroup> group_pos;
     109         [ #  # ]:          0 :     GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/true, group_pos);
     110                 :          0 :     std::vector<OutputGroup> group_all;
     111         [ #  # ]:          0 :     GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);
     112                 :            : 
     113         [ #  # ]:          0 :     for (const OutputGroup& group : group_all) {
     114 [ #  # ][ #  # ]:          0 :         const CoinEligibilityFilter filter(fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<int>(), fuzzed_data_provider.ConsumeIntegral<uint64_t>());
         [ #  # ][ #  # ]
     115         [ #  # ]:          0 :         (void)group.EligibleForSpending(filter);
     116                 :            :     }
     117                 :            : 
     118                 :            :     // Run coinselection algorithms
     119         [ #  # ]:          0 :     auto result_bnb = SelectCoinsBnB(group_pos, target, coin_params.m_cost_of_change, MAX_STANDARD_TX_WEIGHT);
     120         [ #  # ]:          0 :     if (result_bnb) {
     121 [ #  # ][ #  # ]:          0 :         assert(result_bnb->GetChange(coin_params.m_cost_of_change, CAmount{0}) == 0);
                 [ #  # ]
     122 [ #  # ][ #  # ]:          0 :         assert(result_bnb->GetSelectedValue() >= target);
                 [ #  # ]
     123 [ #  # ][ #  # ]:          0 :         (void)result_bnb->GetShuffledInputVector();
     124 [ #  # ][ #  # ]:          0 :         (void)result_bnb->GetInputSet();
     125                 :          0 :     }
     126                 :            : 
     127         [ #  # ]:          0 :     auto result_srd = SelectCoinsSRD(group_pos, target, coin_params.m_change_fee, fast_random_context, MAX_STANDARD_TX_WEIGHT);
     128         [ #  # ]:          0 :     if (result_srd) {
     129 [ #  # ][ #  # ]:          0 :         assert(result_srd->GetSelectedValue() >= target);
                 [ #  # ]
     130 [ #  # ][ #  # ]:          0 :         assert(result_srd->GetChange(CHANGE_LOWER, coin_params.m_change_fee) > 0); // Demonstrate that SRD creates change of at least CHANGE_LOWER
                 [ #  # ]
     131 [ #  # ][ #  # ]:          0 :         result_srd->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
     132 [ #  # ][ #  # ]:          0 :         (void)result_srd->GetShuffledInputVector();
     133 [ #  # ][ #  # ]:          0 :         (void)result_srd->GetInputSet();
     134                 :          0 :     }
     135                 :            : 
     136         [ #  # ]:          0 :     CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
     137         [ #  # ]:          0 :     auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context, MAX_STANDARD_TX_WEIGHT);
     138         [ #  # ]:          0 :     if (result_knapsack) {
     139 [ #  # ][ #  # ]:          0 :         assert(result_knapsack->GetSelectedValue() >= target);
                 [ #  # ]
     140 [ #  # ][ #  # ]:          0 :         result_knapsack->ComputeAndSetWaste(coin_params.min_viable_change, coin_params.m_cost_of_change, coin_params.m_change_fee);
     141 [ #  # ][ #  # ]:          0 :         (void)result_knapsack->GetShuffledInputVector();
     142 [ #  # ][ #  # ]:          0 :         (void)result_knapsack->GetInputSet();
     143                 :          0 :     }
     144                 :            : 
     145                 :            :     // If the total balance is sufficient for the target and we are not using
     146                 :            :     // effective values, Knapsack should always find a solution (unless the selection exceeded the max tx weight).
     147 [ #  # ][ #  # ]:          0 :     if (total_balance >= target && subtract_fee_outputs && !HasErrorMsg(result_knapsack)) {
         [ #  # ][ #  # ]
     148         [ #  # ]:          0 :         assert(result_knapsack);
     149                 :          0 :     }
     150                 :            : 
     151                 :          0 :     std::vector<COutput> utxos;
     152 [ #  # ][ #  # ]:          0 :     std::vector<util::Result<SelectionResult>> results{result_srd, result_knapsack, result_bnb};
         [ #  # ][ #  # ]
     153         [ #  # ]:          0 :     CAmount new_total_balance{CreateCoins(fuzzed_data_provider, utxos, coin_params, next_locktime)};
     154         [ #  # ]:          0 :     if (new_total_balance > 0) {
     155                 :          0 :         std::set<std::shared_ptr<COutput>> new_utxo_pool;
     156         [ #  # ]:          0 :         for (const auto& utxo : utxos) {
     157 [ #  # ][ #  # ]:          0 :             new_utxo_pool.insert(std::make_shared<COutput>(utxo));
     158                 :            :         }
     159         [ #  # ]:          0 :         for (auto& result : results) {
     160         [ #  # ]:          0 :             if (!result) continue;
     161 [ #  # ][ #  # ]:          0 :             const auto weight{result->GetWeight()};
     162 [ #  # ][ #  # ]:          0 :             result->AddInputs(new_utxo_pool, subtract_fee_outputs);
     163 [ #  # ][ #  # ]:          0 :             assert(result->GetWeight() > weight);
                 [ #  # ]
     164                 :            :         }
     165                 :          0 :     }
     166                 :            : 
     167                 :          0 :     std::vector<COutput> manual_inputs;
     168         [ #  # ]:          0 :     CAmount manual_balance{CreateCoins(fuzzed_data_provider, manual_inputs, coin_params, next_locktime)};
     169         [ #  # ]:          0 :     if (manual_balance == 0) return;
     170         [ #  # ]:          0 :     auto manual_selection{ManualSelection(manual_inputs, manual_balance, coin_params.m_subtract_fee_outputs)};
     171         [ #  # ]:          0 :     for (auto& result : results) {
     172         [ #  # ]:          0 :         if (!result) continue;
     173 [ #  # ][ #  # ]:          0 :         const CAmount old_target{result->GetTarget()};
     174 [ #  # ][ #  # ]:          0 :         const std::set<std::shared_ptr<COutput>> input_set{result->GetInputSet()};
                 [ #  # ]
     175 [ #  # ][ #  # ]:          0 :         const int old_weight{result->GetWeight()};
     176 [ #  # ][ #  # ]:          0 :         result->Merge(manual_selection);
     177 [ #  # ][ #  # ]:          0 :         assert(result->GetInputSet().size() == input_set.size() + manual_inputs.size());
                 [ #  # ]
     178 [ #  # ][ #  # ]:          0 :         assert(result->GetTarget() == old_target + manual_selection.GetTarget());
         [ #  # ][ #  # ]
     179 [ #  # ][ #  # ]:          0 :         assert(result->GetWeight() == old_weight + manual_selection.GetWeight());
         [ #  # ][ #  # ]
     180                 :          0 :     }
     181         [ #  # ]:          0 : }
     182                 :            : 
     183                 :            : } // namespace wallet

Generated by: LCOV version 1.14