Merge bitcoin/bitcoin#17331: Use effective values throughout coin selection

51a3ac242c92e69b59df26f8f9e287b31e5c3b0f Have OutputGroup determine the value to use (Andrew Chow)
6d6d2784759878ef0c4ac128d12aac68add1edca Change SelectCoins_test to actually test SelectCoins (Andrew Chow)
9d3bd74ab4430532d6e53eef8cf77ad999044b14 Remove CreateTransaction while loop and some related variables (Andrew Chow)
6f0d5189af4c881fe8b97a0c28ce1ffa33480715 Remove use_bnb and bnb_used (Andrew Chow)
de26eb0e1fa2b6f03c58ba104d00f7a8ffead39c Do both BnB and Knapsack coin selection in SelectCoinsMinConf (Andrew Chow)
01dc8ebda50a382d45d3d169b2c3f3965869dcae Have KnapsackSolver actually use effective values (Andrew Chow)
bf26e018de33216d6f0ed0d6ff822b93536f7cc1 Roll static tx fees into nValueToSelect instead of having it be separate (Andrew Chow)
cc3f14b27c06b7a0da1472f5c7100c3f0b76fd98 Move output reductions for fee to after coin selection (Andrew Chow)
d97d25d95006725e705635530b27643363d6b2a4 Make cost_of_change part of CoinSelectionParams (Andrew Chow)
af5867c89688b06173b295b7c32a42845ea455da Move some calculations to common code in SelectCoinsMinConf (Andrew Chow)
1bf4a62cb61bd4b91d9cd4e379fea2b914786342 scripted-diff: rename some variables (Andrew Chow)

Pull request description:

  Changes `KnapsackSolver` to use effective values instead of just the nominal txout value. Since fees are taken into account during the selection itself, we finally get rid of the `CreateTransaction` loop as well as a few other things that only were only necessary because of that loop.

  This should not change coin selection behavior at all (except maybe remove weird edge cases that were caused by the loop). In order to keep behavior the same, `KnapsackSolver` will select outputs with a negative effective value (as it did before).

ACKs for top commit:
  ryanofsky:
    Code review ACK 51a3ac242c92e69b59df26f8f9e287b31e5c3b0f. Looks good to go!
  instagibbs:
    review ACK https://github.com/bitcoin/bitcoin/pull/17331/commits/51a3ac242c92e69b59df26f8f9e287b31e5c3b0f
  meshcollider:
    re-light-utACK 51a3ac242c92e69b59df26f8f9e287b31e5c3b0f

Tree-SHA512: 372c27e00edcd5dbf85177421ba88f20bfdaf1791b6e3dc022c44876ecc379403e2375ed69e71c512c49e6af87641001ff385c4b25ab93684b3a08a53bf3824e

6 files changed, 309 insertions, 380 deletions

diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
index 80acdec044..c279a9af2f 100644
--- a/src/bench/coin_selection.cpp
+++ b/src/bench/coin_selection.cpp
@@ -49,15 +49,14 @@ static void CoinSelection(benchmark::Bench& bench)
     }
 
     const CoinEligibilityFilter filter_standard(1, 6, 0);
-    const CoinSelectionParams coin_selection_params(/* use_bnb= */ true, /* change_output_size= */ 34,
+    const CoinSelectionParams coin_selection_params(/* change_output_size= */ 34,
                                                     /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
                                                     /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
                                                     /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
     bench.run([&] {
         std::set<CInputCoin> setCoinsRet;
         CAmount nValueRet;
-        bool bnb_used;
-        bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params, bnb_used);
+        bool success = wallet.SelectCoinsMinConf(1003 * COIN, filter_standard, coins, setCoinsRet, nValueRet, coin_selection_params);
         assert(success);
         assert(nValueRet == 1003 * COIN);
         assert(setCoinsRet.size() == 2);
@@ -101,12 +100,11 @@ static void BnBExhaustion(benchmark::Bench& bench)
     std::vector<OutputGroup> utxo_pool;
     CoinSet selection;
     CAmount value_ret = 0;
-    CAmount not_input_fees = 0;
 
     bench.run([&] {
         // Benchmark
         CAmount target = make_hard_case(17, utxo_pool);
-        SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret, not_input_fees); // Should exhaust
+        SelectCoinsBnB(utxo_pool, target, 0, selection, value_ret); // Should exhaust
 
         // Cleanup
         utxo_pool.clear();
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 5a18308a73..6d502e1df1 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -14,7 +14,7 @@
 struct {
     bool operator()(const OutputGroup& a, const OutputGroup& b) const
     {
-        return a.effective_value > b.effective_value;
+        return a.GetSelectionAmount() > b.GetSelectionAmount();
     }
 } descending;
 
@@ -49,37 +49,34 @@ struct {
  * @param const std::vector<CInputCoin>& utxo_pool The set of UTXOs that we are choosing from.
  *        These UTXOs will be sorted in descending order by effective value and the CInputCoins'
  *        values are their effective values.
- * @param const CAmount& target_value This is the value that we want to select. It is the lower
+ * @param const CAmount& selection_target This is the value that we want to select. It is the lower
  *        bound of the range.
  * @param const CAmount& cost_of_change This is the cost of creating and spending a change output.
- *        This plus target_value is the upper bound of the range.
+ *        This plus selection_target is the upper bound of the range.
  * @param std::set<CInputCoin>& out_set -> This is an output parameter for the set of CInputCoins
  *        that have been selected.
  * @param CAmount& value_ret -> This is an output parameter for the total value of the CInputCoins
  *        that were selected.
- * @param CAmount not_input_fees -> The fees that need to be paid for the outputs and fixed size
- *        overhead (version, locktime, marker and flag)
  */
 
 static const size_t TOTAL_TRIES = 100000;
 
-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
+bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret)
 {
     out_set.clear();
     CAmount curr_value = 0;
 
     std::vector<bool> curr_selection; // select the utxo at this index
     curr_selection.reserve(utxo_pool.size());
-    CAmount actual_target = not_input_fees + target_value;
 
     // Calculate curr_available_value
     CAmount curr_available_value = 0;
     for (const OutputGroup& utxo : utxo_pool) {
         // Assert that this utxo is not negative. It should never be negative, effective value calculation should have removed it
-        assert(utxo.effective_value > 0);
-        curr_available_value += utxo.effective_value;
+        assert(utxo.GetSelectionAmount() > 0);
+        curr_available_value += utxo.GetSelectionAmount();
     }
-    if (curr_available_value < actual_target) {
+    if (curr_available_value < selection_target) {
         return false;
     }
 
@@ -94,12 +91,12 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_v
     for (size_t i = 0; i < TOTAL_TRIES; ++i) {
         // Conditions for starting a backtrack
         bool backtrack = false;
-        if (curr_value + curr_available_value < actual_target ||                // Cannot possibly reach target with the amount remaining in the curr_available_value.
-            curr_value > actual_target + cost_of_change ||    // Selected value is out of range, go back and try other branch
+        if (curr_value + curr_available_value < selection_target ||                // Cannot possibly reach target with the amount remaining in the curr_available_value.
+            curr_value > selection_target + cost_of_change ||    // Selected value is out of range, go back and try other branch
             (curr_waste > best_waste && (utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0)) { // Don't select things which we know will be more wasteful if the waste is increasing
             backtrack = true;
-        } else if (curr_value >= actual_target) {       // Selected value is within range
-            curr_waste += (curr_value - actual_target); // This is the excess value which is added to the waste for the below comparison
+        } else if (curr_value >= selection_target) {       // Selected value is within range
+            curr_waste += (curr_value - selection_target); // This is the excess value which is added to the waste for the below comparison
             // Adding another UTXO after this check could bring the waste down if the long term fee is higher than the current fee.
             // However we are not going to explore that because this optimization for the waste is only done when we have hit our target
             // value. Adding any more UTXOs will be just burning the UTXO; it will go entirely to fees. Thus we aren't going to
@@ -112,7 +109,7 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_v
                     break;
                 }
             }
-            curr_waste -= (curr_value - actual_target); // Remove the excess value as we will be selecting different coins now
+            curr_waste -= (curr_value - selection_target); // Remove the excess value as we will be selecting different coins now
             backtrack = true;
         }
 
@@ -121,7 +118,7 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_v
             // Walk backwards to find the last included UTXO that still needs to have its omission branch traversed.
             while (!curr_selection.empty() && !curr_selection.back()) {
                 curr_selection.pop_back();
-                curr_available_value += utxo_pool.at(curr_selection.size()).effective_value;
+                curr_available_value += utxo_pool.at(curr_selection.size()).GetSelectionAmount();
             }
 
             if (curr_selection.empty()) { // We have walked back to the first utxo and no branch is untraversed. All solutions searched
@@ -131,24 +128,24 @@ bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_v
             // Output was included on previous iterations, try excluding now.
             curr_selection.back() = false;
             OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
-            curr_value -= utxo.effective_value;
+            curr_value -= utxo.GetSelectionAmount();
             curr_waste -= utxo.fee - utxo.long_term_fee;
         } else { // Moving forwards, continuing down this branch
             OutputGroup& utxo = utxo_pool.at(curr_selection.size());
 
             // Remove this utxo from the curr_available_value utxo amount
-            curr_available_value -= utxo.effective_value;
+            curr_available_value -= utxo.GetSelectionAmount();
 
             // Avoid searching a branch if the previous UTXO has the same value and same waste and was excluded. Since the ratio of fee to
             // long term fee is the same, we only need to check if one of those values match in order to know that the waste is the same.
             if (!curr_selection.empty() && !curr_selection.back() &&
-                utxo.effective_value == utxo_pool.at(curr_selection.size() - 1).effective_value &&
+                utxo.GetSelectionAmount() == utxo_pool.at(curr_selection.size() - 1).GetSelectionAmount() &&
                 utxo.fee == utxo_pool.at(curr_selection.size() - 1).fee) {
                 curr_selection.push_back(false);
             } else {
                 // Inclusion branch first (Largest First Exploration)
                 curr_selection.push_back(true);
-                curr_value += utxo.effective_value;
+                curr_value += utxo.GetSelectionAmount();
                 curr_waste += utxo.fee - utxo.long_term_fee;
             }
         }
@@ -230,14 +227,14 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
     Shuffle(groups.begin(), groups.end(), FastRandomContext());
 
     for (const OutputGroup& group : groups) {
-        if (group.m_value == nTargetValue) {
+        if (group.GetSelectionAmount() == nTargetValue) {
             util::insert(setCoinsRet, group.m_outputs);
             nValueRet += group.m_value;
             return true;
-        } else if (group.m_value < nTargetValue + MIN_CHANGE) {
+        } else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) {
             applicable_groups.push_back(group);
-            nTotalLower += group.m_value;
-        } else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
+            nTotalLower += group.GetSelectionAmount();
+        } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
             lowest_larger = group;
         }
     }
@@ -270,7 +267,7 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& group
     // If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
     //                                   or the next bigger coin is closer), return the bigger coin
     if (lowest_larger &&
-        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) {
+        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->GetSelectionAmount() <= nBest)) {
         util::insert(setCoinsRet, lowest_larger->m_outputs);
         nValueRet += lowest_larger->m_value;
     } else {
@@ -339,3 +336,8 @@ bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_f
         && m_ancestors <= eligibility_filter.max_ancestors
         && m_descendants <= eligibility_filter.max_descendants;
 }
+
+CAmount OutputGroup::GetSelectionAmount() const
+{
+    return m_subtract_fee_outputs ? m_value : effective_value;
+}
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index 5645e6db46..7a3fb82139 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -57,6 +57,47 @@ public:
     }
 };
 
+/** Parameters for one iteration of Coin Selection. */
+struct CoinSelectionParams
+{
+    /** Size of a change output in bytes, determined by the output type. */
+    size_t change_output_size = 0;
+    /** Size of the input to spend a change output in virtual bytes. */
+    size_t change_spend_size = 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. */
+    CAmount m_cost_of_change{0};
+    /** The targeted feerate of the transaction being built. */
+    CFeeRate m_effective_feerate;
+    /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend
+     * the change output sometime in the future. */
+    CFeeRate m_long_term_feerate;
+    /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
+    CFeeRate m_discard_feerate;
+    /** Size of the transaction before coin selection, consisting of the header and recipient
+     * output(s), excluding the inputs and change output(s). */
+    size_t tx_noinputs_size = 0;
+    /** Indicate that we are subtracting the fee from outputs */
+    bool m_subtract_fee_outputs = false;
+    /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs
+     * associated with the same address. This helps reduce privacy leaks resulting from address
+     * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
+    bool m_avoid_partial_spends = false;
+
+    CoinSelectionParams(size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate,
+                        CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) :
+        change_output_size(change_output_size),
+        change_spend_size(change_spend_size),
+        m_effective_feerate(effective_feerate),
+        m_long_term_feerate(long_term_feerate),
+        m_discard_feerate(discard_feerate),
+        tx_noinputs_size(tx_noinputs_size),
+        m_avoid_partial_spends(avoid_partial)
+    {}
+    CoinSelectionParams() {}
+};
+
 /** Parameters for filtering which OutputGroups we may use in coin selection.
  * We start by being very selective and requiring multiple confirmations and
  * then get more permissive if we cannot fund the transaction. */
@@ -109,18 +150,23 @@ struct OutputGroup
      * a lower feerate). Calculated using long term fee estimate. This is used to decide whether
      * it could be economical to create a change output. */
     CFeeRate m_long_term_feerate{0};
+    /** Indicate that we are subtracting the fee from outputs.
+     * When true, the value that is used for coin selection is the UTXO's real value rather than effective value */
+    bool m_subtract_fee_outputs{false};
 
     OutputGroup() {}
-    OutputGroup(const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate) :
-        m_effective_feerate(effective_feerate),
-        m_long_term_feerate(long_term_feerate)
+    OutputGroup(const CoinSelectionParams& params) :
+        m_effective_feerate(params.m_effective_feerate),
+        m_long_term_feerate(params.m_long_term_feerate),
+        m_subtract_fee_outputs(params.m_subtract_fee_outputs)
     {}
 
     void Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants, bool positive_only);
     bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
+    CAmount GetSelectionAmount() const;
 };
 
-bool SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees);
+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
 bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet);
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 7bca385deb..14c3578473 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -35,7 +35,7 @@ static CAmount balance = 0;
 CoinEligibilityFilter filter_standard(1, 6, 0);
 CoinEligibilityFilter filter_confirmed(1, 1, 0);
 CoinEligibilityFilter filter_standard_extra(6, 6, 0);
-CoinSelectionParams coin_selection_params(/* use_bnb= */ false, /* change_output_size= */ 0,
+CoinSelectionParams coin_selection_params(/* change_output_size= */ 0,
                                           /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(0),
                                           /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
                                           /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
@@ -148,14 +148,13 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     CoinSet selection;
     CoinSet actual_selection;
     CAmount value_ret = 0;
-    CAmount not_input_fees = 0;
 
     /////////////////////////
     // Known Outcome tests //
     /////////////////////////
 
     // Empty utxo pool
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret));
     selection.clear();
 
     // Add utxos
@@ -166,7 +165,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
 
     // Select 1 Cent
     add_coin(1 * CENT, 1, actual_selection);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 0.5 * CENT, selection, value_ret));
     BOOST_CHECK(equal_sets(selection, actual_selection));
     BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
     actual_selection.clear();
@@ -174,7 +173,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
 
     // Select 2 Cent
     add_coin(2 * CENT, 2, actual_selection);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 2 * CENT, 0.5 * CENT, selection, value_ret));
     BOOST_CHECK(equal_sets(selection, actual_selection));
     BOOST_CHECK_EQUAL(value_ret, 2 * CENT);
     actual_selection.clear();
@@ -183,27 +182,27 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     // Select 5 Cent
     add_coin(4 * CENT, 4, actual_selection);
     add_coin(1 * CENT, 1, actual_selection);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 5 * CENT, 0.5 * CENT, selection, value_ret));
     BOOST_CHECK(equal_sets(selection, actual_selection));
     BOOST_CHECK_EQUAL(value_ret, 5 * CENT);
     actual_selection.clear();
     selection.clear();
 
     // Select 11 Cent, not possible
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 11 * CENT, 0.5 * CENT, selection, value_ret));
     actual_selection.clear();
     selection.clear();
 
     // Cost of change is greater than the difference between target value and utxo sum
     add_coin(1 * CENT, 1, actual_selection);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0.5 * CENT, selection, value_ret));
     BOOST_CHECK_EQUAL(value_ret, 1 * CENT);
     BOOST_CHECK(equal_sets(selection, actual_selection));
     actual_selection.clear();
     selection.clear();
 
     // Cost of change is less than the difference between target value and utxo sum
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0, selection, value_ret, not_input_fees));
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.9 * CENT, 0, selection, value_ret));
     actual_selection.clear();
     selection.clear();
 
@@ -212,7 +211,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     add_coin(5 * CENT, 5, actual_selection);
     add_coin(4 * CENT, 4, actual_selection);
     add_coin(1 * CENT, 1, actual_selection);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 0.5 * CENT, selection, value_ret));
     BOOST_CHECK(equal_sets(selection, actual_selection));
     BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
     actual_selection.clear();
@@ -223,21 +222,21 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     add_coin(5 * CENT, 5, actual_selection);
     add_coin(3 * CENT, 3, actual_selection);
     add_coin(2 * CENT, 2, actual_selection);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 10 * CENT, 5000, selection, value_ret));
     BOOST_CHECK_EQUAL(value_ret, 10 * CENT);
     // FIXME: this test is redundant with the above, because 1 Cent is selected, not "too small"
     // BOOST_CHECK(equal_sets(selection, actual_selection));
 
     // Select 0.25 Cent, not possible
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT, selection, value_ret, not_input_fees));
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 0.25 * CENT, 0.5 * CENT, selection, value_ret));
     actual_selection.clear();
     selection.clear();
 
     // Iteration exhaustion test
     CAmount target = make_hard_case(17, utxo_pool);
-    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees)); // Should exhaust
+    BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret)); // Should exhaust
     target = make_hard_case(14, utxo_pool);
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret, not_input_fees)); // Should not exhaust
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), target, 0, selection, value_ret)); // Should not exhaust
 
     // Test same value early bailout optimization
     utxo_pool.clear();
@@ -254,7 +253,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     for (int i = 0; i < 50000; ++i) {
         add_coin(5 * CENT, 7, utxo_pool);
     }
-    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret, not_input_fees));
+    BOOST_CHECK(SelectCoinsBnB(GroupCoins(utxo_pool), 30 * CENT, 5000, selection, value_ret));
     BOOST_CHECK_EQUAL(value_ret, 30 * CENT);
     BOOST_CHECK(equal_sets(selection, actual_selection));
 
@@ -268,29 +267,27 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
     }
     // Run 100 times, to make sure it is never finding a solution
     for (int i = 0; i < 100; ++i) {
-        BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret, not_input_fees));
+        BOOST_CHECK(!SelectCoinsBnB(GroupCoins(utxo_pool), 1 * CENT, 2 * CENT, selection, value_ret));
     }
 
     // Make sure that effective value is working in SelectCoinsMinConf when BnB is used
-    CoinSelectionParams coin_selection_params_bnb(/* use_bnb= */ true, /* change_output_size= */ 0,
+    CoinSelectionParams coin_selection_params_bnb(/* change_output_size= */ 0,
                                                   /* change_spend_size= */ 0, /* effective_feerate= */ CFeeRate(3000),
                                                   /* long_term_feerate= */ CFeeRate(1000), /* discard_feerate= */ CFeeRate(1000),
                                                   /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
     CoinSet setCoinsRet;
     CAmount nValueRet;
-    bool bnb_used;
     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.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used));
+    BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb));
 
     // Test fees subtracted from output:
     empty_wallet();
     add_coin(1 * CENT);
     vCoins.at(0).nInputBytes = 40;
-    BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used));
     coin_selection_params_bnb.m_subtract_fee_outputs = true;
-    BOOST_CHECK(testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb, bnb_used));
+    BOOST_CHECK(testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params_bnb));
     BOOST_CHECK_EQUAL(nValueRet, 1 * CENT);
 
     // Make sure that can use BnB when there are preset inputs
@@ -307,9 +304,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         coin_control.fAllowOtherInputs = true;
         coin_control.Select(COutPoint(vCoins.at(0).tx->GetHash(), vCoins.at(0).i));
         coin_selection_params_bnb.m_effective_feerate = CFeeRate(0);
-        BOOST_CHECK(wallet->SelectCoins(vCoins, 10 * CENT, setCoinsRet, nValueRet, coin_control, coin_selection_params_bnb, bnb_used));
-        BOOST_CHECK(bnb_used);
-        BOOST_CHECK(coin_selection_params_bnb.use_bnb);
+        BOOST_CHECK(wallet->SelectCoins(vCoins, 10 * CENT, setCoinsRet, nValueRet, coin_control, coin_selection_params_bnb));
     }
 }
 
@@ -317,7 +312,6 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
 {
     CoinSet setCoinsRet, setCoinsRet2;
     CAmount nValueRet;
-    bool bnb_used;
 
     LOCK(testWallet.cs_wallet);
     testWallet.SetupLegacyScriptPubKeyMan();
@@ -328,24 +322,24 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         empty_wallet();
 
         // with an empty wallet we can't even pay one cent
-        BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
 
         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.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(!testWallet.SelectCoinsMinConf( 1 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
 
         // but we can find a new 1 cent
-        BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf( 1 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf( 3 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(!testWallet.SelectCoinsMinConf( 3 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
 
         // we can make 3 cents of new coins
-        BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf( 3 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 3 * CENT);
 
         add_coin(5*CENT);           // add a mature 5 cent coin,
@@ -355,33 +349,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.SelectCoinsMinConf(38 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         // we can't even make 37 cents if we don't allow new coins even if they're from us
-        BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(!testWallet.SelectCoinsMinConf(38 * CENT, filter_standard_extra, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         // but we can make 37 cents if we accept new coins from ourself
-        BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(37 * CENT, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 37 * CENT);
         // and we can make 38 cents if we accept all new coins
-        BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(38 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf(34 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(34 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf( 7 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf( 7 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf( 8 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf( 8 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf( 9 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf( 9 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 10 * CENT);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
@@ -395,30 +389,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.SelectCoinsMinConf(71 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
-        BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(71 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
+        BOOST_CHECK(!testWallet.SelectCoinsMinConf(72 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
 
         // 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.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(16 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf(11 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(11 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 11 * CENT);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
 
@@ -427,11 +421,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.SelectCoinsMinConf(95 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(95 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 1 * COIN);  // we should get 1 BTC in 1 coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
-        BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(195 * CENT, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 2 * COIN);  // we should get 2 BTC in 1 coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
@@ -446,14 +440,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.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
 
         // if we add more small coins:
@@ -461,7 +455,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.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 1 * MIN_CHANGE); // we should get the exact amount
 
         // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
@@ -470,7 +464,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         for (int j = 0; j < 20; j++)
             add_coin(50000 * COIN);
 
-        BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(500000 * COIN, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 500000 * COIN); // we should get the exact amount
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 10U); // in ten coins
 
@@ -483,7 +477,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.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(1 * MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 1111 * MIN_CHANGE); // we get the bigger coin
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 1U);
 
@@ -493,7 +487,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.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK( testWallet.SelectCoinsMinConf(MIN_CHANGE, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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
 
@@ -504,12 +498,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.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 10001 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         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.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+        BOOST_CHECK(testWallet.SelectCoinsMinConf(MIN_CHANGE * 9990 / 100, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
         BOOST_CHECK_EQUAL(nValueRet, 101 * MIN_CHANGE);
         BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
       }
@@ -523,7 +517,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.SelectCoinsMinConf(2000, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+             BOOST_CHECK(testWallet.SelectCoinsMinConf(2000, filter_confirmed, vCoins, setCoinsRet, nValueRet, coin_selection_params));
 
              if (amt - 2000 < MIN_CHANGE) {
                  // needs more than one input:
@@ -549,17 +543,19 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
           for (int i = 0; i < RUN_TESTS; i++) {
             // picking 50 from 100 coins doesn't depend on the shuffle,
             // but does depend on randomness in the stochastic approximation code
-            BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
-            BOOST_CHECK(testWallet.SelectCoinsMinConf(50 * COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
+            BOOST_CHECK(KnapsackSolver(50 * COIN, GroupCoins(vCoins), setCoinsRet, nValueRet));
+            BOOST_CHECK(KnapsackSolver(50 * COIN, GroupCoins(vCoins), setCoinsRet2, nValueRet));
             BOOST_CHECK(!equal_sets(setCoinsRet, setCoinsRet2));
 
             int fails = 0;
             for (int j = 0; j < RANDOM_REPEATS; j++)
             {
-                // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
-                // run the test RANDOM_REPEATS times and only complain if all of them fail
-                BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
-                BOOST_CHECK(testWallet.SelectCoinsMinConf(COIN, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
+                // Test that the KnapsackSolver selects randomly from equivalent coins (same value and same input size).
+                // When choosing 1 from 100 identical coins, 1% of the time, this test will choose the same coin twice
+                // which will cause it to fail.
+                // To avoid that issue, run the test RANDOM_REPEATS times and only complain if all of them fail
+                BOOST_CHECK(KnapsackSolver(COIN, GroupCoins(vCoins), setCoinsRet, nValueRet));
+                BOOST_CHECK(KnapsackSolver(COIN, GroupCoins(vCoins), setCoinsRet2, nValueRet));
                 if (equal_sets(setCoinsRet, setCoinsRet2))
                     fails++;
             }
@@ -579,10 +575,8 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
             int fails = 0;
             for (int j = 0; j < RANDOM_REPEATS; j++)
             {
-                // selecting 1 from 100 identical coins depends on the shuffle; this test will fail 1% of the time
-                // run the test RANDOM_REPEATS times and only complain if all of them fail
-                BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet , nValueRet, coin_selection_params, bnb_used));
-                BOOST_CHECK(testWallet.SelectCoinsMinConf(90*CENT, filter_standard, vCoins, setCoinsRet2, nValueRet, coin_selection_params, bnb_used));
+                BOOST_CHECK(KnapsackSolver(90*CENT, GroupCoins(vCoins), setCoinsRet, nValueRet));
+                BOOST_CHECK(KnapsackSolver(90*CENT, GroupCoins(vCoins), setCoinsRet2, nValueRet));
                 if (equal_sets(setCoinsRet, setCoinsRet2))
                     fails++;
             }
@@ -597,7 +591,6 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
 {
     CoinSet setCoinsRet;
     CAmount nValueRet;
-    bool bnb_used;
 
     LOCK(testWallet.cs_wallet);
     testWallet.SetupLegacyScriptPubKeyMan();
@@ -609,7 +602,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
         add_coin(1000 * COIN);
     add_coin(3 * COIN);
 
-    BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used));
+    BOOST_CHECK(testWallet.SelectCoinsMinConf(1003 * COIN, filter_standard, vCoins, setCoinsRet, nValueRet, coin_selection_params));
     BOOST_CHECK_EQUAL(nValueRet, 1003 * COIN);
     BOOST_CHECK_EQUAL(setCoinsRet.size(), 2U);
 
@@ -619,6 +612,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
 // Tests that with the ideal conditions, the coin selector will always be able to find a solution that can pay the target value
 BOOST_AUTO_TEST_CASE(SelectCoins_test)
 {
+    LOCK(testWallet.cs_wallet);
     testWallet.SetupLegacyScriptPubKeyMan();
 
     // Random generator stuff
@@ -644,19 +638,14 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
         CAmount target = rand.randrange(balance - 1000) + 1000;
 
         // Perform selection
-        CoinSelectionParams coin_selection_params_knapsack(/* use_bnb= */ false, /* change_output_size= */ 34,
-                                                           /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
-                                                           /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
-                                                           /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
-        CoinSelectionParams coin_selection_params_bnb(/* use_bnb= */ true, /* change_output_size= */ 34,
-                                                      /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
-                                                      /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
-                                                      /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
+        CoinSelectionParams cs_params(/* change_output_size= */ 34,
+                                      /* change_spend_size= */ 148, /* effective_feerate= */ CFeeRate(0),
+                                      /* long_term_feerate= */ CFeeRate(0), /* discard_feerate= */ CFeeRate(0),
+                                      /* tx_no_inputs_size= */ 0, /* avoid_partial= */ false);
         CoinSet out_set;
         CAmount out_value = 0;
-        bool bnb_used = false;
-        BOOST_CHECK(testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_bnb, bnb_used) ||
-                    testWallet.SelectCoinsMinConf(target, filter_standard, vCoins, out_set, out_value, coin_selection_params_knapsack, bnb_used));
+        CCoinControl cc;
+        BOOST_CHECK(testWallet.SelectCoins(vCoins, target, out_set, out_value, cc, cs_params));
         BOOST_CHECK_GE(out_value, target);
     }
 }
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 7cdf2fcda0..e603ce7d0b 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -2396,44 +2396,28 @@ const CTxOut& CWallet::FindNonChangeParentOutput(const CTransaction& tx, int out
 }
 
 bool CWallet::SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
-                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const
+                                 std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params) const
 {
     setCoinsRet.clear();
     nValueRet = 0;
 
-    if (coin_selection_params.use_bnb) {
-        // Get the feerate for effective value.
-        // When subtracting the fee from the outputs, we want the effective feerate to be 0
-        CFeeRate effective_feerate{0};
-        if (!coin_selection_params.m_subtract_fee_outputs) {
-            effective_feerate = coin_selection_params.m_effective_feerate;
-        }
-
-        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, effective_feerate, coin_selection_params.m_long_term_feerate, eligibility_filter, true /* positive_only */);
-
-        // Calculate cost of change
-        CAmount cost_of_change = coin_selection_params.m_discard_feerate.GetFee(coin_selection_params.change_spend_size) + coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.change_output_size);
-
-        // Calculate the fees for things that aren't inputs
-        CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
-        bnb_used = true;
-        return SelectCoinsBnB(groups, nTargetValue, cost_of_change, setCoinsRet, nValueRet, not_input_fees);
-    } else {
-        std::vector<OutputGroup> groups = GroupOutputs(coins, !coin_selection_params.m_avoid_partial_spends, CFeeRate(0), CFeeRate(0), eligibility_filter, false /* positive_only */);
-
-        bnb_used = false;
-        return KnapsackSolver(nTargetValue, groups, setCoinsRet, nValueRet);
+    // 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;
     }
+    // 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);
 }
 
-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, bool& bnb_used) const
+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
 {
     std::vector<COutput> vCoins(vAvailableCoins);
     CAmount value_to_select = nTargetValue;
 
-    // Default to bnb was not used. If we use it, we set it later
-    bnb_used = false;
-
     // coin control -> return all selected outputs (we want all selected to go into the transaction for sure)
     if (coin_control.HasSelected() && !coin_control.fAllowOtherInputs)
     {
@@ -2470,10 +2454,10 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
                 return false; // Not solvable, can't estimate size for fee
             }
             coin.effective_value = coin.txout.nValue - coin_selection_params.m_effective_feerate.GetFee(coin.m_input_bytes);
-            if (coin_selection_params.use_bnb) {
-                value_to_select -= coin.effective_value;
-            } else {
+            if (coin_selection_params.m_subtract_fee_outputs) {
                 value_to_select -= coin.txout.nValue;
+            } else {
+                value_to_select -= coin.effective_value;
             }
             setPresetCoins.insert(coin);
         } else {
@@ -2515,26 +2499,26 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
 
         // 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.
-        if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true;
-        if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true;
+        if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 6, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
+        if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(1, 1, 0), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
 
         // Fall back to using zero confirmation change (but with as few ancestors in the mempool as
         // possible) if we cannot fund the transaction otherwise.
         if (m_spend_zero_conf_change) {
-            if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) return true;
+            if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, 2), vCoins, setCoinsRet, nValueRet, coin_selection_params)) return true;
             if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
-                                   vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) {
+                                   vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
                 return true;
             }
             if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
-                                   vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) {
+                                   vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
                 return true;
             }
             // If partial groups are allowed, relax the requirement of spending OutputGroups (groups
             // of UTXOs sent to the same address, which are obviously controlled by a single wallet)
             // in their entirety.
             if (SelectCoinsMinConf(value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
-                                   vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) {
+                                   vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
                 return true;
             }
             // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
@@ -2542,7 +2526,7 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
             if (coin_control.m_include_unsafe_inputs
                 && SelectCoinsMinConf(value_to_select,
                     CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
-                    vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) {
+                    vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
                 return true;
             }
             // Try with unlimited ancestors/descendants. The transaction will still need to meet
@@ -2550,7 +2534,7 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
             // OutputGroups use heuristics that may overestimate ancestor/descendant counts.
             if (!fRejectLongChains && SelectCoinsMinConf(value_to_select,
                                       CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */),
-                                      vCoins, setCoinsRet, nValueRet, coin_selection_params, bnb_used)) {
+                                      vCoins, setCoinsRet, nValueRet, coin_selection_params)) {
                 return true;
             }
         }
@@ -2815,7 +2799,6 @@ bool CWallet::CreateTransactionInternal(
     CAmount nValue = 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);
-    int nChangePosRequest = nChangePosInOut;
     unsigned int nSubtractFeeFromAmount = 0;
     for (const auto& recipient : vecSend)
     {
@@ -2837,7 +2820,6 @@ bool CWallet::CreateTransactionInternal(
 
     CMutableTransaction txNew;
     FeeCalculation feeCalc;
-    CAmount nFeeNeeded;
     std::pair<int64_t, int64_t> tx_sizes;
     int nBytes;
     {
@@ -2881,6 +2863,16 @@ bool CWallet::CreateTransactionInternal(
             CTxOut change_prototype_txout(0, scriptChange);
             coin_selection_params.change_output_size = GetSerializeSize(change_prototype_txout);
 
+            // Get size of spending the change output
+            int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
+            // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
+            // as lower-bound to allow BnB to do it's thing
+            if (change_spend_size == -1) {
+                coin_selection_params.change_spend_size = DUMMY_NESTED_P2WPKH_INPUT_SIZE;
+            } else {
+                coin_selection_params.change_spend_size = (size_t)change_spend_size;
+            }
+
             // Set discard feerate
             coin_selection_params.m_discard_feerate = GetDiscardRate(*this);
 
@@ -2903,205 +2895,147 @@ bool CWallet::CreateTransactionInternal(
             cc_temp.m_confirm_target = chain().estimateMaxBlocks();
             coin_selection_params.m_long_term_feerate = GetMinimumFeeRate(*this, cc_temp, nullptr);
 
-            nFeeRet = 0;
-            bool pick_new_inputs = true;
-            CAmount nValueIn = 0;
+            // 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.
+            // For spending the change output in the future, we use the discard feerate for now.
+            // So cost of change = (change output size * effective feerate) + (size of spending change output * discard feerate)
+            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;
 
-            // BnB selector is the only selector used when this is true.
-            // That should only happen on the first pass through the loop.
-            coin_selection_params.use_bnb = true;
             coin_selection_params.m_subtract_fee_outputs = nSubtractFeeFromAmount != 0; // If we are doing subtract fee from recipient, don't use effective values
-            // Start with no fee and loop until there is enough fee
-            while (true)
-            {
-                nChangePosInOut = nChangePosRequest;
-                txNew.vin.clear();
-                txNew.vout.clear();
-                bool fFirst = true;
 
-                CAmount nValueToSelect = nValue;
-                if (nSubtractFeeFromAmount == 0)
-                    nValueToSelect += nFeeRet;
+            // vouts to the payees
+            if (!coin_selection_params.m_subtract_fee_outputs) {
+                coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size)
+            }
+            for (const auto& recipient : vecSend)
+            {
+                CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
 
-                // vouts to the payees
+                // Include the fee cost for outputs.
                 if (!coin_selection_params.m_subtract_fee_outputs) {
-                    coin_selection_params.tx_noinputs_size = 11; // Static vsize overhead + outputs vsize. 4 nVersion, 4 nLocktime, 1 input count, 1 output count, 1 witness overhead (dummy, flag, stack size)
+                    coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION);
                 }
-                for (const auto& recipient : vecSend)
+
+                if (IsDust(txout, chain().relayDustFee()))
                 {
-                    CTxOut txout(recipient.nAmount, recipient.scriptPubKey);
+                    error = _("Transaction amount too small");
+                    return false;
+                }
+                txNew.vout.push_back(txout);
+            }
 
-                    if (recipient.fSubtractFeeFromAmount)
-                    {
-                        assert(nSubtractFeeFromAmount != 0);
-                        txout.nValue -= nFeeRet / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient
+            // Include the fees for things that aren't inputs, excluding the change output
+            const CAmount not_input_fees = coin_selection_params.m_effective_feerate.GetFee(coin_selection_params.tx_noinputs_size);
+            CAmount nValueToSelect = nValue + not_input_fees;
 
-                        if (fFirst) // first receiver pays the remainder not divisible by output count
-                        {
-                            fFirst = false;
-                            txout.nValue -= nFeeRet % nSubtractFeeFromAmount;
-                        }
-                    }
-                    // Include the fee cost for outputs. Note this is only used for BnB right now
-                    if (!coin_selection_params.m_subtract_fee_outputs) {
-                        coin_selection_params.tx_noinputs_size += ::GetSerializeSize(txout, PROTOCOL_VERSION);
-                    }
+            // Choose coins to use
+            CAmount inputs_sum = 0;
+            setCoins.clear();
+            if (!SelectCoins(vAvailableCoins, /* nTargetValue */ nValueToSelect, setCoins, inputs_sum, coin_control, coin_selection_params))
+            {
+                error = _("Insufficient funds");
+                return false;
+            }
 
-                    if (IsDust(txout, chain().relayDustFee()))
-                    {
-                        if (recipient.fSubtractFeeFromAmount && nFeeRet > 0)
-                        {
-                            if (txout.nValue < 0)
-                                error = _("The transaction amount is too small to pay the fee");
-                            else
-                                error = _("The transaction amount is too small to send after the fee has been deducted");
-                        }
-                        else
-                            error = _("Transaction amount too small");
-                        return false;
-                    }
-                    txNew.vout.push_back(txout);
-                }
+            // 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 = inputs_sum - nValue;
+            assert(change_and_fee >= 0);
+            CTxOut newTxOut(change_and_fee, scriptChange);
 
-                // Choose coins to use
-                bool bnb_used = false;
-                if (pick_new_inputs) {
-                    nValueIn = 0;
-                    setCoins.clear();
-                    int change_spend_size = CalculateMaximumSignedInputSize(change_prototype_txout, this);
-                    // If the wallet doesn't know how to sign change output, assume p2sh-p2wpkh
-                    // as lower-bound to allow BnB to do it's thing
-                    if (change_spend_size == -1) {
-                        coin_selection_params.change_spend_size = DUMMY_NESTED_P2WPKH_INPUT_SIZE;
-                    } else {
-                        coin_selection_params.change_spend_size = (size_t)change_spend_size;
-                    }
-                    if (!SelectCoins(vAvailableCoins, nValueToSelect, setCoins, nValueIn, coin_control, coin_selection_params, bnb_used))
-                    {
-                        // If BnB was used, it was the first pass. No longer the first pass and continue loop with knapsack.
-                        if (bnb_used) {
-                            coin_selection_params.use_bnb = false;
-                            continue;
-                        }
-                        else {
-                            error = _("Insufficient funds");
-                            return false;
-                        }
-                    }
-                } else {
-                    bnb_used = false;
-                }
+            if (nChangePosInOut == -1)
+            {
+                // Insert change txn at random position:
+                nChangePosInOut = GetRandInt(txNew.vout.size()+1);
+            }
+            else if ((unsigned int)nChangePosInOut > txNew.vout.size())
+            {
+                error = _("Change index out of range");
+                return false;
+            }
 
-                const CAmount nChange = nValueIn - nValueToSelect;
-                if (nChange > 0)
-                {
-                    // Fill a vout to ourself
-                    CTxOut newTxOut(nChange, scriptChange);
+            assert(nChangePosInOut != -1);
+            auto change_position = txNew.vout.insert(txNew.vout.begin() + nChangePosInOut, newTxOut);
 
-                    // Never create dust outputs; if we would, just
-                    // add the dust to the fee.
-                    // The nChange when BnB is used is always going to go to fees.
-                    if (IsDust(newTxOut, coin_selection_params.m_discard_feerate) || bnb_used)
-                    {
-                        nChangePosInOut = -1;
-                        nFeeRet += nChange;
-                    }
-                    else
-                    {
-                        if (nChangePosInOut == -1)
-                        {
-                            // Insert change txn at random position:
-                            nChangePosInOut = GetRandInt(txNew.vout.size()+1);
-                        }
-                        else if ((unsigned int)nChangePosInOut > txNew.vout.size())
-                        {
-                            error = _("Change index out of range");
-                            return false;
-                        }
+            // Dummy fill vin for maximum size estimation
+            //
+            for (const auto& coin : setCoins) {
+                txNew.vin.push_back(CTxIn(coin.outpoint,CScript()));
+            }
 
-                        std::vector<CTxOut>::iterator position = txNew.vout.begin()+nChangePosInOut;
-                        txNew.vout.insert(position, newTxOut);
-                    }
-                } else {
-                    nChangePosInOut = -1;
-                }
+            // Calculate the transaction fee
+            tx_sizes = CalculateMaximumSignedTxSize(CTransaction(txNew), this, coin_control.fAllowWatchOnly);
+            nBytes = tx_sizes.first;
+            if (nBytes < 0) {
+                error = _("Signing transaction failed");
+                return false;
+            }
+            nFeeRet = coin_selection_params.m_effective_feerate.GetFee(nBytes);
 
-                // Dummy fill vin for maximum size estimation
-                //
-                for (const auto& coin : setCoins) {
-                    txNew.vin.push_back(CTxIn(coin.outpoint,CScript()));
-                }
+            // Subtract fee from the change output if not subtrating it from recipient outputs
+            CAmount fee_needed = nFeeRet;
+            if (nSubtractFeeFromAmount == 0) {
+                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), this, coin_control.fAllowWatchOnly);
                 nBytes = tx_sizes.first;
-                if (nBytes < 0) {
-                    error = _("Signing transaction failed");
-                    return false;
-                }
+                fee_needed = coin_selection_params.m_effective_feerate.GetFee(nBytes);
+            }
 
-                nFeeNeeded = coin_selection_params.m_effective_feerate.GetFee(nBytes);
-                if (nFeeRet >= nFeeNeeded) {
-                    // Reduce fee to only the needed amount if possible. This
-                    // prevents potential overpayment in fees if the coins
-                    // selected to meet nFeeNeeded result in a transaction that
-                    // requires less fee than the prior iteration.
-
-                    // If we have no change and a big enough excess fee, then
-                    // try to construct transaction again only without picking
-                    // new inputs. We now know we only need the smaller fee
-                    // (because of reduced tx size) and so we should add a
-                    // change output. Only try this once.
-                    if (nChangePosInOut == -1 && nSubtractFeeFromAmount == 0 && pick_new_inputs) {
-                        unsigned int tx_size_with_change = nBytes + coin_selection_params.change_output_size + 2; // Add 2 as a buffer in case increasing # of outputs changes compact size
-                        CAmount fee_needed_with_change = coin_selection_params.m_effective_feerate.GetFee(tx_size_with_change);
-                        CAmount minimum_value_for_change = GetDustThreshold(change_prototype_txout, coin_selection_params.m_discard_feerate);
-                        if (nFeeRet >= fee_needed_with_change + minimum_value_for_change) {
-                            pick_new_inputs = false;
-                            nFeeRet = fee_needed_with_change;
-                            continue;
-                        }
-                    }
+            // 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 we have change output already, just increase it
-                    if (nFeeRet > nFeeNeeded && nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) {
-                        CAmount extraFeePaid = nFeeRet - nFeeNeeded;
-                        std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
-                        change_position->nValue += extraFeePaid;
-                        nFeeRet -= extraFeePaid;
+            // Reduce output values for subtractFeeFromAmount
+            if (nSubtractFeeFromAmount != 0) {
+                CAmount to_reduce = fee_needed + change_amount - change_and_fee;
+                int i = 0;
+                bool fFirst = true;
+                for (const auto& recipient : vecSend)
+                {
+                    if (i == nChangePosInOut) {
+                        ++i;
                     }
-                    break; // Done, enough fee included.
-                }
-                else if (!pick_new_inputs) {
-                    // This shouldn't happen, we should have had enough excess
-                    // fee to pay for the new output and still meet nFeeNeeded
-                    // Or we should have just subtracted fee from recipients and
-                    // nFeeNeeded should not have changed
-                    error = _("Transaction fee and change calculation failed");
-                    return false;
-                }
+                    CTxOut& txout = txNew.vout[i];
 
-                // Try to reduce change to include necessary fee
-                if (nChangePosInOut != -1 && nSubtractFeeFromAmount == 0) {
-                    CAmount additionalFeeNeeded = nFeeNeeded - nFeeRet;
-                    std::vector<CTxOut>::iterator change_position = txNew.vout.begin()+nChangePosInOut;
-                    // Only reduce change if remaining amount is still a large enough output.
-                    if (change_position->nValue >= MIN_FINAL_CHANGE + additionalFeeNeeded) {
-                        change_position->nValue -= additionalFeeNeeded;
-                        nFeeRet += additionalFeeNeeded;
-                        break; // Done, able to increase fee from change
-                    }
-                }
+                    if (recipient.fSubtractFeeFromAmount)
+                    {
+                        txout.nValue -= to_reduce / nSubtractFeeFromAmount; // Subtract fee equally from each selected recipient
 
-                // If subtracting fee from recipients, we now know what fee we
-                // need to subtract, we have no reason to reselect inputs
-                if (nSubtractFeeFromAmount > 0) {
-                    pick_new_inputs = false;
-                }
+                        if (fFirst) // first receiver pays the remainder not divisible by output count
+                        {
+                            fFirst = false;
+                            txout.nValue -= to_reduce % nSubtractFeeFromAmount;
+                        }
 
-                // Include more fee and try again.
-                nFeeRet = nFeeNeeded;
-                coin_selection_params.use_bnb = false;
-                continue;
+                        // Error if this output is reduced to be below dust
+                        if (IsDust(txout, chain().relayDustFee())) {
+                            if (txout.nValue < 0) {
+                                error = _("The transaction amount is too small to pay the fee");
+                            } else {
+                                error = _("The transaction amount is too small to send after the fee has been deducted");
+                            }
+                            return false;
+                        }
+                    }
+                    ++i;
+                }
+                nFeeRet = fee_needed;
             }
 
             // Give up if change keypool ran out and change is required
@@ -3163,8 +3097,8 @@ bool CWallet::CreateTransactionInternal(
     reservedest.KeepDestination();
     fee_calc_out = feeCalc;
 
-    WalletLogPrintf("Fee Calculation: Fee:%d Bytes:%u Needed:%d Tgt:%d (requested %d) Reason:\"%s\" Decay %.5f: Estimation: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
-              nFeeRet, nBytes, nFeeNeeded, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,
+    WalletLogPrintf("Fee Calculation: Fee:%d Bytes:%u Tgt:%d (requested %d) Reason:\"%s\" Decay %.5f: Estimation: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out) Fail: (%g - %g) %.2f%% %.1f/(%.1f %d mem %.1f out)\n",
+              nFeeRet, nBytes, feeCalc.returnedTarget, feeCalc.desiredTarget, StringForFeeReason(feeCalc.reason), feeCalc.est.decay,
               feeCalc.est.pass.start, feeCalc.est.pass.end,
               (feeCalc.est.pass.totalConfirmed + feeCalc.est.pass.inMempool + feeCalc.est.pass.leftMempool) > 0.0 ? 100 * feeCalc.est.pass.withinTarget / (feeCalc.est.pass.totalConfirmed + feeCalc.est.pass.inMempool + feeCalc.est.pass.leftMempool) : 0.0,
               feeCalc.est.pass.withinTarget, feeCalc.est.pass.totalConfirmed, feeCalc.est.pass.inMempool, feeCalc.est.pass.leftMempool,
@@ -4298,12 +4232,12 @@ bool CWalletTx::IsImmatureCoinBase() const
     return GetBlocksToMaturity() > 0;
 }
 
-std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, bool separate_coins, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const
+std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only) const
 {
     std::vector<OutputGroup> groups_out;
 
-    if (separate_coins) {
-        // Single coin means no grouping. Each COutput gets its own OutputGroup.
+    if (!coin_sel_params.m_avoid_partial_spends) {
+        // Allowing partial spends  means no grouping. Each COutput gets its own OutputGroup.
         for (const COutput& output : outputs) {
             // Skip outputs we cannot spend
             if (!output.fSpendable) continue;
@@ -4313,11 +4247,11 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
             CInputCoin input_coin = output.GetInputCoin();
 
             // Make an OutputGroup containing just this output
-            OutputGroup group{effective_feerate, long_term_feerate};
+            OutputGroup group{coin_sel_params};
             group.Insert(input_coin, output.nDepth, output.tx->IsFromMe(ISMINE_ALL), ancestors, descendants, positive_only);
 
             // Check the OutputGroup's eligibility. Only add the eligible ones.
-            if (positive_only && group.effective_value <= 0) continue;
+            if (positive_only && group.GetSelectionAmount() <= 0) continue;
             if (group.m_outputs.size() > 0 && group.EligibleForSpending(filter)) groups_out.push_back(group);
         }
         return groups_out;
@@ -4343,7 +4277,7 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
 
         if (groups.size() == 0) {
             // No OutputGroups for this scriptPubKey yet, add one
-            groups.emplace_back(effective_feerate, long_term_feerate);
+            groups.emplace_back(coin_sel_params);
         }
 
         // Get the last OutputGroup in the vector so that we can add the CInputCoin to it
@@ -4354,7 +4288,7 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
         // to avoid surprising users with very high fees.
         if (group->m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) {
             // The last output group is full, add a new group to the vector and use that group for the insertion
-            groups.emplace_back(effective_feerate, long_term_feerate);
+            groups.emplace_back(coin_sel_params);
             group = &groups.back();
         }
 
@@ -4376,7 +4310,7 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
             }
 
             // Check the OutputGroup's eligibility. Only add the eligible ones.
-            if (positive_only && group.effective_value <= 0) continue;
+            if (positive_only && group.GetSelectionAmount() <= 0) continue;
             if (group.m_outputs.size() > 0 && group.EligibleForSpending(filter)) groups_out.push_back(group);
         }
     }
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index fc4edd8d20..5f48e77590 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -612,46 +612,6 @@ public:
     }
 };
 
-/** Parameters for one iteration of Coin Selection. */
-struct CoinSelectionParams
-{
-    /** Toggles use of Branch and Bound instead of Knapsack solver. */
-    bool use_bnb = true;
-    /** Size of a change output in bytes, determined by the output type. */
-    size_t change_output_size = 0;
-    /** Size of the input to spend a change output in virtual bytes. */
-    size_t change_spend_size = 0;
-    /** The targeted feerate of the transaction being built. */
-    CFeeRate m_effective_feerate;
-    /** The feerate estimate used to estimate an upper bound on what should be sufficient to spend
-     * the change output sometime in the future. */
-    CFeeRate m_long_term_feerate;
-    /** If the cost to spend a change output at the discard feerate exceeds its value, drop it to fees. */
-    CFeeRate m_discard_feerate;
-    /** Size of the transaction before coin selection, consisting of the header and recipient
-     * output(s), excluding the inputs and change output(s). */
-    size_t tx_noinputs_size = 0;
-    /** Indicate that we are subtracting the fee from outputs */
-    bool m_subtract_fee_outputs = false;
-    /** When true, always spend all (up to OUTPUT_GROUP_MAX_ENTRIES) or none of the outputs
-     * associated with the same address. This helps reduce privacy leaks resulting from address
-     * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
-    bool m_avoid_partial_spends = false;
-
-    CoinSelectionParams(bool use_bnb, size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate,
-                        CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial) :
-        use_bnb(use_bnb),
-        change_output_size(change_output_size),
-        change_spend_size(change_spend_size),
-        m_effective_feerate(effective_feerate),
-        m_long_term_feerate(long_term_feerate),
-        m_discard_feerate(discard_feerate),
-        tx_noinputs_size(tx_noinputs_size),
-        m_avoid_partial_spends(avoid_partial)
-    {}
-    CoinSelectionParams() {}
-};
-
 class WalletRescanReserver; //forward declarations for ScanForWalletTransactions/RescanFromTime
 /**
  * A CWallet maintains a set of transactions and balances, and provides the ability to create new transactions.
@@ -792,7 +752,7 @@ public:
      *                                  from coin_control and Coin Selection if successful.
      */
     bool SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAmount& nTargetValue, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet,
-                    const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params, bool& bnb_used) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
+                    const CCoinControl& coin_control, CoinSelectionParams& coin_selection_params) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 
     /** Get a name for this wallet for logging/debugging purposes.
      */
@@ -881,7 +841,7 @@ public:
      * param@[out]  nValueRet       Used to return the total value of selected coins.
      */
     bool SelectCoinsMinConf(const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, std::vector<COutput> coins,
-        std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params, bool& bnb_used) const;
+        std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet, const CoinSelectionParams& coin_selection_params) const;
 
     bool IsSpent(const uint256& hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 
@@ -889,7 +849,7 @@ public:
     bool IsSpentKey(const uint256& hash, unsigned int n) const EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
     void SetSpentKeyState(WalletBatch& batch, const uint256& hash, unsigned int n, bool used, std::set<CTxDestination>& tx_destinations) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);
 
-    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, bool separate_coins, const CFeeRate& effective_feerate, const CFeeRate& long_term_feerate, const CoinEligibilityFilter& filter, bool positive_only) const;
+    std::vector<OutputGroup> GroupOutputs(const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only) const;
 
     /** Display address on an external signer. Returns false if external signer support is not compiled */
     bool DisplayAddress(const CTxDestination& dest) EXCLUSIVE_LOCKS_REQUIRED(cs_wallet);