Inside Bitcoin

1// Copyright (c) 2017-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 <consensus/amount.h>
6#include <node/context.h>
7#include <policy/policy.h>
8#include <primitives/transaction.h>
9#include <random.h>
10#include <test/util/common.h>
11#include <test/util/setup_common.h>
12#include <util/translation.h>
13#include <wallet/coincontrol.h>
14#include <wallet/coinselection.h>
15#include <wallet/spend.h>
16#include <wallet/test/util.h>
17#include <wallet/test/wallet_test_fixture.h>
18#include <wallet/wallet.h>
19
20#include <algorithm>
21#include <boost/test/unit_test.hpp>
22#include <random>
23
24namespace wallet {
25BOOST_FIXTURE_TEST_SUITE(coinselector_tests, WalletTestingSetup)
26
27// how many times to run all the tests to have a chance to catch errors that only show up with particular random shuffles
28#define RUN_TESTS 100
29
30// some tests fail 1% of the time due to bad luck.
31// we repeat those tests this many times and only complain if all iterations of the test fail
32#define RANDOM_REPEATS 5
33
34static const CoinEligibilityFilter filter_standard(1, 6, 0);
35static const CoinEligibilityFilter filter_confirmed(1, 1, 0);
36static const CoinEligibilityFilter filter_standard_extra(6, 6, 0);
37static int nextLockTime = 0;
38
39static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
40{
41    CMutableTransaction tx;
42    tx.vout.resize(nInput + 1);
43    tx.vout[nInput].nValue = nValue;
44    tx.nLockTime = nextLockTime++;        // so all transactions get different hashes
45    COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/ 0);
46    OutputGroup group;
47    group.Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*cluster_count=*/ 0);
48    result.AddInput(group);
49}
50
51static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee)
52{
53    CMutableTransaction tx;
54    tx.vout.resize(nInput + 1);
55    tx.vout[nInput].nValue = nValue;
56    tx.nLockTime = nextLockTime++;        // so all transactions get different hashes
57    std::shared_ptr<COutput> coin = std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/148, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, fee);
58    OutputGroup group;
59    group.Insert(coin, /*ancestors=*/ 0, /*cluster_count=*/ 0);
60    coin->long_term_fee = long_term_fee; // group.Insert() will modify long_term_fee, so we need to set it afterwards
61    result.AddInput(group);
62}
63
64static void add_coin(CoinsResult& available_coins, CWallet& wallet, const CAmount& nValue, CFeeRate feerate = CFeeRate(0), int nAge = 6*24, bool fIsFromMe = false, int nInput =0, bool spendable = false, int custom_size = 0)
65{
66    CMutableTransaction tx;
67    tx.nLockTime = nextLockTime++;        // so all transactions get different hashes
68    tx.vout.resize(nInput + 1);
69    tx.vout[nInput].nValue = nValue;
70    if (spendable) {
71        tx.vout[nInput].scriptPubKey = GetScriptForDestination(*Assert(wallet.GetNewDestination(OutputType::BECH32, "")));
72    }
73    Txid txid = tx.GetHash();
74
75    LOCK(wallet.cs_wallet);
76    auto ret = wallet.mapWallet.emplace(std::piecewise_construct, std::forward_as_tuple(txid), std::forward_as_tuple(MakeTransactionRef(std::move(tx)), TxStateInactive{}));
77    assert(ret.second);
78    CWalletTx& wtx = (*ret.first).second;
79    const auto& txout = wtx.GetTx()->vout.at(nInput);
80    available_coins.Add(OutputType::BECH32, {COutPoint(wtx.GetHash(), nInput), txout, nAge, custom_size == 0 ? CalculateMaximumSignedInputSize(txout, &wallet, /*coin_control=*/nullptr) : custom_size, /*solvable=*/true, /*safe=*/true, wtx.GetTxTime(), fIsFromMe, feerate});
81}
82
83// Helpers
84std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
85                                              CAmount change_target, FastRandomContext& rng)
86{
87    auto res{KnapsackSolver(groups, nTargetValue, change_target, rng, MAX_STANDARD_TX_WEIGHT)};
88    return res ? std::optional<SelectionResult>(*res) : std::nullopt;
89}
90
91std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change)
92{
93    auto res{SelectCoinsBnB(utxo_pool, selection_target, cost_of_change, MAX_STANDARD_TX_WEIGHT)};
94    return res ? std::optional<SelectionResult>(*res) : std::nullopt;
95}
96
97/** Check if SelectionResult a is equivalent to SelectionResult b.
98 * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */
99static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
100{
101    std::vector<CAmount> a_amts;
102    std::vector<CAmount> b_amts;
103    for (const auto& coin : a.GetInputSet()) {
104        a_amts.push_back(coin->txout.nValue);
105    }
106    for (const auto& coin : b.GetInputSet()) {
107        b_amts.push_back(coin->txout.nValue);
108    }
109    std::sort(a_amts.begin(), a_amts.end());
110    std::sort(b_amts.begin(), b_amts.end());
111
112    std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
113    return ret.first == a_amts.end() && ret.second == b_amts.end();
114}
115
116/** Check if this selection is equal to another one. Equal means same inputs (i.e same value and prevout) */
117static bool EqualResult(const SelectionResult& a, const SelectionResult& b)
118{
119    std::pair<OutputSet::iterator, OutputSet::iterator> ret = std::mismatch(a.GetInputSet().begin(), a.GetInputSet().end(), b.GetInputSet().begin(),
120        [](const std::shared_ptr<COutput>& a, const std::shared_ptr<COutput>& b) {
121            return a->outpoint == b->outpoint;
122        });
123    return ret.first == a.GetInputSet().end() && ret.second == b.GetInputSet().end();
124}
125
126inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins, bool subtract_fee_outputs = false)
127{
128    static std::vector<OutputGroup> static_groups;
129    static_groups.clear();
130    for (auto& coin : available_coins) {
131        static_groups.emplace_back();
132        OutputGroup& group = static_groups.back();
133        group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/ 0, /*cluster_count=*/ 0);
134        group.m_subtract_fee_outputs = subtract_fee_outputs;
135    }
136    return static_groups;
137}
138
139inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinsResult& available_coins, CWallet& wallet, const CoinEligibilityFilter& filter)
140{
141    FastRandomContext rand{};
142    CoinSelectionParams coin_selection_params{
143        rand,
144        /*change_output_size=*/ 0,
145        /*change_spend_size=*/ 0,
146        /*min_change_target=*/ CENT,
147        /*effective_feerate=*/ CFeeRate(0),
148        /*long_term_feerate=*/ CFeeRate(0),
149        /*discard_feerate=*/ CFeeRate(0),
150        /*tx_noinputs_size=*/ 0,
151        /*avoid_partial=*/ false,
152    };
153    static OutputGroupTypeMap static_groups;
154    static_groups = GroupOutputs(wallet, available_coins, coin_selection_params, {{filter}})[filter];
155    return static_groups.all_groups.mixed_group;
156}
157
158static std::unique_ptr<CWallet> NewWallet(const node::NodeContext& m_node, const std::string& wallet_name = "")
159{
160    std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), wallet_name, CreateMockableWalletDatabase());
161    LOCK(wallet->cs_wallet);
162    wallet->SetWalletFlag(WALLET_FLAG_DESCRIPTORS);
163    wallet->SetupDescriptorScriptPubKeyMans();
164    return wallet;
165}
166
167// Branch and bound coin selection tests
168BOOST_AUTO_TEST_CASE(bnb_search_test)
169{
170    FastRandomContext rand{};
171    // Setup
172    SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB);
173    size_t expected_attempts;
174
175    ////////////////////
176    // Behavior tests //
177    ////////////////////
178
179    // Make sure that effective value is working in AttemptSelection when BnB is used
180    CoinSelectionParams coin_selection_params_bnb{
181        rand,
182        /*change_output_size=*/ 31,
183        /*change_spend_size=*/ 68,
184        /*min_change_target=*/ 0,
185        /*effective_feerate=*/ CFeeRate(3000),
186        /*long_term_feerate=*/ CFeeRate(1000),
187        /*discard_feerate=*/ CFeeRate(1000),
188        /*tx_noinputs_size=*/ 0,
189        /*avoid_partial=*/ false,
190    };
191    coin_selection_params_bnb.m_change_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_output_size);
192    coin_selection_params_bnb.m_cost_of_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size) + coin_selection_params_bnb.m_change_fee;
193    coin_selection_params_bnb.min_viable_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size);
194
195    {
196        std::unique_ptr<CWallet> wallet = NewWallet(m_node);
197
198        CoinsResult available_coins;
199
200        add_coin(available_coins, *wallet, 1, coin_selection_params_bnb.m_effective_feerate);
201        available_coins.All().at(0).input_bytes = 40; // Make sure that it has a negative effective value. The next check should assert if this somehow got through. Otherwise it will fail
202        BOOST_CHECK(!SelectCoinsBnB(GroupCoins(available_coins.All()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change));
203
204        // Test fees subtracted from output:
205        available_coins = {};
206        add_coin(available_coins, *wallet, 1 * CENT, coin_selection_params_bnb.m_effective_feerate);
207        available_coins.All().at(0).input_bytes = 40;
208        const auto result9 = SelectCoinsBnB(GroupCoins(available_coins.All()), 1 * CENT, coin_selection_params_bnb.m_cost_of_change);
209        BOOST_CHECK(result9);
210        BOOST_CHECK_EQUAL(result9->GetSelectedValue(), 1 * CENT);
211        expected_attempts = 1;
212        BOOST_CHECK_MESSAGE(result9->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result9->GetSelectionsEvaluated()));
213    }
214
215    {
216        std::unique_ptr<CWallet> wallet = NewWallet(m_node);
217
218        CoinsResult available_coins;
219
220        coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
221        add_coin(available_coins, *wallet, 5 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
222        add_coin(available_coins, *wallet, 3 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
223        add_coin(available_coins, *wallet, 2 * CENT, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);
224        CCoinControl coin_control;
225        coin_control.m_allow_other_inputs = true;
226        COutput select_coin = available_coins.All().at(0);
227        coin_control.Select(select_coin.outpoint);
228        CoinsResult selected_input;
229        selected_input.Add(OutputType::BECH32, select_coin);
230        available_coins.Erase({available_coins.coins[OutputType::BECH32].begin()->outpoint});
231
232        LOCK(wallet->cs_wallet);
233        const auto result10 = SelectCoins(*wallet, available_coins, selected_input, 10 * CENT, coin_control, coin_selection_params_bnb);
234        BOOST_CHECK(result10);
235        expected_attempts = 3;
236        BOOST_CHECK_MESSAGE(result10->GetSelectionsEvaluated() == expected_attempts, strprintf("Expected %i attempts, but got %i", expected_attempts, result10->GetSelectionsEvaluated()));
237    }
238    {
239        std::unique_ptr<CWallet> wallet = NewWallet(m_node);
240        LOCK(wallet->cs_wallet); // Every 'SelectCoins' call requires it
241
242        CoinsResult available_coins;
243
244        // pre selected coin should be selected even if disadvantageous
245        coin_selection_params_bnb.m_effective_feerate = CFeeRate(5000);
246        coin_selection_params_bnb.m_long_term_feerate = CFeeRate(3000);
247
248        // Add selectable outputs, increasing their raw amounts by their input fee to make the effective value equal to the raw amount
249        CAmount input_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(/*virtual_bytes=*/68); // bech32 input size (default test output type)
250        add_coin(available_coins, *wallet, 10 * CENT + input_fee, coin_selection_params_bnb.m_effective_feerate, 6 * 24, false, 0, true);