Fix waste calculation in SelectionResult #28366

pull murchandamus wants to merge 2 commits into bitcoin:master from murchandamus:2023-08-fix-waste-calculation changing 6 files +88 −101
  1. murchandamus commented at 10:17 pm on August 29, 2023: contributor
    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).
  2. 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.

  3. murchandamus marked this as a draft on Aug 29, 2023
  4. DrahtBot added the label Needs rebase on Aug 29, 2023
  5. murchandamus force-pushed on Aug 30, 2023
  6. murchandamus commented at 3:28 pm on August 30, 2023: contributor
    Rebased to address conflict
  7. DrahtBot removed the label Needs rebase on Aug 30, 2023
  8. murchandamus force-pushed on Aug 30, 2023
  9. DrahtBot added the label CI failed on Aug 30, 2023
  10. DrahtBot removed the label CI failed on Aug 30, 2023
  11. glozow added the label Wallet on Sep 1, 2023
  12. DrahtBot added the label CI failed on Sep 3, 2023
  13. DrahtBot removed the label CI failed on Sep 5, 2023
  14. murchandamus force-pushed on Sep 13, 2023
  15. murchandamus commented at 7:15 pm on September 13, 2023: contributor
    Rebased on latest #26152
  16. murchandamus force-pushed on Sep 13, 2023
  17. DrahtBot added the label CI failed on Sep 13, 2023
  18. DrahtBot removed the label CI failed on Sep 13, 2023
  19. 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.

  20. murchandamus force-pushed on Sep 14, 2023
  21. murchandamus marked this as ready for review on Sep 14, 2023
  22. murchandamus commented at 8:25 pm on September 14, 2023: contributor

    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.

  23. aureleoules commented at 12:45 pm on November 30, 2023: member

    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
    
  24. DrahtBot added the label CI failed on Jan 12, 2024
  25. murchandamus force-pushed on Jan 16, 2024
  26. DrahtBot removed the label CI failed on Jan 16, 2024
  27. murchandamus marked this as a draft on Jan 16, 2024
  28. murchandamus commented at 7:54 pm on January 16, 2024: contributor
    Fixed the coin_selection benchmark, thanks @aureleoules.
  29. murchandamus force-pushed on Jan 16, 2024
  30. murchandamus marked this as ready for review on Jan 16, 2024
  31. DrahtBot added the label CI failed on Feb 12, 2024
  32. 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.

    Debug: https://github.com/bitcoin/bitcoin/runs/20547490347

  33. maflcko commented at 7:50 am on April 5, 2024: member
    Are you still working on this?
  34. murchandamus force-pushed on Apr 5, 2024
  35. murchandamus commented at 4:43 pm on April 5, 2024: contributor

    Are you still working on this?

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

  36. murchandamus force-pushed on Apr 5, 2024
  37. DrahtBot removed the label CI failed on Apr 6, 2024
  38. 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.

    0    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.
  39. achow101 commented at 6:00 pm on April 24, 2024: member
    ACK e95b9159380f2de7f9a6e7a202cc171ad285ee6c
  40. DrahtBot requested review from S3RK on Apr 24, 2024
  41. 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?

    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.
    

    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.
  42. 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:

    1. 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.
    2. 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.

    1. 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.
    2. 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.

  43. ismaelsadeeq commented at 12:31 pm on May 3, 2024: member

    Concept ACK

    This is a nice cleanup 👍🏾

  44. 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.
  45. 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
  46. 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
  47. 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:

    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.

  48. 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
  49. S3RK approved
  50. 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.

  51. DrahtBot requested review from ismaelsadeeq on May 8, 2024
  52. murchandamus commented at 6:48 pm on May 24, 2024: contributor
    Thanks @achow101, @s3rk, and @ismaelsadeeq, I hope I addressed all of your comments satisfactorily.
  53. murchandamus force-pushed on May 24, 2024
  54. 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
  55. murchandamus force-pushed on May 24, 2024
  56. murchandamus commented at 6:56 pm on May 24, 2024: contributor

    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

  57. DrahtBot added the label CI failed on May 25, 2024
  58. DrahtBot commented at 0: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.

    Debug: https://github.com/bitcoin/bitcoin/runs/25393161083

  59. S3RK commented at 7:29 am on May 27, 2024: contributor

    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      | 
    
  60. Use `exact_target` shorthand in coinselector_tests bd34dd85e7
  61. murchandamus force-pushed on May 28, 2024
  62. DrahtBot removed the label CI failed on May 28, 2024
  63. murchandamus commented at 5:20 pm on May 29, 2024: contributor

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

    Fixed the issue with clang-tidy, sorry about that

  64. 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:

    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+    }
    

    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.
  65. furszy commented at 8:54 pm on May 29, 2024: member
    Code ACK bd34dd85e7b8b4cc26d2173d84bbeda2e9c27624
  66. DrahtBot requested review from achow101 on May 29, 2024
  67. DrahtBot requested review from S3RK on May 29, 2024
  68. ismaelsadeeq approved
  69. ismaelsadeeq commented at 6:12 pm on May 31, 2024: member
    Code Review ACK bd34dd85e7b8b4cc26d2173d84bbeda2e9c27624
  70. achow101 commented at 10:25 pm on June 4, 2024: member
    ACK bd34dd85e7b8b4cc26d2173d84bbeda2e9c27624
  71. achow101 merged this on Jun 4, 2024
  72. achow101 closed this on Jun 4, 2024


github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-26 03:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me