Bitcoin Core  27.99.0
P2P Digital Currency
coin_selection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-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 <bench/bench.h>
6 #include <interfaces/chain.h>
7 #include <node/context.h>
8 #include <policy/policy.h>
9 #include <wallet/coinselection.h>
10 #include <wallet/spend.h>
11 #include <wallet/wallet.h>
12 #include <wallet/test/util.h>
13 
14 #include <set>
15 
16 using node::NodeContext;
19 using wallet::COutput;
20 using wallet::CWallet;
21 using wallet::CWalletTx;
28 
29 static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
30 {
31  static int nextLockTime = 0;
33  tx.nLockTime = nextLockTime++; // so all transactions get different hashes
34  tx.vout.resize(1);
35  tx.vout[0].nValue = nValue;
36  wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
37 }
38 
39 // Simple benchmark for wallet coin selection. Note that it maybe be necessary
40 // to build up more complicated scenarios in order to get meaningful
41 // measurements of performance. From laanwj, "Wallet coin selection is probably
42 // the hardest, as you need a wider selection of scenarios, just testing the
43 // same one over and over isn't too useful. Generating random isn't useful
44 // either for measurements."
45 // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484)
46 static void CoinSelection(benchmark::Bench& bench)
47 {
49  auto chain = interfaces::MakeChain(node);
50  CWallet wallet(chain.get(), "", CreateMockableWalletDatabase());
51  std::vector<std::unique_ptr<CWalletTx>> wtxs;
52  LOCK(wallet.cs_wallet);
53 
54  // Add coins.
55  for (int i = 0; i < 1000; ++i) {
56  addCoin(1000 * COIN, wallet, wtxs);
57  }
58  addCoin(3 * COIN, wallet, wtxs);
59 
60  // Create coins
61  wallet::CoinsResult available_coins;
62  for (const auto& wtx : wtxs) {
63  const auto txout = wtx->tx->vout.at(0);
64  available_coins.coins[OutputType::BECH32].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr), /*spendable=*/true, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/ 0);
65  }
66 
68  FastRandomContext rand{};
69  const CoinSelectionParams coin_selection_params{
70  rand,
71  /*change_output_size=*/ 34,
72  /*change_spend_size=*/ 148,
73  /*min_change_target=*/ CHANGE_LOWER,
74  /*effective_feerate=*/ CFeeRate(0),
75  /*long_term_feerate=*/ CFeeRate(0),
76  /*discard_feerate=*/ CFeeRate(0),
77  /*tx_noinputs_size=*/ 0,
78  /*avoid_partial=*/ false,
79  };
80  auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
81  bench.run([&] {
82  auto result = AttemptSelection(wallet.chain(), 1003 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
83  assert(result);
84  assert(result->GetSelectedValue() == 1003 * COIN);
85  assert(result->GetInputSet().size() == 2);
86  });
87 }
88 
89 // Copied from src/wallet/test/coinselector_tests.cpp
90 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
91 {
93  tx.vout.resize(nInput + 1);
94  tx.vout[nInput].nValue = nValue;
95  COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 0, /*input_bytes=*/ -1, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ true, /*fees=*/ 0);
96  set.emplace_back();
97  set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*descendants=*/ 0);
98 }
99 // Copied from src/wallet/test/coinselector_tests.cpp
100 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
101 {
102  utxo_pool.clear();
103  CAmount target = 0;
104  for (int i = 0; i < utxos; ++i) {
105  target += CAmount{1} << (utxos+i);
106  add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
107  add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
108  }
109  return target;
110 }
111 
112 static void BnBExhaustion(benchmark::Bench& bench)
113 {
114  // Setup
115  std::vector<OutputGroup> utxo_pool;
116 
117  bench.run([&] {
118  // Benchmark
119  CAmount target = make_hard_case(17, utxo_pool);
120  SelectCoinsBnB(utxo_pool, target, 0, MAX_STANDARD_TX_WEIGHT); // Should exhaust
121 
122  // Cleanup
123  utxo_pool.clear();
124  });
125 }
126 
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition: amount.h:15
Fee rate in satoshis per kilovirtualbyte: CAmount / kvB.
Definition: feerate.h:33
An outpoint - a combination of a transaction hash and an index n into its vout.
Definition: transaction.h:29
Fast randomness source.
Definition: random.h:145
Main entry point to nanobench's benchmarking facility.
Definition: nanobench.h:627
Bench & run(char const *benchmarkName, Op &&op)
Repeatedly calls op() based on the configuration, and performs measurements.
Definition: nanobench.h:1234
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
Definition: wallet.h:301
A transaction with a bunch of additional info that only the owner cares about.
Definition: transaction.h:177
static void CoinSelection(benchmark::Bench &bench)
static void addCoin(const CAmount &nValue, const CWallet &wallet, std::vector< std::unique_ptr< CWalletTx >> &wtxs)
static CAmount make_hard_case(int utxos, std::vector< OutputGroup > &utxo_pool)
static void BnBExhaustion(benchmark::Bench &bench)
static void add_coin(const CAmount &nValue, int nInput, std::vector< OutputGroup > &set)
BENCHMARK(CoinSelection, benchmark::PriorityLevel::HIGH)
@ HIGH
Definition: bench.h:47
std::unique_ptr< Chain > MakeChain(node::NodeContext &node)
Return implementation of Chain interface.
Definition: interfaces.cpp:836
Definition: init.h:25
util::Result< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, int max_weight)
static const CoinEligibilityFilter filter_standard(1, 6, 0)
FilteredOutputGroups GroupOutputs(const CWallet &wallet, const CoinsResult &coins, const CoinSelectionParams &coin_sel_params, const std::vector< SelectionFilter > &filters, std::vector< OutputGroup > &ret_discarded_groups)
Definition: spend.cpp:524
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition: coinselection.h:23
util::Result< SelectionResult > AttemptSelection(interfaces::Chain &chain, const CAmount &nTargetValue, OutputGroupTypeMap &groups, const CoinSelectionParams &coin_selection_params, bool allow_mixed_output_types)
Attempt to find a valid input set that preserves privacy by not mixing OutputTypes.
Definition: spend.cpp:654
std::unique_ptr< WalletDatabase > CreateMockableWalletDatabase(MockableData records)
Definition: util.cpp:190
static int nextLockTime
int CalculateMaximumSignedInputSize(const CTxOut &txout, const COutPoint outpoint, const SigningProvider *provider, bool can_grind_r, const CCoinControl *coin_control)
Definition: spend.cpp:81
std::shared_ptr< CWallet > wallet
static constexpr int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
Definition: policy.h:27
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:424
A mutable version of CTransaction.
Definition: transaction.h:378
std::vector< CTxOut > vout
Definition: transaction.h:380
Txid GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:69
NodeContext struct containing references to chain state and connection state.
Definition: context.h:53
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:28
Parameters for filtering which OutputGroups we may use in coin selection.
Parameters for one iteration of Coin Selection.
COutputs available for spending, stored by OutputType.
Definition: spend.h:40
std::map< OutputType, std::vector< COutput > > coins
Definition: spend.h:41
A group of UTXOs paid to the same output script.
State of transaction not confirmed or conflicting with a known block and not in the mempool.
Definition: transaction.h:58
#define LOCK(cs)
Definition: sync.h:257
assert(!tx.IsCoinBase())