Merge #12257: [wallet] Use destination groups instead of coins in coin select

232f96f5c8a3920c09db92f4dbac2ad7d10ce8cf doc: Add release notes for -avoidpartialspends (Karl-Johan Alm)
e00b4699cc6d2ee5697d38dd6607eb2631c9b77a clean-up: Remove no longer used ivars from CInputCoin (Karl-Johan Alm)
43e04d13b1ffc02b1082176e87f420198b40c7b1 wallet: Remove deprecated OutputEligibleForSpending (Karl-Johan Alm)
0128121101fb3ee82f3abd3973a967a4226ffe0e test: Add basic testing for wallet groups (Karl-Johan Alm)
59d6f7b4e2f847ec1f2ff46c84e6157655984f85 wallet: Switch to using output groups instead of coins in coin selection (Karl-Johan Alm)
87ebce25d66952f5ce565bb5130dcf5e24049872 wallet: Add output grouping (Karl-Johan Alm)
bb629cb9dc567cc819724d9f4852652926e60cbf Add -avoidpartialspends and m_avoid_partial_spends (Karl-Johan Alm)
65b3eda458221644616d0fdd6ba0fe01bdbce893 wallet: Add input bytes to CInputCoin (Karl-Johan Alm)
a443d7a0ca333b0bae63e04b5d476f9ad9c7aeac moveonly: CoinElegibilityFilter into coinselection.h (Karl-Johan Alm)
173e18a289088c6087ba6fac708e322aa63b7a94 utils: Add insert() convenience templates (Karl-Johan Alm)

Pull request description:

  This PR adds an optional (off by default) `-avoidpartialspends` flag, which changes coin select to use output groups rather than outputs, where each output group corresponds to all outputs with the same destination.

  It is a privacy improvement, as each time you spend some output, any other output that is publicly associated with the destination (address) will also be spent at the same time, at the cost of fee increase for cases where coin select without group restriction would find a more optimal set of coins (see example below).

  For regular use without address reuse, this PR should have no effect on the user experience whatsoever; it only affects users who, for some reason, have multiple outputs with the same destination (i.e. address reuse).

  Nodes with this turned off will still try to avoid partial spending, if the fee of the resulting transaction is not greater than the fee of the original transaction.

  Example: a node has four outputs linked to two addresses `A` and `B`:

  * 1.0 btc to `A`
  * 0.5 btc to `A`
  * 1.0 btc to `B`
  * 0.5 btc to `B`

  The node sends 0.2 btc to `C`. Without `-avoidpartialspends`, the following coin selection will occur:
  * 0.5 btc to `A` or `B` is picked
  * 0.2 btc is output to `C`
  * 0.3 - fee is output to (unique change address)

  With `-avoidpartialspends`, the following will instead happen:
  * Both of (0.5, 1.0) btc to `A` or `B` is picked (one or the other pair)
  * 0.2 btc is output to `C`
  * 1.3 - fee is output to (unique change address)

  As noted, the pro here is that, assuming nobody sends to the address after you spend from it, you will only ever use one address once. The con is that the transaction becomes slightly larger in this case, because it is overpicking outputs to adhere to the no partial spending rule.

  This complements #10386, in particular it addresses @luke-jr and @gmaxwell's concerns in https://github.com/bitcoin/bitcoin/pull/10386#issuecomment-300667926 and https://github.com/bitcoin/bitcoin/pull/10386#issuecomment-302361381.

  Together with `-avoidreuse`, this fully addresses the concerns in #10065 I believe.

Tree-SHA512: 24687a4490ba59cf4198ed90052944ff4996653a4257833bb52ed24d058b3e924800c9b3790aeb6be6385b653b49e304453e5d7ff960e64c682fc23bfc447621

1 files changed, 88 insertions, 62 deletions

diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
index 78258cdec2..1a810e763f 100644
--- a/src/wallet/coinselection.cpp
+++ b/src/wallet/coinselection.cpp
@@ -8,7 +8,7 @@
 
 // Descending order comparator
 struct {
-    bool operator()(const CInputCoin& a, const CInputCoin& b) const
+    bool operator()(const OutputGroup& a, const OutputGroup& b) const
     {
         return a.effective_value > b.effective_value;
     }
@@ -59,7 +59,7 @@ struct {
 
 static const size_t TOTAL_TRIES = 100000;
 
-bool SelectCoinsBnB(std::vector<CInputCoin>& 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& target_value, const CAmount& cost_of_change, std::set<CInputCoin>& out_set, CAmount& value_ret, CAmount not_input_fees)
 {
     out_set.clear();
     CAmount curr_value = 0;
@@ -70,7 +70,7 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
 
     // Calculate curr_available_value
     CAmount curr_available_value = 0;
-    for (const CInputCoin& utxo : utxo_pool) {
+    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;
@@ -123,11 +123,11 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
 
             // Output was included on previous iterations, try excluding now.
             curr_selection.back() = false;
-            CInputCoin& utxo = utxo_pool.at(curr_selection.size() - 1);
+            OutputGroup& utxo = utxo_pool.at(curr_selection.size() - 1);
             curr_value -= utxo.effective_value;
             curr_waste -= utxo.fee - utxo.long_term_fee;
         } else { // Moving forwards, continuing down this branch
-            CInputCoin& utxo = utxo_pool.at(curr_selection.size());
+            OutputGroup& utxo = utxo_pool.at(curr_selection.size());
 
             // Remove this utxo from the curr_available_value utxo amount
             curr_available_value -= utxo.effective_value;
@@ -156,32 +156,32 @@ bool SelectCoinsBnB(std::vector<CInputCoin>& utxo_pool, const CAmount& target_va
     value_ret = 0;
     for (size_t i = 0; i < best_selection.size(); ++i) {
         if (best_selection.at(i)) {
-            out_set.insert(utxo_pool.at(i));
-            value_ret += utxo_pool.at(i).txout.nValue;
+            util::insert(out_set, utxo_pool.at(i).m_outputs);
+            value_ret += utxo_pool.at(i).m_value;
         }
     }
 
     return true;
 }
 
-static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const CAmount& nTotalLower, const CAmount& nTargetValue,
+static void ApproximateBestSubset(const std::vector<OutputGroup>& groups, const CAmount& nTotalLower, const CAmount& nTargetValue,
                                   std::vector<char>& vfBest, CAmount& nBest, int iterations = 1000)
 {
     std::vector<char> vfIncluded;
 
-    vfBest.assign(vValue.size(), true);
+    vfBest.assign(groups.size(), true);
     nBest = nTotalLower;
 
     FastRandomContext insecure_rand;
 
     for (int nRep = 0; nRep < iterations && nBest != nTargetValue; nRep++)
     {
-        vfIncluded.assign(vValue.size(), false);
+        vfIncluded.assign(groups.size(), false);
         CAmount nTotal = 0;
         bool fReachedTarget = false;
         for (int nPass = 0; nPass < 2 && !fReachedTarget; nPass++)
         {
-            for (unsigned int i = 0; i < vValue.size(); i++)
+            for (unsigned int i = 0; i < groups.size(); i++)
             {
                 //The solver here uses a randomized algorithm,
                 //the randomness serves no real security purpose but is just
@@ -191,7 +191,7 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
                 //the selection random.
                 if (nPass == 0 ? insecure_rand.randbool() : !vfIncluded[i])
                 {
-                    nTotal += vValue[i].txout.nValue;
+                    nTotal += groups[i].m_value;
                     vfIncluded[i] = true;
                     if (nTotal >= nTargetValue)
                     {
@@ -201,7 +201,7 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
                             nBest = nTotal;
                             vfBest = vfIncluded;
                         }
-                        nTotal -= vValue[i].txout.nValue;
+                        nTotal -= groups[i].m_value;
                         vfIncluded[i] = false;
                     }
                 }
@@ -210,86 +210,75 @@ static void ApproximateBestSubset(const std::vector<CInputCoin>& vValue, const C
     }
 }
 
-bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
+bool KnapsackSolver(const CAmount& nTargetValue, std::vector<OutputGroup>& groups, std::set<CInputCoin>& setCoinsRet, CAmount& nValueRet)
 {
     setCoinsRet.clear();
     nValueRet = 0;
 
     // List of values less than target
-    boost::optional<CInputCoin> coinLowestLarger;
-    std::vector<CInputCoin> vValue;
+    boost::optional<OutputGroup> lowest_larger;
+    std::vector<OutputGroup> applicable_groups;
     CAmount nTotalLower = 0;
 
-    random_shuffle(vCoins.begin(), vCoins.end(), GetRandInt);
+    random_shuffle(groups.begin(), groups.end(), GetRandInt);
 
-    for (const CInputCoin &coin : vCoins)
-    {
-        if (coin.txout.nValue == nTargetValue)
-        {
-            setCoinsRet.insert(coin);
-            nValueRet += coin.txout.nValue;
+    for (const OutputGroup& group : groups) {
+        if (group.m_value == nTargetValue) {
+            util::insert(setCoinsRet, group.m_outputs);
+            nValueRet += group.m_value;
             return true;
-        }
-        else if (coin.txout.nValue < nTargetValue + MIN_CHANGE)
-        {
-            vValue.push_back(coin);
-            nTotalLower += coin.txout.nValue;
-        }
-        else if (!coinLowestLarger || coin.txout.nValue < coinLowestLarger->txout.nValue)
-        {
-            coinLowestLarger = coin;
+        } else if (group.m_value < nTargetValue + MIN_CHANGE) {
+            applicable_groups.push_back(group);
+            nTotalLower += group.m_value;
+        } else if (!lowest_larger || group.m_value < lowest_larger->m_value) {
+            lowest_larger = group;
         }
     }
 
-    if (nTotalLower == nTargetValue)
-    {
-        for (const auto& input : vValue)
-        {
-            setCoinsRet.insert(input);
-            nValueRet += input.txout.nValue;
+    if (nTotalLower == nTargetValue) {
+        for (const auto& group : applicable_groups) {
+            util::insert(setCoinsRet, group.m_outputs);
+            nValueRet += group.m_value;
         }
         return true;
     }
 
-    if (nTotalLower < nTargetValue)
-    {
-        if (!coinLowestLarger)
-            return false;
-        setCoinsRet.insert(coinLowestLarger.get());
-        nValueRet += coinLowestLarger->txout.nValue;
+    if (nTotalLower < nTargetValue) {
+        if (!lowest_larger) return false;
+        util::insert(setCoinsRet, lowest_larger->m_outputs);
+        nValueRet += lowest_larger->m_value;
         return true;
     }
 
     // Solve subset sum by stochastic approximation
-    std::sort(vValue.begin(), vValue.end(), descending);
+    std::sort(applicable_groups.begin(), applicable_groups.end(), descending);
     std::vector<char> vfBest;
     CAmount nBest;
 
-    ApproximateBestSubset(vValue, nTotalLower, nTargetValue, vfBest, nBest);
-    if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE)
-        ApproximateBestSubset(vValue, nTotalLower, nTargetValue + MIN_CHANGE, vfBest, nBest);
+    ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue, vfBest, nBest);
+    if (nBest != nTargetValue && nTotalLower >= nTargetValue + MIN_CHANGE) {
+        ApproximateBestSubset(applicable_groups, nTotalLower, nTargetValue + MIN_CHANGE, 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 (coinLowestLarger &&
-        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || coinLowestLarger->txout.nValue <= nBest))
-    {
-        setCoinsRet.insert(coinLowestLarger.get());
-        nValueRet += coinLowestLarger->txout.nValue;
-    }
-    else {
-        for (unsigned int i = 0; i < vValue.size(); i++)
-            if (vfBest[i])
-            {
-                setCoinsRet.insert(vValue[i]);
-                nValueRet += vValue[i].txout.nValue;
+    if (lowest_larger &&
+        ((nBest != nTargetValue && nBest < nTargetValue + MIN_CHANGE) || lowest_larger->m_value <= nBest)) {
+        util::insert(setCoinsRet, lowest_larger->m_outputs);
+        nValueRet += lowest_larger->m_value;
+    } else {
+        for (unsigned int i = 0; i < applicable_groups.size(); i++) {
+            if (vfBest[i]) {
+                util::insert(setCoinsRet, applicable_groups[i].m_outputs);
+                nValueRet += applicable_groups[i].m_value;
             }
+        }
 
         if (LogAcceptCategory(BCLog::SELECTCOINS)) {
             LogPrint(BCLog::SELECTCOINS, "SelectCoins() best subset: "); /* Continued */
-            for (unsigned int i = 0; i < vValue.size(); i++) {
+            for (unsigned int i = 0; i < applicable_groups.size(); i++) {
                 if (vfBest[i]) {
-                    LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(vValue[i].txout.nValue)); /* Continued */
+                    LogPrint(BCLog::SELECTCOINS, "%s ", FormatMoney(applicable_groups[i].m_value)); /* Continued */
                 }
             }
             LogPrint(BCLog::SELECTCOINS, "total %s\n", FormatMoney(nBest));
@@ -298,3 +287,40 @@ bool KnapsackSolver(const CAmount& nTargetValue, std::vector<CInputCoin>& vCoins
 
     return true;
 }
+
+/******************************************************************************
+
+ OutputGroup
+
+ ******************************************************************************/
+
+void OutputGroup::Insert(const CInputCoin& output, int depth, bool from_me, size_t ancestors, size_t descendants) {
+    m_outputs.push_back(output);
+    m_from_me &= from_me;
+    m_value += output.effective_value;
+    m_depth = std::min(m_depth, depth);
+    // m_ancestors is currently the max ancestor count for all coins in the group; however, this is
+    // not ideal, as a wallet will consider e.g. thirty 2-ancestor coins as having two ancestors,
+    // when in reality it has 60 ancestors.
+    m_ancestors = std::max(m_ancestors, ancestors);
+    // m_descendants is the count as seen from the top ancestor, not the descendants as seen from the
+    // coin itself; thus, this value is accurate
+    m_descendants = std::max(m_descendants, descendants);
+    effective_value = m_value;
+}
+
+std::vector<CInputCoin>::iterator OutputGroup::Discard(const CInputCoin& output) {
+    auto it = m_outputs.begin();
+    while (it != m_outputs.end() && it->outpoint != output.outpoint) ++it;
+    if (it == m_outputs.end()) return it;
+    m_value -= output.effective_value;
+    effective_value -= output.effective_value;
+    return m_outputs.erase(it);
+}
+
+bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const
+{
+    return m_depth >= (m_from_me ? eligibility_filter.conf_mine : eligibility_filter.conf_theirs)
+        && m_ancestors <= eligibility_filter.max_ancestors
+        && m_descendants <= eligibility_filter.max_descendants;
+}