Merge #13808: wallet: shuffle coins before grouping, where warranted

18f690ec2f7eb1b4aa51825bfed0cbfdadc93ac7 wallet: shuffle coins before grouping, where warranted (Karl-Johan Alm)

Pull request description:

  Coins are randomly shuffled in coin selection to avoid unintentional privacy leaks regarding the user's coin set. For the case where a user has a lot of coins with the same destination, these will be grouped into groups of 10 *before* the shuffling.

  It is unclear whether this has any implications at all, but this PR plugs the potential issue, if there ever is one, by shuffling the coins before they are grouped.

  Issue brought up in https://github.com/bitcoin/bitcoin/pull/12257#discussion_r204554549

Tree-SHA512: fb50ed4b5fc03ab4853d45b76e1c64476ad5bcd797497179bc37b9262885c974ed6811159fd8e581f1461b6cc6d0a66146f4b70a2777c0f5e818d1322e0edb89

1 files changed, 9 insertions, 1 deletions

diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 597d108aef..73d2b205c2 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -35,6 +35,8 @@
 
 #include <boost/algorithm/string/replace.hpp>
 
+static const size_t OUTPUT_GROUP_MAX_ENTRIES = 10;
+
 static CCriticalSection cs_wallets;
 static std::vector<std::shared_ptr<CWallet>> vpwallets GUARDED_BY(cs_wallets);
 
@@ -2525,6 +2527,12 @@ bool CWallet::SelectCoins(const std::vector<COutput>& vAvailableCoins, const CAm
 
     // form groups from remaining coins; note that preset coins will not
     // automatically have their associated (same address) coins included
+    if (coin_control.m_avoid_partial_spends && vCoins.size() > OUTPUT_GROUP_MAX_ENTRIES) {
+        // Cases where we have 11+ outputs all pointing to the same destination may result in
+        // privacy leaks as they will potentially be deterministically sorted. We solve that by
+        // explicitly shuffling the outputs before processing
+        std::shuffle(vCoins.begin(), vCoins.end(), FastRandomContext());
+    }
     std::vector<OutputGroup> groups = GroupOutputs(vCoins, !coin_control.m_avoid_partial_spends);
 
     size_t max_ancestors = (size_t)std::max<int64_t>(1, gArgs.GetArg("-limitancestorcount", DEFAULT_ANCESTOR_LIMIT));
@@ -4444,7 +4452,7 @@ std::vector<OutputGroup> CWallet::GroupOutputs(const std::vector<COutput>& outpu
                 // Limit output groups to no more than 10 entries, to protect
                 // against inadvertently creating a too-large transaction
                 // when using -avoidpartialspends
-                if (gmap[dst].m_outputs.size() >= 10) {
+                if (gmap[dst].m_outputs.size() >= OUTPUT_GROUP_MAX_ENTRIES) {
                     groups.push_back(gmap[dst]);
                     gmap.erase(dst);
                 }