@yancyribbens pointed out that SRD would fail to find a possible solution if there are multiple UTXOs of the same effective value with diverse weight.
This adds a tiebreaker that will make SRD succeed in such a scenario.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33223.
<!--021abf342d371248e50ceaed478a90ca-->
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| 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-->
No conflicts as of last run.
<!--5faf32d7da4f0f540f40219e4f7537a3-->
1239 | @@ -1240,6 +1240,26 @@ BOOST_AUTO_TEST_CASE(srd_tests) 1240 | BOOST_CHECK(res); 1241 | BOOST_CHECK(res->GetWeight() <= max_selection_weight); 1242 | } 1243 | + 1244 | + { 1245 | + // ################################################################################################################
Move to coinselection_tests.cpp
I ran the SRD tests, all pass as expected. To validate the comparator change, I also re-ran the fourth SRD test using the old comparator, and it fails (as expected). This confirms that the test setup is effective at catching the bug. The new comparator correctly enforces the weight limit, and the test demonstrates that the previous implementation of the comparator can only succeed by chance (~1 in a billion). Looks good to me.
528 | @@ -529,6 +529,9 @@ class MinOutputGroupComparator
529 | public:
530 | int operator() (const OutputGroup& group1, const OutputGroup& group2) const
531 | {
Since the goal here is to use the same sort as descending_effval_weight, L532 - L 535 can be replaced with this single line:
return descending_effval_weight(group1, group2);
Thanks, I took this suggestion.
Any reason this is in Draft?
I want to use the opportunity to move the SRD tests to the coinselection_tests, but haven’t gotten around to it yet.
<!--8ac04cdde196e94527acabf64b896448-->
There hasn't been much activity lately. What is the status here?
Finding reviewers may take time. However, if the patch is no longer relevant, please close this pull request. If the author lost interest or time to work on this, please close it and mark it with one of the labels 'Up for grabs' or 'Insufficient Review', so that it can be picked up in the future.
I reworked this PR to build on the refactor of the SRD tests, #34886. (First five commits are the other PR.)
269 | @@ -270,6 +270,13 @@ BOOST_AUTO_TEST_CASE(srd_test) 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); 273 | + 274 | + // Create UTXO pool with UTXOs of same effective value but different weights 275 | + std::vector<OutputGroup> mixed_weight_pool; 276 | + AddDuplicateCoins(mixed_weight_pool, 100, 5 * CENT, cs_params);
Minor improvement when #34886 has been merged:
AddDuplicateCoins(mixed_weight_pool, /*count=*/100, /*amount=*/5 * CENT, cs_params);
Rebased on latest #34886
When UTXOs tie in effective value, prefer keeping the lower weight UTXO.
Co-authored-by: Yancy <github@yancy.lol>
With #34886 merged, this is ready for review.
utACK eff9e798b95ef06e0899f348f142703e8504ac5d