This transfers the tests from the old coin selection test framework that was based on ignoring fees to the new coin selection framework that tests the coin selection algorithms with realistic feerates and fees.
The PR also includes a minor improvement of the test framework to allow the CoinSelectionParams used by the tests to be initialized with other feerates, and adds some feerates around the new minimum feerate to the tested feerates.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | w0xlt, brunoerg, achow101 |
| Concept ACK | yancyribbens |
If your review is incorrectly listed, please copy-paste <code><!--meta-tag:bot-skip--></code> into the comment that the bot should ignore.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed.
<sub>Task test ancestor commits: https://github.com/bitcoin/bitcoin/actions/runs/23366323668/job/67980934546</sub>
<sub>LLM reason (✨ experimental): CMake build failed, with gmake exiting Error 2 (non-zero exit status from cmake --build).</sub>
<details><summary>Hints</summary>
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.
</details>
264 | @@ -265,6 +265,11 @@ BOOST_AUTO_TEST_CASE(srd_test) 265 | TestSRDFail("Undershoot minimum change by one sat", utxo_pool, /*selection_target=*/9 * CENT - cs_params.m_change_fee - CHANGE_LOWER + 1, cs_params); 266 | TestSRDFail("Spend more than available", utxo_pool, /*selection_target=*/9 * CENT + 1, cs_params); 267 | TestSRDFail("Spend everything", utxo_pool, /*selection_target=*/9 * CENT, cs_params); 268 | + 269 | + AddDuplicateCoins(utxo_pool, /*count=*/100, /*amount=*/5 * CENT, cs_params); 270 | + AddDuplicateCoins(utxo_pool, /*count=*/3, /*amount=*/7 * CENT, cs_params); 271 | + TestSRDSuccess("Select most valuable UTXOs for acceptable weight", utxo_pool, /*selection_target=*/20 * CENT, cs_params, /*max_selection_weight=*/4 * 4 * (P2WPKH_INPUT_VSIZE - 1 )); 272 | + TestSRDFail("No acceptable weight possible", utxo_pool, /*selection_target=*/25 * CENT, cs_params, /*max_selection_weight=*/4 * 3 * (P2WPKH_INPUT_VSIZE), /*expect_max_weight_exceeded=*/true);
TestSRDFail("No acceptable weight possible", utxo_pool, /*selection_target=*/25 * CENT, cs_params, /*max_selection_weight=*/4 * 3 * P2WPKH_INPUT_VSIZE, /*expect_max_weight_exceeded=*/true);
Approach ACK
122 | @@ -123,7 +123,7 @@ static void TestBnBFail(std::string test_title, std::vector<OutputGroup>& utxo_p 123 | 124 | BOOST_AUTO_TEST_CASE(bnb_test) 125 | { 126 | - std::vector<int> feerates = {0, 1, 5'000, 10'000, 25'000, 59'764, 500'000, 999'000, 1'500'000}; 127 | + std::vector<int> feerates = {0, 1, 99, 100, 315, 1'000, 2'345, 10'292, 59'764, 1'500'000};
in 81827b160f28b11e181856038badf4134923bdd0 it would be nice to have a little more detail in the commit message about why the new feerates are added. Is it because these are more realistic values?
Thanks, I added some commentary to the commit message to motivate the feerates I picked.
Concept ACK on adding representative feerates to SRD tests. Also Concept ACK on continuing to get all these tests in the same file. It's confusing to contributes (like myself) when the tests are in a few different places since I forget which is which.
Also, it would make things easier to review I think if the commit messages provide a little more detail about why a change is being done. For example https://cbea.ms/git-commit/. I don't think it's a rule to be followed to always say why, however it can lead to less head scratching about what the diff shows if practiced judiciously.
Concept ACK
Thanks for the review and comments. @yancyribbens: I reworked the commit messages to add more explanation to each commit. There were no code changes in this update, only the commit messages were changed.
Failure seems to be unrelated: #34782
231 | + BOOST_CHECK(expect_max_weight_exceeded == max_weight_exceeded); 232 | +} 233 | + 234 | +BOOST_AUTO_TEST_CASE(srd_test) 235 | +{ 236 | + std::vector<int> feerates = {0, 1, 99, 100, 315, 1'000, 2'345, 10'292, 59'764, 1'500'000};
6b5abcfa8cd2fa378b3aa6225f1dcde75524c8e0: nit: The feerates could be a static const to avoid duplication since we're using the same for both srd_test and bnb_test?
Sure, will do
222 | @@ -225,5 +223,55 @@ BOOST_AUTO_TEST_CASE(bnb_feerate_sensitivity_test) 223 | TestBnBSuccess("Prefer two light inputs over two heavy inputs at high feerates", high_feerate_pool, /*selection_target=*/13 * CENT, /*expected_input_amounts=*/{3 * CENT, 10 * CENT}, high_feerate_params); 224 | } 225 | 226 | +static void TestSRDSuccess(std::string test_title, std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CoinSelectionParams& cs_params = default_cs_params, const int max_selection_weight = MAX_STANDARD_TX_WEIGHT) 227 | +{ 228 | + SelectionResult expected_result(CAmount(0), SelectionAlgorithm::SRD);
expected_result is never used.
Thanks, removed.
code review ACK fe38494e04189583b96980c634176ad7506a002d
Thanks for the review @brunoerg. I removed the obsolete line, made the feerates a static const, and introduced a weight check into the success cases.
reACK 31d21f105d74953d03b7e6ebae6d1529c162aa87
241 | +{ 242 | + CAmount expected_min_amount = selection_target + cs_params.m_change_fee + CHANGE_LOWER; 243 | + 244 | + const auto result = SelectCoinsSRD(utxo_pool, selection_target, cs_params.m_change_fee, cs_params.rng_fast, max_selection_weight); 245 | + BOOST_CHECK_MESSAGE(result, "Falsy result in SRD-Success: " + test_title); 246 | + BOOST_CHECK_MESSAGE(result->GetSelectedValue() >= expected_min_amount, strprintf("Selected amount is lower than expected in SRD-Success: %s. Expected %d, but got %d", test_title, expected_min_amount, result->GetSelectedValue()));
Shouldn't effective value be used here?
GetSelectedValue() returns the sum of absolute txout.nValue amounts (before fee deduction).
const CAmount selected_effective_value = result->GetSelectedEffectiveValue();
BOOST_CHECK_MESSAGE(selected_effective_value >= expected_min_amount, strprintf("Selected effective value is lower than expected in SRD-Success: %s. Expected %d, but got %d", test_title, expected_min_amount, selected_effective_value));
Yes, thanks for catching that!
258 | +BOOST_AUTO_TEST_CASE(srd_test) 259 | +{ 260 | + for (int feerate : FEERATES) { 261 | + std::vector<OutputGroup> utxo_pool; 262 | + 263 | + CoinSelectionParams cs_params = init_cs_params(feerate);
nit:
const CoinSelectionParams cs_params = init_cs_params(feerate);
Taken and also applied to the BnB tests
31 | + * - new default minimum feerate: 100 s/kvB 32 | + * - old default minimum feerate: 1000 s/kvB 33 | + * - a few non-round realistic feerates around default minimum feerate, 34 | + * dust feerate, and default LTFRE: 315 s/kvB, 2345 s/kvB, and 35 | + * 10'292 s/kvB 36 | + * - a high feerate that has been exceeded occassionally: 59'764 s/kvB
nit:
* - a high feerate that has been exceeded occasionally.: 59'764 s/kvB
61 | - dcsp.m_cost_of_change = /*204 + 155 sats=*/dcsp.min_viable_change + dcsp.m_change_fee; 62 | - dcsp.m_subtract_fee_outputs = false; 63 | - return dcsp; 64 | + csp.m_change_fee = /*155 sats=*/csp.m_effective_feerate.GetFee(csp.change_output_size); 65 | + csp.min_viable_change = /*204 sats=*/csp.m_discard_feerate.GetFee(csp.change_spend_size); 66 | + csp.m_cost_of_change = /*204 + 155 sats=*/csp.min_viable_change + csp.m_change_fee;
m_change_fee depends on m_effective_feerate (which is no longer hardcoded).
m_cost_of_change sums both of the preceding values; therefore, it depends on m_change_fee.
csp.m_change_fee = csp.m_effective_feerate.GetFee(csp.change_output_size);
csp.min_viable_change = /*204 sats=*/csp.m_discard_feerate.GetFee(csp.change_spend_size);
csp.m_cost_of_change = csp.min_viable_change + csp.m_change_fee;
I turned this into comments at the end of the lines clarifying that it is for the default feerate.
The most frequent change to CoinSelectionParams so far seems to be
amendments to the feerate, and the feerate propagates to other members
of the CoinSelectionParams, so we add it as an input parameter.
This also adds the CoinSelectionParams to the BnBFail tests, which
previously were always run with the default CoinSelectionParams.
The default minimum feerate was lowered from 1000 s/kvB to 100 s/kvB.
This adjusts the set of feerates used in the tests to accommodate that
new feerate and to cover other potential special cases:
- zero: 0 s/kvB
- minimum non-zero s/kvB: 1 s/kvB
- just below the new default minimum feerate: 99 s/kvB
- new default minimum feerate: 100 s/kvB
- old default minimum feerate: 1000 s/kvB
- a few non-round realistic feerates around default minimum feerate,
dust feerate, and default LTFRE: 315 s/kvB, 2345 s/kvB, and
10'292 s/kvB
- a high feerate that has been exceeded occassionally: 59'764 s/kvB
- a huge feerate that is extremely uncommon: 1'500'000 s/kvB
This refactor is part of the effort to move the coin selection tests to
a framework that can use non-zero, realistic feerates. The insufficient
funds failure case is extended with a few additional similar variants of
the failure.
Previously, SRD had only failure and edge-case coverage, so we add a few
simple coin selection targets that should quickly succeed, including one
that will create a minimal change output.
Also:
- Add weight check to Success cases.
Per the introduction of TRUC transactions, it is more likely that we
will attempt to build transactions of limited weight (e.g., TRUC child
transactions may not exceed 4000 WU). When SRD exceeds the input weight
limit, it evicts the OutputGroup with the lowest effective value before
selecting additional UTXOs: we test that SRD will find a solution that
depends on the eviction working correctly, and that it fails as expected
when no solution is possible.
Thanks for the review, @w0xlt. I took all your suggestions.
ACK 858a0a9c96b622e7d8a6b2b700f26c898971c10e
reACK 858a0a9c96b622e7d8a6b2b700f26c898971c10e
will update mutation testing for coin selection as soon as it gets merged.
ACK 858a0a9c96b622e7d8a6b2b700f26c898971c10e