From c8cf08ea743e430c2bf3fe46439594257b0937e5 Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Mon, 15 Aug 2022 09:30:31 +0200
Subject: wallet: ensure m_min_change_target always covers change fee

---
 src/wallet/coinselection.cpp           | 6 +++---
 src/wallet/coinselection.h             | 4 +++-
 src/wallet/spend.cpp                   | 3 ++-
 src/wallet/test/fuzz/coinselection.cpp | 4 +++-
 4 files changed, 11 insertions(+), 6 deletions(-)

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 49e6bac462..37cc7e37c8 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -389,14 +389,14 @@ 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;
     }
 }
 
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index e257d3f7c7..191476779f 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -252,6 +252,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 +262,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
 {
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 61d86844df..9babb5e04e 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -794,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;
@@ -863,6 +862,8 @@ 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);
+
     // 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)
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
index 3465f2f331..52bd74126d 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};
@@ -85,7 +87,7 @@ FUZZ_TARGET(coinselection)
     auto result_srd = SelectCoinsSRD(group_pos, target, fast_random_context);
     if (result_srd) result_srd->ComputeAndSetWaste(cost_of_change);
 
-    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);
 
-- 
cgit v1.2.3


From 06f558e4e2164d1916f258c731efe4586728a23b Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 6 Jul 2022 08:51:22 +0200
Subject: wallet: accurate SelectionResult::m_target

SelectionResult::m_target should be equal to actual selection target.
Selection target is the sum of all recipient amounts plus non input fees.
So we need to remove change_fee from the m_target. It's safe because change
target is always greater than the change fee, so we can always cover fees
if change output is created.
---
 src/wallet/coinselection.cpp |  6 ++++++
 src/wallet/spend.cpp         | 20 ++++----------------
 2 files changed, 10 insertions(+), 16 deletions(-)

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 37cc7e37c8..0f2e57f9a1 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -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);
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 9babb5e04e..aed6dc89d2 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -489,31 +489,19 @@ 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)}) {
+    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.m_cost_of_change);
         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)}) {
+    if (auto srd_result{SelectCoinsSRD(positive_groups, nTargetValue, coin_selection_params.rng_fast)}) {
         srd_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
         results.push_back(*srd_result);
     }
-- 
cgit v1.2.3


From f8e796348b644c011ad9a8312356d4426c16cc4b Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 6 Jul 2022 09:18:17 +0200
Subject: wallet: add SelectionResult::Merge

---
 src/wallet/coinselection.cpp | 10 ++++++++++
 src/wallet/coinselection.h   | 15 ++++++++++-----
 src/wallet/spend.cpp         |  4 ++--
 3 files changed, 22 insertions(+), 7 deletions(-)

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 0f2e57f9a1..a61921f69f 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -433,6 +433,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;
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index 191476779f..fa24fec6e9 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -281,17 +281,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) {}
 
@@ -308,12 +307,18 @@ public:
     void ComputeAndSetWaste(CAmount change_cost);
     [[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;
+
+    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 aed6dc89d2..223377cf0e 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -667,7 +667,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
 
     // Add preset inputs to result
     res->AddInput(preset_inputs);
-    if (res->m_algo == SelectionAlgorithm::MANUAL) {
+    if (res->GetAlgo() == SelectionAlgorithm::MANUAL) {
         res->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
     }
 
@@ -890,7 +890,7 @@ 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());
+    TRACE5(coin_selection, selected_coins, wallet.GetName().c_str(), GetAlgorithmName(result->GetAlgo()).c_str(), result->GetTarget(), 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.
-- 
cgit v1.2.3


From e3210a722542a9cb5f7e4be72470dbe488c281fd Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 6 Jul 2022 08:15:20 +0200
Subject: wallet: account for preselected inputs in target

When we have preselected inputs the coin selection search target is reduced
by the sum of (effective) values. This causes incorrect m_target value.

Create separate instance of SelectionResult for all the preselected inputs and
set the target equal to the sum of (effective) values. Target for preselected
SelectionResult is equal to the delta for the search target. To get the final
SelectionResult with accurate m_target we merge both SelectionResult instances.
---
 src/wallet/spend.cpp | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 223377cf0e..cbb03dc177 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -607,12 +607,15 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
         Shuffle(available_coins.other.begin(), available_coins.other.end(), 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.
@@ -666,7 +669,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
     if (!res) return std::nullopt;
 
     // Add preset inputs to result
-    res->AddInput(preset_inputs);
+    res->Merge(preselected);
     if (res->GetAlgo() == SelectionAlgorithm::MANUAL) {
         res->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
     }
-- 
cgit v1.2.3


From 72cad28da05cfce9e4950f2dc5a709da41d251f4 Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 6 Jul 2022 09:00:57 +0200
Subject: wallet: calculate and store min_viable_change

---
 src/wallet/coinselection.h | 4 ++++
 src/wallet/spend.cpp       | 7 +++++++
 2 files changed, 11 insertions(+)

diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index fa24fec6e9..d1038a117a 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. */
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index cbb03dc177..d1fa3dbcb6 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -855,6 +855,13 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
 
     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)
-- 
cgit v1.2.3


From 15e97a6886902ebb378829993a972dc52558aa92 Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 6 Jul 2022 09:00:26 +0200
Subject: wallet: add SelectionResult::GetChange

---
 src/wallet/coinselection.cpp | 25 +++++++++++++++++++++++++
 src/wallet/coinselection.h   | 21 +++++++++++++++++++++
 2 files changed, 46 insertions(+)

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index a61921f69f..58d297724d 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -421,6 +421,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();
@@ -480,4 +485,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 d1038a117a..dd52241e2a 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -303,6 +303,8 @@ public:
     /** Get the sum of the input values */
     [[nodiscard]] CAmount GetSelectedValue() const;
 
+    [[nodiscard]] CAmount GetSelectedEffectiveValue() const;
+
     void Clear();
 
     void AddInput(const OutputGroup& group);
@@ -320,6 +322,25 @@ public:
 
     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; }
-- 
cgit v1.2.3


From 87e0ef903133492e76b7c7556209554d4a0c3d66 Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 13 Jul 2022 08:54:44 +0200
Subject: wallet: use GetChange() in tx building

---
 src/wallet/spend.cpp | 66 ++++++++++++++++++----------------------------------
 1 file changed, 22 insertions(+), 44 deletions(-)

diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index d1fa3dbcb6..f9429907cd 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -902,23 +902,20 @@ static util::Result<CreatedTransactionResult> CreateTransactionInternal(
     }
     TRACE5(coin_selection, selected_coins, wallet.GetName().c_str(), GetAlgorithmName(result->GetAlgo()).c_str(), result->GetTarget(), 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")};
+    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();
 
@@ -942,42 +939,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);
+    CAmount fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
+    nFeeRet = result->GetSelectedValue() - recipients_sum - change_amount;
 
-        // 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);
-    }
-
-    // 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)
-- 
cgit v1.2.3


From 4fef5344288e454460b80db0316294e1ec1ad8ad Mon Sep 17 00:00:00 2001
From: S3RK <1466284+S3RK@users.noreply.github.com>
Date: Wed, 6 Jul 2022 09:03:01 +0200
Subject: wallet: use GetChange() when computing waste

---
 src/wallet/coinselection.cpp           | 12 +++++++++---
 src/wallet/coinselection.h             |  2 +-
 src/wallet/spend.cpp                   |  8 ++++----
 src/wallet/test/coinselector_tests.cpp | 13 +++++++++----
 src/wallet/test/fuzz/coinselection.cpp |  4 ++--
 5 files changed, 25 insertions(+), 14 deletions(-)

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 58d297724d..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;
@@ -406,9 +406,15 @@ CAmount GenerateChangeTarget(const CAmount payment_value, const CAmount change_f
     }
 }
 
-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
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index dd52241e2a..761c2be0b3 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -310,7 +310,7 @@ public:
     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);
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index f9429907cd..718c499e7b 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -497,12 +497,12 @@ std::optional<SelectionResult> ChooseSelectionResult(const CWallet& wallet, cons
     // 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, /*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.m_cost_of_change);
+        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);
     }
 
     if (auto srd_result{SelectCoinsSRD(positive_groups, nTargetValue, coin_selection_params.rng_fast)}) {
-        srd_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+        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);
     }
 
@@ -574,7 +574,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;
     }
 
@@ -671,7 +671,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
     // Add preset inputs to result
     res->Merge(preselected);
     if (res->GetAlgo() == SelectionAlgorithm::MANUAL) {
-        res->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
+        res->ComputeAndSetWaste(coin_selection_params.min_viable_change, coin_selection_params.m_cost_of_change, coin_selection_params.m_change_fee);
     }
 
     return res;
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index a4a7216436..3c21dae712 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 52bd74126d..90a328179e 100644
--- a/src/wallet/test/fuzz/coinselection.cpp
+++ b/src/wallet/test/fuzz/coinselection.cpp
@@ -85,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, 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.
-- 
cgit v1.2.3