Merge bitcoin/bitcoin#24494: wallet: generate random change target for each tx for better privacy

9053f64fcbd26d87c26ae6b982d17756a6ea0896 [doc] release notes for random change target (glozow)
46f2fed6c5e0fa623bfeabf61ba4811d5cf8f47c [wallet] remove MIN_CHANGE (glozow)
a44236addd01cff4e4d751e0f379d399fbfc8eae [wallet] randomly generate change targets (glozow)
1e52e6bd0a8888efb4ed247d74ec7ca9dfc2e002 refactor coin selection for parameterizable change target (glozow)

Pull request description:

  Closes #24458 - the wallet always chooses 1 million sats as its change target, making it easier to fingerprint transactions created by the Core wallet. Instead of using a fixed value, choose one randomly each time (within a range). Using 50ksat (around $20) as the lower bound and `min(1 million sat, 2 * average payment value)` as the upper bound.
  RFC: If the payment is <25ksat, this doesn't work, so we're using the range (payment amount, 50ksat) instead.

ACKs for top commit:
  achow101:
    ACK 9053f64fcbd26d87c26ae6b982d17756a6ea0896
  Xekyo:
    reACK 9053f64fcbd26d87c26ae6b982d17756a6ea0896

Tree-SHA512: 45ce5d064697065549473347648e29935733f3deffc71a6ab995449431f60302d1f9911a0994dfdb960b48c48b5d8859f168b396ff2a62db67d535a7db041d35

1 files changed, 29 insertions, 6 deletions

diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
index da77b21626..784a91e827 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. */
 struct COutput {
@@ -93,8 +93,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. */
@@ -114,11 +119,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),
@@ -217,6 +224,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:
@@ -266,7 +288,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