Bitcoin Core  22.99.0
P2P Digital Currency
coin_selection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-2020 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 static void addCoin(const CAmount& nValue, const CWallet& wallet, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
15 {
16  static int nextLockTime = 0;
18  tx.nLockTime = nextLockTime++; // so all transactions get different hashes
19  tx.vout.resize(1);
20  tx.vout[0].nValue = nValue;
21  wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx))));
22 }
23 
24 // Simple benchmark for wallet coin selection. Note that it maybe be necessary
25 // to build up more complicated scenarios in order to get meaningful
26 // measurements of performance. From laanwj, "Wallet coin selection is probably
27 // the hardest, as you need a wider selection of scenarios, just testing the
28 // same one over and over isn't too useful. Generating random isn't useful
29 // either for measurements."
30 // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484)
31 static void CoinSelection(benchmark::Bench& bench)
32 {
34  auto chain = interfaces::MakeChain(node);
35  CWallet wallet(chain.get(), "", CreateDummyWalletDatabase());
36  std::vector<std::unique_ptr<CWalletTx>> wtxs;
37  LOCK(wallet.cs_wallet);
38 
39  // Add coins.
40  for (int i = 0; i < 1000; ++i) {
41  addCoin(1000 * COIN, wallet, wtxs);
42  }
43  addCoin(3 * COIN, wallet, wtxs);
44 
45  // Create coins
46  std::vector<COutput> coins;
47  for (const auto& wtx : wtxs) {
48  coins.emplace_back(wallet, *wtx, 0 /* iIn */, 6 * 24 /* nDepthIn */, true /* spendable */, true /* solvable */, true /* safe */);
49  }
50 
52  const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34,
53  /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
54  /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
55  /* tx_noinputs_size= */ 0, /* avoid_partial= */ false);
56  bench.run([&] {
57  std::set<CInputCoin> setCoinsRet;
58  CAmount nValueRet;
59  bool success = AttemptSelection(wallet, 1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params);
60  assert(success);
61  assert(nValueRet == 1003 * COIN);
62  assert(setCoinsRet.size() == 2);
63  });
64 }
65 
66 typedef std::set<CInputCoin> CoinSet;
67 
68 // Copied from src/wallet/test/coinselector_tests.cpp
69 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
70 {
72  tx.vout.resize(nInput + 1);
73  tx.vout[nInput].nValue = nValue;
74  CInputCoin coin(MakeTransactionRef(tx), nInput);
75  set.emplace_back();
76  set.back().Insert(coin, 0, true, 0, 0, false);
77 }
78 // Copied from src/wallet/test/coinselector_tests.cpp
79 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
80 {
81  utxo_pool.clear();
82  CAmount target = 0;
83  for (int i = 0; i < utxos; ++i) {
84  target += (CAmount)1 << (utxos+i);
85  add_coin((CAmount)1 << (utxos+i), 2*i, utxo_pool);
86  add_coin(((CAmount)1 << (utxos+i)) + ((CAmount)1 << (utxos-1-i)), 2*i + 1, utxo_pool);
87  }
88  return target;
89 }
90 
91 static void BnBExhaustion(benchmark::Bench& bench)
92 {
93  // Setup
94  std::vector<OutputGroup> utxo_pool;
95  CoinSet selection;
96  CAmount value_ret = 0;
97 
98  bench.run([&] {
99  // Benchmark
100  CAmount target = make_hard_case(17, utxo_pool);
101  SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret); // Should exhaust
102 
103  // Cleanup
104  utxo_pool.clear();
105  selection.clear();
106  });
107 }
108 
assert
assert(!tx.IsCoinBase())
CreateDummyWalletDatabase
std::unique_ptr< WalletDatabase > CreateDummyWalletDatabase()
Return object for accessing dummy database with no read/write capabilities.
Definition: walletdb.cpp:1183
wallet.h
make_hard_case
static CAmount make_hard_case(int utxos, std::vector< OutputGroup > &utxo_pool)
Definition: coin_selection.cpp:79
CoinSelection
static void CoinSelection(benchmark::Bench &bench)
Definition: coin_selection.cpp:31
BENCHMARK
BENCHMARK(CoinSelection)
interfaces::MakeChain
std::unique_ptr< Chain > MakeChain(NodeContext &node)
Return implementation of Chain interface.
Definition: interfaces.cpp:714
addCoin
static void addCoin(const CAmount &nValue, const CWallet &wallet, std::vector< std::unique_ptr< CWalletTx >> &wtxs)
Definition: coin_selection.cpp:14
add_coin
static void add_coin(const CAmount &nValue, int nInput, std::vector< OutputGroup > &set)
Definition: coin_selection.cpp:69
ankerl::nanobench::Bench
Main entry point to nanobench's benchmarking facility.
Definition: nanobench.h:616
MakeTransactionRef
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:387
wallet
Definition: interfaces.cpp:50
CoinEligibilityFilter
Parameters for filtering which OutputGroups we may use in coin selection.
Definition: coinselection.h:118
chain.h
context.h
CFeeRate
Fee rate in satoshis per kilobyte: CAmount / kB.
Definition: feerate.h:29
filter_standard
static const CoinEligibilityFilter filter_standard(1, 6, 0)
CMutableTransaction::nLockTime
uint32_t nLockTime
Definition: transaction.h:349
coinselection.h
SelectCoinsBnB
bool SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change, std::set< CInputCoin > &out_set, CAmount &value_ret)
Definition: coinselection.cpp:67
CoinSelectionParams
Parameters for one iteration of Coin Selection.
Definition: coinselection.h:75
AttemptSelection
bool AttemptSelection(const CWallet &wallet, const CAmount &nTargetValue, const CoinEligibilityFilter &eligibility_filter, std::vector< COutput > coins, std::set< CInputCoin > &setCoinsRet, CAmount &nValueRet, const CoinSelectionParams &coin_selection_params)
Shuffle and select coins until nTargetValue is reached while avoiding small change; This method is st...
Definition: spend.cpp:376
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
bench.h
CInputCoin
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:21
CMutableTransaction::vout
std::vector< CTxOut > vout
Definition: transaction.h:347
LOCK
#define LOCK(cs)
Definition: sync.h:226
CWallet
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
Definition: wallet.h:228
node
Definition: interfaces.cpp:68
CoinSet
std::set< CInputCoin > CoinSet
Definition: coin_selection.cpp:66
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:344
NodeContext
NodeContext struct containing references to chain state and connection state.
Definition: context.h:39
BnBExhaustion
static void BnBExhaustion(benchmark::Bench &bench)
Definition: coin_selection.cpp:91
spend.h