wallet: Decide which coin selection solution to use based on waste metric

achow101 commented at 0:02 am on May 21, 2021: member

Branch and Bound introduced a metric that we call waste. This metric is used as part of bounding the search tree, but it can be generalized to all coin selection solutions, including those with change. As such, this PR introduces the waste metric at a higher level so that we can run both of our coin selection algorithms (BnB and KnapsackSolver) and choose the one which has the least waste. In the event that both find a solution with the same change, we choose the one that spends more inputs.

Also this PR sets the long term feerate to 10 sat/vb rather than using the 1008 block estimate. This allows the long term feerate to be the feerate that we switch between consolidating and optimizing for fees. This also removes a bug where the long term feerate would incorrectly be set to the fallback fee. While this doesn’t matter prior to this PR, it does have an effect following this. The long term feerate can be configured by the user through a new -consolidatefeerate option.

achow101 marked this as a draft on May 21, 2021

fanquake added the label Wallet on May 21, 2021

achow101 commented at 0:32 am on May 21, 2021: member

Note that there will be a followup PR to this which introduces a struct that encapsulates the selection. This struct will also do the waste calculation which will remove the ugly tuples stuff that is currently done to allow for the waste calculation.

DrahtBot commented at 3:52 am on May 21, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#22100 (refactor: Clean up new wallet spend, receive files added #21207 by ryanofsky)
#22019 (wallet: Introduce SelectionResult for encapsulating a coin selection solution by achow101)
#21206 (refactor: Make CWalletTx sync state type-safe by ryanofsky)
#17526 (Use Single Random Draw In addition to knapsack as coin selection fallback by achow101)

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.

achow101 force-pushed on May 25, 2021

achow101 marked this as ready for review on May 25, 2021

achow101 commented at 3:49 pm on May 25, 2021: member

With #17331 now merged, this is ready for review.

DrahtBot added the label Needs rebase on May 30, 2021

achow101 force-pushed on May 30, 2021

DrahtBot removed the label Needs rebase on May 30, 2021

in src/wallet/coinselection.cpp:365 in a92c5611ad outdated

360+    // Consider the cost of making change and spending it in the future
361+    // If we aren't making change, the caller should've set change_cost to 0
362+    waste += change_cost;
363+
364+    // When we are not making change (change_cost  == 0), consider the excess we are throwing away to fees
365+    waste += selected_value - target;

OttoAllmendinger commented at 2:23 pm on June 1, 2021:

0if (change_cost == 0) {
1  ..
2}

achow101 commented at 5:15 pm on June 1, 2021:

Fixed.

in src/wallet/coinselection.cpp:367 in a92c5611ad outdated

362+    waste += change_cost;
363+
364+    // When we are not making change (change_cost  == 0), consider the excess we are throwing away to fees
365+    waste += selected_value - target;
366+
367+    return target;

OttoAllmendinger commented at 2:23 pm on June 1, 2021:

return waste;

achow101 commented at 5:15 pm on June 1, 2021:

Fixed.

achow101 force-pushed on Jun 1, 2021

in src/wallet/spend.cpp:371 in e09aab121d outdated

368-        return true;
369+    std::set<CInputCoin> bnb_coins;
370+    CAmount bnb_value;
371+    bool bnb_ret = SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, bnb_coins, bnb_value);
372+    if (bnb_ret) {
373+        results.push_back(std::make_tuple(bnb_coins, bnb_value, /* cost of change */ CAmount(0), nTargetValue));

sipa commented at 7:16 pm on June 2, 2021:

You can std::move bnb_coins here to avoid a copy.

achow101 commented at 10:16 pm on June 2, 2021:

Done

in src/wallet/spend.cpp:382 in e09aab121d outdated

380-    return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet);
381+    std::set<CInputCoin> knapsack_coins;
382+    CAmount knapsack_value;
383+    bool knapsack_ret = KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, knapsack_coins, knapsack_value);
384+    if (knapsack_ret) {
385+        results.push_back(std::make_tuple(knapsack_coins, knapsack_value, coin_selection_params.m_cost_of_change, nTargetValue + coin_selection_params.m_change_fee));

sipa commented at 7:17 pm on June 2, 2021:

You can std::move knapsack_coins here to avoid a copy.

achow101 commented at 10:16 pm on June 2, 2021:

Done

in src/wallet/spend.cpp:397 in e09aab121d outdated

395+    for (const auto& result : results) {
396+        const auto& selected_inputs = std::get<0>(result);
397+        CAmount this_waste = GetSelectionWaste(selected_inputs, std::get<2>(result), std::get<3>(result));
398+        // Update the best waste either when this waste is better, or when the waste is the same and this result has more inputs
399+        if (this_waste < best_waste || (this_waste == best_waste && selected_inputs.size() > setCoinsRet.size())) {
400+            setCoinsRet = selected_inputs;

sipa commented at 7:18 pm on June 2, 2021:

It’s slightly inefficient to copy the selected inputs into setCoinsRet inside the loop itself, as it may result in multiple useless copies.

As an alternative, you could create a vector of e.g. (CAmount waste, std::ref<std::set<CInputCoins>> inputs) pairs by std::transforming the results vector, and then returning *std::min_element(that vector).second.

achow101 commented at 10:17 pm on June 2, 2021:

Based on this suggestion, I’ve changed this to do the waste calculation at the time of insertion into results. This eliminates the need for a std::transform. Then std::min_element is used to get the least waste element.

sipa commented at 7:22 pm on June 2, 2021: member

Does this introduce any behavior changes besides the long-term feerate change?

I would think not, as the BNB search always has waste 0, so if it works, it will still always be chosen?

achow101 commented at 9:10 pm on June 2, 2021: member

Does this introduce any behavior changes besides the long-term feerate change?

I would think not, as the BNB search always has waste 0, so if it works, it will still always be chosen?

There is a behavior change as BnB can non-zero waste. Part of the waste is the excess thrown away to fees. Because BnB uses a matching window, it is possible for it to have an excess which is included as part of the waste calculation. Additionally, the difference between the fee and the long term fee is usually non-zero, so the waste is also usually non-zero.

The main result of this behavior change is that when target feerate is less than the long term feerate, we will choose the result that consolidates more. This is because the difference between the fee and the long term fee will be negative which generally makes the waste negative. When you have more inputs, the waste will be more negative, and so the most negative solution is used. When the target feerate is greater than the long term feerate, then we will choose the result that pays the least fees. This is because the difference between the fee and the long term fee is positive, so the waste is generally positive. With less inputs, both the waste and fees will be lower, so we end up choosing the solution with lower fees.

This strategy does not necessarily mean that one algorithm will tend to be chosen over another, but rather as a standard way to measure how “good” they are.

sipa commented at 9:13 pm on June 2, 2021: member

@achow101 Oh, of course. Thanks for reminding me on the point of the waste metric.

achow101 force-pushed on Jun 2, 2021

in src/wallet/spend.cpp:703 in f872c232ff outdated

702-            CCoinControl cc_temp;
703-            cc_temp.m_confirm_target = chain().estimateMaxBlocks();
704-            coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
705+            // Get the long term fee estimate. This estimate is really the fee rate at which we are still willing to consolidate inputs.
706+            // By default, we use 10 sat/vbyte.
707+            coin_selection_params.m_long_term_feerate = CFeeRate(10, COIN); // Use 10 sat per vbyte

jarolrod commented at 1:26 pm on June 8, 2021:

What’s the rationale behind 10 sat per vbyte? Why that number?

Seems a bit scary to hard-code a value here.

achow101 commented at 4:13 pm on June 8, 2021:

@Xekyo suggested it based on his analysis and experience.

This should really be a configurable option, I just didn’t implement that yet.

achow101 commented at 6:59 pm on August 17, 2021:

Forgot to mention that this was made a configurable option.

in src/wallet/spend.cpp:390 in f872c232ff outdated

389+        // No solution found
390+        return false;
391+    }
392+
393+    // Choose the result with the least waste
394+    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b){

jarolrod commented at 1:26 pm on June 8, 2021:

nit

0    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {

achow101 commented at 7:20 pm on August 17, 2021:

Done

jarolrod commented at 1:29 pm on June 8, 2021: member

Concept ACK

This is interesting. This allows us to decide which algorithm to use by examining, what can be considered, the opportunity cost of each coin selection algorithm.

DrahtBot added the label Needs rebase on Jun 9, 2021

achow101 force-pushed on Jun 9, 2021

DrahtBot removed the label Needs rebase on Jun 9, 2021

Xekyo commented at 5:46 pm on June 11, 2021: member

and choose the one which has the least change. In the event that both find a solution with the same change, we choose the one that spends more inputs.

Is it possible that you meant “least waste” and “same waste” instead of change?

achow101 commented at 5:54 pm on June 11, 2021: member

and choose the one which has the least change. In the event that both find a solution with the same change, we choose the one that spends more inputs.

Is it possible that you meant “least waste” and “same waste” instead of change?

Yes

in src/wallet/test/coinselector_tests.cpp:144 in 21bc2f9407 outdated

135@@ -136,6 +136,14 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
136     return static_groups;
137 }
138 
139+inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinEligibilityFilter& filter)

Xekyo commented at 6:07 pm on June 11, 2021:

Nit: the introduction KnapsackGroupOutputs should be mentioned in the commit message. Should be potentially a separate commit.

achow101 commented at 9:07 pm on June 11, 2021:

I’ve mentioned it in the commit message

in src/wallet/test/coinselector_tests.cpp:147 in 21bc2f9407 outdated

135@@ -136,6 +136,14 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
136     return static_groups;
137 }
138 
139+inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinEligibilityFilter& filter)
140+{
141+    static std::vector<OutputGroup> static_groups;
142+    static_groups.clear();
143+    static_groups = testWallet.GroupOutputs(vCoins, coin_selection_params, filter, false);

Xekyo commented at 6:08 pm on June 11, 2021:

How come this uses “GroupOutputs” when BnB uses “GroupCoins”? What’s the difference?

achow101 commented at 9:08 pm on June 11, 2021:

I’ve added an explanation in the commit message. The reason is because the KnapsackSolver tests involve different eligibility filters which GroupCoins does not.

in src/wallet/coinselection.cpp:367 in 6ae3ed7b18 outdated

362+    waste += change_cost;
363+
364+    if (change_cost == 0) {
365+        // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
366+        waste += selected_value - target;
367+    }

Xekyo commented at 6:26 pm on June 11, 2021:

This is not just the excess, but selected_value - target will also include all input fees paid for the input set. However, we counted the input fees already above in the comparison with the long_term_fee.

I think this should be selected_value - txweight*feerate - sum(recipient outputs), or alternatively additionally deduct sum(coin.m_fee) for each input for the code as currently written.

A few good tests for the waste metric would be:

Transaction with change has excess of 0
Transaction with feerate of 10 sat/vB has waste that is exactly cost_of_change+excess (one of which would be zero in the case of having change and the other in the case of not having change)
Transaction with same count of inputs has higher waster at higher feerate than at lower feerate.

achow101 commented at 9:09 pm on June 11, 2021:

Changed to calculated selected_value with coin.effective_value. This will ensure the fee is subtracted. Also renamed it to selected_effective_value.

Also added a commit with test cases.

Xekyo commented at 9:32 pm on June 11, 2021:

Ah, very elegant!

in src/wallet/coinselection.h:171 in 6ae3ed7b18 outdated

165@@ -166,6 +166,18 @@ struct OutputGroup
166     CAmount GetSelectionAmount() const;
167 };
168 
169+/** Compute the waste for this result given the cost of change
170+ * waste = change_cost + excess + inputs * (effective_feerate - long_term_feerate)
171+ * excess = selected_target - actual_target

Xekyo commented at 6:28 pm on June 11, 2021:

As pointed out above, this formula would count the input fees again, and here also the change cost.

achow101 commented at 9:09 pm on June 11, 2021:

Changed to selected_effective_value.

Xekyo commented at 6:49 pm on June 11, 2021: member

Concept ACK, but needs tests for the waste metric calculation.

achow101 force-pushed on Jun 11, 2021

Xekyo commented at 9:47 pm on June 11, 2021: member

Good improvements in 6f607eeefb37036d5b0ada89cb3772cbc0de5fb2

Will try to think of more tests and review more carefully before ACK. Maybe also add a test that out of two transactions with the same excess the one with more inputs has the lower waste at a feerate lower than long_term_feerate.

in src/wallet/test/coinselector_tests.cpp:295 in cc3e51de33 outdated

287@@ -280,14 +288,14 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
288     empty_wallet();
289     add_coin(1);
290     vCoins.at(0).nInputBytes = 40; // Make sure that it has a negative effective value. The next check should assert if this somehow got through. Otherwise it will fail
291-    BOOST_CHECK(!testWallet.AttemptSelection( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb));
292+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(vCoins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change, setCoinsRet, nValueRet));

Xekyo commented at 9:05 pm on June 30, 2021:

Feels like this part could be a scripted diff.

achow101 commented at 10:31 pm on July 2, 2021:

Done

in src/wallet/coinselection.cpp:366 in a8d87d8fc3 outdated

361+    // If we aren't making change, the caller should've set change_cost to 0
362+    waste += change_cost;
363+
364+    if (change_cost == 0) {
365+        // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
366+        waste += selected_effective_value - target;

Xekyo commented at 9:10 pm on June 30, 2021:

Could perhaps assert that selected_effective_value is greater than target as it would be a dead giveaway that the inputs to this function are bonkers.

achow101 commented at 10:31 pm on July 2, 2021:

Done

in src/wallet/coinselection.h:171 in a8d87d8fc3 outdated

165@@ -166,6 +166,18 @@ struct OutputGroup
166     CAmount GetSelectionAmount() const;
167 };
168 
169+/** Compute the waste for this result given the cost of change
170+ * waste = change_cost + excess + inputs * (effective_feerate - long_term_feerate)
171+ * excess = selected_effective_value - actual_target

Xekyo commented at 9:12 pm on June 30, 2021:

I think we may have removed actual_target previously. Is this comment perhaps a holdout?

achow101 commented at 10:31 pm on July 2, 2021:

Changed to just target.

in src/wallet/coinselection.h:180 in a8d87d8fc3 outdated

172+ * change_cost = change_fee + change_long_term_fee
173+ *
174+ * @param[in] inputs The selected inputs
175+ * @param[in] change_cost The cost of creating change and spending it in the future.
176+ * @param[in] target The amount targeted by the coin selection algorithm.
177+ * @return The waste

Xekyo commented at 9:13 pm on June 30, 2021:

The function’s documentation should perhaps explain that it will only ever use either change_cost or excess.

achow101 commented at 10:31 pm on July 2, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:670 in b15d84f868 outdated

662@@ -658,4 +663,47 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
663     }
664 }
665 
666+BOOST_AUTO_TEST_CASE(waste_test)
667+{
668+    CoinSet selection;
669+    const CAmount fee = CAmount(100);
670+    const CAmount change_cost = CAmount(100);

Xekyo commented at 10:04 pm on June 30, 2021:

You may want to use different values (preferably not direct multiples) for fee and change_cost as otherwise some weird interaction might hide a defect, maybe something like 100 and 125.

achow101 commented at 10:31 pm on July 2, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:701 in b15d84f868 outdated

696+    add_coin(1 * COIN, 1, selection, fee, fee);
697+    add_coin(2 * COIN, 2, selection, fee, fee);
698+    BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target));
699+    selection.clear();
700+
701+    // Waste will be greater when fee is greater, but long term fee is the same

Xekyo commented at 10:07 pm on June 30, 2021:

Perhaps also add a test where the long_term_fee is greater than the fee.

achow101 commented at 10:31 pm on July 2, 2021:

Done

in src/wallet/spend.cpp:363 in 6f607eeefb outdated

356@@ -357,17 +357,43 @@ bool CWallet::AttemptSelection(const CAmount& nTargetValue, const CoinEligibilit
357 {
358     setCoinsRet.clear();
359     nValueRet = 0;
360+    // Vector of results for use with waste calculation
361+    // In order: calculated waste, selected inputs, selected value
362+    // TODO: Use a struct representing the selection result
363+    std::vector<std::tuple<CAmount, std::set<CInputCoin>, CAmount>> results;

Xekyo commented at 10:10 pm on June 30, 2021:

You may want to be a bit more explicit here whether the third value is the selected value, the selected effective value, or the target value. (I assume it’s the first, but we’ve been juggling all of these, being more precise wouldn’t hurt.)

achow101 commented at 10:31 pm on July 2, 2021:

Done

meshcollider commented at 1:24 am on August 20, 2021:

Do you anticipate having more coin selection algorithms in future? Why bother with the vector etc. rather than just direct comparison between the two results?

achow101 commented at 1:48 am on August 20, 2021:

Yes, #17526 will be updated to add another result to this vector.

in src/wallet/spend.cpp:390 in 6f607eeefb outdated

388+    if (results.size() == 0) {
389+        // No solution found
390+        return false;
391+    }
392+
393+    // Choose the result with the least waste

Xekyo commented at 10:14 pm on June 30, 2021:

Clearly, this function does not only select by waste, but has a fallback tiebreaker. ;)

achow101 commented at 10:31 pm on July 2, 2021:

Done

Xekyo commented at 10:17 pm on June 30, 2021: member

Some minor points and a suggestion for another test.

achow101 force-pushed on Jul 2, 2021

in src/wallet/coinselection.h:180 in 8a0a1b3f35 outdated

175+ * @param[in] change_cost The cost of creating change and spending it in the future. Only used if there is change. Must be 0 if there is no change.
176+ * @param[in] target The amount targeted by the coin selection algorithm.
177+ * @param[in] real_value Whether to use the input's real value (when true) or the effective value (when false)
178+ * @return The waste
179+ */
180+CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, const CAmount change_cost, const CAmount target, bool real_value = false);

Xekyo commented at 8:25 pm on July 8, 2021:

I’d have a slight preference for a more specific “use_effective_value” than “real_value” with an inverted bool value.

0CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, const CAmount change_cost, const CAmount target, bool use_effective_value = true);

Talkless commented at 1:09 pm on August 17, 2021:

Maybe worth adding [[nodiscard]] for a new GetSelectionWaste?

achow101 commented at 7:20 pm on August 17, 2021:

Done both suggestions.

in src/wallet/spend.cpp:393 in 8a0a1b3f35 outdated

391+    }
392+
393+    // Choose the result with the least waste
394+    // If the waste is the same, choose the one which spends more inputs.
395+    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b){
396+        return std::get<0>(a) < std::get<0>(b) || (std::get<0>(a) == std::get<0>(b) && std::get<1>(a).size() > std::get<1>(b).size());

S3RK commented at 7:07 am on July 14, 2021:

Note to reviewers: this looks much better with #22019

in src/wallet/spend.cpp:690 in 8a0a1b3f35 outdated

689-    CCoinControl cc_temp;
690-    cc_temp.m_confirm_target = chain().estimateMaxBlocks();
691-    coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
692+    // Get the long term fee estimate. This estimate is really the fee rate at which we are still willing to consolidate inputs.
693+    // By default, we use 10 sat/vbyte.
694+    coin_selection_params.m_long_term_feerate = CFeeRate(10, COIN); // Use 10 sat per vbyte

S3RK commented at 7:07 am on July 14, 2021:

Warrants updating comment in coinselection.h

nit: duplicate comment with the one just one line above

achow101 commented at 7:21 pm on August 17, 2021:

No longer relevant with -consolidatefeerate option.

in src/wallet/test/coinselector_tests.cpp:725 in 8a0a1b3f35 outdated

721+    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
722+    const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target);
723+    BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2);
724+    BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
725+    selection.clear();
726+

S3RK commented at 7:24 am on July 14, 2021:

nit: Maybe add a test for zero waste case?

achow101 commented at 7:21 pm on August 17, 2021:

Done

S3RK approved

S3RK commented at 7:35 am on July 14, 2021: member

Code Review ACK 8a0a1b3

I’m woking on a functional test to verify the overall flow. The idea is to craft a specific coin set, set the fee manually to A) below B) above long_term_fee and verify that we’ve got more inputs in case A

ryanofsky commented at 11:45 am on July 14, 2021: member

I’m woking on a functional test to verify the overall flow

This reminds me to beg for review of #22155. Functional tests for coin selection are great but for some parts unit tests are more convenient, so I really want to add this wallet spend test module and get some tests in there.

achow101 force-pushed on Jul 21, 2021

in src/dummywallet.cpp:31 in 0be3fa4a9a outdated

27@@ -28,6 +28,7 @@ void DummyWalletInit::AddWalletOptions(ArgsManager& argsman) const
28         "-addresstype",
29         "-avoidpartialspends",
30         "-changetype",
31+        "-discardfee=<amt>",

S3RK commented at 7:25 am on July 22, 2021:

AssertionError: Please add {’-consolidatefeerate’} to the hidden args in DummyWalletInit::AddWalletOptions

achow101 commented at 6:17 pm on July 22, 2021:

Oops, fixed.

josedanielrojaspixel referenced this in commit 068d2cea60 on Jul 22, 2021

achow101 force-pushed on Jul 22, 2021

laanwj added this to the "Blockers" column in a project

in src/wallet/init.cpp:48 in 1ce0c97c7a outdated

44@@ -45,6 +45,7 @@ void WalletInit::AddWalletOptions(ArgsManager& argsman) const
45     argsman.AddArg("-addresstype", strprintf("What type of addresses to use (\"legacy\", \"p2sh-segwit\", or \"bech32\", default: \"%s\")", FormatOutputType(DEFAULT_ADDRESS_TYPE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
46     argsman.AddArg("-avoidpartialspends", strprintf("Group outputs by address, selecting many (possibly all) or none, instead of selecting on a per-output basis. Privacy is improved as addresses are mostly swept with fewer transactions and outputs are aggregated in clean change addresses. It may result in higher fees due to less optimal coin selection caused by this added limitation and possibly a larger-than-necessary number of inputs being used. Always enabled for wallets with \"avoid_reuse\" enabled, otherwise default: %u.", DEFAULT_AVOIDPARTIALSPENDS), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
47     argsman.AddArg("-changetype", "What type of change to use (\"legacy\", \"p2sh-segwit\", or \"bech32\"). Default is same as -addresstype, except when -addresstype=p2sh-segwit a native segwit output is used when sending to a native segwit address)", ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
48+    argsman.AddArg("-consolidatefeerate=<amt>", strprintf("The fee rate (in %s/kvB) that indicates the highest feerate you are comfortable making consolidation transactions at (default: %s). ", CURRENCY_UNIT, FormatMoney(DEFAULT_CONSOLIDATE_FEERATE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);

S3RK commented at 6:48 am on July 26, 2021:

nit: unnecessary space after the dot in the description

achow101 commented at 7:21 pm on August 17, 2021:

Fixed.

S3RK commented at 6:49 am on July 26, 2021: member

Re-ACK 1ce0c97

Compared to 8a0a1b3 the first commit is replaced to make consolidating fee rate configurable.

in src/wallet/test/coinselector_tests.cpp:63 in 6cbe2c4bd9 outdated

60+    coin.m_fee = fee;
61+    coin.m_long_term_fee = long_term_fee;
62+    set.insert(coin);
63 }
64 
65+

fjahr commented at 5:56 pm on August 1, 2021:

nit: Empty line not necessary?

achow101 commented at 7:21 pm on August 17, 2021:

Removed

in src/wallet/test/coinselector_tests.cpp:718 in 6cbe2c4bd9 outdated

713+    const CAmount waste3 = GetSelectionWaste(selection, change_cost, target);
714+    BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3);
715+    BOOST_CHECK_LT(waste3, waste1);
716+    selection.clear();
717+
718+    // Waste without change is the excesss and difference between fee and long term fee

fjahr commented at 6:50 pm on August 1, 2021:

excesss

achow101 commented at 7:21 pm on August 17, 2021:

Fixed.

in src/wallet/test/coinselector_tests.cpp:683 in 6cbe2c4bd9 outdated

678+    add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
679+    const CAmount waste1 = GetSelectionWaste(selection, change_cost, target);
680+    BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1);
681+    selection.clear();
682+
683+    // Waste without change is the excesss and difference between fee and long term fee

fjahr commented at 6:51 pm on August 1, 2021:

excesss

achow101 commented at 7:21 pm on August 17, 2021:

Fixed.

fjahr commented at 7:10 pm on August 1, 2021: member

Concept ACK

Looks good already at the first look but I will need to do another pass with a focus on the tests.

GeneFerneau commented at 1:56 am on August 13, 2021: none

Approach ACK 1ce0c97

Did a manual review, everything looks good. Tangentially, doing a deeper review of KnapsackSolver, but use looks consistent with other uses across the codebase.

Still running tests locally, and trying to think of more edge cases. The existing tests look pretty throrough.

in src/wallet/spend.cpp:369 in 1ce0c97c7a outdated

366     std::vector<OutputGroup> positive_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, true /* positive_only */);
367-    if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet)) {
368-        return true;
369+    std::set<CInputCoin> bnb_coins;
370+    CAmount bnb_value;
371+    bool bnb_ret = SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, bnb_coins, bnb_value);

Talkless commented at 1:14 pm on August 17, 2021:

Is it necessary to bring variable in to scope that is used only for if? Probably personal preference, but adding variable automatically “makes you” (a reviewer) to look for it’s uses elsewhere, including possible re-assignemnt as it it’s nor marked as const.

Please consider adding const or just remove that variable and “if” the SelectCoinsBnB result directly.

achow101 commented at 7:21 pm on August 17, 2021:

This variable was used in a previous revision. Changed to use the in the if directly.

in src/wallet/spend.cpp:380 in 1ce0c97c7a outdated

378     // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output.
379     // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output.
380-    return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet);
381+    std::set<CInputCoin> knapsack_coins;
382+    CAmount knapsack_value;
383+    bool knapsack_ret = KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, knapsack_coins, knapsack_value);

Talkless commented at 1:15 pm on August 17, 2021:

Same as per bool bnb_ret comment.

achow101 commented at 7:22 pm on August 17, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:147 in 1ce0c97c7a outdated

140@@ -136,6 +141,14 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
141     return static_groups;
142 }
143 
144+inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinEligibilityFilter& filter)
145+{
146+    static std::vector<OutputGroup> static_groups;
147+    static_groups.clear();

Talkless commented at 1:34 pm on August 17, 2021:

Why .clear()? It does not change the capacity (actual internal buffer size, if that was in mind).

Just next line completely re-assigns static_groups and it seems that should be enough?

achow101 commented at 7:22 pm on August 17, 2021:

This was copied from one of the other functions, but indeed is unnecessary, so I have removed it.

achow101 force-pushed on Aug 17, 2021

achow101 commented at 7:34 pm on August 17, 2021: member

Also rebased to pick up #22686

achow101 force-pushed on Aug 17, 2021

in src/wallet/init.cpp:48 in 47214f7aa4 outdated

44@@ -45,6 +45,7 @@ void WalletInit::AddWalletOptions(ArgsManager& argsman) const
45     argsman.AddArg("-addresstype", strprintf("What type of addresses to use (\"legacy\", \"p2sh-segwit\", or \"bech32\", default: \"%s\")", FormatOutputType(DEFAULT_ADDRESS_TYPE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
46     argsman.AddArg("-avoidpartialspends", strprintf("Group outputs by address, selecting many (possibly all) or none, instead of selecting on a per-output basis. Privacy is improved as addresses are mostly swept with fewer transactions and outputs are aggregated in clean change addresses. It may result in higher fees due to less optimal coin selection caused by this added limitation and possibly a larger-than-necessary number of inputs being used. Always enabled for wallets with \"avoid_reuse\" enabled, otherwise default: %u.", DEFAULT_AVOIDPARTIALSPENDS), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
47     argsman.AddArg("-changetype", "What type of change to use (\"legacy\", \"p2sh-segwit\", or \"bech32\"). Default is same as -addresstype, except when -addresstype=p2sh-segwit a native segwit output is used when sending to a native segwit address)", ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
48+    argsman.AddArg("-consolidatefeerate=<amt>", strprintf("The fee rate (in %s/kvB) that indicates the highest feerate you are comfortable making consolidation transactions at (default: %s).", CURRENCY_UNIT, FormatMoney(DEFAULT_CONSOLIDATE_FEERATE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);

Xekyo commented at 8:07 pm on August 17, 2021:

Mh, I’m thinking about the use of “consolidation transaction” here. I would usually use that term for a transaction that has the exclusive purpose of converting multiple UTXOs to a single UTXO without performing a payment.

Perhaps: “the maximum feerate at which transaction building may use more inputs than strictly necessary to reduce the wallet’s UTXO pool”.

Xekyo commented at 8:18 pm on August 17, 2021:

Also, this sentence uses “fee rate” and “feerate” once each. Personally, I prefer “feerate”.

achow101 commented at 10:26 pm on August 17, 2021:

Changed.

in test/functional/rpc_fundrawtransaction.py:546 in 821a8b908d outdated

542@@ -543,7 +543,7 @@ def test_locked_wallet(self):
543         self.nodes[1].getnewaddress()
544         self.nodes[1].getrawchangeaddress()
545         inputs = []
546-        outputs = {self.nodes[0].getnewaddress():1.09999500}
547+        outputs = {self.nodes[0].getnewaddress():1.19999500}

achow101 commented at 8:11 pm on August 17, 2021:

Note: I believe this change is related to #22686. What I think was happening in previous revisions of this PR is that due to that bug, KnapsackSolver would find a solution without change that doesn’t actually work, and because of that, it would also have worse waste than the BnB solution. We don’t see this in master because there is a BnB solution and in master, we default to the BnB solution. This PR, combined with #22686 allows KnapsackSolver to find a solution with change that happens to have less waste, so it was being chosen, causing the test to fail at the fundrawtransaction below. So this value is being changed to just under 1.2 which is the value of that optimal input set KnapsackSolver finds.

S3RK commented at 9:54 am on August 21, 2021:

I recompiled the old version of this PR and confirmed that

achow101 force-pushed on Aug 17, 2021

in src/wallet/spend.cpp:662 in 47214f7aa4 outdated

658@@ -659,10 +659,8 @@ bool CWallet::CreateTransactionInternal(
659         return false;
660     }
661 
662-    // Get long term estimate
663-    CCoinControl cc_temp;
664-    cc_temp.m_confirm_target = chain().estimateMaxBlocks();
665-    coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
666+    // Set the long term fee estimate to the wallet's consolidate feerate

Xekyo commented at 8:20 pm on August 17, 2021:

0    // Set the long term feerate estimate to the wallet's consolidate feerate

achow101 commented at 10:26 pm on August 17, 2021:

Changed.

in src/wallet/coinselection.cpp:347 in f71918ca7e outdated

340@@ -341,3 +341,31 @@ CAmount OutputGroup::GetSelectionAmount() const
341 {
342     return m_subtract_fee_outputs ? m_value : effective_value;
343 }
344+
345+CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, const CAmount change_cost, const CAmount target, bool use_effective_value)
346+{
347+    // If the result is empty, then selection failed. Don't use this one, so set waste to very high

Xekyo commented at 8:33 pm on August 17, 2021:

It seems odd to me that we’d even allow calling GetSelectionWaste with an empty input set. Shouldn’t rather the caller that is evaluating the input set candidates notice that this candidate is ineligible rather than us setting the waste high here so that it doesn’t get used? What if e.g. both selection methods end up having an empty set, do we then pick the smaller of two MAX_MONEY waste values?

I’d probably assert that the input set cannot be empty.

achow101 commented at 10:27 pm on August 17, 2021:

Originally the intent was to always run this function regardless of success or failure. But we won’t be doing that, so it’s fine to assert here. Done.

in src/wallet/spend.cpp:688 in 47214f7aa4 outdated

658@@ -659,10 +659,8 @@ bool CWallet::CreateTransactionInternal(
659         return false;
660     }
661 
662-    // Get long term estimate
663-    CCoinControl cc_temp;
664-    cc_temp.m_confirm_target = chain().estimateMaxBlocks();
665-    coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
666+    // Set the long term fee estimate to the wallet's consolidate feerate
667+    coin_selection_params.m_long_term_feerate = m_consolidate_feerate;

Xekyo commented at 8:44 pm on August 17, 2021:

I feel like “the feerate at which I would perform consolidation transactions” and “the feerate that I expect to be a minimum feerate in the long term” may be subtly different things, but I don’t have an improvement suggestion at the moment.

in src/wallet/test/coinselector_tests.cpp:58 in 53d9add0b6 outdated

55     CMutableTransaction tx;
56     tx.vout.resize(nInput + 1);
57     tx.vout[nInput].nValue = nValue;
58-    set.emplace(MakeTransactionRef(tx), nInput);
59+    CInputCoin coin(MakeTransactionRef(tx), nInput);
60+    coin.effective_value -= fee;

Xekyo commented at 9:43 pm on August 17, 2021:

Shouldn’t this be coin.effective_value = nValue - fee;?

It seems easier to review and more obviously correct to calculate the correct value for effective_value here when all the ingredients for this calculation are already input parameters for the function instead of defining it relative to some initial value for effective_value that is set by the CInputCoin constructor. It does not seem obvious to me that CInputCoin would be initialized with effective_value = nValue. I would have expected the initial value for effective_value to either be undefined until it is set or that the constructor of CInputCoin takes fee or feerate as an optional parameter and immediately sets effective_value to the correct value when the constructor is called.

Otherwise, it seems like an easy way for a bug to happen if someone just calls CInputCoin and uses the initial value of effective_value not realizing that it was not set to the correct amount.

achow101 commented at 10:27 pm on August 17, 2021:

Changed.

Xekyo commented at 10:03 pm on August 17, 2021: member

Re: 810b7fe7ba9504c36de3e190a8c901e2220dd77f LGTM, just got some more nits for you, I guess.

achow101 force-pushed on Aug 17, 2021

Xekyo commented at 6:14 pm on August 18, 2021: member

ACK 15fbe72ede62b9a3686fc000381c1d0fa1807815

fanquake requested review from instagibbs on Aug 18, 2021

fanquake requested review from meshcollider on Aug 18, 2021

instagibbs commented at 9:39 am on August 19, 2021: member

and choose the one which has the least change. In the event that both find a solution with the same change, we choose the one that spends more inputs.

Is it possible that you meant “least waste” and “same waste” instead of change?

Yes

Could you please update the OP with accurate language? I was struggling to understand until I read everything here.

in src/wallet/wallet.h:75 in b94c848489 outdated

70@@ -71,6 +71,8 @@ static const CAmount DEFAULT_FALLBACK_FEE = 0;
71 static const CAmount DEFAULT_DISCARD_FEE = 10000;
72 //! -mintxfee default
73 static const CAmount DEFAULT_TRANSACTION_MINFEE = 1000;
74+//! -consolidatefee default
75+static const CAmount DEFAULT_CONSOLIDATE_FEERATE = 10000; // 10 sat/vbyte

instagibbs commented at 9:45 am on August 19, 2021:

definitely not going to nitpick this but why 10? :)

achow101 commented at 4:06 pm on August 19, 2021:

It seemed like a reasonable number

Xekyo commented at 5:53 pm on August 19, 2021:

Given that we have gotten that question twice again in the last 24h, it would probably be best to add context for that number in the commit messages or code somewhere.

achow101 commented at 6:11 pm on August 19, 2021:

I added to the commit message that it was chosen arbitrarily.

glozow commented at 9:05 am on August 24, 2021:

in 5f81b7e9317f703de6f949c532dac49300a14218 Allow the long term feerate to be configured, default of 10 sat/vb: prefer braced initialization to disallow narrowing conversions

And for those of us who don’t have much intuition on what feerates make sense, perhaps some sanity check static asserts would make sense? e.g. higher than default minfee, lower than default maxfee, some relationship with default discard fee :shrug:

0static const CAmount DEFAULT_CONSOLIDATE_FEERATE{10000}; // 10 sat/vbyte
1static_assert(DEFAULT_CONSOLIDATE_FEERATE >= DEFAULT_TRANSACTION_MINFEE);
2static_assert(DEFAULT_CONSOLIDATE_FEERATE <= DEFAULT_TRANSACTION_MAXFEE);

(static asserts might need to be further down after other stuff is declared)

achow101 commented at 6:07 pm on August 24, 2021:

Changed the initialization I don’t think static asserts are necessary.

instagibbs commented at 9:46 am on August 19, 2021: member

concept ACK

achow101 commented at 4:06 pm on August 19, 2021: member

Updated OP

achow101 force-pushed on Aug 19, 2021

in src/wallet/wallet.h:76 in 5f81b7e931 outdated

70@@ -71,6 +71,8 @@ static const CAmount DEFAULT_FALLBACK_FEE = 0;
71 static const CAmount DEFAULT_DISCARD_FEE = 10000;
72 //! -mintxfee default
73 static const CAmount DEFAULT_TRANSACTION_MINFEE = 1000;
74+//! -consolidatefee default

meshcollider commented at 1:10 am on August 20, 2021:

nit: -consolidatefeerate

glozow commented at 1:09 pm on August 27, 2021:

+1

achow101 commented at 4:46 pm on August 27, 2021:

Done

meshcollider commented at 1:38 am on August 20, 2021: contributor

utACK 1858364a949ea8345df5e845e7d1433b7cd5ffd0

in src/wallet/test/coinselector_tests.cpp:147 in 1858364a94 outdated

140@@ -137,6 +141,13 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
141     return static_groups;
142 }
143 
144+inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinEligibilityFilter& filter)
145+{
146+    static std::vector<OutputGroup> static_groups;
147+    static_groups = testWallet.GroupOutputs(vCoins, coin_selection_params, filter, false);

glozow commented at 10:00 am on August 20, 2021:

nit in caab9da230

0    static_groups = testWallet.GroupOutputs(vCoins, coin_selection_params, filter, /* positive_only */ false);

achow101 commented at 6:06 pm on August 24, 2021:

Done

in src/wallet/coinselection.h:180 in 1858364a94 outdated

173+ *
174+ * @param[in] inputs The selected inputs
175+ * @param[in] change_cost The cost of creating change and spending it in the future. Only used if there is change. Must be 0 if there is no change.
176+ * @param[in] target The amount targeted by the coin selection algorithm.
177+ * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
178+ * @return The waste

glozow commented at 10:14 am on August 20, 2021:

in 5a22462 Add waste metric calculation function: I see that https://github.com/bitcoin/bitcoin/pull/22009/files#r661815255 was addressed, but I still think it could be made clearer that excess is only used if there is no change? For example

 0/** Compute the waste for this result given whether a change output was made and the
 1* opportunity cost of spending these inputs now vs in the future.
 2* If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
 3* If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
 4 * where excess = selected_effective_value - target
 5 * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
 6 *
 7 * [@param](/bitcoin-bitcoin/contributor/param/)[in] inputs The selected inputs
 8 * [@param](/bitcoin-bitcoin/contributor/param/)[in] change_cost The cost of creating change and spending it in the future. Must be 0 if there is no change.
 9 * [@param](/bitcoin-bitcoin/contributor/param/)[in] target The amount targeted by the coin selection algorithm.
10 * [@param](/bitcoin-bitcoin/contributor/param/)[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
11 * [@return](/bitcoin-bitcoin/contributor/return/) The waste

achow101 commented at 6:06 pm on August 24, 2021:

Done

Xekyo commented at 4:28 pm on August 20, 2021: member

@meshcollider: I think there are currently three (Knapsack, BnB, and SRD), and it might be interesting to add a couple more. E.g. smallest-first could be an interesting strategy to create transactions at minRelayTxFee, or at very high feerates, largest-first could perhaps be preferred if it’s smaller.

Xekyo commented at 7:31 pm on August 20, 2021: member

As a follow-up to my comment about the constructor of CInputCoin initializing effective_value with nValue and the subsequent update of the effective_value to the correct magnitude: I ran the functional tests after commenting out the line that initializes effective_value in the CInputCoin with Valgrind and all tests passed, so I think that it might be possible to make CInputCoin const and thus force setting the correct value from the get-go. What do you think about that?

achow101 commented at 8:26 pm on August 20, 2021: member

@Xekyo I’m not quite sure what you mean. The members of CInputCoin can’t be const because the constructor has some logic before they can be set.

S3RK commented at 9:54 am on August 21, 2021: member

utACK 1858364 per git range-diff fdd80b0a5 1ce0c97 1858364. The only changes are related to comments in the PR

Xekyo commented at 2:35 pm on August 23, 2021: member

As discussed, let’s leave it for a follow-up PR.

sipa deleted a comment on Aug 23, 2021

in src/wallet/spend.cpp:688 in 1858364a94 outdated

683@@ -659,10 +684,8 @@ bool CWallet::CreateTransactionInternal(
684         return false;
685     }
686 
687-    // Get long term estimate
688-    CCoinControl cc_temp;
689-    cc_temp.m_confirm_target = chain().estimateMaxBlocks();
690-    coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
691+    // Set the long term feerate estimate to the wallet's consolidate feerate
692+    coin_selection_params.m_long_term_feerate = m_consolidate_feerate;

glozow commented at 9:15 am on August 24, 2021:

nit In 5f81b7e9317f703de6f949c532dac49300a14218 Allow the long term feerate to be configured, default of 10 sat/vb: Since this pulls from a wallet member, it can be initialized ~60 lines earlier, right after coin_selection_params is declared, or even within the constructor.

achow101 commented at 6:07 pm on August 24, 2021:

Done

in src/wallet/coinselection.cpp:345 in 1858364a94 outdated

340@@ -341,3 +341,29 @@ CAmount OutputGroup::GetSelectionAmount() const
341 {
342     return m_subtract_fee_outputs ? m_value : effective_value;
343 }
344+
345+CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, const CAmount change_cost, const CAmount target, bool use_effective_value)

glozow commented at 9:35 am on August 24, 2021:

nit in 5a224629549f1b0ce8ccc99b79aceab8ab809d57 Add waste metric calculation function:

These don’t need to be const, as they’re pass-by-value variables that go out of scope at the end of the function

0CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)

achow101 commented at 6:07 pm on August 24, 2021:

Done

in src/wallet/coinselection.cpp:367 in 1858364a94 outdated

361+
362+    if (change_cost == 0) {
363+        // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
364+        assert(selected_effective_value >= target);
365+        waste += selected_effective_value - target;
366+    }

glozow commented at 9:38 am on August 24, 2021:

nit in 5a22462 Add waste metric calculation function: I believe this would be clearer, but feel free to ignore

0    if (change_cost) {
1        // Consider the cost of making change and spending it in the future
2        // If we aren't making change, the caller should've set change_cost to 0
3        assert(change_cost > 0);
4        waste += change_cost;
5    } else {
6        // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
7        assert(selected_effective_value >= target);
8        waste += selected_effective_value - target;
9    }

achow101 commented at 6:07 pm on August 24, 2021:

Done

in src/wallet/test/coinselector_tests.cpp:673 in 1858364a94 outdated

668+    const CAmount fee = CAmount(100);
669+    const CAmount change_cost = CAmount(125);
670+    const CAmount fee_diff = CAmount(40);
671+    const CAmount in_amt = 3 * COIN;
672+    const CAmount target = 2 * COIN;
673+    const CAmount excess = in_amt - fee * 2 - target;

glozow commented at 9:50 am on August 24, 2021:

In c4acfb73b96041abb5bfacea98f9bf958806ffdf test GetSelectionWaste

0    const CAmount fee{100};
1    const CAmount change_cost{125};
2    const CAmount fee_diff{40};
3    const CAmount in_amt{3 * COIN};
4    const CAmount target{2 * COIN};
5    const CAmount excess{in_amt - fee * 2 - target};

achow101 commented at 6:07 pm on August 24, 2021:

Done

in src/wallet/spend.cpp:380 in 1858364a94 outdated

378     // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output.
379-    return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet);
380+    std::set<CInputCoin> knapsack_coins;
381+    CAmount knapsack_value;
382+    if (KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, knapsack_coins, knapsack_value)) {
383+        results.push_back(std::make_tuple(GetSelectionWaste(knapsack_coins, coin_selection_params.m_cost_of_change, nTargetValue + coin_selection_params.m_change_fee, !coin_selection_params.m_subtract_fee_outputs), std::move(knapsack_coins), knapsack_value));

glozow commented at 10:06 am on August 24, 2021:

in 1858364a949ea8345df5e845e7d1433b7cd5ffd0 Use waste metric for deciding which selection to use: emplace_back to construct in place break up the line for readability (same with the BnB solving portion above)

0        const auto waste = GetSelectionWaste(knapsack_coins, coin_selection_params.m_cost_of_change, nTargetValue + coin_selection_params.m_change_fee, !coin_selection_params.m_subtract_fee_outputs);
1        results.emplace_back(std::make_tuple(waste, std::move(knapsack_coins), knapsack_value));

achow101 commented at 6:07 pm on August 24, 2021:

Done

glozow commented at 10:49 am on August 24, 2021: member

ACK 1858364a949ea8345df5e845e7d1433b7cd5ffd0, some minor suggestions

Waste metric changes make sense and look correct to me. I’m not able to determine whether 10 sat/vbyte is a good consolidation feerate, though as an individual user, I would accept consolidating UTXOs at 10sat/vbyte or lower. While testing, I added some lines to compare the long term fee estimate with 10, and they at least don’t seem drastically different.

achow101 force-pushed on Aug 24, 2021

achow101 commented at 7:41 pm on August 24, 2021: member

Had to rebase due to a hidden merge conflict.

ghost commented at 8:13 pm on August 24, 2021: none

Also this PR sets the long term feerate to 10 sat/vb rather than using the 1008 block estimate.

Initially this didn’t look like the right approach but then found this option is configurable.

According to this comment it was chosen arbitrarily: #22009 (review)

According to this comment Murch suggested it based on some analysis : #22009 (review)

Can you share the analysis used for this value?
How does this affect Coin Selection?

Xekyo commented at 5:59 pm on August 25, 2021: member

I picked it arbitrarily based on staring at a lot of transactions, and then kept it because it produced satisfactory results. I didn’t experiment further with other values, so there may be better ones, and I’d expect that the optimal value would be highly dependent on a wallet’s usage pattern.

I wrote a bit about the results here: https://blog.bitgo.com/utxo-management-for-enterprise-wallets-5357dad08dd1

Even after the funds are consolidated, the wallet achieves an average of 58.5% changeless transactions across three months and 35k transactions for transaction fee savings of about 20%. The feerate sensitive unspent selection results in the average input set at low feerates to be about 1.4 times the size of input sets at higher feerates. Given about 32% of the transactions happening at low feerates, almost 45% of the wallet’s input data occurs at low feerates. This shift to spending more UTXOs at lower feerates reduces the overall fee expenditures of the wallet by at least 13%.

Talkless commented at 2:33 pm on August 26, 2021: none

Code review ACK 21566d03d1131f919df65efae7212c18f657f0fd. Did build on Debian Sid, ran unit and (non-extended) functional tests, but did NOT manually tested this code.

achow101 force-pushed on Aug 26, 2021

in src/wallet/wallet.cpp:2710 in fe47558acd outdated

2700@@ -2701,6 +2701,15 @@ std::shared_ptr<CWallet> CWallet::Create(WalletContext& context, const std::stri
2701         walletInstance->m_default_max_tx_fee = max_fee.value();
2702     }
2703 
2704+    if (gArgs.IsArgSet("-consolidatefeerate")) {
2705+        std::optional<CAmount> consolidate_feerate = ParseMoney(gArgs.GetArg("-consolidatefeerate", ""));
2706+        if (!consolidate_feerate) {
2707+            error = AmountErrMsg("consolidatefeerate", gArgs.GetArg("-consolidatefeerate", ""));
2708+            return nullptr;
2709+        }

glozow commented at 1:08 pm on August 27, 2021:

Assuming the rebase was for #22220, this seems more in keeping with the conventions in https://github.com/bitcoin/bitcoin/commit/5ef2738089efd396186775ad23aaec71ea44ebb1:

0         if (std::optional<CAmount> consolidate_feerate = ParseMoney(gArgs.GetArg("-consolidatefeerate", ""))) {
1             walletInstance->m_consolidate_feerate = CFeeRate{consolidate_feerate.value()};
2         } else {
3             error = AmountErrMsg("consolidatefeerate", gArgs.GetArg("-consolidatefeerate", ""));
4             return nullptr;
5         }

achow101 commented at 4:46 pm on August 27, 2021:

Done

glozow commented at 1:13 pm on August 27, 2021: member

re ACK fe47558 via git range-diff 1858364...fe47558, thanks for accepting suggestions

in src/wallet/test/coinselector_tests.cpp:670 in fe47558acd outdated

661@@ -651,4 +662,73 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
662     }
663 }
664 
665+BOOST_AUTO_TEST_CASE(waste_test)
666+{
667+    CoinSet selection;
668+    const CAmount fee{100};
669+    const CAmount change_cost{125};
670+    const CAmount fee_diff {40};

Xekyo commented at 2:49 pm on August 27, 2021:

Nit:

0    const CAmount fee_diff{40};

achow101 commented at 4:46 pm on August 27, 2021:

Done

Xekyo commented at 2:49 pm on August 27, 2021: member

reACK https://github.com/bitcoin/bitcoin/commit/fe47558acd365264778af5eefd61f0955e168c6f via git range-diff 15fbe72...fe47558

Allow the long term feerate to be configured, default of 10 sat/vb

The long term feerate is really the highest feerate that the user is
comfortable with making consolidatory transactions. This is should thus
be something that can be configured by the user via a new startup option
-consolidatefeerate. The default value is 10 sat/vbyte, chosen
arbitrarily (it seems like a reasonable number).

54de7b4746

tests: Use SelectCoinsBnB directly instead of AttemptSelection

Instead of calling AttemptSelection with the hopes/instruction that it
uses BnB, call SelectCoinsBnB directly to test it.

d5069fc1aa

tests: Add KnapsackGroupOutputs helper function

In order to change the KnapsackSolver tests to call KnapsackSolver, we
need KnapsackGroupOutputs to create the OutputGroups filtered with the
filter criteria.

6a023a6f90

scripted-diff: tests: Use KnapsackSolver directly

When doing the coin selector tests for KnapsackSolver, call it directly
instead of using AttemptSelection and hoping/instructing it uses
KnapsackSolver.

-BEGIN VERIFY SCRIPT-
sed -i 's/testWallet\.AttemptSelection( /KnapsackSolver(/g' src/wallet/test/coinselector_tests.cpp
sed -i 's/testWallet\.AttemptSelection(/KnapsackSolver(/g' src/wallet/test/coinselector_tests.cpp
sed -i 's/, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params)/, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet)/g' src/wallet/test/coinselector_tests.cpp
sed -i 's/, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params)/, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet)/g' src/wallet/test/coinselector_tests.cpp
sed -i 's/, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params)/, KnapsackGroupOutputs(filter_standard_extra), setCoinsRet, nValueRet)/g' src/wallet/test/coinselector_tests.cpp
sed -i 's/BOOST_CHECK( /BOOST_CHECK(/g' src/wallet/test/coinselector_tests.cpp
-END VERIFY SCRIPT-

935b3ddf72

Add waste metric calculation function 4f5ad43b1e

tests: Test GetSelectionWaste

Tests for some waste calculation scenarios

add_coin is modified to allow fee and long term fee to be set for an
added CInputCoin.

b3df0caf7c

Use waste metric for deciding which selection to use

Instead of always choosing BnB if it finds a solution, always do both
BnB and KnapsackSolver and choose the one which has the least waste.

86beee0579

achow101 force-pushed on Aug 27, 2021

Xekyo commented at 10:13 pm on August 31, 2021: member

reACK 86beee0 via git range-diff fe47558…86beee0

meshcollider commented at 4:28 am on September 1, 2021: contributor

re-utACK 86beee05795216738f51fa744539336503c26fd9

meshcollider merged this on Sep 1, 2021

meshcollider closed this on Sep 1, 2021

meshcollider removed this from the "Blockers" column in a project

glozow commented at 10:46 am on September 1, 2021: member

post merge ACK 86beee0 via git range-diff fe47558...86beee0 changes were addressing #22009 (review), #22009 (review), #22009 (review)

kiminuo referenced this in commit 06a624e42e on Sep 9, 2021

in src/wallet/test/coinselector_tests.cpp:730 in 86beee0579

725+
726+    // 0 Waste only when fee == long term fee, no change, and no excess
727+    add_coin(1 * COIN, 1, selection, fee, fee);
728+    add_coin(2 * COIN, 2, selection, fee, fee);
729+    const CAmount exact_target = in_amt - 2 * fee;
730+    BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, 0, exact_target));

rajarshimaitra commented at 10:30 am on September 10, 2021:

As it was discussed in the review club, there are more scenarios when the waste can be zero. Thus the “only” doesn’t seem appropriate here.

I went ahead and opened another PR fixing this with addition of those extra cases. #22938.

rajarshimaitra commented at 10:31 am on September 10, 2021: contributor

Post merge tACK

meshcollider referenced this in commit d5d0a5c604 on Sep 28, 2021

meshcollider referenced this in commit a8bbd4cc81 on Sep 28, 2021

kiminuo referenced this in commit 8ca6105408 on Oct 1, 2021

kiminuo referenced this in commit 9dd6561fa6 on Oct 23, 2021

kiminuo referenced this in commit f4d3e1f0fe on Oct 29, 2021

laanwj referenced this in commit c840ab0231 on Dec 9, 2021

achow101 referenced this in commit c109e7d51c on Mar 11, 2022

DrahtBot locked this on Oct 30, 2022

wallet: Decide which coin selection solution to use based on waste metric #22009

Conflicts