This PR is splitting off some of the improvements made in #28985 and starts addressing the issues raised in #27754.
I aim to completely replace coinselector_tests with coinselection_tests. The goal is to generally use coins created per a nominal effective value so we can get away from testing with CoinSelectionParams that are non-representative and effectuate counterintuitive behavior such as feerate = 0 or cost_of_change = 0
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For detailed information about the code coverage, see the test coverage report.
See the guideline for information on the review process. A summary of reviews will appear here.
No conflicts as of last run.
64+}
65+
66+/** Make multiple coins with given effective values */
67+static void AddCoins(std::vector<COutput>& utxo_pool, std::vector<CAmount> coins, CFeeRate feerate = default_cs_params.m_effective_feerate)
68+{
69+ for (int c : coins) {
In 3dff8f0490b4b92c4adf229a828063dfda6d3a80 “[test] Create coinselection_tests”
The elements in coins are CAmount, not int.
73+
74+/** Group available coins into OutputGroups */
75+inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins, const CoinSelectionParams& cs_params = default_cs_params, bool subtract_fee_outputs = false)
76+{
77+ static std::vector<OutputGroup> static_groups;
78+ static_groups.clear();
In 3dff8f0490b4b92c4adf229a828063dfda6d3a80 “[test] Create coinselection_tests”
There doesn’t seem to be a purpose for having a static variable here. We basically treat it as temporary since it’s cleared every time.
70+ utxo_pool.push_back(MakeCoin(c, true, 0, feerate));
71+ }
72+}
73+
74+/** Group available coins into OutputGroups */
75+inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& available_coins, const CoinSelectionParams& cs_params = default_cs_params, bool subtract_fee_outputs = false)
In 3dff8f0490b4b92c4adf229a828063dfda6d3a80 “[test] Create coinselection_tests”
Since the expected pattern is to always GroupCoins(utxo_pool), it might make sense to make utxo_pool a std::vector<OutputGroup> and combine this function with AddCoins.
103@@ -104,5 +104,40 @@ static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
104 return ret.first == a_amts.end() && ret.second == b_amts.end();
105 }
106
107+static void TestBnBSuccess(std::string test_title, std::vector<COutput>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CFeeRate& feerate = default_cs_params.m_effective_feerate)
108+{
109+ SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB);
110+ CAmount expected_amount = 0;
111+ for (int input_amount : expected_input_amounts) {
In e286c6470bbaa1358fecb7c5a7e109583d158780 “[test] Recreate simple BnB success tests”
The elements of expected_input_amounts are CAmount not int.
115+ group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/ 0, /*descendants=*/ 0);
116+ expected_result.AddInput(group);
117+ }
118+
119+ const auto result = SelectCoinsBnB(GroupCoins(utxo_pool), selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT);
120+ BOOST_CHECK_MESSAGE(result, "BnB-Success: " + test_title);
In e286c6470bbaa1358fecb7c5a7e109583d158780 “[test] Recreate simple BnB success tests”
The *_MESSAGE functions print out the message on failure, not on success. So the message should be something that better indicates what the failure was, not something that might suggest something was successful.
51+}
52+
53+static const CoinSelectionParams default_cs_params = init_default_params();
54+
55+/** Make one coin that either has a given effective value (default) or a given amount (`is_eff_value = false`). */
56+static COutput MakeCoin(const CAmount& amount, bool is_eff_value = true, int nInput = 0, CFeeRate feerate = default_cs_params.m_effective_feerate, int custom_spending_vsize = 68)
nInput from the function parameters of MakeCoin(…).
18+#include <wallet/test/wallet_test_fixture.h>
19+#include <wallet/wallet.h>
20+
21+#include <algorithm>
22+#include <boost/test/unit_test.hpp>
23+#include <random>
In https://github.com/bitcoin/bitcoin/commit/3dff8f0490b4b92c4adf229a828063dfda6d3a80:
I don’t think we need all this includes. For instance, no wallet is used and <wallet/wallet.h> is included, no fee function is used and wallet/fees.h is included, <random.h> and <random> are included.
Maybe run IOWY to clean this up.
I was able to remove all except for
0#include <consensus/amount.h>
1#include <wallet/coinselection.h>
2#include <wallet/test/wallet_test_fixture.h>
3
4#include <boost/test/unit_test.hpp>
I’m not familiar with IOWY and could not turn up anything with a websearch, what is that?
I’m not familiar with IOWY and could not turn up anything with a websearch, what is that?
Upps, the acronym is IWYU from include-what-you-use. I wrote it fast as IOWY “include only what you use”. Should stop using acronyms..
118+
119+ const auto result = SelectCoinsBnB(GroupCoins(utxo_pool), selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT);
120+ BOOST_CHECK_MESSAGE(result, "BnB-Success: " + test_title);
121+ BOOST_CHECK(EquivalentResult(expected_result, *result));
122+ BOOST_CHECK_EQUAL(result->GetSelectedValue(), expected_amount);
123+ expected_result.Clear();
In e286c6470b:
No need to clear expected_result. It’s created within this function.
I’m not completely sure about 584e524eb57444d7192df1049cafde9ccc480406. The commit description says
Originally these tests verified that at a SelectCoins level that a solution with fewer inputs gets preferred at high feerates, and a solution with more inputs gets preferred at low feerates. This outcome relies on the behavior of BnB, so we move these tests under the umbrella of BnB tests.
It is true that the outcome relies only on the BnB behavior currently but that might not be true in the future. There could be other algorithm clashing with it.
9+#include <boost/test/unit_test.hpp>
10+
11+namespace wallet {
12+BOOST_FIXTURE_TEST_SUITE(coinselection_tests, WalletTestingSetup)
13+
14+static int nextLockTime = 0;
40+
41+/** Make one coin that either has a given effective value (default) or a given amount (`is_eff_value = false`). */
42+static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, CoinSelectionParams cs_params = default_cs_params, int custom_spending_vsize = 68)
43+{
44+ // Always assume that we only have one input
45+ const int nInput = 0;
nInput is unused, let’s remove it.
47+ tx.vout.resize(nInput + 1);
48+ CAmount fees = cs_params.m_effective_feerate.GetFee(custom_spending_vsize);
49+ tx.vout[nInput].nValue = amount + int(is_eff_value) * fees;
50+ tx.nLockTime = nextLockTime++; // so all transactions get different hashes
51+ OutputGroup group(cs_params);
52+ group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ custom_spending_vsize, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ fees), /*ancestors=*/0, /*descendants=*/0);
51+ OutputGroup group(cs_params);
52+ group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/ 1, /*input_bytes=*/ custom_spending_vsize, /*spendable=*/ true, /*solvable=*/ true, /*safe=*/ true, /*time=*/ 0, /*from_me=*/ false, /*fees=*/ fees), /*ancestors=*/0, /*descendants=*/0);
53+ return group;
54+}
55+
56+/** Make multiple coins with given effective values */
80@@ -80,5 +81,37 @@ static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
81 return ret.first == a_amts.end() && ret.second == b_amts.end();
82 }
83
84+static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams cs_params = default_cs_params)
Should be a reference.
0static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const std::vector<CAmount>& expected_input_amounts, const CoinSelectionParams& cs_params = default_cs_params)
89+ OutputGroup group = MakeCoin(input_amount, true, cs_params);
90+ expected_amount += group.m_value;
91+ expected_result.AddInput(group);
92+ }
93+
94+ const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT);
0 const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT);
101+{
102+ std::vector<OutputGroup> utxo_pool;
103+ AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT});
104+
105+ // Simple success cases
106+ TestBnBSuccess("Select smallest UTXO", utxo_pool, /*selection_target=*/ 1 * CENT, /*expected_input_amounts=*/ {1 * CENT});
108+ TestBnBSuccess("Select biggest UTXO", utxo_pool, /*selection_target=*/ 5 * CENT, /*expected_input_amounts=*/ {5 * CENT});
109+ TestBnBSuccess("Select two UTXOs", utxo_pool, /*selection_target=*/ 4 * CENT, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT});
110+ TestBnBSuccess("Select all UTXOs", utxo_pool, /*selection_target=*/ 9 * CENT, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT, 5 * CENT});
111+
112+ // BnB finds changeless solution while overshooting by up to cost_of_change
113+ TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/ 9 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT, 5 * CENT});
Should not overselect, so we could do this with 4×CENT
0 TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/ 4 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT});
120+ AddCoins(low_feerate_pool, {2 * CENT, 3 * CENT, 5 * CENT, 10 * CENT});
121+ TestBnBSuccess("Select many inputs at low feerates", low_feerate_pool, /*selection_target=*/ 10 * CENT, /*expected_input_amounts=*/ {2 * CENT, 3 * CENT, 5 * CENT});
122+
123+ std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB)
124+ CoinSelectionParams high_feerate_params = init_default_params();
125+ high_feerate_params.m_effective_feerate = CFeeRate{25'000};
0 CoinSelectionParams high_feerate_params = init_default_params();
1 high_feerate_params.m_effective_feerate = CFeeRate{25'000};
2 std::vector<OutputGroup> high_feerate_pool; // 25 sat/vB (greater than long_term_feerate of 10 sat/vB)
103@@ -104,9 +104,18 @@ static void TestBnBSuccess(std::string test_title, std::vector<OutputGroup>& utx
104 BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, "Selected amount mismatch in BnB-Success: " + test_title);
105 }
106
107+static void TestBnBFail(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target)
108+{
109+ BOOST_CHECK_MESSAGE(!SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/ default_cs_params.m_cost_of_change, /*max_weight=*/MAX_STANDARD_TX_WEIGHT), "BnB-Fail: " + test_title);
127@@ -119,6 +128,14 @@ BOOST_AUTO_TEST_CASE(bnb_test)
128 // BnB finds changeless solution while overshooting by up to cost_of_change
129 TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/ 9 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/ {1 * CENT, 3 * CENT, 5 * CENT});
130
131+ // BnB fails to find changeless solution when overshooting by cost_of_change + 1 sat
132+ TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/ 9 * CENT - default_cs_params.m_cost_of_change - 1);
0 TestBnBFail("Overshoot upper bound", utxo_pool, /*selection_target=*/4 * CENT - default_cs_params.m_cost_of_change - 1);
112 BOOST_AUTO_TEST_CASE(bnb_test)
113 {
114 std::vector<OutputGroup> utxo_pool;
115+
116+ // Fail for empty UTXO pool
117+ TestBnBFail("Empty UTXO pool", utxo_pool, /*selection_target=*/ 1 * CENT);
I’m not completely sure about 584e524. The commit description says
Originally these tests verified that at a SelectCoins level that a solution with fewer inputs gets preferred at high feerates, and a solution with more inputs gets preferred at low feerates. This outcome relies on the behavior of BnB, so we move these tests under the umbrella of BnB tests.
It is true that the outcome relies only on the BnB behavior currently but that might not be true in the future. There could be other algorithm clashing with it.
Yeah, so the old tests assumed that because BnB behaved a certain way, we would get a specific overall outcome. The new tests just check that BnB behaves a certain way. We might still want tests that test the overall outcome as a result from the interaction of multiple coin selection tests, but this one seemed clearly to be testing BnB behavior, and it seemed strange to me to be testing that at the level where the results are combined rather than checking that BnB assumptions are fulfilled by BnB.
Adds a Test Suite, default coin selection parameters as well as helper
functions for creating available coins and to check results.
🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/29957535397
Make sure to run all tests locally, according to the documentation.
The failure may happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
Originally these tests verified that at a SelectCoins level that a
solution with fewer inputs gets preferred at high feerates, and a
solution with more inputs gets preferred at low feerates. This outcome
relies on the behavior of BnB, so we move these tests under the umbrella
of BnB tests.
Originally these tests relied on SFFO to work.
We do not need to repeat the same test multiple times because BnB is
deterministic and will therefore always have the same outcome.
Additionally, this test was redundant because it repeats the "Smallest
combination too big" test.
7+#include <wallet/test/wallet_test_fixture.h>
8+
9+#include <boost/test/unit_test.hpp>
10+
11+namespace wallet {
12+BOOST_FIXTURE_TEST_SUITE(coinselection_tests, WalletTestingSetup)
WalletTestingSetup wallet. So we could save some initialization time on each test case by changing it to TestingSetup. And if any future test requires a wallet, it could be specified in-place.
Labels
Tests