Bitcoin Core  22.99.0
P2P Digital Currency
coin_selection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-2021 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 <wallet/coinselection.h>
9 #include <wallet/spend.h>
10 #include <wallet/wallet.h>
11 
12 #include <set>
13 
14 using node::NodeContext;
16 using wallet::CInputCoin;
17 using wallet::COutput;
18 using wallet::CWallet;
19 using wallet::CWalletTx;
26 
27 static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
28 {
29  static int nextLockTime = 0;
31  tx.nLockTime = nextLockTime++; // so all transactions get different hashes
32  tx.vout.resize(1);
33  tx.vout[0].nValue = nValue;
34  wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
35 }
36 
37 // Simple benchmark for wallet coin selection. Note that it maybe be necessary
38 // to build up more complicated scenarios in order to get meaningful
39 // measurements of performance. From laanwj, "Wallet coin selection is probably
40 // the hardest, as you need a wider selection of scenarios, just testing the
41 // same one over and over isn't too useful. Generating random isn't useful
42 // either for measurements."
43 // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484)
44 static void CoinSelection(benchmark::Bench& bench)
45 {
47  auto chain = interfaces::MakeChain(node);
48  CWallet wallet(chain.get(), "", gArgs, CreateDummyWalletDatabase());
49  std::vector<std::unique_ptr<CWalletTx>> wtxs;
50  LOCK(wallet.cs_wallet);
51 
52  // Add coins.
53  for (int i = 0; i < 1000; ++i) {
54  addCoin(1000 * COIN, wallet, wtxs);
55  }
56  addCoin(3 * COIN, wallet, wtxs);
57 
58  // Create coins
59  std::vector<COutput> coins;
60  for (const auto& wtx : wtxs) {
61  coins.emplace_back(wallet, *wtx, 0 /* iIn */, 6 * 24 /* nDepthIn */, true /* spendable */, true /* solvable */, true /* safe */);
62  }
63 
65  const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34,
66  /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
67  /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
68  /* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
69  bench.run([&] {
70  auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, coin_selection_params);
71  assert(result);
72  assert(result->GetSelectedValue() == 1003 * COIN);
73  assert(result->GetInputSet().size() == 2);
74  });
75 }
76 
77 typedef std::set<CInputCoin> CoinSet;
78 
79 // Copied from src/wallet/test/coinselector_tests.cpp
80 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
81 {
83  tx.vout.resize(nInput + 1);
84  tx.vout[nInput].nValue = nValue;
85  CInputCoin coin(MakeTransactionRef(tx), nInput);
86  set.emplace_back();
87  set.back().Insert(coin, 0, true, 0, 0, false);
88 }
89 // Copied from src/wallet/test/coinselector_tests.cpp
90 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
91 {
92  utxo_pool.clear();
93  CAmount target = 0;
94  for (int i = 0; i < utxos; ++i) {
95  target += (CAmount)1 << (utxos+i);
96  add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
97  add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
98  }
99  return target;
100 }
101 
102 static void BnBExhaustion(benchmark::Bench& bench)
103 {
104  // Setup
105  std::vector<OutputGroup> utxo_pool;
106 
107  bench.run([&] {
108  // Benchmark
109  CAmount target = make_hard_case(17, utxo_pool);
110  SelectCoinsBnB(utxo_pool, target, 0); // Should exhaust
111 
112  // Cleanup
113  utxo_pool.clear();
114  });
115 }
116 
interfaces::MakeChain
std::unique_ptr< Chain > MakeChain(node::NodeContext &node)
Return implementation of Chain interface.
Definition: interfaces.cpp:728
assert
assert(!tx.IsCoinBase())
wallet.h
make_hard_case
static CAmount make_hard_case(int utxos, std::vector< OutputGroup > &utxo_pool)
Definition: coin_selection.cpp:90
wallet::AttemptSelection
std::optional< SelectionResult > AttemptSelection(const CWallet &wallet, const CAmount &nTargetValue, const CoinEligibilityFilter &eligibility_filter, std::vector< COutput > coins, const CoinSelectionParams &coin_selection_params)
Attempt to find a valid input set that meets the provided eligibility filter and target.
Definition: spend.cpp:373
wallet::nextLockTime
static int nextLockTime
Definition: coinselector_tests.cpp:36
CoinSelection
static void CoinSelection(benchmark::Bench &bench)
Definition: coin_selection.cpp:44
BENCHMARK
BENCHMARK(CoinSelection)
node::NodeContext
NodeContext struct containing references to chain state and connection state.
Definition: context.h:40
addCoin
static void addCoin(const CAmount &nValue, const CWallet &wallet, std::vector< std::unique_ptr< CWalletTx >> &wtxs)
Definition: coin_selection.cpp:27
add_coin
static void add_coin(const CAmount &nValue, int nInput, std::vector< OutputGroup > &set)
Definition: coin_selection.cpp:80
ankerl::nanobench::Bench
Main entry point to nanobench's benchmarking facility.
Definition: nanobench.h:616
MakeTransactionRef
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:407
wallet
Definition: node.h:38
chain.h
context.h
wallet::CWalletTx
A transaction with a bunch of additional info that only the owner cares about.
Definition: transaction.h:137
wallet
std::shared_ptr< CWallet > wallet
Definition: notifications.cpp:38
CFeeRate
Fee rate in satoshis per kilobyte: CAmount / kB.
Definition: feerate.h:29
wallet::CreateDummyWalletDatabase
std::unique_ptr< WalletDatabase > CreateDummyWalletDatabase()
Return object for accessing dummy database with no read/write capabilities.
Definition: walletdb.cpp:1184
CMutableTransaction::nLockTime
uint32_t nLockTime
Definition: transaction.h:369
coinselection.h
wallet::CWallet
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
Definition: wallet.h:232
ankerl::nanobench::Bench::run
Bench & run(char const *benchmarkName, Op &&op)
Repeatedly calls op() based on the configuration, and performs measurements.
Definition: nanobench.h:1183
CAmount
int64_t CAmount
Amount in satoshis (Can be negative)
Definition: amount.h:12
wallet::OutputGroup
A group of UTXOs paid to the same output script.
Definition: coinselection.h:139
bench.h
wallet::CInputCoin
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:22
gArgs
ArgsManager gArgs
Definition: system.cpp:87
wallet::SelectCoinsBnB
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
Definition: coinselection.cpp:65
wallet::TxStateInactive
State of transaction not confirmed or conflicting with a known block and not in the mempool.
Definition: transaction.h:48
CMutableTransaction::vout
std::vector< CTxOut > vout
Definition: transaction.h:367
LOCK
#define LOCK(cs)
Definition: sync.h:226
wallet::CoinSelectionParams
Parameters for one iteration of Coin Selection.
Definition: coinselection.h:76
wallet::COutput
Definition: spend.h:17
node
Definition: init.h:22
CoinSet
std::set< CInputCoin > CoinSet
Definition: coin_selection.cpp:77
COIN
static constexpr CAmount COIN
The amount of satoshis in one BTC.
Definition: amount.h:15
CMutableTransaction
A mutable version of CTransaction.
Definition: transaction.h:364
BnBExhaustion
static void BnBExhaustion(benchmark::Bench &bench)
Definition: coin_selection.cpp:102
wallet::CoinEligibilityFilter
Parameters for filtering which OutputGroups we may use in coin selection.
Definition: coinselection.h:119
spend.h
wallet::filter_standard
static const CoinEligibilityFilter filter_standard(1, 6, 0)