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

86beee05795216738f51fa744539336503c26fd9 Use waste metric for deciding which selection to use (Andrew Chow)
b3df0caf7c291a316298e54e73426c765e61c129 tests: Test GetSelectionWaste (Andrew Chow)
4f5ad43b1e05cd7b403f87aae4c4d42e5aea810b Add waste metric calculation function (Andrew Chow)
935b3ddf72aa390087684e03166c707f5b173434 scripted-diff: tests: Use KnapsackSolver directly (Andrew Chow)
6a023a6f904efe38dacd662d919aba74f066b1dc tests: Add KnapsackGroupOutputs helper function (Andrew Chow)
d5069fc1aa7d335f3043227f843cbb9d8ba1507b tests: Use SelectCoinsBnB directly instead of AttemptSelection (Andrew Chow)
54de7b47463d98f860167d4e0b7e4ebb3926b59c Allow the long term feerate to be configured, default of 10 sat/vb (Andrew Chow)

Pull request description:

  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.

ACKs for top commit:
  Xekyo:
    reACK 86beee0 via git range-diff fe47558...86beee0
  meshcollider:
    re-utACK 86beee05795216738f51fa744539336503c26fd9

Tree-SHA512: 54b154b346538eca68ae2a3b83a033b495c1605c14f842bfc43ded2256b110983ce674c647fe753cf0305b1b178403d8d60d6d4203c7a712bec784be52e90d42

8 files changed, 209 insertions, 43 deletions

diff --git a/src/dummywallet.cpp b/src/dummywallet.cpp
index 95886d3138..2d897f4c40 100644
--- a/src/dummywallet.cpp
+++ b/src/dummywallet.cpp
@@ -28,6 +28,7 @@ void DummyWalletInit::AddWalletOptions(ArgsManager& argsman) const
         "-addresstype",
         "-avoidpartialspends",
         "-changetype",
+        "-consolidatefeerate=<amt>",
         "-disablewallet",
         "-discardfee=<amt>",
         "-fallbackfee=<amt>",
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 25b1ee07e4..1699424657 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -341,3 +341,30 @@ CAmount OutputGroup::GetSelectionAmount() const
 {
     return m_subtract_fee_outputs ? m_value : effective_value;
 }
+
+CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value)
+{
+    // This function should not be called with empty inputs as that would mean the selection failed
+    assert(!inputs.empty());
+
+    // Always consider the cost of spending an input now vs in the future.
+    CAmount waste = 0;
+    CAmount selected_effective_value = 0;
+    for (const CInputCoin& coin : inputs) {
+        waste += coin.m_fee - coin.m_long_term_fee;
+        selected_effective_value += use_effective_value ? coin.effective_value : coin.txout.nValue;
+    }
+
+    if (change_cost) {
+        // Consider the cost of making change and spending it in the future
+        // If we aren't making change, the caller should've set change_cost to 0
+        assert(change_cost > 0);
+        waste += change_cost;
+    } else {
+        // When we are not making change (change_cost == 0), consider the excess we are throwing away to fees
+        assert(selected_effective_value >= target);
+        waste += selected_effective_value - target;
+    }
+
+    return waste;
+}
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index 7a3fb82139..35617d455b 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -166,6 +166,21 @@ struct OutputGroup
     CAmount GetSelectionAmount() const;
 };
 
+/** Compute the waste for this result given the cost of change
+ * and the opportunity cost of spending these inputs now vs in the future.
+ * If change exists, waste = change_cost + inputs * (effective_feerate - long_term_feerate)
+ * If no change, waste = excess + inputs * (effective_feerate - long_term_feerate)
+ * where excess = selected_effective_value - target
+ * change_cost = effective_feerate * change_output_size + long_term_feerate * change_spend_size
+ *
+ * @param[in] inputs The selected inputs
+ * @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.
+ * @param[in] target The amount targeted by the coin selection algorithm.
+ * @param[in] use_effective_value Whether to use the input's effective value (when true) or the real value (when false).
+ * @return The waste
+ */
+[[nodiscard]] CAmount GetSelectionWaste(const std::set<CInputCoin>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
+
 bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret);
 
 // Original coin selection algorithm as a fallback
diff --git a/src/wallet/init.cpp b/src/wallet/init.cpp
index eb0d6316c0..bb5f0cceff 100644
--- a/src/wallet/init.cpp
+++ b/src/wallet/init.cpp
@@ -45,6 +45,7 @@ void WalletInit::AddWalletOptions(ArgsManager& argsman) const
     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);
     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);
     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);
+    argsman.AddArg("-consolidatefeerate=<amt>", strprintf("The maximum feerate (in %s/kvB) at which transaction building may use more inputs than strictly necessary so that the wallet's UTXO pool can be reduced (default: %s).", CURRENCY_UNIT, FormatMoney(DEFAULT_CONSOLIDATE_FEERATE)), ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
     argsman.AddArg("-disablewallet", "Do not load the wallet and disable wallet RPC calls", ArgsManager::ALLOW_ANY, OptionsCategory::WALLET);
     argsman.AddArg("-discardfee=<amt>", strprintf("The fee rate (in %s/kvB) that indicates your tolerance for discarding change by adding it to the fee (default: %s). "
                                                                 "Note: An output is discarded if it is dust at this rate, but we will always discard up to the dust relay fee and a discard fee above that is limited by the fee estimate for the longest target",
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 3bb7134b24..928335da2b 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -357,17 +357,44 @@ bool CWallet::AttemptSelection(const CAmount& nTargetValue, const CoinEligibilit
 {
     setCoinsRet.clear();
     nValueRet = 0;
+    // Vector of results for use with waste calculation
+    // In order: calculated waste, selected inputs, selected input value (sum of input values)
+    // TODO: Use a struct representing the selection result
+    std::vector<std::tuple<CAmount, std::set<CInputCoin>, CAmount>> results;
 
     // Note that unlike KnapsackSolver, we do not include the fee for creating a change output as BnB will not create a change output.
     std::vector<OutputGroup> positive_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, true /* positive_only */);
-    if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, setCoinsRet, nValueRet)) {
-        return true;
+    std::set<CInputCoin> bnb_coins;
+    CAmount bnb_value;
+    if (SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change, bnb_coins, bnb_value)) {
+        const auto waste = GetSelectionWaste(bnb_coins, /* cost of change */ CAmount(0), nTargetValue, !coin_selection_params.m_subtract_fee_outputs);
+        results.emplace_back(std::make_tuple(waste, std::move(bnb_coins), bnb_value));
     }
+
     // The knapsack solver has some legacy behavior where it will spend dust outputs. We retain this behavior, so don't filter for positive only here.
     std::vector<OutputGroup> all_groups = GroupOutputs(coins, coin_selection_params, eligibility_filter, false /* positive_only */);
     // While nTargetValue includes the transaction fees for non-input things, it does not include the fee for creating a change output.
     // So we need to include that for KnapsackSolver as well, as we are expecting to create a change output.
-    return KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, setCoinsRet, nValueRet);
+    std::set<CInputCoin> knapsack_coins;
+    CAmount knapsack_value;
+    if (KnapsackSolver(nTargetValue + coin_selection_params.m_change_fee, all_groups, knapsack_coins, knapsack_value)) {
+        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);
+        results.emplace_back(std::make_tuple(waste, std::move(knapsack_coins), knapsack_value));
+    }
+
+    if (results.size() == 0) {
+        // No solution found
+        return false;
+    }
+
+    // Choose the result with the least waste
+    // If the waste is the same, choose the one which spends more inputs.
+    const auto& best_result = std::min_element(results.begin(), results.end(), [](const auto& a, const auto& b) {
+        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());
+    });
+    setCoinsRet = std::get<1>(*best_result);
+    nValueRet = std::get<2>(*best_result);
+    return true;
 }
 
 bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) const
@@ -586,6 +613,9 @@ bool CWallet::CreateTransactionInternal(
     CoinSelectionParams coin_selection_params; // Parameters for coin selection, init with dummy
     coin_selection_params.m_avoid_partial_spends = coin_control.m_avoid_partial_spends;
 
+    // Set the long term feerate estimate to the wallet's consolidate feerate
+    coin_selection_params.m_long_term_feerate = m_consolidate_feerate;
+
     CAmount recipients_sum = 0;
     const OutputType change_type = TransactionChangeType(coin_control.m_change_type ? *coin_control.m_change_type : m_default_change_type, vecSend);
     ReserveDestination reservedest(this, change_type);
@@ -659,11 +689,6 @@ bool CWallet::CreateTransactionInternal(
         return false;
     }
 
-    // Get long term estimate
-    CCoinControl cc_temp;
-    cc_temp.m_confirm_target = chain().estimateMaxBlocks();
-    coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
-
     // Calculate the cost of change
     // Cost of change is the cost of creating the change output + cost of spending the change output in the future.
     // For creating the change output now, we use the effective feerate.
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 3488ae3526..7b2169a5b6 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -49,12 +49,16 @@ static void add_coin(const CAmount& nValue, int nInput, std::vector<CInputCoin>&
     set.emplace_back(MakeTransactionRef(tx), nInput);
 }
 
-static void add_coin(const CAmount& nValue, int nInput, CoinSet& set)
+static void add_coin(const CAmount& nValue, int nInput, CoinSet& set, CAmount fee = 0, CAmount long_term_fee = 0)
 {
     CMutableTransaction tx;
     tx.vout.resize(nInput + 1);
     tx.vout[nInput].nValue = nValue;
-    set.emplace(MakeTransactionRef(tx), nInput);
+    CInputCoin coin(MakeTransactionRef(tx), nInput);
+    coin.effective_value = nValue - fee;
+    coin.m_fee = fee;
+    coin.m_long_term_fee = long_term_fee;
+    set.insert(coin);
 }
 
 static void add_coin(CWallet& wallet, const CAmount& nValue, int nAge = 6*24, bool fIsFromMe = false, int nInput=0, bool spendable = false)
@@ -137,6 +141,13 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& coins)
     return static_groups;
 }
 
+inline std::vector<OutputGroup>& KnapsackGroupOutputs(const CoinEligibilityFilter& filter)
+{
+    static std::vector<OutputGroup> static_groups;
+    static_groups = testWallet.GroupOutputs(vCoins, coin_selection_params, filter, /* positive_only */false);
+    return static_groups;
+}
+
 // Branch and bound coin selection tests
 BOOST_AUTO_TEST_CASE(bnb_search_test)
 {
@@ -281,14 +292,14 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     empty_wallet();
     add_coin(1);
     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
-    BOOST_CHECK(!testWallet.AttemptSelection( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb));
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(vCoins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change, setCoinsRet, nValueRet));
 
     // Test fees subtracted from output:
     empty_wallet();
     add_coin(1 * CENT);
     vCoins.at(0).nInputBytes = 40;
     coin_selection_params_bnb.m_subtract_fee_outputs = true;
-    BOOST_CHECK(testWallet.AttemptSelection( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(vCoins), 1 * CENT, coin_selection_params_bnb.m_cost_of_change, setCoinsRet, nValueRet));
     BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
 
     // Make sure that can use BnB when there are preset inputs
@@ -323,24 +334,24 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         empty_wallet();
 
         // with an empty wallet we can't even pay one cent
-        BOOST_CHECK(!testWallet.AttemptSelection( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(!KnapsackSolver(1 * CENT, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet));
 
         add_coin(1*CENT, 4);        // add a new 1 cent coin
 
         // with a new 1 cent coin, we still can't find a mature 1 cent
-        BOOST_CHECK(!testWallet.AttemptSelection( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(!KnapsackSolver(1 * CENT, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet));
 
         // but we can find a new 1 cent
-        BOOST_CHECK( testWallet.AttemptSelection( 1 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(1 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
 
         add_coin(2*CENT);           // add a mature 2 cent coin
 
         // we can't make 3 cents of mature coins
-        BOOST_CHECK(!testWallet.AttemptSelection( 3 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(!KnapsackSolver(3 * CENT, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet));
 
         // we can make 3 cents of new coins
-        BOOST_CHECK( testWallet.AttemptSelection( 3 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(3 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 3 * CENT);
 
         add_coin(5*CENT);           // add a mature 5 cent coin,
@@ -350,33 +361,33 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         // now we have new: 1+10=11 (of which 10 was self-sent), and mature: 2+5+20=27.  total = 38
 
         // we can't make 38 cents only if we disallow new coins:
-        BOOST_CHECK(!testWallet.AttemptSelection(38 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(!KnapsackSolver(38 * CENT, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet));
         // we can't even make 37 cents if we don't allow new coins even if they're from us
-        BOOST_CHECK(!testWallet.AttemptSelection(38 * CENT, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(!KnapsackSolver(38 * CENT, KnapsackGroupOutputs(filter_standard_extra), setCoinsRet, nValueRet));
         // but we can make 37 cents if we accept new coins from ourself
-        BOOST_CHECK( testWallet.AttemptSelection(37 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(37 * CENT, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 37 * CENT);
         // and we can make 38 cents if we accept all new coins
-        BOOST_CHECK( testWallet.AttemptSelection(38 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(38 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 38 * CENT);
 
         // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
-        BOOST_CHECK( testWallet.AttemptSelection(34 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(34 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 35 * CENT);       // but 35 cents is closest
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);     // the best should be 20+10+5.  it's incredibly unlikely the 1 or 2 got included (but possible)
 
         // when we try making 7 cents, the smaller coins (1,2,5) are enough.  We should see just 2+5
-        BOOST_CHECK( testWallet.AttemptSelection( 7 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(7 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 7 * CENT);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
 
         // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
-        BOOST_CHECK( testWallet.AttemptSelection( 8 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(8 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK(nValueRet == 8 * CENT);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
 
         // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
-        BOOST_CHECK( testWallet.AttemptSelection( 9 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(9 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 10 * CENT);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
@@ -390,30 +401,30 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(30*CENT); // now we have 6+7+8+20+30 = 71 cents total
 
         // check that we have 71 and not 72
-        BOOST_CHECK( testWallet.AttemptSelection(71 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
-        BOOST_CHECK(!testWallet.AttemptSelection(72 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(71 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
+        BOOST_CHECK(!KnapsackSolver(72 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
 
         // now try making 16 cents.  the best smaller coins can do is 6+7+8 = 21; not as good at the next biggest coin, 20
-        BOOST_CHECK( testWallet.AttemptSelection(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(16 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 20 * CENT); // we should get 20 in one coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
         add_coin( 5*CENT); // now we have 5+6+7+8+20+30 = 75 cents total
 
         // now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, better than the next biggest coin, 20
-        BOOST_CHECK( testWallet.AttemptSelection(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(16 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 18 * CENT); // we should get 18 in 3 coins
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
 
         add_coin( 18*CENT); // now we have 5+6+7+8+18+20+30
 
         // and now if we try making 16 cents again, the smaller coins can make 5+6+7 = 18 cents, the same as the next biggest coin, 18
-        BOOST_CHECK( testWallet.AttemptSelection(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(16 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 18 * CENT);  // we should get 18 in 1 coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U); // because in the event of a tie, the biggest coin wins
 
         // now try making 11 cents.  we should get 5+6
-        BOOST_CHECK( testWallet.AttemptSelection(11 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(11 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 11 * CENT);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
 
@@ -422,11 +433,11 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin( 2*COIN);
         add_coin( 3*COIN);
         add_coin( 4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
-        BOOST_CHECK( testWallet.AttemptSelection(95 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(95 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 1 * COIN);  // we should get 1 BTC in 1 coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
-        BOOST_CHECK( testWallet.AttemptSelection(195 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(195 * CENT, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 2 * COIN);  // we should get 2 BTC in 1 coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
@@ -441,14 +452,14 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
 
         // try making 1 * MIN_CHANGE from the 1.5 * MIN_CHANGE
         // we'll get change smaller than MIN_CHANGE whatever happens, so can expect MIN_CHANGE exactly
-        BOOST_CHECK( testWallet.AttemptSelection(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(MIN_CHANGE, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE);
 
         // but if we add a bigger coin, small change is avoided
         add_coin(1111*MIN_CHANGE);
 
         // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
-        BOOST_CHECK( testWallet.AttemptSelection(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(1 * MIN_CHANGE, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
 
         // if we add more small coins:
@@ -456,7 +467,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(MIN_CHANGE * 7 / 10);
 
         // and try again to make 1.0 * MIN_CHANGE
-        BOOST_CHECK( testWallet.AttemptSelection(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(1 * MIN_CHANGE, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
 
         // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
@@ -465,7 +476,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         for (int j = 0; j < 20; j++)
             add_coin(50000 * COIN);
 
-        BOOST_CHECK( testWallet.AttemptSelection(500000 * COIN, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(500000 * COIN, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins
 
@@ -478,7 +489,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(MIN_CHANGE * 6 / 10);
         add_coin(MIN_CHANGE * 7 / 10);
         add_coin(1111 * MIN_CHANGE);
-        BOOST_CHECK( testWallet.AttemptSelection(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(1 * MIN_CHANGE, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE); // we get the bigger coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
@@ -488,7 +499,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(MIN_CHANGE * 6 / 10);
         add_coin(MIN_CHANGE * 8 / 10);
         add_coin(1111 * MIN_CHANGE);
-        BOOST_CHECK( testWallet.AttemptSelection(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(MIN_CHANGE, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE);   // we should get the exact amount
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U); // in two coins 0.4+0.6
 
@@ -499,12 +510,12 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(MIN_CHANGE * 100);
 
         // trying to make 100.01 from these three coins
-        BOOST_CHECK(testWallet.AttemptSelection(MIN_CHANGE * 10001 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(MIN_CHANGE * 10001 / 100, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, MIN_CHANGE * 10105 / 100); // we should get all coins
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 3U);
 
         // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
-        BOOST_CHECK(testWallet.AttemptSelection(MIN_CHANGE * 9990 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(KnapsackSolver(MIN_CHANGE * 9990 / 100, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
         BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
       }
@@ -518,7 +529,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
 
            // We only create the wallet once to save time, but we still run the coin selection RUN_TESTS times.
            for (int i = 0; i < RUN_TESTS; i++) {
-             BOOST_CHECK(testWallet.AttemptSelection(2000, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+             BOOST_CHECK(KnapsackSolver(2000, KnapsackGroupOutputs(filter_confirmed), setCoinsRet, nValueRet));
 
              if (amt - 2000 < MIN_CHANGE) {
                  // needs more than one input:
@@ -603,7 +614,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
         add_coin(1000 * COIN);
     add_coin(3 * COIN);
 
-    BOOST_CHECK(testWallet.AttemptSelection(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+    BOOST_CHECK(KnapsackSolver(1003 * COIN, KnapsackGroupOutputs(filter_standard), setCoinsRet, nValueRet));
     BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN);
     BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
 
@@ -651,4 +662,73 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
     }
 }
 
+BOOST_AUTO_TEST_CASE(waste_test)
+{
+    CoinSet selection;
+    const CAmount fee{100};
+    const CAmount change_cost{125};
+    const CAmount fee_diff{40};
+    const CAmount in_amt{3 * COIN};
+    const CAmount target{2 * COIN};
+    const CAmount excess{in_amt - fee * 2 - target};
+
+    // Waste with change is the change cost and difference between fee and long term fee
+    add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
+    add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
+    const CAmount waste1 = GetSelectionWaste(selection, change_cost, target);
+    BOOST_CHECK_EQUAL(fee_diff * 2 + change_cost, waste1);
+    selection.clear();
+
+    // Waste without change is the excess and difference between fee and long term fee
+    add_coin(1 * COIN, 1, selection, fee, fee - fee_diff);
+    add_coin(2 * COIN, 2, selection, fee, fee - fee_diff);
+    const CAmount waste_nochange1 = GetSelectionWaste(selection, 0, target);
+    BOOST_CHECK_EQUAL(fee_diff * 2 + excess, waste_nochange1);
+    selection.clear();
+
+    // Waste with change and fee == long term fee is just cost of change
+    add_coin(1 * COIN, 1, selection, fee, fee);
+    add_coin(2 * COIN, 2, selection, fee, fee);
+    BOOST_CHECK_EQUAL(change_cost, GetSelectionWaste(selection, change_cost, target));
+    selection.clear();
+
+    // Waste without change and fee == long term fee is just the excess
+    add_coin(1 * COIN, 1, selection, fee, fee);
+    add_coin(2 * COIN, 2, selection, fee, fee);
+    BOOST_CHECK_EQUAL(excess, GetSelectionWaste(selection, 0, target));
+    selection.clear();
+
+    // Waste will be greater when fee is greater, but long term fee is the same
+    add_coin(1 * COIN, 1, selection, fee * 2, fee - fee_diff);
+    add_coin(2 * COIN, 2, selection, fee * 2, fee - fee_diff);
+    const CAmount waste2 = GetSelectionWaste(selection, change_cost, target);
+    BOOST_CHECK_GT(waste2, waste1);
+    selection.clear();
+
+    // Waste with change is the change cost and difference between fee and long term fee
+    // With long term fee greater than fee, waste should be less than when long term fee is less than fee
+    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+    const CAmount waste3 = GetSelectionWaste(selection, change_cost, target);
+    BOOST_CHECK_EQUAL(fee_diff * -2 + change_cost, waste3);
+    BOOST_CHECK_LT(waste3, waste1);
+    selection.clear();
+
+    // Waste without change is the excess and difference between fee and long term fee
+    // With long term fee greater than fee, waste should be less than when long term fee is less than fee
+    add_coin(1 * COIN, 1, selection, fee, fee + fee_diff);
+    add_coin(2 * COIN, 2, selection, fee, fee + fee_diff);
+    const CAmount waste_nochange2 = GetSelectionWaste(selection, 0, target);
+    BOOST_CHECK_EQUAL(fee_diff * -2 + excess, waste_nochange2);
+    BOOST_CHECK_LT(waste_nochange2, waste_nochange1);
+    selection.clear();
+
+    // 0 Waste only when fee == long term fee, no change, and no excess
+    add_coin(1 * COIN, 1, selection, fee, fee);
+    add_coin(2 * COIN, 2, selection, fee, fee);
+    const CAmount exact_target = in_amt - 2 * fee;
+    BOOST_CHECK_EQUAL(0, GetSelectionWaste(selection, 0, exact_target));
+
+}
+
 BOOST_AUTO_TEST_SUITE_END()
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 59bdf0405a..6f3dcf2afa 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2703,6 +2703,15 @@ std::shared_ptr<CWallet> CWallet::Create(WalletContext& context, const std::stri
         walletInstance->m_default_max_tx_fee = max_fee.value();
     }
 
+    if (gArgs.IsArgSet("-consolidatefeerate")) {
+        if (std::optional<CAmount> consolidate_feerate = ParseMoney(gArgs.GetArg("-consolidatefeerate", ""))) {
+            walletInstance->m_consolidate_feerate = CFeeRate(*consolidate_feerate);
+        } else {
+            error = AmountErrMsg("consolidatefeerate", gArgs.GetArg("-consolidatefeerate", ""));
+            return nullptr;
+        }
+    }
+
     if (chain && chain->relayMinFee().GetFeePerK() > HIGH_TX_FEE_PER_KB) {
         warnings.push_back(AmountHighWarn("-minrelaytxfee") + Untranslated(" ") +
                            _("The wallet will avoid paying less than the minimum relay fee."));
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index a1bbf66136..607af3efb0 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -73,6 +73,8 @@ static const CAmount DEFAULT_FALLBACK_FEE = 0;
 static const CAmount DEFAULT_DISCARD_FEE = 10000;
 //! -mintxfee default
 static const CAmount DEFAULT_TRANSACTION_MINFEE = 1000;
+//! -consolidatefeerate default
+static const CAmount DEFAULT_CONSOLIDATE_FEERATE{10000}; // 10 sat/vbyte
 /**
  * maximum fee increase allowed to do partial spend avoidance, even for nodes with this feature disabled by default
  *
@@ -638,6 +640,12 @@ public:
       * output itself, just drop it to fees. */
     CFeeRate m_discard_rate{DEFAULT_DISCARD_FEE};
 
+    /** When the actual feerate is less than the consolidate feerate, we will tend to make transactions which
+     * consolidate inputs. When the actual feerate is greater than the consolidate feerate, we will tend to make
+     * transactions which have the lowest fees.
+     */
+    CFeeRate m_consolidate_feerate{DEFAULT_CONSOLIDATE_FEERATE};
+
     /** The maximum fee amount we're willing to pay to prioritize partial spend avoidance. */
     CAmount m_max_aps_fee{DEFAULT_MAX_AVOIDPARTIALSPEND_FEE}; //!< note: this is absolute fee, not fee rate
     OutputType m_default_address_type{DEFAULT_ADDRESS_TYPE};