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 details see: https://corecheck.dev/bitcoin/bitcoin/pulls/29532.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | achow101, monlovesmango, w0xlt |
| Concept ACK | jasonribble, ismaelsadeeq, yancyribbens |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
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.
🚧 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.
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.
CONTRIBUTIONS.md file, there are some other conventions used by other contributors too, in a similar fashion to conventional commits with (wallet:, ci:, rpc:). In that spirit, wouldn’t be a good idea to, in case there needs to be a change in some of the commits, to change from [test] to test: or coinselection: to scope the commits a little bit more and move towards a common format? Also, do you think is worth to add these conventions to the CONTRIBUTIONS.md file?
160+ TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs);
161+
162+ // Starting with 18 unique UTXOs of similar effective value we will not find the solution
163+ AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17});
164+ TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT);
165+}
51+ OutputGroup group(cs_params);
52+ group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /*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 OutpuGroups with the given values as their effective value */
30+ /*tx_noinputs_size=*/11 + 31, //static header size + output size
31+ /*avoid_partial=*/false,
32+ };
33+ dcsp.m_change_fee = /*155 sats=*/dcsp.m_effective_feerate.GetFee(dcsp.change_output_size);
34+ dcsp.m_cost_of_change = /*204 + 155 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size) + dcsp.m_change_fee;
35+ dcsp.min_viable_change = /*204 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size);
Can we eliminate a call to GetFee via reordering assignment?
0 dcsp.m_change_fee = /*155 sats=*/dcsp.m_effective_feerate.GetFee(dcsp.change_output_size);
1 dcsp.min_viable_change = /*204 sats=*/dcsp.m_discard_feerate.GetFee(dcsp.change_spend_size);
2 dcsp.m_cost_of_change = /*204 + 155 sats=*/dcsp.min_viable_change + dcsp.m_change_fee;
8@@ -9,6 +9,7 @@ target_sources(test_bitcoin
9 init_test_fixture.cpp
10 wallet_test_fixture.cpp
11 coinselector_tests.cpp
12+ coinselection_tests.cpp
159+ // Among up to 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest
160+ TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs);
161+
162+ // Starting with 18 unique UTXOs of similar effective value we will not find the solution
163+ AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17});
164+ TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT);
TOTAL_TRIES limit of 100,000. This test follows the same approach but is slightly different than the one in the original tests. I wanted to replace the old test because I found it too difficult to parse, but I came up with my own way of testing it. I have expanded the explanation of what is going on here, and how I created this artificial example that manages to exhaust the limit with only 18 UTXOs.—To be clear, usually we would be able to handle much bigger UTXO pools and still find solutions, this UTXO pool is specifically crafted to cause all possible combinations to be explored.
133- add_coin(CAmount{1} << (utxos+i), 2*i, utxo_pool);
134- add_coin((CAmount{1} << (utxos+i)) + (CAmount{1} << (utxos-1-i)), 2*i + 1, utxo_pool);
135- }
136- return target;
137-}
138-
make_hard works. Thanks for replacing it with a version that actually explains itself instead of making it a mensa test.
Also, do you think is worth to add these conventions to the
CONTRIBUTIONS.mdfile?
I don’t know! It would be a good thing to ask in the IRC channel or at the weekly meeting. :)
So C++ noob question. Not sure if this is an appropriate place to ask.
I’m noticing that you’re calling CFeeRate with an int:
https://github.com/bitcoin/bitcoin/blob/280e65d3a7993ea38ba49ae00133a7ba709c193e/src/wallet/test/coinselection_tests.cpp#L20-L38
Okay that’s cool, clearly it compiles and runs…but how?
src/policy/feerate.h has the class definition. I don’t see how it’s able to only take an int
This is my best bet of how it works
it’s using std::integral, maybe doing some weird magic I didn’t know we had. But, I don’t see #include <concepts>.
Btw, this curiosity all started because my editor highlighted this error
0no instance of constructor "CFeeRate::CFeeRate" matches the argument listC/C++(289)
Then in src/policy/feerate.h it the IDE says
namespace "std" has no member "integral"C/C++(135)
I see that it does compile but where does CFeeRate get constructed with only an int?
template<std::integral I> is the same as template<typename I>, with the added restriction that I must be a type that satisfies the std::integral concept. Since int does satisfy that concept, I can be instantiated as int.
@jasonribble
template<std::integral I>is the same astemplate<typename I>, with the added restriction thatImust be a type that satisfies thestd::integralconcept. Sinceintdoes satisfy that concept,Ican be instantiated asint.
Magical. Thank you 🙏
But, I don’t see #include <concepts>.
If you check the IWYU logs in the “tidy” CI job you will see that it is indeed missing:
0[19:28:01.280] /ci_container_base/src/policy/feerate.h should add these lines:
1[19:28:01.280] #include <concepts> // for integral
This report is generated on each CI run, but the missing includes are not enforced. This can be confusing, so best to always check the CI output.
it is indeed missing
Oh interesting! Well, I guess not in this important for this PR, but perhaps it should be explicit. Especially so people don’t get those evil red lines
ACK
I went through each of the commits. It is an improvement of the branch and bound selection tests.
97+}
98+
99+BOOST_AUTO_TEST_CASE(bnb_test)
100+{
101+ std::vector<OutputGroup> utxo_pool;
102+ AddCoins(utxo_pool, {1 * CENT, 3 * CENT, 5 * CENT});
91+ }
92+
93+ const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT);
94+ BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title);
95+ BOOST_CHECK_MESSAGE(EquivalentResult(expected_result, *result), "Result mismatch in BnB-Success: " + test_title);
96+ BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, "Selected amount mismatch in BnB-Success: " + test_title);
In https://github.com/bitcoin/bitcoin/commit/f3b0593b8bd67bc919b21cd636a01813fc5538c8:
This could output a bit more detailed error message:
0BOOST_CHECK_MESSAGE(EquivalentResult(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s vs %s", test_title, InputsToString(expected_result), InputsToString(*result)));
1BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d vs %d", test_title, expected_amount, result->GetSelectedValue()));
But you would need something like this too:
0static std::string InputsToString(const SelectionResult& selection)
1{
2 std::string res = "[";
3 for (const auto& input : selection.GetInputSet()) {
4 res += util::ToString(input->txout.nValue);
5 }
6 return res + "]";
7}
18+ * parameters when a diverging value is relevant in the context of a test. */
19+static CoinSelectionParams init_default_params()
20+{
21+ CoinSelectionParams dcsp{
22+ /*rng_fast*/default_rand,
23+ /*change_output_size=*/31,
In a8bf940ae20ed5a03a1cc328212fcac3c3462b43
A comment explaining why you selected these magic numbers would be helpful.
similar to tx_noinputs_size or an indication if they are just random.
i.e values when initializing default CSP, and some defaults in MakeCoin
could also use a const for these magic numbers.
0P2WPKH_VB_SIZE = 31
19+static CoinSelectionParams init_default_params()
20+{
21+ CoinSelectionParams dcsp{
22+ /*rng_fast*/default_rand,
23+ /*change_output_size=*/31,
24+ /*change_spend_size=*/68,
coinselector_tests to coinselection_tests and modify the test name to coinselection_tests?
As mentioned in the opening comment, I’m looking to completely change the approach. Instead of using absolute values and feerates of zero, transactions in the new tests use real feerates, and spend UTXOs whose effective values are round amounts. Since there are a ton of tests, I expected that it would be too much to get reviewed in a single PR, and migrating from the old test suite to the new test suite would make it obvious which ones had been updated already.
It could have also been done by renaming first and then updating in place, but this seemed easier to understand, especially because it was going to use a different framework in parallel. Having even more “MakeCoin” and “AddCoin” etc. functions in the same test suite would have been pretty confusing.
60+ }
61+}
62+
63+/** Check if SelectionResult a is equivalent to SelectionResult b.
64+ * Equivalent means same input values, but maybe different inputs (i.e. same value, different prevout) */
65+static bool EquivalentResult(const SelectionResult& a, const SelectionResult& b)
CheckValueEquivalence for clarity
73+ b_amts.push_back(coin->txout.nValue);
74+ }
75+ std::sort(a_amts.begin(), a_amts.end());
76+ std::sort(b_amts.begin(), b_amts.end());
77+
78+ std::pair<std::vector<CAmount>::iterator, std::vector<CAmount>::iterator> ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
0 auto ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
108+ }
109+
110+ const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT);
111+ BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title);
112+ BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputsToString(expected_result), InputsToString(*result)));
113+BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d, but got %d", test_title, expected_amount, result->GetSelectedValue()));
100+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)
101+{
102+ SelectionResult expected_result(CAmount(0), SelectionAlgorithm::BNB);
103+ CAmount expected_amount = 0;
104+ for (CAmount input_amount : expected_input_amounts) {
105+ OutputGroup group = MakeCoin(input_amount, true, cs_params);
0 OutputGroup group = MakeCoin(input_amount);
nit - you can simplify this line slightly by using the default arguments instead of passing them explicitly.
No, the way this method is written, it is possible to pass in a custom CoinSelectionParams object and it will be passed through to MakeCoin. If I adopted the change you propose, the MakeCoin call here would be limited to the default parameters.
Concept ACK to refactor the tests. TestBnBSuccess and TestBnBFail are much better and easier to read. Thanks!
non-representative and effectuate counterintuitive behavior such as feerate = 0 or cost_of_change = 0
I’m still trying to sus out what the tests are doing now that’s better than before. Most of the current tests use a cost_of_change = 0.5 * COIN, for example. I personally added a test five years ago to test cost_of_change. Also, there are some that do test with varying feerates here that you replaced. Although I do agree that every test should have feerate above zero and existing tests have feerate of zero which means that effective_value == value which is never the case in practice.
Concept ACK to refactor the tests.
TestBnBSuccessandTestBnBFailare much better and easier to read. Thanks!
I’m glad to read that.
non-representative and effectuate counterintuitive behavior such as feerate = 0 or cost_of_change = 0
I’m still trying to sus out what the tests are doing now that’s better than before.
For example, our waste calculation used to assume that cost_of_change being zero indicated that the transaction is changeless and any excess should be dropped to fees even when there were enough funds left to create a change output. This can lead to unexpected outcomes when we are comparing two selections with change. We would expect at low feerates the input set with more inputs to be preferred, but instead the selection with the smaller change budget is preferred.
My motivation for this PR was that I was debugging issues several times and lost hours due to expecting other outcomes than the ones exhibited in the tests, because setting values to zero that should never be zero leads to all sorts of quirky outcomes. Using values that can actually appear in production makes these tests much easier to follow.
Most of the current tests use a cost_of_change = 0.5 * COIN, for example.
These new tests do not exhibit the behavior you point out. Which commit is this that you are linking to? As mentioned, this is just the first PR of an attempt to completely replace the old tests, to be followed by more refactors if/when this ever gets merged.
Also, there are some that do test with varying feerates here that you replaced.
Yes, I believe that these tests have been replaced with new tests that introduce equivalent coverage. Please see the commit “test: Move BnB feerate sensitivity tests” and the commit message of the commit.
Which commit is this that you are linking to?
This is master from only a few days ago when I submitted the review feedback.
127@@ -121,6 +128,12 @@ BOOST_AUTO_TEST_CASE(bnb_test)
128
129 // BnB finds changeless solution while overshooting by up to cost_of_change
130 TestBnBSuccess("Select upper bound", utxo_pool, /*selection_target=*/4 * CENT - default_cs_params.m_cost_of_change, /*expected_input_amounts=*/{1 * CENT, 3 * CENT});
131+
132+ // Test skipping of equivalent input sets
133+ std::vector<OutputGroup> clone_pool;
134+ AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT});
122 BOOST_AUTO_TEST_CASE(bnb_test)
123 {
124 std::vector<OutputGroup> utxo_pool;
125+
126+ // Fail for empty UTXO pool
127+ TestBnBFail("Empty UTXO pool", utxo_pool, /*selection_target=*/1 * CENT);
/*selection_target=* comments to be more distracting than helpful personally.
150@@ -151,6 +151,41 @@ BOOST_AUTO_TEST_CASE(bnb_test)
151 AddCoins(clone_pool, {2 * CENT, 7 * CENT, 7 * CENT});
152 AddDuplicateCoins(clone_pool, 50'000, 5 * CENT);
153 TestBnBSuccess("Skip equivalent input sets", clone_pool, /*selection_target=*/16 * CENT, /*expected_input_amounts=*/{2 * CENT, 7 * CENT, 7 * CENT});
154+
155+ /* Test BnB attempt limit (`TOTAL_TRIES`)
total_tries, like coin_grinder. I recently added that to the rust implementation since I think it’s useful for regression testing. If BnB was ever refactored or had changes it would come in handy imo.
We would expect at low feerates the input set with more inputs to be preferred, but instead the selection with the smaller change budget is preferred.
I’m familiar with change_budget as it exists in coin-grinder. Beyond that, I’m not sure how that ties in to BnB and SRD.
Please see the commit “test: Move BnB feerate sensitivity tests” and the commit message of the commit.
I reviewed the commits, and it appears that the test coverage is equivalent. It might be helpful to document a baseline of what we want to be sure is tested for each algorithm at some point, understanding that extended coverage is handled by fuzz testing/mutation testing/property testing.
189+}
190+
191+BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test)
192+{
193+ // Create sets of UTXOs with the same effective amounts at different feerates (but different absolute amounts)
194+ std::vector<OutputGroup> low_feerate_pool; // 5 sat/vB (default, and lower than long_term_feerate of 10 sat/vB)
This file has some strange formatting that does not show up in Github. My editor (Vim) just shows a character that seems like a translation error.
5 sat
I opened the file with xxd and the translation is 35e2 80af 7361 742f. 35 is the hex for 5 in ascii, and 73 is the hex for s. It looks like 80 is extended hex for the euro sign and e2 and af also have extended hex meanings. There are more of these weird encodings thought the file.
0xe280af is the UTF-8 encoding for a narrow no-break space: https://www.fileformat.info/info/unicode/char/202f/index.htm
🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/39320450081
Try to run the tests locally, according to the documentation. However, a CI failure may still 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.
157+ * Generally, on a diverse UTXO pool BnB will quickly pass over UTXOs bigger than the target and then start
158+ * combining small counts of UTXOs that in sum remain under the selection_target+cost_of_change. When there are
159+ * multiple UTXOs that have matching amount and cost, combinations with equivalent input sets are skipped. The UTXO
160+ * pool for this test is specifically crafted to create as much branching as possible. The selection target is
161+ * 8 CENT while all UTXOs are slightly bigger than 1 CENT. The smallest eight are 100,000…100,007 sats, while the larger
162+ * ten are 100,009,…,100,018 sats plus cost_of_change.
0 * nine are 100,008,…,100,016 sats plus cost_of_change.
As discussed during Bitcoin Core Review Club, at least one test with 0 fee rate should probably be added to avoid test coverage regression.
Thanks for hosting Murch!
9@@ -10,6 +10,7 @@ target_sources(test_bitcoin
10 wallet_test_fixture.cpp
11 db_tests.cpp
12 coinselector_tests.cpp
13+ coinselection_tests.cpp
coinselection_tests.cpp is introduced in the first commit, this change may be there as well.
86+
87+ auto ret = std::mismatch(a_amts.begin(), a_amts.end(), b_amts.begin());
88+ return ret.first == a_amts.end() && ret.second == b_amts.end();
89+}
90+
91+static std::string InputsToString(const SelectionResult& selection)
nit: Just for clarity
0static std::string InputAmountsToString(const SelectionResult& selection)
96+ res += " ";
97+ }
98+ return res + "]";
99+}
100+
101+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, int custom_spending_vsize = 68)
nit: Perhaps the commit descriptions (“BnB rate sensitivity tests”, “simple BnB failure tests”, and “BnB iteration exhaustion test”, for example) could become functions for clarity (not necessarily new test cases).
I’m not sure I understand what you mean. Do you mean that I introduce helper functions like “TestBnBSuccess” for the new tests instead of making them their own test cases?
nit: Some commits can be squashed to avoid warnings like “unused function”. @w0xlt: I ran each commit, and I did not receive this warning. Could you let me know which commit resulted in that warning for you?
As discussed during Bitcoin Core Review Club, at least one test with 0 fee rate should probably be added to avoid test coverage regression. @monlovesmango: I added another commit to run the simple tests at various feerates, including the feerates 0 sat/kvB, 1 sat/kvB, and 1,500,000 sat/kvB.
Rebased due to strange CI failures
Edit: It seems to me that
wallet_backwards_compatibility.py got addressed via #32369p2p_i2p_ports.py. Anyone have an idea?86+ std::string res = "[ ";
87+ for (const auto& input : selection.GetInputSet()) {
88+ res += util::ToString(input->txout.nValue);
89+ res += " ";
90+ }
91+ return res + "]";
In 30479487c26dec47ac609009838d82b53cce4a3c “test: Recreate simple BnB success tests”
This is essentially a reimplementation of util::Join. This could be a one-liner of:
0 return "[" + util::Join(selection.GetInputSet(), " ", [](const auto& input){ return util::ToString(input->txout.nValue);}) + "]";
161+ * 8 CENT while all UTXOs are slightly bigger than 1 CENT. The smallest eight are 100,000…100,007 sats, while the larger
162+ * nine are 100,368…100,375 (i.e., 100,008…100,016 sats plus cost_of_change (359 sats)).
163+ *
164+ * Because BnB will only select input sets that fall between selection_target and selection_target + cost_of_change,
165+ * and the search traverses the UTXO pool from large to small amounts, the search will visit every single
166+ * combination of eight inputs. All except the last combination will overshoot by more than cost_of_change on the eighth input, because the larger nine inputs each exceed 1 CENT by more than cost_of_change.
In 1c1087132eb88c1e4e5a3ded89c8712ac8a54638 “test: Recreate BnB iteration exhaustion test”
nit: This line is double the length of all the other ones, it could use as linebreak somewhere.
ACK https://github.com/bitcoin/bitcoin/pull/29532/commits/dbf1f2663b1afbe03d6b1855f83db604bc79979e
I ran each commit, and I did not receive this warning. Could you let me know which commit resulted in that warning for you?
It was caused by the coinselection_tests.cpp as you mentioned here: #29532 (review)
Do you mean that I introduce helper functions like “TestBnBSuccess” for the new tests instead of making them their own test cases?
I was referring to something like the code below (which encapsulates the latest commit changes), but it was just a suggestion. The current code looks good to me too.
0void iteration_exhaustion_test(...){
1
2 std::vector<OutputGroup> doppelganger_pool;
3 std::vector<CAmount> doppelgangers;
4 std::vector<CAmount> expected_inputs;
5 for (int i = 0; i < 17; ++i) {
6// ...
7 }
8 AddCoins(doppelganger_pool, doppelgangers);
9 // Among up to 17 unique UTXOs of similar effective value we will find a solution composed of the eight smallest UTXOs
10 TestBnBSuccess("Combine smallest 8 of 17 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT, /*expected_input_amounts=*/expected_inputs);
11
12 // Starting with 18 unique UTXOs of similar effective value we will not find the solution due to exceeding the attempt limit
13 AddCoins(doppelganger_pool, {1 * CENT + default_cs_params.m_cost_of_change + 17});
14 TestBnBFail("Exhaust looking for smallest 8 of 18 unique UTXOs", doppelganger_pool, /*selection_target=*/8 * CENT);
15}
16
17BOOST_AUTO_TEST_CASE(bnb_test) {
18// ...
19iteration_exhaustion_test(...);
20}
Recreates the tests in a new test suite coinselection_tests.cpp that is
based on UTXOs being created per their effective values rather than
nominal values and uses transactions with non-zero feerates.
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.
108+ expected_result.AddInput(group);
109+ }
110+
111+ const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT);
112+ BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title);
113+ BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result)));
Nit: this seems to be checking for a match, not a mismatch
0 BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result match in BnB-Success: %s. Expected %s, and got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result)));
--log_level=all and was misinterpreting these as success messages. Please disregard..
109+ }
110+
111+ const auto result = SelectCoinsBnB(utxo_pool, selection_target, /*cost_of_change=*/default_cs_params.m_cost_of_change, /*max_selection_weight=*/MAX_STANDARD_TX_WEIGHT);
112+ BOOST_CHECK_MESSAGE(result, "Falsy result in BnB-Success: " + test_title);
113+ BOOST_CHECK_MESSAGE(HaveEquivalentValues(expected_result, *result), strprintf("Result mismatch in BnB-Success: %s. Expected %s, but got %s", test_title, InputAmountsToString(expected_result), InputAmountsToString(*result)));
114+ BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount mismatch in BnB-Success: %s. Expected %d, but got %d", test_title, expected_amount, result->GetSelectedValue()));
Nit: this also seems to be checking for a match
0 BOOST_CHECK_MESSAGE(result->GetSelectedValue() == expected_amount, strprintf("Selected amount match in BnB-Success: %s. Expected %d, and got %d", test_title, expected_amount, result->GetSelectedValue()));
Disregard, misunderstood when message would be displayed.
ACK dbf1f2663b1afbe03d6b1855f83db604bc79979e
I like how it now covers a variety of fee rates.
I was referring to something like the code below (which encapsulates the latest commit changes), but it was just a suggestion. The current code looks good to me too.
I see, thanks. I guess it could be nice to be able to run the test suite in smaller portions especially if some of the tests took a long time, but it overall runs extremely quickly, so I’m not sure it is necessary to further structure the tests at this time.
I intend to work on porting the other algorithms’ tests in the same manner, and I can pick this up in a follow-up commit, if we decide that’s the way to go then.
39+}
40+
41+static const CoinSelectionParams default_cs_params = init_default_params();
42+
43+/** Make one OutputGroup with a single UTXO that either has a given effective value (default) or a given amount (`is_eff_value = false`). */
44+static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, CoinSelectionParams cs_params = default_cs_params, int custom_spending_vsize = 68)
is_eff_value arg is always true for all the tests. What about removing it?.
Also, you are expecting group.GetSelectionAmount() to be equal to tx.vout[0].nValue with this parameter right?. I’m unsure that will always be the case.
As a test, could try adding an assertion at the end of this function. I have a hunch it will crash.
I believe the plan is to rewrite all of the tests into this style over the course of a couple PRs. So this parameter is here to allow for the future testing of SFFO behavior.
Also, you are expecting group.GetSelectionAmount() to be equal to tx.vout[0].nValue with this parameter right?
Only when it is false. The purpose is to have group.GetSelectionAmount() be eqaul to amount, so nValue is increased by the amount in fees so that they match after fees are deducted.