Fix waste calculation in SelectionResult #28366

murchandamus commented at 10:17 PM on August 29, 2023: member

PR #26152 moved waste calculation into SelectionResult to be able to correct the waste score on basis of the bump_fee_group_discount for overlapping ancestries. This left two functions with largely overlapping purpose, where one was simply a wrapper of the other. This PR cleans up the overlap, and fixes the double-meaning of change_cost where the GetChange() function assumed that no change was created when change_cost was set to 0. This behavior was exploited in a bunch of tests, but is problematic, because a change_cost of 0 is permitted with custom settings for feerate and discard_feerate (i.e. when they’re both 0).

DrahtBot commented at 10:17 PM on August 29, 2023: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	furszy, ismaelsadeeq, achow101
Stale ACK	S3RK

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#30080 (wallet: add coin selection parameter add_excess_to_recipient_position for changeless txs with excess that would be added to fees by remyers)
#29523 (Wallet: Add max_tx_weight to transaction funding options (take 2) by ismaelsadeeq)

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.

murchandamus marked this as a draft on Aug 29, 2023

DrahtBot added the label Needs rebase on Aug 29, 2023

murchandamus force-pushed on Aug 30, 2023

murchandamus commented at 3:28 PM on August 30, 2023: member

Rebased to address conflict

DrahtBot removed the label Needs rebase on Aug 30, 2023

murchandamus force-pushed on Aug 30, 2023

DrahtBot added the label CI failed on Aug 30, 2023

DrahtBot removed the label CI failed on Aug 30, 2023

glozow added the label Wallet on Sep 1, 2023

DrahtBot added the label CI failed on Sep 3, 2023

DrahtBot removed the label CI failed on Sep 5, 2023

murchandamus force-pushed on Sep 13, 2023

murchandamus commented at 7:15 PM on September 13, 2023: member

Rebased on latest #26152

murchandamus force-pushed on Sep 13, 2023

DrahtBot added the label CI failed on Sep 13, 2023

DrahtBot removed the label CI failed on Sep 13, 2023

S3RK commented at 6:42 AM on September 14, 2023: contributor

Approach ACK

Commit message in 0a31864bbe6ab8cbc081f56ea490e123bf25ed7c says that GetChange() relied to special meaning of change_cost == 0, but actually it was GetSelectionWaste() function which was in fault.

murchandamus force-pushed on Sep 14, 2023

murchandamus marked this as ready for review on Sep 14, 2023

murchandamus commented at 8:25 PM on September 14, 2023: member

Approach ACK

Commit message in 0a31864 says that GetChange() relied to special meaning of change_cost == 0, but actually it was GetSelectionWaste() function which was in fault.

Thanks, I updated the commit message and rebased on master. Ready for review.

aureleoules commented at 12:45 PM on November 30, 2023: contributor

The CoinSelection benchmarks fails when I run it with -min-time=1000

./src/bench/bench_bitcoin -filter=CoinSelection -min-time=1000
bench_bitcoin: bench/coin_selection.cpp:84: CoinSelection(ankerl::nanobench::Bench&)::<lambda()>: Assertion `result->GetSelectedValue() == 1003 * COIN' failed.
Aborted

DrahtBot added the label CI failed on Jan 12, 2024

murchandamus force-pushed on Jan 16, 2024

DrahtBot removed the label CI failed on Jan 16, 2024

murchandamus marked this as a draft on Jan 16, 2024

murchandamus commented at 7:54 PM on January 16, 2024: member

Fixed the coin_selection benchmark, thanks @aureleoules.

murchandamus force-pushed on Jan 16, 2024

murchandamus marked this as ready for review on Jan 16, 2024

DrahtBot added the label CI failed on Feb 12, 2024

DrahtBot commented at 4:13 AM on February 12, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is 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.

Leave a comment here, if you need help tracking down a confusing failure.

<sub>Debug: https://github.com/bitcoin/bitcoin/runs/20547490347</sub>

maflcko commented at 7:50 AM on April 5, 2024: member

Are you still working on this?

murchandamus force-pushed on Apr 5, 2024

murchandamus commented at 4:43 PM on April 5, 2024: member

Are you still working on this?

Thanks, rebased and fixed the call from adding CoinGrinder that was using the removed function.

murchandamus force-pushed on Apr 5, 2024

DrahtBot removed the label CI failed on Apr 6, 2024

in src/wallet/coinselection.cpp:845 in 44db79b0c4 outdated

 847 | -    if (change > 0) {
 848 | -        m_waste = GetSelectionWaste(change_cost, m_target, m_use_effective);
 849 | -    } else {
 850 | -        m_waste = GetSelectionWaste(0, m_target, m_use_effective);
 851 | -    }
 852 | +    bool makes_change = (0 != GetChange(min_viable_change, change_fee));

achow101 commented at 5:52 PM on April 24, 2024:

In 44db79b0c48d6b1a26dba6ab01c2a296d610c06b "Refactor ComputeAndSetWaste()"

nit: Unnecessary parentheses, also usually the check of the value is after the function. Could also use brace initialization.

    bool makes_change{GetChange(min_viable_change, change_fee) != 0};

murchandamus commented at 3:39 PM on May 24, 2024:

Adopted the proposed change, but those lines get removed in the next commit anyway.

achow101 commented at 6:00 PM on April 24, 2024: member

ACK e95b9159380f2de7f9a6e7a202cc171ad285ee6c

DrahtBot requested review from S3RK on Apr 24, 2024

in src/wallet/coinselection.h:384 in e95b915938 outdated

 381 | +     * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
 382 | +     *
 383 | +     * @param[in] min_viable_change The minimum amount necessary to make a change output economic
 384 | +     * @param[in] change_cost       The cost of creating change and spending it in the future.
 385 | +     *                              Only used if there is change, in which case it must be positive.
 386 | +     *                              Must be 0 if there is no change.

ismaelsadeeq commented at 12:23 PM on May 3, 2024:

From the commit message in e95b9159380f2de7f9a6e7a202cc171ad285ee6c you mention we can have change_cost of 0 and also a change output, so this is no longer the case?

    * [@param](/bitcoin-bitcoin/contributor/param/)[in] change_cost       The cost of creating change and spending it in the future.
     *                              Only used if there is change.

murchandamus commented at 5:48 PM on May 24, 2024:

Thanks, the "must be 0 if there is no change" is indeed outdated. I removed it.

in src/bench/coin_selection.cpp:82 in e95b915938 outdated

  81 |          /*avoid_partial=*/ false,
  82 |      };
  83 |      auto group = wallet::GroupOutputs(wallet, available_coins, coin_selection_params, {{filter_standard}})[filter_standard];
  84 |      bench.run([&] {
  85 | -        auto result = AttemptSelection(wallet.chain(), 1003 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);
  86 | +        auto result = AttemptSelection(wallet.chain(), 1002.99 * COIN, group, coin_selection_params, /*allow_mixed_output_types=*/true);

ismaelsadeeq commented at 12:26 PM on May 3, 2024:

Why are you reducing 0.1 here?

And above why are effective_feerate, long_term_feerate, and discard_feerate now having values?

murchandamus commented at 5:05 PM on May 24, 2024:

Good question.

It has been a while since I made this change, but if I remember correctly, my fixing the duplicate meaning of change_cost broke this bench test due to the following:

Before my change, we would set change_cost to 0 as a signal that a transaction does not require a change output. This would happen when a coin selection algorithm found a changeless solution and after creating the recipient outputs there would not be sufficient funds to make a viable change output. However, change_cost will also be computed to be zero when effective_feerate, long_term_feerate, and discard_feerate are zero.

IIRC, this lead to some unintuitive behavior in coin selection:

One coin selection algorithm may propose a changeless input set with the two UTXOs 1000+3 BTC. Its waste score would be calculated to be 0, as both the effective_feerate and the long_term_feerate are set to 0 and there is no excess.
Another coin selection algorithm might propose a solution that should lead to a change output, e.g. two UTXOs 1000+1000 BTC. Because change_cost was computed to be 0, the transaction building would not create a change output, drop the excess 997 BTC to fees, and therefore assess the waste score to be 997 BTC of waste.

The changeless solution would be preferred, because of its waste score, and the bench would always succeed in finding a two input solution that uses exactly 1000+3 BTC in the inputs.

After my rewrite, change_cost only contains the computed value and is no longer used as a signal on whether we have sufficient budget to create a change output.

As before, the changeless solution would have a waste score of 0, as both the effective_feerate and the long_term_feerate are set to 0 and there is no excess.
However, the solution that creates change due to picking two UTXOs with 1000+1000 BTC, would now recognize that it has a ton of money left and that it should create a change output. Instead of dropping the excess 997 BTC to fees, it would create a change output of 997 BTC. Since the effective_feerate and discard_feerate is 0, the change_cost is 0. Because the effective_feerate and long_term_feerate are 0, the waste score on the inputs is also 0. Since effective_feerate is 0, the fees for transaction header and recipient outputs are also 0. Therefore, the transaction with a change output now also gets a waste score of 0, correctly.

All of the proposed input sets get presented to ChooseSelectionResult(…) which picks the lowest waste score, but all solutions are tied with the same waste score of zero. The tie-breaker is to prefer the input set with more inputs, but all solutions have two inputs and are tied on that as well. Finally, it picks the first element from the result vector. The bench test expects that 1003 BTC get selected, but when it selects 2000 BTC, the bench fails.

Therefore, I fixed the bench to not depend on using feerates that are do not appear in standard transactions and lead to quirky coin selection behavior, which required that I reduce the target to leave a money for fees. I would argue that we could probably do much better for a bench that tests coin selection in general.

ismaelsadeeq commented at 12:31 PM on May 3, 2024: member

Concept ACK

This is a nice cleanup 👍🏾

in src/wallet/test/coinselector_tests.cpp:888 in e95b915938 outdated

 885 |  
 886 |      // The following tests that the waste is calculated correctly in various scenarios.
 887 | -    // ComputeAndSetWaste will first determine the size of the change output. We don't really
 888 | +    // RecalculateWaste will first determine the size of the change output. We don't really
 889 |      // care about the change and just want to use the variant that always includes the change_cost,
 890 |      // so min_viable_change and change_fee are set to 0 to ensure that.

S3RK commented at 7:12 AM on May 8, 2024:

This comment needs to be adjusted

murchandamus commented at 6:00 PM on May 24, 2024:

Yes! Thanks, I adjusted the comment.

in src/wallet/test/coinselector_tests.cpp:952 in e95b915938 outdated

 951 |      }
 952 |  
 953 |      {
 954 | -        // No Waste when fee == long_term_fee, no change, and no excess
 955 | +        // Waste is 0 when fee == long_term_fee, no change, and no excess
 956 |          const CAmount exact_target{in_amt - fee * 2};

S3RK commented at 7:16 AM on May 8, 2024:

nit: this could be pulled to the begging of the test next to other declarations and then reused in the tests above (and below as well)

murchandamus commented at 6:39 PM on May 24, 2024:

I introduced an exact_target variable above this test block and used it everywhere it applies

in src/wallet/test/coinselector_tests.cpp:981 in e95b915938 outdated

 988 |      }
 989 |  
 990 |      {
 991 |          // Negative waste when the long term fee is greater than the current fee and the selected value == target
 992 | -        const CAmount exact_target{3 * COIN - 2 * fee};
 993 | +        const CAmount exact_target{in_amt - 2 * fee};

S3RK commented at 7:18 AM on May 8, 2024:

nit: same variable is already defined within another local scope above, could be reused. See another comment.

murchandamus commented at 6:17 PM on May 24, 2024:

used exact_target as proposed

in src/wallet/test/coinselector_tests.cpp:994 in e95b915938 outdated

 993 | @@ -993,7 +994,7 @@ BOOST_AUTO_TEST_CASE(waste_test)
 994 |          const CAmount target_waste2{-2 * large_fee_diff + change_cost}; // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost

S3RK commented at 7:21 AM on May 8, 2024:

nit: do you want to add assert for the comment above? It's not obvious that the statement holds given variable declarations are hundreds of lines above.

the comment: "Negative waste when the long term fee is greater than the current fee and change_cost < - (inputs * (fee - long_term_fee))"

murchandamus commented at 6:26 PM on May 24, 2024:

Added a calculation comment to illustrate the situation:

        // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
        // = (2 * 100) - (2 * (100 + 90)) + 125
        // = 200 - 380 + 125 = -55

and asserted that my calculation is correct.

in src/wallet/test/coinselector_tests.cpp:971 in e95b915938 outdated

 976 |  
 977 |      {
 978 | -        // No Waste when (fee - long_term_fee) == (-excess), no change cost
 979 | -        const CAmount new_target{in_amt - fee * 2 - fee_diff * 2};
 980 | +        // Waste is 0 when (fee - long_term_fee) == (-excess), no change cost
 981 | +        const CAmount new_target{in_amt - fee * 2 - /*excess=*/fee_diff * 2};

S3RK commented at 7:24 AM on May 8, 2024:

nit: could use exact_target - excess if you introduce exact_target var

murchandamus commented at 6:11 PM on May 24, 2024:

Pulled exact_target out as another variable

S3RK approved

S3RK commented at 7:28 AM on May 8, 2024: contributor

Code review ACK e95b9159380f2de7f9a6e7a202cc171ad285ee6c

I'm not sure whether 44db79b0c48d6b1a26dba6ab01c2a296d610c06b is useful since it's fully replaced by the following commit.

Also added a bunch of nits in the tests about comments and potential simplifications, but nothing blocking.

DrahtBot requested review from ismaelsadeeq on May 8, 2024

murchandamus commented at 6:48 PM on May 24, 2024: member

Thanks @achow101, @s3rk, and @ismaelsadeeq, I hope I addressed all of your comments satisfactorily.

murchandamus force-pushed on May 24, 2024

Fold GetSelectionWaste() into ComputeAndSetWaste()

Both `GetSelectionWaste()` and `ComputeAndSetWaste()` now are part of
`SelectionResult`. Instead of `ComputeAndSetWaste()` being a wrapper for
`GetSelectionWaste()`, we combine them to a new function
`RecalculateWaste()`.

As I was combining the logic of the two functions, I noticed that
`GetSelectionWaste()` was making the odd assumption that the
`change_cost` being set to zero means that no change is created.
However, if we build transactions at a feerate of zero with the
`discard_feerate` also set to zero, we'd organically have a
`change_cost` of zero, even when we create change on a transaction.

This commit cleans up this duplicate meaning of `change_cost` and relies
on `GetChange()` to figure out whether there is change on basis of the
`min_viable_change` and whatever is left after deducting fees.

Since this broke a bunch of tests that relied on the double-meaning of
`change_cost` a bunch of tests had to be fixed.

7aa7e30441

murchandamus force-pushed on May 24, 2024

murchandamus commented at 6:56 PM on May 24, 2024: member

I'm not sure whether 44db79b is useful since it's fully replaced by the following commit.

Ah oops, yeah I guess the first commit was a vestige of my first attempt at this. I squashed it into the second commit.

Diff of before reviews to latest: https://github.com/bitcoin/bitcoin/compare/e95b9159380f2de7f9a6e7a202cc171ad285ee6c..2c18b86

DrahtBot added the label CI failed on May 25, 2024

DrahtBot commented at 12:52 AM on May 25, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is 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.

Leave a comment here, if you need help tracking down a confusing failure.

<sub>Debug: https://github.com/bitcoin/bitcoin/runs/25393161083</sub>

S3RK commented at 7:29 AM on May 27, 2024: contributor

Happy to reack, but you need to fix clang-tidy first

wallet/test/coinselector_tests.cpp:893:43: error: argument name 'current_fee' in comment does not match parameter name 'fee' [bugprone-argument-comment,-warnings-as-errors]
  893 |         add_coin(1 * COIN, 1, selection1, /*current_fee=*/fee, /*long_term_fee=*/fee - fee_diff);
      |                                           ^
wallet/test/coinselector_tests.cpp:61:90: note: 'fee' declared here
   61 | static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee)
      |

Use `exact_target` shorthand in coinselector_tests bd34dd85e7

murchandamus force-pushed on May 28, 2024

DrahtBot removed the label CI failed on May 28, 2024

murchandamus commented at 5:20 PM on May 29, 2024: member

Happy to reack, but you need to fix clang-tidy first

Fixed the issue with clang-tidy, sorry about that

in src/wallet/coinselection.cpp:197 in 7aa7e30441 outdated

 193 | @@ -194,7 +194,7 @@ util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool
 194 |      for (const size_t& i : best_selection) {
 195 |          result.AddInput(utxo_pool.at(i));
 196 |      }
 197 | -    result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0});
 198 | +    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});

furszy commented at 8:52 PM on May 29, 2024:

Could set the second parameter, change_cost, to 0 instead of providing cost_of_change. The parameter is only used if there is change and BnB goal is to not generate one.

murchandamus commented at 6:02 PM on May 30, 2024:

I guess, but the point of this PR is that change_cost no longer needs to be set to 0 to indicate that no change is being created.

In fact, it would actually be better if change_fee were set to the actual value here rather than 0.

murchandamus commented at 6:27 PM on May 30, 2024:

Unfortunately, we don’t have the change_fee or feerate readily available in the BnB function. The following passes the tests, though:

-    result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
+    /* Calculate the fee for a P2WPKH change output */
+    if (utxo_pool.at(0).long_term_fee) {
+        const CFeeRate feerate = utxo_pool.at(0).m_long_term_feerate * (utxo_pool.at(0).fee / utxo_pool.at(0).long_term_fee);
+        const CAmount change_fee = feerate.GetFee(31);
+        result.RecalculateWaste(cost_of_change, cost_of_change, change_fee);
+    } else {
+        /* Use 1 sat/vB and 31 vB in case no long_term_feerate is set */
+        result.RecalculateWaste(cost_of_change, cost_of_change, /*change_fee=*/CAmount{31});
+    }

murchandamus commented at 6:28 PM on May 30, 2024:

Please let me know if you have a suggestion how I should amend the code.

furszy commented at 8:54 PM on May 29, 2024: member

Code ACK bd34dd85e7b8b4cc26d2173d84bbeda2e9c27624

DrahtBot requested review from achow101 on May 29, 2024

DrahtBot requested review from S3RK on May 29, 2024

ismaelsadeeq approved

ismaelsadeeq commented at 6:12 PM on May 31, 2024: member

Code Review ACK bd34dd85e7b8b4cc26d2173d84bbeda2e9c27624

achow101 commented at 10:25 PM on June 4, 2024: member

ACK bd34dd85e7b8b4cc26d2173d84bbeda2e9c27624

achow101 merged this on Jun 4, 2024

achow101 closed this on Jun 4, 2024

murchandamus deleted the branch on Feb 12, 2025

murchandamus restored the branch on Feb 12, 2025

bitcoin locked this on Feb 12, 2026