Repository: bitcoin/bitcoin (language: cpp)

Issue:
wallet: Rethinking MIN_CHANGE
MIN_CHANGE is a privacy leak, since it is an easily observable wallet behaviour. Any output almost equal, but minimally larger than MIN_CHANGE is highly likely the change output of a tx.

Also, MIN_CHANGE is quite high, considering the value of bitcoin.

An easy fix for the second issue would be to just lower the value, but maybe some randomization can be done to also fix the first issue?


Discussion / hints:
I think the solution we came up with (@Xekyo @achow101 lmk if wrong) is to get rid of MIN_CHANGE and, instead, pick the change target for each selection as a random value between 50ksat and 500ksat, also limited by payment value?
> limited by payment value?

I think limited by *double* the payment value? Otherwise it might be easier to apply the https://en.bitcoin.it/wiki/Privacy#Unnecessary_input_heuristic ?
Yes, double the payment value was what we decided.
> MIN_CHANGE is a privacy leak, since it is an easily observable wallet behaviour. Any output almost equal, but minimally larger than MIN_CHANGE is highly likely the change output of a tx.
> 
> Also, MIN_CHANGE is quite high, considering the value of bitcoin.
> 
> An easy fix for the second issue would be to just lower the value, but maybe some randomization can be done to also fix the first issue?

Will making it run time variable fix this? https://github.com/bitcoin/bitcoin/pull/6669#discussion_r41622295

It will be configurable similar to long term fee rate added in https://github.com/bitcoin/bitcoin/pull/22009 
> Will making it run time variable fix this? https://github.com/bitcoin/bitcoin/pull/6669#discussion_r41622295

No, because most users don't change the default arguments. If there is one user changing it to another constant, it will actually be a more unique fingerprint, making it worse.
Working on this now

Fix patch:
diff --git a/doc/release-notes-24494.md b/doc/release-notes-24494.md
new file mode 100644
index 0000000000000..afbb9264336ee
--- /dev/null
+++ b/doc/release-notes-24494.md
@@ -0,0 +1,2 @@
+To help prevent fingerprinting transactions created by the Bitcoin Core wallet, change output
+amounts are now randomized. (#24494)
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
index 16a8948f99267..18a780646f816 100644
--- a/src/bench/coin_selection.cpp
+++ b/src/bench/coin_selection.cpp
@@ -13,6 +13,7 @@
 
 using node::NodeContext;
 using wallet::AttemptSelection;
+using wallet::CHANGE_LOWER;
 using wallet::COutput;
 using wallet::CWallet;
 using wallet::CWalletTx;
@@ -66,6 +67,7 @@ static void CoinSelection(benchmark::Bench& bench)
         rand,
         /* change_output_size= */ 34,
         /* change_spend_size= */ 148,
+        /*min_change_target=*/ CHANGE_LOWER,
         /* effective_feerate= */ CFeeRate(0),
         /* long_term_feerate= */ CFeeRate(0),
         /* discard_feerate= */ CFeeRate(0),
diff --git a/src/qt/coincontroldialog.cpp b/src/qt/coincontroldialog.cpp
index d7a2aaaf19aca..1f66cb4d19c0a 100644
--- a/src/qt/coincontroldialog.cpp
+++ b/src/qt/coincontroldialog.cpp
@@ -32,7 +32,6 @@
 #include <QTreeWidget>
 
 using wallet::CCoinControl;
-using wallet::MIN_CHANGE;
 
 QList<CAmount> CoinControlDialog::payAmounts;
 bool CoinControlDialog::fSubtractFeeFromAmount = false;
@@ -485,11 +484,10 @@ void CoinControlDialog::updateLabels(CCoinControl& m_coin_control, WalletModel *
             if (!CoinControlDialog::fSubtractFeeFromAmount)
                 nChange -= nPayFee;
 
-            // Never create dust outputs; if we would, just add the dust to the fee.
-            if (nChange > 0 && nChange < MIN_CHANGE)
-            {
+            if (nChange > 0) {
                 // Assumes a p2pkh script size
                 CTxOut txout(nChange, CScript() << std::vector<unsigned char>(24, 0));
+                // Never create dust outputs; if we would, just add the dust to the fee.
                 if (IsDust(txout, model->node().getDustRelayFee()))
                 {
                     nPayFee += nChange;
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 38c5939232374..433759e086f11 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -187,11 +187,24 @@ std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& ut
     return std::nullopt;
 }
 
-static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
+/** Find a subset of the OutputGroups that is at least as large as, but as close as possible to, the
+ * target amount; solve subset sum.
+ * param@[in]   groups          OutputGroups to choose from, sorted by value in descending order.
+ * param@[in]   nTotalLower     Total (effective) value of the UTXOs in groups.
+ * param@[in]   nTargetValue    Subset sum target, not including change.
+ * param@[out]  vfBest          Boolean vector representing the subset chosen that is closest to
+ *                              nTargetValue, with indices corresponding to groups. If the ith
+ *                              entry is true, that means the ith group in groups was selected.
+ * param@[out]  nBest           Total amount of subset chosen that is closest to nTargetValue.
+ * param@[in]   iterations      Maximum number of tries.
+ */
+static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::vector<OutputGroup>& groups,
+                                  const CAmount& nTotalLower, const CAmount& nTargetValue,
                                   std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
 {
     std::vector<char> vfIncluded;
 
+    // Worst case "best" approximation is just all of the groups.
     vfBest.assign(groups.size(), true);
     nBest = nTotalLower;
 
@@ -217,6 +230,8 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v
                     if (nTotal >= nTargetValue)
                     {
                         fReachedTarget = true;
+                        // If the total is between nTargetValue and nBest, it's our new best
+                        // approximation.
                         if (nTotal < nBest)
                         {
                             nBest = nTotal;
@@ -231,12 +246,15 @@ static void ApproximateBestSubset(FastRandomContext& insecure_rand, const std::v
     }
 }
 
-std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, FastRandomContext& rng)
+std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
+                                              CAmount change_target, FastRandomContext& rng)
 {
     SelectionResult result(nTargetValue);
 
     // List of values less than target
     std::optional<OutputGroup> lowest_larger;
+    // Groups with selection amount smaller than the target and any change we might produce.
+    // Don't include groups larger than this, because they will only cause us to overshoot.
     std::vector<OutputGroup> applicable_groups;
     CAmount nTotalLower = 0;
 
@@ -246,7 +264,7 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,
         if (group.GetSelectionAmount() == nTargetValue) {
             result.AddInput(group);
             return result;
-        } else if (group.GetSelectionAmount() < nTargetValue + MIN_CHANGE) {
+        } else if (group.GetSelectionAmount() < nTargetValue + change_target) {
             applicable_groups.push_back(group);
             nTotalLower += group.GetSelectionAmount();
         } else if (!lowest_larger || group.GetSelectionAmount() < lowest_larger->GetSelectionAmount()) {
@@ -273,14 +291,14 @@ std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups,
     CAmount nBest;
 
     ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
-    if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
-        ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
+    if (nBest != nTargetValue && nTotalLower >= nTargetValue + change_target) {
+        ApproximateBestSubset(rng, applicable_groups, nTotalLower, nTargetValue + change_target, vfBest, nBest);
     }
 
     // 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->GetSelectionAmount() <= nBest)) {
+        ((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
         result.AddInput(*lowest_larger);
     } else {
         for (unsigned int i = 0; i < applicable_groups.size(); i++) {
@@ -380,6 +398,17 @@ CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost,
     return waste;
 }
 
+CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng)
+{
+    if (payment_value <= CHANGE_LOWER / 2) {
+        return 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;
+    }
+}
+
 void SelectionResult::ComputeAndSetWaste(CAmount change_cost)
 {
     m_waste = GetSelectionWaste(m_selected_inputs, change_cost, m_target, m_use_effective);
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index 504d57aa78597..2e20efa8c1521 100644
--- a/src/wallet/coinselection.h
+++ b/src/wallet/coinselection.h
@@ -13,10 +13,10 @@
 #include <optional>
 
 namespace wallet {
-//! target minimum change amount
-static constexpr CAmount MIN_CHANGE{COIN / 100};
-//! final minimum change amount after paying for fees
-static const CAmount MIN_FINAL_CHANGE = MIN_CHANGE/2;
+//! lower bound for randomly-chosen target change amount
+static constexpr CAmount CHANGE_LOWER{50000};
+//! upper bound for randomly-chosen target change amount
+static constexpr CAmount CHANGE_UPPER{1000000};
 
 /** A UTXO under consideration for use in funding a new transaction. */
 class COutput
@@ -94,8 +94,13 @@ struct CoinSelectionParams {
     size_t change_output_size = 0;
     /** Size of the input to spend a change output in virtual bytes. */
     size_t change_spend_size = 0;
+    /** 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};
     /** Cost of creating the change output. */
     CAmount m_change_fee{0};
+    /** The pre-determined minimum value to target when funding a change output. */
+    CAmount m_change_target{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. */
@@ -115,11 +120,13 @@ struct CoinSelectionParams {
      * reuse. Dust outputs are not eligible to be added to output groups and thus not considered. */
     bool m_avoid_partial_spends = false;
 
-    CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size, CFeeRate effective_feerate,
+    CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size,
+                        CAmount min_change_target, CFeeRate effective_feerate,
                         CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
         : rng_fast{rng_fast},
           change_output_size(change_output_size),
           change_spend_size(change_spend_size),
+          m_min_change_target(min_change_target),
           m_effective_feerate(effective_feerate),
           m_long_term_feerate(long_term_feerate),
           m_discard_feerate(discard_feerate),
@@ -218,6 +225,21 @@ struct OutputGroup
  */
 [[nodiscard]] CAmount GetSelectionWaste(const std::set<COutput>& inputs, CAmount change_cost, CAmount target, bool use_effective_value = true);
 
+
+/** Chooose 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.
+ * The random value is between 50ksat and min(2 * payment_value, 1milsat)
+ * When payment_value <= 25ksat, the value is just 50ksat.
+ *
+ * Making change amounts similar to the payment value may help disguise which output(s) are payments
+ * are which ones are change. Using double the payment value may increase the number of inputs
+ * needed (and thus be more expensive in fees), but breaks analysis techniques which assume the
+ * 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).
+ */
+[[nodiscard]] CAmount GenerateChangeTarget(CAmount payment_value, FastRandomContext& rng);
+
 struct SelectionResult
 {
 private:
@@ -267,7 +289,8 @@ std::optional<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_poo
 std::optional<SelectionResult> SelectCoinsSRD(const std::vector<OutputGroup>& utxo_pool, CAmount target_value, FastRandomContext& rng);
 
 // Original coin selection algorithm as a fallback
-std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue, FastRandomContext& rng);
+std::optional<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, const CAmount& nTargetValue,
+                                              CAmount change_target, FastRandomContext& rng);
 } // namespace wallet
 
 #endif // BITCOIN_WALLET_COINSELECTION_H
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 304a9f10ca229..b2839f2afedaf 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -19,6 +19,8 @@
 #include <wallet/transaction.h>
 #include <wallet/wallet.h>
 
+#include <cmath>
+
 using interfaces::FoundBlock;
 
 namespace wallet {
@@ -389,14 +391,17 @@ std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAm
     std::vector<OutputGroup> all_groups = GroupOutputs(wallet, 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.
-    if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue + coin_selection_params.m_change_fee, coin_selection_params.rng_fast)}) {
+    if (auto knapsack_result{KnapsackSolver(all_groups, nTargetValue + coin_selection_params.m_change_fee,
+                                            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);
     }
 
-    // We include the minimum final change for SRD as we do want to avoid making really small change.
-    // KnapsackSolver does not need this because it includes MIN_CHANGE internally.
-    const CAmount srd_target = nTargetValue + coin_selection_params.m_change_fee + MIN_FINAL_CHANGE;
+    // 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 = nTargetValue + coin_selection_params.m_change_fee + CHANGE_LOWER;
     if (auto srd_result{SelectCoinsSRD(positive_groups, srd_target, coin_selection_params.rng_fast)}) {
         srd_result->ComputeAndSetWaste(coin_selection_params.m_cost_of_change);
         results.push_back(*srd_result);
@@ -680,6 +685,7 @@ static bool CreateTransactionInternal(
             coin_selection_params.m_subtract_fee_outputs = true;
         }
     }
+    coin_selection_params.m_change_target = GenerateChangeTarget(std::floor(recipients_sum / vecSend.size()), rng_fast);
 
     // Create change script that will be used if we need change
     CScript scriptChange;


Test patch:
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
index 14bec8ca4c042..87ce18c8c92ed 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -150,6 +150,7 @@ inline std::vector<OutputGroup>& KnapsackGroupOutputs(const std::vector<COutput>
         rand,
         /* change_output_size= */ 0,
         /* change_spend_size= */ 0,
+        /*min_change_target=*/ CENT,
         /* effective_feerate= */ CFeeRate(0),
         /* long_term_feerate= */ CFeeRate(0),
         /* discard_feerate= */ CFeeRate(0),
@@ -294,6 +295,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
         rand,
         /* change_output_size= */ 0,
         /* change_spend_size= */ 0,
+        /*min_change_target=*/ 0,
         /* effective_feerate= */ CFeeRate(3000),
         /* long_term_feerate= */ CFeeRate(1000),
         /* discard_feerate= */ CFeeRate(1000),
@@ -347,7 +349,7 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
 BOOST_AUTO_TEST_CASE(knapsack_solver_test)
 {
     FastRandomContext rand{};
-    const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v) { return KnapsackSolver(g, v, rand); }};
+    const auto temp1{[&rand](std::vector<OutputGroup>& g, const CAmount& v, CAmount c) { return KnapsackSolver(g, v, c, rand); }};
     const auto KnapsackSolver{temp1};
     std::unique_ptr<CWallet> wallet = std::make_unique<CWallet>(m_node.chain.get(), "", m_args, CreateMockWalletDatabase());
     wallet->LoadWallet();
@@ -363,25 +365,25 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         coins.clear();
 
         // with an empty wallet we can't even pay one cent
-        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT));
+        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT, CENT));
 
         add_coin(coins, *wallet, 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(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT));
+        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1 * CENT, CENT));
 
         // but we can find a new 1 cent
-        const auto result1 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT);
+        const auto result1 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
         BOOST_CHECK(result1);
         BOOST_CHECK_EQUAL(result1->GetSelectedValue(), 1 * CENT);
 
         add_coin(coins, *wallet, 2*CENT);           // add a mature 2 cent coin
 
         // we can't make 3 cents of mature coins
-        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 3 * CENT));
+        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 3 * CENT, CENT));
 
         // we can make 3 cents of new coins
-        const auto result2 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 3 * CENT);
+        const auto result2 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 3 * CENT, CENT);
         BOOST_CHECK(result2);
         BOOST_CHECK_EQUAL(result2->GetSelectedValue(), 3 * CENT);
 
@@ -392,38 +394,38 @@ 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(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 38 * CENT));
+        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 38 * CENT, CENT));
         // we can't even make 37 cents if we don't allow new coins even if they're from us
-        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard_extra), 38 * CENT));
+        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard_extra), 38 * CENT, CENT));
         // but we can make 37 cents if we accept new coins from ourself
-        const auto result3 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 37 * CENT);
+        const auto result3 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 37 * CENT, CENT);
         BOOST_CHECK(result3);
         BOOST_CHECK_EQUAL(result3->GetSelectedValue(), 37 * CENT);
         // and we can make 38 cents if we accept all new coins
-        const auto result4 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 38 * CENT);
+        const auto result4 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 38 * CENT, CENT);
         BOOST_CHECK(result4);
         BOOST_CHECK_EQUAL(result4->GetSelectedValue(), 38 * CENT);
 
         // try making 34 cents from 1,2,5,10,20 - we can't do it exactly
-        const auto result5 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 34 * CENT);
+        const auto result5 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 34 * CENT, CENT);
         BOOST_CHECK(result5);
         BOOST_CHECK_EQUAL(result5->GetSelectedValue(), 35 * CENT);       // but 35 cents is closest
         BOOST_CHECK_EQUAL(result5->GetInputSet().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
-        const auto result6 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 7 * CENT);
+        const auto result6 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 7 * CENT, CENT);
         BOOST_CHECK(result6);
         BOOST_CHECK_EQUAL(result6->GetSelectedValue(), 7 * CENT);
         BOOST_CHECK_EQUAL(result6->GetInputSet().size(), 2U);
 
         // when we try making 8 cents, the smaller coins (1,2,5) are exactly enough.
-        const auto result7 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 8 * CENT);
+        const auto result7 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 8 * CENT, CENT);
         BOOST_CHECK(result7);
         BOOST_CHECK(result7->GetSelectedValue() == 8 * CENT);
         BOOST_CHECK_EQUAL(result7->GetInputSet().size(), 3U);
 
         // when we try making 9 cents, no subset of smaller coins is enough, and we get the next bigger coin (10)
-        const auto result8 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 9 * CENT);
+        const auto result8 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 9 * CENT, CENT);
         BOOST_CHECK(result8);
         BOOST_CHECK_EQUAL(result8->GetSelectedValue(), 10 * CENT);
         BOOST_CHECK_EQUAL(result8->GetInputSet().size(), 1U);
@@ -438,12 +440,12 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(coins, *wallet, 30*CENT); // now we have 6+7+8+20+30 = 71 cents total
 
         // check that we have 71 and not 72
-        const auto result9 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 71 * CENT);
+        const auto result9 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 71 * CENT, CENT);
         BOOST_CHECK(result9);
-        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 72 * CENT));
+        BOOST_CHECK(!KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 72 * CENT, CENT));
 
         // 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
-        const auto result10 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT);
+        const auto result10 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT);
         BOOST_CHECK(result10);
         BOOST_CHECK_EQUAL(result10->GetSelectedValue(), 20 * CENT); // we should get 20 in one coin
         BOOST_CHECK_EQUAL(result10->GetInputSet().size(), 1U);
@@ -451,7 +453,7 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(coins, *wallet,  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
-        const auto result11 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT);
+        const auto result11 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT);
         BOOST_CHECK(result11);
         BOOST_CHECK_EQUAL(result11->GetSelectedValue(), 18 * CENT); // we should get 18 in 3 coins
         BOOST_CHECK_EQUAL(result11->GetInputSet().size(), 3U);
@@ -459,13 +461,13 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(coins, *wallet,  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
-        const auto result12 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT);
+        const auto result12 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 16 * CENT, CENT);
         BOOST_CHECK(result12);
         BOOST_CHECK_EQUAL(result12->GetSelectedValue(), 18 * CENT);  // we should get 18 in 1 coin
         BOOST_CHECK_EQUAL(result12->GetInputSet().size(), 1U); // because in the event of a tie, the biggest coin wins
 
         // now try making 11 cents.  we should get 5+6
-        const auto result13 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 11 * CENT);
+        const auto result13 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 11 * CENT, CENT);
         BOOST_CHECK(result13);
         BOOST_CHECK_EQUAL(result13->GetSelectedValue(), 11 * CENT);
         BOOST_CHECK_EQUAL(result13->GetInputSet().size(), 2U);
@@ -475,12 +477,12 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         add_coin(coins, *wallet,  2*COIN);
         add_coin(coins, *wallet,  3*COIN);
         add_coin(coins, *wallet,  4*COIN); // now we have 5+6+7+8+18+20+30+100+200+300+400 = 1094 cents
-        const auto result14 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 95 * CENT);
+        const auto result14 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 95 * CENT, CENT);
         BOOST_CHECK(result14);
         BOOST_CHECK_EQUAL(result14->GetSelectedValue(), 1 * COIN);  // we should get 1 BTC in 1 coin
         BOOST_CHECK_EQUAL(result14->GetInputSet().size(), 1U);
 
-        const auto result15 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 195 * CENT);
+        const auto result15 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 195 * CENT, CENT);
         BOOST_CHECK(result15);
         BOOST_CHECK_EQUAL(result15->GetSelectedValue(), 2 * COIN);  // we should get 2 BTC in 1 coin
         BOOST_CHECK_EQUAL(result15->GetInputSet().size(), 1U);
@@ -488,34 +490,34 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         // empty the wallet and start again, now with fractions of a cent, to test small change avoidance
 
         coins.clear();
-        add_coin(coins, *wallet, MIN_CHANGE * 1 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 2 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 3 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 4 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 5 / 10);
-
-        // 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
-        const auto result16 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE);
+        add_coin(coins, *wallet, CENT * 1 / 10);
+        add_coin(coins, *wallet, CENT * 2 / 10);
+        add_coin(coins, *wallet, CENT * 3 / 10);
+        add_coin(coins, *wallet, CENT * 4 / 10);
+        add_coin(coins, *wallet, CENT * 5 / 10);
+
+        // try making 1 * CENT from the 1.5 * CENT
+        // we'll get change smaller than CENT whatever happens, so can expect CENT exactly
+        const auto result16 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT, CENT);
         BOOST_CHECK(result16);
-        BOOST_CHECK_EQUAL(result16->GetSelectedValue(), MIN_CHANGE);
+        BOOST_CHECK_EQUAL(result16->GetSelectedValue(), CENT);
 
         // but if we add a bigger coin, small change is avoided
-        add_coin(coins, *wallet, 1111*MIN_CHANGE);
+        add_coin(coins, *wallet, 1111*CENT);
 
         // try making 1 from 0.1 + 0.2 + 0.3 + 0.4 + 0.5 + 1111 = 1112.5
-        const auto result17 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * MIN_CHANGE);
+        const auto result17 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
         BOOST_CHECK(result17);
-        BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * MIN_CHANGE); // we should get the exact amount
+        BOOST_CHECK_EQUAL(result17->GetSelectedValue(), 1 * CENT); // we should get the exact amount
 
         // if we add more small coins:
-        add_coin(coins, *wallet, MIN_CHANGE * 6 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 7 / 10);
+        add_coin(coins, *wallet, CENT * 6 / 10);
+        add_coin(coins, *wallet, CENT * 7 / 10);
 
-        // and try again to make 1.0 * MIN_CHANGE
-        const auto result18 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * MIN_CHANGE);
+        // and try again to make 1.0 * CENT
+        const auto result18 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
         BOOST_CHECK(result18);
-        BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * MIN_CHANGE); // we should get the exact amount
+        BOOST_CHECK_EQUAL(result18->GetSelectedValue(), 1 * CENT); // we should get the exact amount
 
         // run the 'mtgox' test (see https://blockexplorer.com/tx/29a3efd3ef04f9153d47a990bd7b048a4b2d213daaa5fb8ed670fb85f13bdbcf)
         // they tried to consolidate 10 50k coins into one 500k coin, and ended up with 50k in change
@@ -523,52 +525,52 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
         for (int j = 0; j < 20; j++)
             add_coin(coins, *wallet, 50000 * COIN);
 
-        const auto result19 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 500000 * COIN);
+        const auto result19 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 500000 * COIN, CENT);
         BOOST_CHECK(result19);
         BOOST_CHECK_EQUAL(result19->GetSelectedValue(), 500000 * COIN); // we should get the exact amount
         BOOST_CHECK_EQUAL(result19->GetInputSet().size(), 10U); // in ten coins
 
-        // if there's not enough in the smaller coins to make at least 1 * MIN_CHANGE change (0.5+0.6+0.7 < 1.0+1.0),
+        // if there's not enough in the smaller coins to make at least 1 * CENT change (0.5+0.6+0.7 < 1.0+1.0),
         // we need to try finding an exact subset anyway
 
         // sometimes it will fail, and so we use the next biggest coin:
         coins.clear();
-        add_coin(coins, *wallet, MIN_CHANGE * 5 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 6 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 7 / 10);
-        add_coin(coins, *wallet, 1111 * MIN_CHANGE);
-        const auto result20 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * MIN_CHANGE);
+        add_coin(coins, *wallet, CENT * 5 / 10);
+        add_coin(coins, *wallet, CENT * 6 / 10);
+        add_coin(coins, *wallet, CENT * 7 / 10);
+        add_coin(coins, *wallet, 1111 * CENT);
+        const auto result20 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 1 * CENT, CENT);
         BOOST_CHECK(result20);
-        BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * MIN_CHANGE); // we get the bigger coin
+        BOOST_CHECK_EQUAL(result20->GetSelectedValue(), 1111 * CENT); // we get the bigger coin
         BOOST_CHECK_EQUAL(result20->GetInputSet().size(), 1U);
 
         // but sometimes it's possible, and we use an exact subset (0.4 + 0.6 = 1.0)
         coins.clear();
-        add_coin(coins, *wallet, MIN_CHANGE * 4 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 6 / 10);
-        add_coin(coins, *wallet, MIN_CHANGE * 8 / 10);
-        add_coin(coins, *wallet, 1111 * MIN_CHANGE);
-        const auto result21 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE);
+        add_coin(coins, *wallet, CENT * 4 / 10);
+        add_coin(coins, *wallet, CENT * 6 / 10);
+        add_coin(coins, *wallet, CENT * 8 / 10);
+        add_coin(coins, *wallet, 1111 * CENT);
+        const auto result21 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT, CENT);
         BOOST_CHECK(result21);
-        BOOST_CHECK_EQUAL(result21->GetSelectedValue(), MIN_CHANGE);   // we should get the exact amount
+        BOOST_CHECK_EQUAL(result21->GetSelectedValue(), CENT);   // we should get the exact amount
         BOOST_CHECK_EQUAL(result21->GetInputSet().size(), 2U); // in two coins 0.4+0.6
 
         // test avoiding small change
         coins.clear();
-        add_coin(coins, *wallet, MIN_CHANGE * 5 / 100);
-        add_coin(coins, *wallet, MIN_CHANGE * 1);
-        add_coin(coins, *wallet, MIN_CHANGE * 100);
+        add_coin(coins, *wallet, CENT * 5 / 100);
+        add_coin(coins, *wallet, CENT * 1);
+        add_coin(coins, *wallet, CENT * 100);
 
         // trying to make 100.01 from these three coins
-        const auto result22 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE * 10001 / 100);
+        const auto result22 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT * 10001 / 100, CENT);
         BOOST_CHECK(result22);
-        BOOST_CHECK_EQUAL(result22->GetSelectedValue(), MIN_CHANGE * 10105 / 100); // we should get all coins
+        BOOST_CHECK_EQUAL(result22->GetSelectedValue(), CENT * 10105 / 100); // we should get all coins
         BOOST_CHECK_EQUAL(result22->GetInputSet().size(), 3U);
 
         // but if we try to make 99.9, we should take the bigger of the two small coins to avoid small change
-        const auto result23 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), MIN_CHANGE * 9990 / 100);
+        const auto result23 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), CENT * 9990 / 100, CENT);
         BOOST_CHECK(result23);
-        BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * MIN_CHANGE);
+        BOOST_CHECK_EQUAL(result23->GetSelectedValue(), 101 * CENT);
         BOOST_CHECK_EQUAL(result23->GetInputSet().size(), 2U);
     }
 
@@ -581,12 +583,12 @@ 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++) {
-            const auto result24 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 2000);
+            const auto result24 = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_confirmed), 2000, CENT);
             BOOST_CHECK(result24);
 
-            if (amt - 2000 < MIN_CHANGE) {
+            if (amt - 2000 < CENT) {
                 // needs more than one input:
-                uint16_t returnSize = std::ceil((2000.0 + MIN_CHANGE)/amt);
+                uint16_t returnSize = std::ceil((2000.0 + CENT)/amt);
                 CAmount returnValue = amt * returnSize;
                 BOOST_CHECK_EQUAL(result24->GetSelectedValue(), returnValue);
                 BOOST_CHECK_EQUAL(result24->GetInputSet().size(), returnSize);
@@ -608,9 +610,9 @@ 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
-            const auto result25 = KnapsackSolver(GroupCoins(coins), 50 * COIN);
+            const auto result25 = KnapsackSolver(GroupCoins(coins), 50 * COIN, CENT);
             BOOST_CHECK(result25);
-            const auto result26 = KnapsackSolver(GroupCoins(coins), 50 * COIN);
+            const auto result26 = KnapsackSolver(GroupCoins(coins), 50 * COIN, CENT);
             BOOST_CHECK(result26);
             BOOST_CHECK(!EqualResult(*result25, *result26));
 
@@ -621,9 +623,9 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
                 // 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
-                const auto result27 = KnapsackSolver(GroupCoins(coins), COIN);
+                const auto result27 = KnapsackSolver(GroupCoins(coins), COIN, CENT);
                 BOOST_CHECK(result27);
-                const auto result28 = KnapsackSolver(GroupCoins(coins), COIN);
+                const auto result28 = KnapsackSolver(GroupCoins(coins), COIN, CENT);
                 BOOST_CHECK(result28);
                 if (EqualResult(*result27, *result28))
                     fails++;
@@ -644,9 +646,9 @@ BOOST_AUTO_TEST_CASE(knapsack_solver_test)
             int fails = 0;
             for (int j = 0; j < RANDOM_REPEATS; j++)
             {
-                const auto result29 = KnapsackSolver(GroupCoins(coins), 90 * CENT);
+                const auto result29 = KnapsackSolver(GroupCoins(coins), 90 * CENT, CENT);
                 BOOST_CHECK(result29);
-                const auto result30 = KnapsackSolver(GroupCoins(coins), 90 * CENT);
+                const auto result30 = KnapsackSolver(GroupCoins(coins), 90 * CENT, CENT);
                 BOOST_CHECK(result30);
                 if (EqualResult(*result29, *result30))
                     fails++;
@@ -672,7 +674,7 @@ BOOST_AUTO_TEST_CASE(ApproximateBestSubset)
         add_coin(coins, *wallet, 1000 * COIN);
     add_coin(coins, *wallet, 3 * COIN);
 
-    const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN, rand);
+    const auto result = KnapsackSolver(KnapsackGroupOutputs(coins, *wallet, filter_standard), 1003 * COIN, CENT, rand);
     BOOST_CHECK(result);
     BOOST_CHECK_EQUAL(result->GetSelectedValue(), 1003 * COIN);
     BOOST_CHECK_EQUAL(result->GetInputSet().size(), 2U);
@@ -717,6 +719,7 @@ BOOST_AUTO_TEST_CASE(SelectCoins_test)
             rand,
             /* change_output_size= */ 34,
             /* change_spend_size= */ 148,
+            /*min_change_target=*/ CENT,
             /* effective_feerate= */ CFeeRate(0),
             /* long_term_feerate= */ CFeeRate(0),
             /* discard_feerate= */ CFeeRate(0),
diff --git a/test/functional/wallet_bumpfee.py b/test/functional/wallet_bumpfee.py
index f6843d597de80..3b23ee8e94aac 100755
--- a/test/functional/wallet_bumpfee.py
+++ b/test/functional/wallet_bumpfee.py
@@ -442,7 +442,9 @@ def test_watchonly_psbt(self, peer_node, rbf_node, dest_address):
     self.generate(peer_node, 1)
 
     # Create single-input PSBT for transaction to be bumped
-    psbt = watcher.walletcreatefundedpsbt([], {dest_address: 0.0005}, 0, {"fee_rate": 1}, True)['psbt']
+    # Ensure the payment amount + change can be fully funded using one of the 0.001BTC inputs.
+    psbt = watcher.walletcreatefundedpsbt([watcher.listunspent()[0]], {dest_address: 0.0005}, 0,
+            {"fee_rate": 1, "add_inputs": False}, True)['psbt']
     psbt_signed = signer.walletprocesspsbt(psbt=psbt, sign=True, sighashtype="ALL", bip32derivs=True)
     psbt_final = watcher.finalizepsbt(psbt_signed["psbt"])
     original_txid = watcher.sendrawtransaction(psbt_final["hex"])