Bitcoin Core  24.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 <wallet/coinselection.h>
9 #include <wallet/spend.h>
10 #include <wallet/wallet.h>
11 
12 #include <set>
13 
14 using node::NodeContext;
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  wallet::CoinsResult available_coins;
60  for (const auto& wtx : wtxs) {
61  const auto txout = wtx->tx->vout.at(0);
62  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);
63  }
64 
66  FastRandomContext rand{};
67  const CoinSelectionParams coin_selection_params{
68  rand,
69  /*change_output_size=*/ 34,
70  /*change_spend_size=*/ 148,
71  /*min_change_target=*/ CHANGE_LOWER,
72  /*effective_feerate=*/ CFeeRate(0),
73  /*long_term_feerate=*/ CFeeRate(0),
74  /*discard_feerate=*/ CFeeRate(0),
75  /*tx_noinputs_size=*/ 0,
76  /*avoid_partial=*/ false,
77  };
78  bench.run([&] {
79  auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, available_coins, coin_selection_params, /*allow_mixed_output_types=*/true);
80  assert(result);
81  assert(result->GetSelectedValue() == 1003 * COIN);
82  assert(result->GetInputSet().size() == 2);
83  });
84 }
85 
86 // Copied from src/wallet/test/coinselector_tests.cpp
87 static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>& set)
88 {
90  tx.vout.resize(nInput + 1);
91  tx.vout[nInput].nValue = nValue;
92  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);
93  set.emplace_back();
94  set.back().Insert(output, /*ancestors=*/ 0, /*descendants=*/ 0, /*positive_only=*/ false);
95 }
96 // Copied from src/wallet/test/coinselector_tests.cpp
97 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
98 {
99  utxo_pool.clear();
100  CAmount target = 0;
101  for (int i = 0; i < utxos; ++i) {
102  target += CAmount{1} << (utxos+i);
103  add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
104  add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
105  }
106  return target;
107 }
108 
109 static void BnBExhaustion(benchmark::Bench& bench)
110 {
111  // Setup
112  std::vector<OutputGroup> utxo_pool;
113 
114  bench.run([&] {
115  // Benchmark
116  CAmount target = make_hard_case(17, utxo_pool);
117  SelectCoinsBnB(utxo_pool, target, 0); // Should exhaust
118 
119  // Cleanup
120  utxo_pool.clear();
121  });
122 }
123 
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:36
Fast randomness source.
Definition: random.h:143
Main entry point to nanobench's benchmarking facility.
Definition: nanobench.h:616
Bench & run(char const *benchmarkName, Op &&op)
Repeatedly calls op() based on the configuration, and performs measurements.
Definition: nanobench.h:1183
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
Definition: wallet.h:237
A transaction with a bunch of additional info that only the owner cares about.
Definition: transaction.h:138
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:797
Definition: init.h:25
Definition: node.h:39
static const CoinEligibilityFilter filter_standard(1, 6, 0)
static constexpr CAmount CHANGE_LOWER
lower bound for randomly-chosen target change amount
Definition: coinselection.h:20
std::unique_ptr< WalletDatabase > CreateDummyWalletDatabase()
Return object for accessing dummy database with no read/write capabilities.
Definition: walletdb.cpp:1236
int CalculateMaximumSignedInputSize(const CTxOut &txout, const COutPoint outpoint, const SigningProvider *provider, const CCoinControl *coin_control)
Definition: spend.cpp:33
std::optional< SelectionResult > SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const CAmount &selection_target, const CAmount &cost_of_change)
static int nextLockTime
util::Result< SelectionResult > AttemptSelection(const CWallet &wallet, const CAmount &nTargetValue, const CoinEligibilityFilter &eligibility_filter, const CoinsResult &available_coins, 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:494
std::shared_ptr< CWallet > wallet
static CTransactionRef MakeTransactionRef(Tx &&txIn)
Definition: transaction.h:422
A mutable version of CTransaction.
Definition: transaction.h:380
uint256 GetHash() const
Compute the hash of this CMutableTransaction.
Definition: transaction.cpp:68
std::vector< CTxOut > vout
Definition: transaction.h:382
NodeContext struct containing references to chain state and connection state.
Definition: context.h:43
A UTXO under consideration for use in funding a new transaction.
Definition: coinselection.h:25
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:48
#define LOCK(cs)
Definition: sync.h:258
ArgsManager gArgs
Definition: system.cpp:73
assert(!tx.IsCoinBase())