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).
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For detailed information about the code coverage, see the test coverage report.
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.
Reviewers, this pull request conflicts with the following ones:
add_excess_to_recipient_position for changeless txs with excess that would be added to fees by remyers)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.
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.
Approach ACK
Commit message in 0a31864 says that
GetChange()relied to special meaning ofchange_cost == 0, but actually it wasGetSelectionWaste()function which was in fault.
Thanks, I updated the commit message and rebased on master. Ready for review.
The CoinSelection benchmarks fails when I run it with -min-time=1000
0./src/bench/bench_bitcoin -filter=CoinSelection -min-time=1000
1bench_bitcoin: bench/coin_selection.cpp:84: CoinSelection(ankerl::nanobench::Bench&)::<lambda()>: Assertion `result->GetSelectedValue() == 1003 * COIN' failed.
2Aborted
🚧 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.
Are you still working on this?
Thanks, rebased and fixed the call from adding CoinGrinder that was using the removed function.
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));
In 44db79b0c48d6b1a26dba6ab01c2a296d610c06b “Refactor ComputeAndSetWaste()”
nit: Unnecessary parentheses, also usually the check of the value is after the function. Could also use brace initialization.
0 bool makes_change{GetChange(min_viable_change, change_fee) != 0};
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.
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?
0 * [@param](/bitcoin-bitcoin/contributor/param/)[in] change_cost The cost of creating change and spending it in the future.
1 * Only used if there is change.
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);
Why are you reducing 0.1 here?
And above why are effective_feerate, long_term_feerate, and discard_feerate now having values?
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:
effective_feerate and the long_term_feerate are set to 0 and there is no excess.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.
effective_feerate and the long_term_feerate are set to 0 and there is no excess.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.
Concept ACK
This is a nice cleanup 👍🏾
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.
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};
exact_target variable above this test block and used it everywhere it applies
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};
exact_target as proposed
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
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))”
Added a calculation comment to illustrate the situation:
0 // = (2 * fee) - (2 * (fee + large_fee_diff)) + change_cost
1 // = (2 * 100) - (2 * (100 + 90)) + 125
2 // = 200 - 380 + 125 = -55
and asserted that my calculation is correct.
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};
exact_target - excess if you introduce exact_target var
exact_target out as another variable
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.
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.
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
🚧 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.
Happy to reack, but you need to fix clang-tidy first
0wallet/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]
1 893 | add_coin(1 * COIN, 1, selection1, /*current_fee=*/fee, /*long_term_fee=*/fee - fee_diff);
2 | ^
3wallet/test/coinselector_tests.cpp:61:90: note: 'fee' declared here
4 61 | static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result, CAmount fee, CAmount long_term_fee)
5 |
Happy to reack, but you need to fix clang-tidy first
Fixed the issue with clang-tidy, sorry about that
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});
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.
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.
Unfortunately, we don’t have the change_fee or feerate readily available in the BnB function. The following passes the tests, though:
0- result.RecalculateWaste(cost_of_change, cost_of_change, CAmount{0});
1+ /* Calculate the fee for a P2WPKH change output */
2+ if (utxo_pool.at(0).long_term_fee) {
3+ const CFeeRate feerate = utxo_pool.at(0).m_long_term_feerate * (utxo_pool.at(0).fee / utxo_pool.at(0).long_term_fee);
4+ const CAmount change_fee = feerate.GetFee(31);
5+ result.RecalculateWaste(cost_of_change, cost_of_change, change_fee);
6+ } else {
7+ /* Use 1 sat/vB and 31 vB in case no long_term_feerate is set */
8+ result.RecalculateWaste(cost_of_change, cost_of_change, /*change_fee=*/CAmount{31});
9+ }