coin_selection.cpp raw
1 // Copyright (c) 2012-present 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 <consensus/amount.h>
7 #include <outputtype.h>
8 #include <policy/feerate.h>
9 #include <policy/policy.h>
10 #include <primitives/transaction.h>
11 #include <random.h>
12 #include <sync.h>
13 #include <test/util/setup_common.h>
14 #include <util/check.h>
15 #include <util/result.h>
16 #include <wallet/coinselection.h>
17 #include <wallet/db.h>
18 #include <wallet/spend.h>
19 #include <wallet/sqlite.h>
20 #include <wallet/transaction.h>
21 #include <wallet/wallet.h>
22
23 #include <cstddef>
24 #include <cstdint>
25 #include <map>
26 #include <memory>
27 #include <optional>
28 #include <string>
29 #include <utility>
30 #include <vector>
31
32 namespace wallet {
33 static void addCoin(const CAmount& nValue, std::vector<std::unique_ptr<CWalletTx>>& wtxs)
34 {
35 static int nextLockTime = 0;
36 CMutableTransaction tx;
37 tx.nLockTime = nextLockTime++; // so all transactions get different hashes
38 tx.vout.resize(1);
39 tx.vout[0].nValue = nValue;
40 wtxs.push_back(std::make_unique<CWalletTx>(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
41 }
42
43 // This benchmark is based on a large diverse UTXO pool. The UTXOs are
44 // pseudorandomly generated and assigned one of the four relevant output types
45 // P2PKH, P2SH-P2WPKH, P2WPKH, and P2TR UTXOs.
46 // Smaller amounts are more likely to be generated than larger amounts. This
47 // UTXO pool is used to run coin selection for pseudorandom selection targets.
48 // Altogether, this gives us a deterministic benchmark with a somewhat
49 // representative coin selection scenario.
50 static void CoinSelection(benchmark::Bench& bench)
51 {
52 const auto test_setup = MakeNoLogFileContext<TestingSetup>();
53 CWallet wallet(test_setup->m_node.chain.get(), "", MakeInMemoryWalletDatabase());
54 std::vector<std::unique_ptr<CWalletTx>> wtxs;
55 LOCK(wallet.cs_wallet);
56
57 // Keep selection deterministic for benchmark stability
58 FastRandomContext det_rand{/*fDeterministic=*/true};
59
60 // Generate coin amounts biased towards smaller amounts
61 for (int i = 0; i < 400; ++i) {
62 CAmount amount;
63 int p{det_rand.randrange(100)};
64 if (p < 50) {
65 amount = 10'000 + det_rand.randrange(90'000);
66 } else if (p < 75) {
67 amount = 100'000 + det_rand.randrange(900'000);
68 } else if (p < 95) {
69 amount = 1'000'000 + det_rand.randrange(9'000'000);
70 } else {
71 amount = 10'000'000 + det_rand.randrange(90'000'000);
72 }
73 addCoin(amount, wtxs);
74 }
75
76 // Create coins from the amounts assigning them various output types
77 wallet::CoinsResult available_coins;
78 for (const auto& wtx : wtxs) {
79 const auto txout = wtx->tx->vout.at(0);
80 OutputType outtype;
81 int input_bytes;
82 int y{det_rand.randrange(100)};
83 if (y < 35) {
84 outtype = OutputType::LEGACY;
85 input_bytes = 148;
86 } else if (y < 55) {
87 outtype = OutputType::P2SH_SEGWIT;
88 input_bytes = 91;
89 } else if (y < 90) {
90 outtype = OutputType::BECH32;
91 input_bytes = 68;
92 } else {
93 outtype = OutputType::BECH32M;
94 input_bytes = 58;
95 }
96 CAmount fees = 20 * input_bytes;
97 available_coins.coins[outtype].emplace_back(COutPoint(wtx->GetHash(), 0), txout, /*depth=*/6 * 24, /*input_bytes=*/input_bytes, /*solvable=*/true, /*safe=*/true, wtx->GetTxTime(), /*from_me=*/true, /*fees=*/fees);
98 }
99
100 const CoinEligibilityFilter filter_standard(/*conf_mine=*/1, /*conf_theirs=*/6, /*max_ancestors=*/0);
101
102 constexpr size_t NUM_TARGETS{10};
103 std::vector<CAmount> targets;
104 targets.reserve(NUM_TARGETS);
105 for (size_t i{0}; i < NUM_TARGETS; ++i) {
106 targets.push_back(10'000'000 + det_rand.randrange(90'000'000));
107 }
108
109 std::optional<FastRandomContext> rng;
110 std::optional<CoinSelectionParams> params;
111 std::vector<wallet::OutputGroupTypeMap> groups;
112 bench.batch(NUM_TARGETS).unit("selection").epochIterations(1)
113 .setup([&] {
114 rng.emplace(/*fDeterministic=*/true);
115 params.emplace(*rng);
116
117 params->change_output_size = 31;
118 params->change_spend_size = 68;
119 params->m_min_change_target = CHANGE_LOWER;
120 params->m_effective_feerate = CFeeRate{20'000};
121 params->m_long_term_feerate = CFeeRate{10'000};
122 params->m_discard_feerate = CFeeRate{3000};
123 params->tx_noinputs_size = 72;
124 params->m_avoid_partial_spends = false;
125
126 params->m_change_fee = params->m_effective_feerate.GetFee(params->change_output_size);
127 params->min_viable_change = params->m_discard_feerate.GetFee(params->change_spend_size);
128 params->m_cost_of_change = params->min_viable_change + params->m_change_fee;
129
130 groups.assign(NUM_TARGETS, wallet::GroupOutputs(wallet, available_coins, *params, {{filter_standard}})[filter_standard]);
131 })
132 .run([&] {
133 for (size_t i{0}; i < NUM_TARGETS; ++i) {
134 auto result{AttemptSelection(wallet.chain(), targets[i], groups[i], *params, /*allow_mixed_output_types=*/true)};
135 assert(result && result->GetSelectedValue() >= targets[i]);
136 }
137 });
138 }
139
140 static void add_coin(const CAmount& nValue, uint32_t nInput, std::vector<OutputGroup>& set)
141 {
142 CMutableTransaction tx;
143 tx.vout.resize(nInput + 1);
144 tx.vout[nInput].nValue = nValue;
145 COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/0, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, /*fees=*/0);
146 set.emplace_back();
147 set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/0, /*cluster_count=*/0);
148 }
149
150 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
151 {
152 utxo_pool.clear();
153 CAmount target = 0;
154 for (int i = 0; i < utxos; ++i) {
155 target += CAmount{1} << (utxos+i);
156 add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
157 add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
158 }
159 return target;
160 }
161
162 static void BnBExhaustion(benchmark::Bench& bench)
163 {
164 std::vector<OutputGroup> utxo_pool;
165 CAmount target;
166 bench.setup([&] { target = make_hard_case(17, utxo_pool); })
167 .run([&] {
168 auto res{SelectCoinsBnB(utxo_pool, target, /*cost_of_change=*/0, MAX_STANDARD_TX_WEIGHT)}; // Should exhaust
169 ankerl::nanobench::doNotOptimizeAway(res);
170 });
171 }
172
173 BENCHMARK(CoinSelection);
174 BENCHMARK(BnBExhaustion);
175 }; // namespace wallet
176