coinselection: Tiebreak SRD eviction by weight #33223

murchandamus commented at 10:51 PM on August 19, 2025: member

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.

DrahtBot commented at 10:51 PM on August 19, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33223.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	yancyribbens

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.

Conflicts

No conflicts as of last run.

in src/wallet/test/coinselector_tests.cpp:1245 in 0dee81b985

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 | +        // ################################################################################################################

murchandamus commented at 10:51 PM on August 19, 2025:

Move to coinselection_tests.cpp

cedwies commented at 5:11 PM on August 21, 2025: contributor

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.

in src/wallet/coinselection.cpp:531 in 0dee81b985 outdated

 528 | @@ -529,6 +529,9 @@ class MinOutputGroupComparator
 529 |  public:
 530 |      int operator() (const OutputGroup& group1, const OutputGroup& group2) const
 531 |      {

yancyribbens commented at 6:09 PM on August 22, 2025:

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);

murchandamus commented at 11:20 PM on March 20, 2026:

Thanks, I took this suggestion.

yancyribbens commented at 7:33 PM on August 22, 2025: contributor

Any reason this is in Draft?

murchandamus commented at 9:35 PM on August 27, 2025: member

I want to use the opportunity to move the SRD tests to the coinselection_tests, but haven’t gotten around to it yet.

DrahtBot commented at 1:59 AM on February 23, 2026: contributor

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.

murchandamus force-pushed on Mar 20, 2026

murchandamus commented at 11:18 PM on March 20, 2026: member

I reworked this PR to build on the refactor of the SRD tests, #34886. (First five commits are the other PR.)

murchandamus force-pushed on Mar 20, 2026

DrahtBot added the label CI failed on Mar 20, 2026

murchandamus force-pushed on Mar 20, 2026

in src/wallet/test/coinselection_tests.cpp:276 in 2b19737f38

 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);

murchandamus commented at 12:00 AM on March 21, 2026:

Minor improvement when #34886 has been merged:

        AddDuplicateCoins(mixed_weight_pool, /*count=*/100, /*amount=*/5 * CENT, cs_params);

DrahtBot removed the label CI failed on Mar 21, 2026

murchandamus force-pushed on Apr 7, 2026

murchandamus commented at 11:04 PM on April 7, 2026: member

Rebased on latest #34886

coinselection: Tiebreak SRD eviction by weight

When UTXOs tie in effective value, prefer keeping the lower weight UTXO.

Co-authored-by: Yancy <github@yancy.lol>

eff9e798b9

murchandamus force-pushed on Apr 9, 2026

murchandamus marked this as ready for review on Apr 9, 2026

murchandamus commented at 10:36 PM on April 9, 2026: member

With #34886 merged, this is ready for review.

yancyribbens commented at 2:30 PM on April 10, 2026: contributor

utACK eff9e798b95ef06e0899f348f142703e8504ac5d

fanquake closed this on May 21, 2026

fanquake reopened this on May 21, 2026

DrahtBot added the label CI failed on May 21, 2026

maflcko closed this on May 21, 2026

maflcko reopened this on May 21, 2026

DrahtBot removed the label CI failed on May 21, 2026

fanquake merged this on May 21, 2026

fanquake closed this on May 21, 2026