Merge bitcoin/bitcoin#25647: wallet: return change from SelectionResult

4fef5344288e454460b80db0316294e1ec1ad8ad wallet: use GetChange() when computing waste (S3RK)
87e0ef903133492e76b7c7556209554d4a0c3d66 wallet: use GetChange() in tx building (S3RK)
15e97a6886902ebb378829993a972dc52558aa92 wallet: add SelectionResult::GetChange (S3RK)
72cad28da05cfce9e4950f2dc5a709da41d251f4 wallet: calculate and store min_viable_change (S3RK)
e3210a722542a9cb5f7e4be72470dbe488c281fd wallet: account for preselected inputs in target (S3RK)
f8e796348b644c011ad9a8312356d4426c16cc4b wallet: add SelectionResult::Merge (S3RK)
06f558e4e2164d1916f258c731efe4586728a23b wallet: accurate SelectionResult::m_target (S3RK)
c8cf08ea743e430c2bf3fe46439594257b0937e5 wallet: ensure m_min_change_target always covers change fee (S3RK)

Pull request description:

  Benefits:
  1. more accurate waste calculation for knapsack. Waste calculation is now consistent with tx building code. Before we always assumed change for knapsack even when the solution is changeless4.
  2. simpler tx building code. Only create change output when it's needed
  3. makes it easier to correctly account for fees for CPFP inputs (should be done in a follow up)

  In the first three commits we fix the code to accurately track selection target in `SelectionResult::m_target`
  Then we introduce new variable `min_change` that represents the minimum viable change amount
  Then we introduce `SelectionResult::GetChange()` which incapsulates dropping change for fee logic and uses correct values of `SelectionResult::m_target`
  Then we use `SelectionResult::GetChange()` in both tx building and waste calculation code

  This PR is a refactoring and shouldn't change the behaviour.
  There is only one known small change (arguably a bug fix). Before we dropped change output if it's smaller than `cost_of_change` after paying change fees. This is incorrect as `cost_of_change` already includes `change_fee`.

ACKs for top commit:
  achow101:
    ACK 4fef5344288e454460b80db0316294e1ec1ad8ad
  Xekyo:
    crACK 4fef5344288e454460b80db0316294e1ec1ad8ad
  furszy:
    Code review ACK 4fef5344
  w0xlt:
    ACK https://github.com/bitcoin/bitcoin/pull/25647/commits/4fef5344288e454460b80db0316294e1ec1ad8ad

Tree-SHA512: 31a7455d4129bc39a444da0f16ad478d690d4d9627b2b8fdb5605facc6488171926bf02f5d7d9a545b2b59efafcf5bb3d404005e4da15c7b44b3f7d441afb941

5 files changed, 153 insertions, 90 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 49e6bac462..b568e90998 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -156,7 +156,7 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
     for (const size_t& i : best_selection) {
         result.AddInput(utxo_pool.at(i));
     }
-    result.ComputeAndSetWaste(CAmount{0});
+    result.ComputeAndSetWaste(cost_of_change, cost_of_change, CAmount{0});
     assert(best_waste == result.GetWaste());
 
     return result;
@@ -166,6 +166,12 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut
 {
     SelectionResult result(target_value, SelectionAlgorithm::SRD);
 
+    // Include change for SRD as we want to avoid making really small change if the selection just
+    // barely meets the target. Just use the lower bound change target instead of the randomly
+    // generated one, since SRD will result in a random change amount anyway; avoid making the
+    // target needlessly large.
+    target_value += CHANGE_LOWER;
+
     std::vector<size_t> indexes;
     indexes.resize(utxo_pool.size());
     std::iota(indexes.begin(), indexes.end(), 0);
@@ -389,20 +395,26 @@ CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost,
     return waste;
 }
 
-CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
+CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng)
 {
     if (payment_value <= CHANGE_LOWER / 2) {
-        return CHANGE_LOWER;
+        return change_fee + CHANGE_LOWER;
     } else {
         // random value between 50ksat and min (payment_value * 2, 1milsat)
         const auto upper_bound = std::min(payment_value * 2, CHANGE_UPPER);
-        return rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
+        return change_fee + rng.randrange(upper_bound - CHANGE_LOWER) + CHANGE_LOWER;
     }
 }
 
-void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
+void SelectionResult::ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee)
 {
-    m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+    const CAmount change = GetChange(min_viable_change, change_fee);
+
+    if (change > 0) {
+        m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
+    } else {
+        m_waste = GetSelectionWaste(m_selected_inputs, 0, m_target, m_use_effective);
+    }
 }
 
 CAmount SelectionResult::GetWaste() const
@@ -415,6 +427,11 @@ CAmount SelectionResult::GetSelectedValue() const
     return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.txout.nValue; });
 }
 
+CAmount SelectionResult::GetSelectedEffectiveValue() const
+{
+    return std::accumulate(m_selected_inputs.cbegin(), m_selected_inputs.cend(), CAmount{0}, [](CAmount sum, const auto& coin) { return sum + coin.GetEffectiveValue(); });
+}
+
 void SelectionResult::Clear()
 {
     m_selected_inputs.clear();
@@ -427,6 +444,16 @@ void SelectionResult::AddInput(const OutputGroup& group)
     m_use_effective = !group.m_subtract_fee_outputs;
 }
 
+void SelectionResult::Merge(const SelectionResult& other)
+{
+    m_target += other.m_target;
+    m_use_effective |= other.m_use_effective;
+    if (m_algo == SelectionAlgorithm::MANUAL) {
+        m_algo = other.m_algo;
+    }
+    util::insert(m_selected_inputs, other.m_selected_inputs);
+}
+
 const std::set<COutput>& SelectionResult::GetInputSet() const
 {
     return m_selected_inputs;
@@ -464,4 +491,24 @@ std::string GetAlgorithmName(const SelectionAlgorithm algo)
     }
     assert(false);
 }
+
+CAmount SelectionResult::GetChange(const CAmount min_viable_change, const CAmount change_fee) const
+{
+    // change = SUM(inputs) - SUM(outputs) - fees
+    // 1) With SFFO we don't pay any fees
+    // 2) Otherwise we pay all the fees:
+    //  - input fees are covered by GetSelectedEffectiveValue()
+    //  - non_input_fee is included in m_target
+    //  - change_fee
+    const CAmount change = m_use_effective
+                           ? GetSelectedEffectiveValue() - m_target - change_fee
+                           : GetSelectedValue() - m_target;
+
+    if (change < min_viable_change) {
+        return 0;
+    }
+
+    return change;
+}
+
 } // namespace wallet
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index e257d3f7c7..761c2be0b3 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -123,6 +123,10 @@ struct CoinSelectionParams {
     /** Mininmum change to target in Knapsack solver: select coins to cover the payment and
      * at least this value of change. */
     CAmount m_min_change_target{0};
+    /** Minimum amount for creating a change output.
+     * If change budget is smaller than min_change then we forgo creation of change output.
+     */
+    CAmount min_viable_change{0};
     /** Cost of creating the change output. */
     CAmount m_change_fee{0};
     /** Cost of creating the change output + cost of spending the change output in the future. */
@@ -252,6 +256,7 @@ struct OutputGroup
 
 /** Choose a random change target for each transaction to make it harder to fingerprint the Core
  * wallet based on the change output values of transactions it creates.
+ * Change target covers at least change fees and adds a random value on top of it.
  * The random value is between 50ksat and min(2 * payment_value, 1milsat)
  * When payment_value <= 25ksat, the value is just 50ksat.
  *
@@ -261,8 +266,9 @@ struct OutputGroup
  * coins selected are just sufficient to cover the payment amount ("unnecessary input" heuristic).
  *
  * @param[in]   payment_value   Average payment value of the transaction output(s).
+ * @param[in]   change_fee      Fee for creating a change output.
  */
-[[nodiscard]] CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng);
+[[nodiscard]] CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_fee, FastRandomContext& rng);
 
 enum class SelectionAlgorithm : uint8_t
 {
@@ -279,17 +285,16 @@ struct SelectionResult
 private:
     /** Set of inputs selected by the algorithm to use in the transaction */
     std::set<COutput> m_selected_inputs;
+    /** The target the algorithm selected for. Equal to the recipient amount plus non-input fees */
+    CAmount m_target;
+    /** The algorithm used to produce this result */
+    SelectionAlgorithm m_algo;
     /** Whether the input values for calculations should be the effective value (true) or normal value (false) */
     bool m_use_effective{false};
     /** The computed waste */
     std::optional<CAmount> m_waste;
 
 public:
-    /** The target the algorithm selected for. Note that this may not be equal to the recipient amount as it can include non-input fees */
-    const CAmount m_target;
-    /** The algorithm used to produce this result */
-    const SelectionAlgorithm m_algo;
-
     explicit SelectionResult(const CAmount target, SelectionAlgorithm algo)
         : m_target(target), m_algo(algo) {}
 
@@ -298,20 +303,47 @@ public:
     /** Get the sum of the input values */
     [[nodiscard]] CAmount GetSelectedValue() const;
 
+    [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
+
     void Clear();
 
     void AddInput(const OutputGroup& group);
 
     /** Calculates and stores the waste for this selection via GetSelectionWaste */
-    void ComputeAndSetWaste(CAmount change_cost);
+    void ComputeAndSetWaste(const CAmount min_viable_change, const CAmount change_cost, const CAmount change_fee);
     [[nodiscard]] CAmount GetWaste() const;
 
+    void Merge(const SelectionResult& other);
+
     /** Get m_selected_inputs */
     const std::set<COutput>& GetInputSet() const;
     /** Get the vector of COutputs that will be used to fill in a CTransaction's vin */
     std::vector<COutput> GetShuffledInputVector() const;
 
     bool operator<(SelectionResult other) const;
+
+    /** Get the amount for the change output after paying needed fees.
+     *
+     * The change amount is not 100% precise due to discrepancies in fee calculation.
+     * The final change amount (if any) should be corrected after calculating the final tx fees.
+     * When there is a discrepancy, most of the time the final change would be slightly bigger than estimated.
+     *
+     * Following are the possible factors of discrepancy:
+     *  + non-input fees always include segwit flags
+     *  + input fee estimation always include segwit stack size
+     *  + input fees are rounded individually and not collectively, which leads to small rounding errors
+     *  - input counter size is always assumed to be 1vbyte
+     *
+     * @param[in]  min_viable_change  Minimum amount for change output, if change would be less then we forgo change
+     * @param[in]  change_fee         Fees to include change output in the tx
+     * @returns Amount for change output, 0 when there is no change.
+     *
+     */
+    CAmount GetChange(const CAmount min_viable_change, const CAmount change_fee) const;
+
+    CAmount GetTarget() const { return m_target; }
+
+    SelectionAlgorithm GetAlgo() const { return m_algo; }
 };
 
 std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change);
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 001acd04e2..92cf771358 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -502,32 +502,20 @@ std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, cons
     // Vector of results. We will choose the best one based on waste.
     std::vector<SelectionResult> 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(wallet, available_coins, coin_selection_params, eligibility_filter, true /* positive_only */);
+    std::vector<OutputGroup> positive_groups = GroupOutputs(wallet, available_coins, coin_selection_params, eligibility_filter, /*positive_only=*/true);
     if (auto bnb_result{SelectCoinsBnB(positive_groups, nTargetValue, coin_selection_params.m_cost_of_change)}) {
         results.push_back(*bnb_result);
     }
 
     // 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(wallet, available_coins, coin_selection_params, eligibility_filter, false /* positive_only */);
-    CAmount target_with_change = nTargetValue;
-    // 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 and SRD as well, as we are expecting to create a change output.
-    if (!coin_selection_params.m_subtract_fee_outputs) {
-        target_with_change += coin_selection_params.m_change_fee;
-    }
-    if (auto knapsack_result{KnapsackSolver(all_groups, target_with_change, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {
-        knapsack_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+    std::vector<OutputGroup> all_groups = GroupOutputs(wallet, available_coins, coin_selection_params, eligibility_filter, /*positive_only=*/false);
+    if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue, coin_selection_params.m_min_change_target, coin_selection_params.rng_fast)}) {
+        knapsack_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         results.push_back(*knapsack_result);
     }
 
-    // Include change for SRD as we want to avoid making really small change if the selection just
-    // barely meets the target. Just use the lower bound change target instead of the randomly
-    // generated one, since SRD will result in a random change amount anyway; avoid making the
-    // target needlessly large.
-    const CAmount srd_target = target_with_change + CHANGE_LOWER;
-    if (auto srd_result{SelectCoinsSRD(positive_groups, srd_target, coin_selection_params.rng_fast)}) {
-        srd_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+    if (auto srd_result{SelectCoinsSRD(positive_groups, nTargetValue, coin_selection_params.rng_fast)}) {
+        srd_result->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         results.push_back(*srd_result);
     }
 
@@ -603,7 +591,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         SelectionResult result(nTargetValue, SelectionAlgorithm::MANUAL);
         result.AddInput(preset_inputs);
         if (result.GetSelectedValue() < nTargetValue) return std::nullopt;
-        result.ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+        result.ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
         return result;
     }
 
@@ -628,12 +616,15 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         available_coins.Shuffle(coin_selection_params.rng_fast);
     }
 
+    SelectionResult preselected(preset_inputs.GetSelectionAmount(), SelectionAlgorithm::MANUAL);
+    preselected.AddInput(preset_inputs);
+
     // Coin Selection attempts to select inputs from a pool of eligible UTXOs to fund the
     // transaction at a target feerate. If an attempt fails, more attempts may be made using a more
     // permissive CoinEligibilityFilter.
     std::optional<SelectionResult> res = [&] {
         // Pre-selected inputs already cover the target amount.
-        if (value_to_select <= 0) return std::make_optional(SelectionResult(nTargetValue, SelectionAlgorithm::MANUAL));
+        if (value_to_select <= 0) return std::make_optional(SelectionResult(value_to_select, SelectionAlgorithm::MANUAL));
 
         // If possible, fund the transaction with confirmed UTXOs only. Prefer at least six
         // confirmations on outputs received from other wallets and only spend confirmed change.
@@ -687,9 +678,9 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
     if (!res) return std::nullopt;
 
     // Add preset inputs to result
-    res->AddInput(preset_inputs);
-    if (res->m_algo == SelectionAlgorithm::MANUAL) {
-        res->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+    res->Merge(preselected);
+    if (res->GetAlgo() == SelectionAlgorithm::MANUAL) {
+        res->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
     }
 
     return res;
@@ -803,7 +794,6 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
             coin_selection_params.m_subtract_fee_outputs = true;
         }
     }
-    coin_selection_params.m_min_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), rng_fast);
 
     // Create change script that will be used if we need change
     CScript scriptChange;
@@ -872,6 +862,15 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     coin_selection_params.m_change_fee = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
     coin_selection_params.m_cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_change_fee;
 
+    coin_selection_params.m_min_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), coin_selection_params.m_change_fee, rng_fast);
+
+    // The smallest change amount should be:
+    // 1. at least equal to dust threshold
+    // 2. at least 1 sat greater than fees to spend it at m_discard_feerate
+    const auto dust = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
+    const auto change_spend_fee = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size);
+    coin_selection_params.min_viable_change = std::max(change_spend_fee + 1, dust);
+
     // vouts to the payees
     if (!coin_selection_params.m_subtract_fee_outputs) {
         coin_selection_params.tx_noinputs_size = 10; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 witness overhead (dummy, flag, stack size)
@@ -910,25 +909,22 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     if (!result) {
         return util::Error{_("Insufficient funds")};
     }
-    TRACE5(coin_selection, selected_coins, wallet.GetName().c_str(), GetAlgorithmName(result->m_algo).c_str(), result->m_target, result->GetWaste(), result->GetSelectedValue());
-
-    // Always make a change output
-    // We will reduce the fee from this change output later, and remove the output if it is too small.
-    const CAmount change_and_fee = result->GetSelectedValue() - recipients_sum;
-    assert(change_and_fee >= 0);
-    CTxOut newTxOut(change_and_fee, scriptChange);
-
-    if (nChangePosInOut == -1) {
-        // Insert change txn at random position:
-        nChangePosInOut = rng_fast.randrange(txNew.vout.size() + 1);
-    }
-    else if ((unsigned int)nChangePosInOut > txNew.vout.size()) {
-        return util::Error{_("Transaction change output index out of range")};
+    TRACE5(coin_selection, selected_coins, wallet.GetName().c_str(), GetAlgorithmName(result->GetAlgo()).c_str(), result->GetTarget(), result->GetWaste(), result->GetSelectedValue());
+
+    const CAmount change_amount = result->GetChange(coin_selection_params.min_viable_change, coin_selection_params.m_change_fee);
+    if (change_amount > 0) {
+        CTxOut newTxOut(change_amount, scriptChange);
+        if (nChangePosInOut == -1) {
+            // Insert change txn at random position:
+            nChangePosInOut = rng_fast.randrange(txNew.vout.size() + 1);
+        } else if ((unsigned int)nChangePosInOut > txNew.vout.size()) {
+            return util::Error{_("Transaction change output index out of range")};
+        }
+        txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut);
+    } else {
+        nChangePosInOut = -1;
     }
 
-    assert(nChangePosInOut != -1);
-    auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut);
-
     // Shuffle selected coins and fill in final vin
     std::vector<COutput> selected_coins = result->GetShuffledInputVector();
 
@@ -952,42 +948,23 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     if (nBytes == -1) {
         return util::Error{_("Missing solving data for estimating transaction size")};
     }
-    nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
-
-    // Subtract fee from the change output if not subtracting it from recipient outputs
-    CAmount fee_needed = nFeeRet;
-    if (!coin_selection_params.m_subtract_fee_outputs) {
-        change_position->nValue -= fee_needed;
-    }
-
-    // We want to drop the change to fees if:
-    // 1. The change output would be dust
-    // 2. The change is within the (almost) exact match window, i.e. it is less than or equal to the cost of the change output (cost_of_change)
-    CAmount change_amount = change_position->nValue;
-    if (IsDust(*change_position, coin_selection_params.m_discard_feerate) || change_amount <= coin_selection_params.m_cost_of_change)
-    {
-        nChangePosInOut = -1;
-        change_amount = 0;
-        txNew.vout.erase(change_position);
-
-        // Because we have dropped this change, the tx size and required fee will be different, so let's recalculate those
-        tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), &wallet, &coin_control);
-        nBytes = tx_sizes.vsize;
-        fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
-    }
+    CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
+    nFeeRet = result->GetSelectedValue() - recipients_sum - change_amount;
 
-    // The only time that fee_needed should be less than the amount available for fees (in change_and_fee - change_amount) is when
+    // The only time that fee_needed should be less than the amount available for fees is when
     // we are subtracting the fee from the outputs. If this occurs at any other time, it is a bug.
-    assert(coin_selection_params.m_subtract_fee_outputs || fee_needed <= change_and_fee - change_amount);
+    assert(coin_selection_params.m_subtract_fee_outputs || fee_needed <= nFeeRet);
 
-    // Update nFeeRet in case fee_needed changed due to dropping the change output
-    if (fee_needed <= change_and_fee - change_amount) {
-        nFeeRet = change_and_fee - change_amount;
+    // If there is a change output and we overpay the fees then increase the change to match the fee needed
+    if (nChangePosInOut != -1 && fee_needed < nFeeRet) {
+        auto& change = txNew.vout.at(nChangePosInOut);
+        change.nValue += nFeeRet - fee_needed;
+        nFeeRet = fee_needed;
     }
 
     // Reduce output values for subtractFeeFromAmount
     if (coin_selection_params.m_subtract_fee_outputs) {
-        CAmount to_reduce = fee_needed + change_amount - change_and_fee;
+        CAmount to_reduce = fee_needed - nFeeRet;
         int i = 0;
         bool fFirst = true;
         for (const auto& recipient : vecSend)
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 4dfdc87a38..30a7fb9eb6 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -248,9 +248,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
 
     // Iteration exhaustion test
     CAmount target = make_hard_case(17, utxo_pool);
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0)); // Should exhaust
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 1)); // Should exhaust
     target = make_hard_case(14, utxo_pool);
-    const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 0); // Should not exhaust
+    const auto result7 = SelectCoinsBnB(GroupCoins(utxo_pool), target, 1); // Should not exhaust
     BOOST_CHECK(result7);
 
     // Test same value early bailout optimization
@@ -289,8 +289,8 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     // Make sure that effective value is working in AttemptSelection when BnB is used
     CoinSelectionParams coin_selection_params_bnb{
         rand,
-        /*change_output_size=*/ 0,
-        /*change_spend_size=*/ 0,
+        /*change_output_size=*/ 31,
+        /*change_spend_size=*/ 68,
         /*min_change_target=*/ 0,
         /*effective_feerate=*/ CFeeRate(3000),
         /*long_term_feerate=*/ CFeeRate(1000),
@@ -298,6 +298,9 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         /*tx_noinputs_size=*/ 0,
         /*avoid_partial=*/ false,
     };
+    coin_selection_params_bnb.m_change_fee = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_output_size);
+    coin_selection_params_bnb.m_cost_of_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size) + coin_selection_params_bnb.m_change_fee;
+    coin_selection_params_bnb.min_viable_change = coin_selection_params_bnb.m_effective_feerate.GetFee(coin_selection_params_bnb.change_spend_size);
     {
         std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
         wallet->LoadWallet();
@@ -777,6 +780,8 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
             /*tx_noinputs_size=*/ 0,
             /*avoid_partial=*/ false,
         };
+        cs_params.m_cost_of_change = 1;
+        cs_params.min_viable_change = 1;
         CCoinControl cc;
         const auto result = SelectCoins(*wallet, available_coins, target, cc, cs_params);
         BOOST_CHECK(result);
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
index 3465f2f331..90a328179e 100644
--- a/src/wallet/test/fuzz/coinselection.cpp
+++ b/src/wallet/test/fuzz/coinselection.cpp
@@ -58,6 +58,8 @@ FUZZ_TARGET(coinselection)
     coin_params.m_subtract_fee_outputs = subtract_fee_outputs;
     coin_params.m_long_term_feerate = long_term_fee_rate;
     coin_params.m_effective_feerate = effective_fee_rate;
+    coin_params.change_output_size = fuzzed_data_provider.ConsumeIntegralInRange<int>(10, 1000);
+    coin_params.m_change_fee = effective_fee_rate.GetFee(coin_params.change_output_size);
 
     // Create some coins
     CAmount total_balance{0};
@@ -83,11 +85,11 @@ FUZZ_TARGET(coinselection)
     const auto result_bnb = SelectCoinsBnB(group_pos, target, cost_of_change);
 
     auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context);
-    if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change);
+    if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
 
-    CAmount change_target{GenerateChangeTarget(target, fast_random_context)};
+    CAmount change_target{GenerateChangeTarget(target, coin_params.m_change_fee, fast_random_context)};
     auto result_knapsack = KnapsackSolver(group_all, target, change_target, fast_random_context);
-    if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change);
+    if (result_knapsack) result_knapsack->ComputeAndSetWaste(cost_of_change, cost_of_change, 0);
 
     // If the total balance is sufficient for the target and we are not using
     // effective values, Knapsack should always find a solution.