1  // Copyright (c) 2012-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 <bench/bench.h>
  6  #include <consensus/amount.h>
  7  #include <interfaces/chain.h>
  8  #include <node/context.h>
  9  #include <outputtype.h>
 10  #include <policy/feerate.h>
 11  #include <policy/policy.h>
 12  #include <primitives/transaction.h>
 13  #include <random.h>
 14  #include <sync.h>
 15  #include <util/result.h>
 16  #include <wallet/coinselection.h>
 17  #include <wallet/spend.h>
 18  #include <wallet/test/util.h>
 19  #include <wallet/transaction.h>
 20  #include <wallet/wallet.h>
 21  
 22  #include <cassert>
 23  #include <map>
 24  #include <memory>
 25  #include <set>
 26  #include <utility>
 27  #include <vector>
 28  
 29  using node::NodeContext;
 30  using wallet::AttemptSelection;
 31  using wallet::CHANGE_LOWER;
 32  using wallet::COutput;
 33  using wallet::CWallet;
 34  using wallet::CWalletTx;
 35  using wallet::CoinEligibilityFilter;
 36  using wallet::CoinSelectionParams;
 37  using wallet::CreateMockableWalletDatabase;
 38  using wallet::OutputGroup;
 39  using wallet::SelectCoinsBnB;
 40  using wallet::TxStateInactive;
 41  
 42  static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
 43  {
 44      static int nextLockTime = 0;
 45      CMutableTransaction tx;
 46      tx.nLockTime = nextLockTime++; // so all transactions get different hashes
 47      tx.vout.resize(1);
 48      tx.vout[0].nValue = nValue;
 49      wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
 50  }
 51  
 52  // Simple benchmark for wallet coin selection. Note that it maybe be necessary
 53  // to build up more complicated scenarios in order to get meaningful
 54  // measurements of performance. From laanwj, "Wallet coin selection is probably
 55  // the hardest, as you need a wider selection of scenarios, just testing the
 56  // same one over and over isn't too useful. Generating random isn't useful
 57  // either for measurements."
 58  // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484)
 59  static void CoinSelection(benchmark::Bench& bench)
 60  {
 61      NodeContext node;
 62      auto chain = interfaces::MakeChain(node);
 63      CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
 64      std::vector<std::unique_ptr<CWalletTx>> wtxs;
 65      LOCK(wallet.cs_wallet);
 66  
 67      // Add coins.
 68      for (int i = 0; i < 1000; ++i) {
 69          addCoin(1000 * COIN, wallet, wtxs);
 70      }
 71      addCoin(3 * COIN, wallet, wtxs);
 72  
 73      // Create coins
 74      wallet::CoinsResult available_coins;
 75      for (const auto& wtx : wtxs) {
 76          const auto txout = wtx->tx->vout.at(0);
 77          available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0);
 78      }
 79  
 80      const CoinEligibilityFilter filter_standard(1, 6, 0);
 81      FastRandomContext rand{};
 82      const CoinSelectionParams coin_selection_params{
 83          rand,
 84          /*change_output_size=*/ 34,
 85          /*change_spend_size=*/ 148,
 86          /*min_change_target=*/ CHANGE_LOWER,
 87          /*effective_feerate=*/ CFeeRate(20'000),
 88          /*long_term_feerate=*/ CFeeRate(10'000),
 89          /*discard_feerate=*/ CFeeRate(3000),
 90          /*tx_noinputs_size=*/ 0,
 91          /*avoid_partial=*/ false,
 92      };
 93      auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
 94      bench.run([&] {
 95          auto result = AttemptSelection(wallet.chain(), 1002.99 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
 96          assert(result);
 97          assert(result->GetSelectedValue() == 1003 * COIN);
 98          assert(result->GetInputSet().size() == 2);
 99      });
100  }
101  
102  // Copied from src/wallet/test/coinselector_tests.cpp
103  static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
104  {
105      CMutableTransaction tx;
106      tx.vout.resize(nInput + 1);
107      tx.vout[nInput].nValue = nValue;
108      COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/0, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, /*fees=*/0);
109      set.emplace_back();
110      set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*cluster_count=*/ 0);
111  }
112  // Copied from src/wallet/test/coinselector_tests.cpp
113  static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
114  {
115      utxo_pool.clear();
116      CAmount target = 0;
117      for (int i = 0; i < utxos; ++i) {
118          target += CAmount{1} << (utxos+i);
119          add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
120          add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
121      }
122      return target;
123  }
124  
125  static void BnBExhaustion(benchmark::Bench& bench)
126  {
127      // Setup
128      std::vector<OutputGroup> utxo_pool;
129  
130      bench.run([&] {
131          // Benchmark
132          CAmount target = make_hard_case(17, utxo_pool);
133          (void)SelectCoinsBnB(utxo_pool, target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
134  
135          // Cleanup
136          utxo_pool.clear();
137      });
138  }
139  
140  BENCHMARK(CoinSelection);
141  BENCHMARK(BnBExhaustion);