Bitcoin ABC  0.28.12
P2P Digital Currency
coin_selection.cpp
Go to the documentation of this file.
1 // Copyright (c) 2012-2016 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 <chainparams.h>
7 #include <consensus/amount.h>
8 #include <interfaces/chain.h>
9 #include <node/context.h>
10 #include <wallet/coinselection.h>
11 #include <wallet/spend.h>
12 #include <wallet/wallet.h>
13 
14 #include <memory>
15 #include <set>
16 
17 using node::NodeContext;
18 
19 static void addCoin(const Amount nValue, const CWallet &wallet,
20  std::vector<std::unique_ptr<CWalletTx>> &wtxs) {
21  static int nextLockTime = 0;
23  // so all transactions get different hashes
24  tx.nLockTime = nextLockTime++;
25  tx.vout.resize(1);
26  tx.vout[0].nValue = nValue;
27  wtxs.push_back(
28  std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx))));
29 }
30 
31 // Simple benchmark for wallet coin selection. Note that it maybe be necessary
32 // to build up more complicated scenarios in order to get meaningful
33 // measurements of performance. From laanwj, "Wallet coin selection is probably
34 // the hardest, as you need a wider selection of scenarios, just testing the
35 // same one over and over isn't too useful. Generating random isn't useful
36 // either for measurements."
37 // (https://github.com/bitcoin/bitcoin/issues/7883#issuecomment-224807484)
38 static void CoinSelection(benchmark::Bench &bench) {
40 
42  auto chain = interfaces::MakeChain(node, Params());
43  CWallet wallet(chain.get(), "", CreateDummyWalletDatabase());
44  wallet.SetupLegacyScriptPubKeyMan();
45  std::vector<std::unique_ptr<CWalletTx>> wtxs;
46  LOCK(wallet.cs_wallet);
47 
48  // Add coins.
49  for (int i = 0; i < 1000; ++i) {
50  addCoin(1000 * COIN, wallet, wtxs);
51  }
52  addCoin(3 * COIN, wallet, wtxs);
53 
54  // Create coins
55  std::vector<COutput> coins;
56  for (const auto &wtx : wtxs) {
57  coins.emplace_back(wallet, *wtx, 0 /* iIn */, 6 * 24 /* nDepthIn */,
58  true /* spendable */, true /* solvable */,
59  true /* safe */);
60  }
61 
64  true, 34, 148, CFeeRate(Amount::zero()), 0, false);
65  bench.run([&] {
66  std::set<CInputCoin> setCoinsRet;
67  Amount nValueRet;
68  bool bnb_used;
69  bool success = SelectCoinsMinConf(wallet, 1003 * COIN, filter_standard,
70  coins, setCoinsRet, nValueRet,
71  coin_selection_params, bnb_used);
72  assert(success);
73  assert(nValueRet == 1003 * COIN);
74  assert(setCoinsRet.size() == 2);
75  });
76 }
77 
78 typedef std::set<CInputCoin> CoinSet;
79 std::vector<std::unique_ptr<CWalletTx>> wtxn;
80 
81 // Copied from src/wallet/test/coinselector_tests.cpp
82 static void add_coin(const CWallet &wallet, const Amount nValue, int nInput,
83  std::vector<OutputGroup> &set) {
85  tx.vout.resize(nInput + 1);
86  tx.vout[nInput].nValue = nValue;
87  auto wtx = std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)));
88  set.emplace_back();
89  set.back().Insert(
90  COutput(wallet, *wtx, nInput, 0, true, true, true).GetInputCoin(), 0,
91  true, false);
92  wtxn.emplace_back(std::move(wtx));
93 }
94 
95 // Copied from src/wallet/test/coinselector_tests.cpp
96 static Amount make_hard_case(const CWallet &wallet, int utxos,
97  std::vector<OutputGroup> &utxo_pool) {
98  utxo_pool.clear();
99  Amount target = Amount::zero();
100  for (int i = 0; i < utxos; ++i) {
101  const Amount base = (int64_t(1) << (utxos + i)) * SATOSHI;
102  target += base;
103  add_coin(wallet, base, 2 * i, utxo_pool);
104  add_coin(wallet, base + (int64_t(1) << (utxos - 1 - i)) * SATOSHI,
105  2 * i + 1, utxo_pool);
106  }
107  return target;
108 }
109 
110 static void BnBExhaustion(benchmark::Bench &bench) {
112 
114  auto chain = interfaces::MakeChain(node, Params());
115  CWallet wallet(chain.get(), "", CreateDummyWalletDatabase());
116 
117  LOCK(wallet.cs_wallet);
118 
119  // Setup
120  wallet.SetupLegacyScriptPubKeyMan();
121  std::vector<OutputGroup> utxo_pool;
122  CoinSet selection;
123  Amount value_ret = Amount::zero();
124  Amount not_input_fees = Amount::zero();
125 
126  bench.run([&] {
127  // Benchmark
128  Amount target = make_hard_case(wallet, 17, utxo_pool);
129  // Should exhaust
130  SelectCoinsBnB(utxo_pool, target, Amount::zero(), selection, value_ret,
131  not_input_fees);
132 
133  // Cleanup
134  utxo_pool.clear();
135  selection.clear();
136  });
137 }
138 
static constexpr Amount SATOSHI
Definition: amount.h:143
static constexpr Amount COIN
Definition: amount.h:144
void SelectParams(const std::string &network)
Sets the params returned by Params() to those for the given BIP70 chain name.
const CChainParams & Params()
Return the currently selected parameters.
static const std::string REGTEST
Fee rate in satoshis per kilobyte: Amount / kB.
Definition: feerate.h:21
A mutable version of CTransaction.
Definition: transaction.h:274
std::vector< CTxOut > vout
Definition: transaction.h:277
Definition: spend.h:19
A CWallet maintains a set of transactions and balances, and provides the ability to create new transa...
Definition: wallet.h:253
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
static void CoinSelection(benchmark::Bench &bench)
static void add_coin(const CWallet &wallet, const Amount nValue, int nInput, std::vector< OutputGroup > &set)
static void addCoin(const Amount nValue, const CWallet &wallet, std::vector< std::unique_ptr< CWalletTx >> &wtxs)
static void BnBExhaustion(benchmark::Bench &bench)
std::vector< std::unique_ptr< CWalletTx > > wtxn
std::set< CInputCoin > CoinSet
static Amount make_hard_case(const CWallet &wallet, int utxos, std::vector< OutputGroup > &utxo_pool)
BENCHMARK(CoinSelection)
bool SelectCoinsBnB(std::vector< OutputGroup > &utxo_pool, const Amount &target_value, const Amount &cost_of_change, std::set< CInputCoin > &out_set, Amount &value_ret, const Amount not_input_fees)
This is the Branch and Bound Coin Selection algorithm designed by Murch.
CoinSelectionParams coin_selection_params(false, 0, 0, CFeeRate(Amount::zero()), 0, false)
CoinEligibilityFilter filter_standard(1, 6)
std::unique_ptr< Chain > MakeChain(node::NodeContext &node, const CChainParams &params)
Return implementation of Chain interface.
Definition: interfaces.cpp:788
Definition: init.h:28
static CTransactionRef MakeTransactionRef()
Definition: transaction.h:316
bool SelectCoinsMinConf(const CWallet &wallet, const Amount nTargetValue, const CoinEligibilityFilter &eligibility_filter, std::vector< COutput > coins, std::set< CInputCoin > &setCoinsRet, Amount &nValueRet, const CoinSelectionParams &coin_selection_params, bool &bnb_used)
Shuffle and select coins until nTargetValue is reached while avoiding small change; This method is st...
Definition: spend.cpp:419
Definition: amount.h:19
static constexpr Amount zero() noexcept
Definition: amount.h:32
NodeContext struct containing references to chain state and connection state.
Definition: context.h:38
#define LOCK(cs)
Definition: sync.h:306
assert(!tx.IsCoinBase())
std::unique_ptr< WalletDatabase > CreateDummyWalletDatabase()
Return object for accessing dummy database with no read/write capabilities.
Definition: walletdb.cpp:1170