wallet: run coin selection by `OutputType`

Run coin selection on each OutputType separately, choosing the best
solution according to the waste metric.

This is to avoid mixing UTXOs that are of different OutputTypes,
which can hurt privacy.

If no single OutputType can fund the transaction, then coin selection
considers the entire wallet, potentially mixing (current behavior).

This is done inside AttemptSelection so that all OutputTypes are
considered at each back-off in coin selection.

3 files changed, 50 insertions, 23 deletions

diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
index bb3ced8406..a80ec3703c 100644
--- a/src/bench/coin_selection.cpp
+++ b/src/bench/coin_selection.cpp
@@ -76,7 +76,7 @@ static void CoinSelection(benchmark::Bench& bench)
         /*avoid_partial=*/ false,
     };
     bench.run([&] {
-        auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, available_coins, coin_selection_params);
+        auto result = AttemptSelection(wallet, 1003 * COIN, filter_standard, available_coins, coin_selection_params, /*allow_mixed_output_types=*/true);
         assert(result);
         assert(result->GetSelectedValue() == 1003 * COIN);
         assert(result->GetInputSet().size() == 2);
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index 9e7085f7d3..c00a2cd023 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -451,9 +451,34 @@ std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<C
 }
 
 std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const CoinsResult& available_coins,
-                               const CoinSelectionParams& coin_selection_params)
+                               const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types)
 {
-    std::optional<SelectionResult> result = ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.all(), coin_selection_params);
+    // Run coin selection on each OutputType and compute the Waste Metric
+    std::vector<SelectionResult> results;
+    if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.legacy, coin_selection_params)}) {
+        results.push_back(*result);
+    }
+    if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.P2SH_segwit, coin_selection_params)}) {
+        results.push_back(*result);
+    }
+    if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.bech32, coin_selection_params)}) {
+        results.push_back(*result);
+    }
+    if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.bech32m, coin_selection_params)}) {
+        results.push_back(*result);
+    }
+
+    // If we can't fund the transaction from any individual OutputType, run coin selection
+    // over all available coins, else pick the best solution from the results
+    if (results.size() == 0) {
+        if (allow_mixed_output_types) {
+            if (auto result{ChooseSelectionResult(wallet, nTargetValue, eligibility_filter, available_coins.all(), coin_selection_params)}) {
+                return result;
+            }
+        }
+        return std::optional<SelectionResult>();
+    };
+    std::optional<SelectionResult> result{*std::min_element(results.begin(), results.end())};
     return result;
 };
 
@@ -601,26 +626,27 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
 
         // 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 (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), available_coins, coin_selection_params)}) return r1;
-        if (auto r2{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), available_coins, coin_selection_params)}) return r2;
+        if (auto r1{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 6, 0), available_coins, coin_selection_params, /*allow_mixed_output_types=*/false)}) return r1;
+        // Allow mixing only if no solution from any single output type can be found
+        if (auto r2{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(1, 1, 0), available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) return r2;
 
         // 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 (wallet.m_spend_zero_conf_change) {
-            if (auto r3{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), available_coins, coin_selection_params)}) return r3;
+            if (auto r3{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, 2), available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) return r3;
             if (auto r4{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, std::min((size_t)4, max_ancestors/3), std::min((size_t)4, max_descendants/3)),
-                                   available_coins, coin_selection_params)}) {
+                                   available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) {
                 return r4;
             }
             if (auto r5{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2),
-                                   available_coins, coin_selection_params)}) {
+                                   available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) {
                 return r5;
             }
             // 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 (auto r6{AttemptSelection(wallet, value_to_select, CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
-                                   available_coins, coin_selection_params)}) {
+                                   available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) {
                 return r6;
             }
             // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
@@ -628,7 +654,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
             if (coin_control.m_include_unsafe_inputs) {
                 if (auto r7{AttemptSelection(wallet, value_to_select,
                     CoinEligibilityFilter(0 /* conf_mine */, 0 /* conf_theirs */, max_ancestors-1, max_descendants-1, true /* include_partial_groups */),
-                    available_coins, coin_selection_params)}) {
+                    available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) {
                     return r7;
                 }
             }
@@ -638,7 +664,7 @@ std::optional<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& a
             if (!fRejectLongChains) {
                 if (auto r8{AttemptSelection(wallet, value_to_select,
                                       CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(), std::numeric_limits<uint64_t>::max(), true /* include_partial_groups */),
-                                      available_coins, coin_selection_params)}) {
+                                      available_coins, coin_selection_params, /*allow_mixed_output_types=*/true)}) {
                     return r8;
                 }
             }
diff --git a/src/wallet/spend.h b/src/wallet/spend.h
index a9216e22ee..96ecd690be 100644
--- a/src/wallet/spend.h
+++ b/src/wallet/spend.h
@@ -91,22 +91,23 @@ const CTxOut& FindNonChangeParentOutput(const CWallet& wallet, const COutPoint&
 std::map<CTxDestination, std::vector<COutput>> ListCoins(const CWallet& wallet) EXCLUSIVE_LOCKS_REQUIRED(wallet.cs_wallet);
 
 std::vector<OutputGroup> GroupOutputs(const CWallet& wallet, const std::vector<COutput>& outputs, const CoinSelectionParams& coin_sel_params, const CoinEligibilityFilter& filter, bool positive_only);
-
 /**
- * Attempt to find a valid input set that meets the provided eligibility filter and target.
- * Multiple coin selection algorithms will be run and the input set that produces the least waste
- * (according to the waste metric) will be chosen.
+ * Attempt to find a valid input set that preserves privacy by not mixing OutputTypes.
+ * `ChooseSelectionResult()` will be called on each OutputType individually and the best
+ * the solution (according to the waste metric) will be chosen. If a valid input cannot be found from any
+ * single OutputType, fallback to running `ChooseSelectionResult()` over all available coins.
  *
- * param@[in]  wallet                 The wallet which provides solving data for the coins
- * param@[in]  nTargetValue           The target value
- * param@[in]  eligilibity_filter     A filter containing rules for which coins are allowed to be included in this selection
- * param@[in]  available_coins        The struct of coins, organized by OutputType, available for selection prior to filtering
- * param@[in]  coin_selection_params  Parameters for the coin selection
- * returns                            If successful, a SelectionResult containing the input set
- *                                    If failed, a nullopt
+ * param@[in]  wallet                    The wallet which provides solving data for the coins
+ * param@[in]  nTargetValue              The target value
+ * param@[in]  eligilibity_filter        A filter containing rules for which coins are allowed to be included in this selection
+ * param@[in]  available_coins           The struct of coins, organized by OutputType, available for selection prior to filtering
+ * param@[in]  coin_selection_params     Parameters for the coin selection
+ * param@[in]  allow_mixed_output_types  Relax restriction that SelectionResults must be of the same OutputType
+ * returns                               If successful, a SelectionResult containing the input set
+ *                                       If failed, a nullopt
  */
 std::optional<SelectionResult> AttemptSelection(const CWallet& wallet, const CAmount& nTargetValue, const CoinEligibilityFilter& eligibility_filter, const CoinsResult& available_coins,
-                        const CoinSelectionParams& coin_selection_params);
+                        const CoinSelectionParams& coin_selection_params, bool allow_mixed_output_types);
 
 /**
  * Attempt to find a valid input set that meets the provided eligibility filter and target.