[doc] coin selection filters by max cluster count, not descendant

glozow · glozow · commit dc5e20cf97f8 · 2025-12-10T07:04:57.000-08:00
Avoid confusion by clarifying the docs and renaming the variables that
now hold cluster count rather than descendant count. No behavior change.
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
@@ -107,7 +107,7 @@ static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>
     tx.vout[nInput].nValue = nValue;
     COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/0, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/true, /*fees=*/0);
     set.emplace_back();
-    set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*descendants=*/ 0);
+    set.back().Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*cluster_count=*/ 0);
 }
 // Copied from src/wallet/test/coinselector_tests.cpp
 static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)
diff --git a/src/wallet/coinselection.cpp b/src/wallet/coinselection.cpp
@@ -752,7 +752,7 @@ util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, c
 
  ******************************************************************************/
 
-void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t descendants) {
+void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count) {
     m_outputs.push_back(output);
     auto& coin = *m_outputs.back();
 
@@ -770,9 +770,9 @@ void OutputGroup::Insert(const std::shared_ptr<COutput>& output, size_t ancestor
     // the sum, rather than the max; this will overestimate in the cases where multiple inputs
     // have common ancestors
     m_ancestors += ancestors;
-    // descendants is the count as seen from the top ancestor, not the descendants as seen from the
-    // coin itself; thus, this value is counted as the max, not the sum
-    m_descendants = std::max(m_descendants, descendants);
+    // This is the maximum cluster count among all outputs. If these outputs are from distinct clusters but spent in the
+    // same transaction, their clusters will be merged, potentially exceeding the mempool's max cluster count.
+    m_max_cluster_count = std::max(m_max_cluster_count, cluster_count);
 
     if (output->input_bytes > 0) {
         m_weight += output->input_bytes * WITNESS_SCALE_FACTOR;
@@ -783,7 +783,7 @@ bool OutputGroup::EligibleForSpending(const CoinEligibilityFilter& eligibility_f
 {
     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;
+        && m_max_cluster_count <= eligibility_filter.max_cluster_count;
 }
 
 CAmount OutputGroup::GetSelectionAmount() const
diff --git a/src/wallet/coinselection.h b/src/wallet/coinselection.h
@@ -207,19 +207,20 @@ struct CoinEligibilityFilter
     const int conf_theirs;
     /** Maximum number of unconfirmed ancestors aggregated across all UTXOs in an OutputGroup. */
     const uint64_t max_ancestors;
-    /** Maximum number of descendants that a single UTXO in the OutputGroup may have. */
-    const uint64_t max_descendants;
+    /** Maximum cluster count that a single UTXO in the OutputGroup may have. In practice, this filter also caps the
+     * maximum descendant count, as a transaction's descendant count is never larger than its cluster count. */
+    const uint64_t max_cluster_count;
     /** When avoid_reuse=true and there are full groups (OUTPUT_GROUP_MAX_ENTRIES), whether or not to use any partial groups.*/
     const bool m_include_partial_groups{false};
 
     CoinEligibilityFilter() = delete;
-    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_ancestors) {}
-    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants) {}
-    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_descendants, bool include_partial) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_descendants(max_descendants), m_include_partial_groups(include_partial) {}
+    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_cluster_count(max_ancestors) {}
+    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_cluster_count) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_cluster_count(max_cluster_count) {}
+    CoinEligibilityFilter(int conf_mine, int conf_theirs, uint64_t max_ancestors, uint64_t max_cluster_count, bool include_partial) : conf_mine(conf_mine), conf_theirs(conf_theirs), max_ancestors(max_ancestors), max_cluster_count(max_cluster_count), m_include_partial_groups(include_partial) {}
 
     bool operator<(const CoinEligibilityFilter& other) const {
-        return std::tie(conf_mine, conf_theirs, max_ancestors, max_descendants, m_include_partial_groups)
-               < std::tie(other.conf_mine, other.conf_theirs, other.max_ancestors, other.max_descendants, other.m_include_partial_groups);
+        return std::tie(conf_mine, conf_theirs, max_ancestors, max_cluster_count, m_include_partial_groups)
+               < std::tie(other.conf_mine, other.conf_theirs, other.max_ancestors, other.max_cluster_count, other.m_include_partial_groups);
     }
 };
 
@@ -239,8 +240,8 @@ struct OutputGroup
     /** The aggregated count of unconfirmed ancestors of all UTXOs in this
      * group. Not deduplicated and may overestimate when ancestors are shared. */
     size_t m_ancestors{0};
-    /** The maximum count of descendants of a single UTXO in this output group. */
-    size_t m_descendants{0};
+    /** The maximum cluster count of a single UTXO in this output group. */
+    size_t m_max_cluster_count{0};
     /** The value of the UTXOs after deducting the cost of spending them at the effective feerate. */
     CAmount effective_value{0};
     /** The fee to spend these UTXOs at the effective feerate. */
@@ -263,7 +264,7 @@ struct OutputGroup
         m_subtract_fee_outputs(params.m_subtract_fee_outputs)
     {}
 
-    void Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t descendants);
+    void Insert(const std::shared_ptr<COutput>& output, size_t ancestors, size_t cluster_count);
     bool EligibleForSpending(const CoinEligibilityFilter& eligibility_filter) const;
     CAmount GetSelectionAmount() const;
 };
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
@@ -405,8 +405,8 @@ CoinsResult AvailableCoins(const CWallet& wallet,
                     if (wtx.truc_child_in_mempool.has_value()) continue;
 
                     // this unconfirmed v3 transaction has a parent: spending would create a third generation
-                    size_t ancestors, descendants;
-                    wallet.chain().getTransactionAncestry(wtx.tx->GetHash(), ancestors, descendants);
+                    size_t ancestors, unused_cluster_count;
+                    wallet.chain().getTransactionAncestry(wtx.tx->GetHash(), ancestors, unused_cluster_count);
                     if (ancestors > 1) continue;
                 } else {
                     if (wtx.tx->version == TRUC_VERSION) continue;
@@ -866,11 +866,16 @@ util::Result<SelectionResult> SelectCoins(const CWallet& wallet, CoinsResult& av
 
 util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, CoinsResult& available_coins, const CAmount& value_to_select, const CoinSelectionParams& coin_selection_params)
 {
+    // Try to enforce a mixture of cluster limits and ancestor/descendant limits on transactions we create by limiting
+    // the ancestors and the maximum cluster count of any UTXO we use. We use the ancestor/descendant limits, which are
+    // lower than the cluster limits, to avoid exceeding any ancestor/descendant limits of legacy nodes. This filter is safe
+    // because a transaction's ancestor or descendant count cannot be larger than its cluster count.
+    // TODO: these limits can be relaxed in the future, and we can replace the ancestor filter with a cluster equivalent.
     unsigned int limit_ancestor_count = 0;
     unsigned int limit_descendant_count = 0;
     wallet.chain().getPackageLimits(limit_ancestor_count, limit_descendant_count);
     const size_t max_ancestors = (size_t)std::max<int64_t>(1, limit_ancestor_count);
-    const size_t max_descendants = (size_t)std::max<int64_t>(1, limit_descendant_count);
+    const size_t max_cluster_count = (size_t)std::max<int64_t>(1, limit_descendant_count);
     const bool fRejectLongChains = gArgs.GetBoolArg("-walletrejectlongchains", DEFAULT_WALLET_REJECT_LONG_CHAINS);
 
     // Cases where we have 101+ outputs all pointing to the same destination may result in
@@ -895,20 +900,21 @@ util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, Coin
         // possible) if we cannot fund the transaction otherwise.
         if (wallet.m_spend_zero_conf_change) {
             ordered_filters.push_back({CoinEligibilityFilter(0, 1, 2)});
-            ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::min(size_t{4}, max_ancestors/3), std::min(size_t{4}, max_descendants/3))});
-            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors/2, max_descendants/2)});
+            ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::min(size_t{4}, max_ancestors/3), std::min(size_t{4}, max_cluster_count/3))});
+            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors/2, max_cluster_count/2)});
             // 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.
-            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors-1, max_descendants-1, /*include_partial=*/true)});
+            ordered_filters.push_back({CoinEligibilityFilter(0, 1, max_ancestors-1, max_cluster_count-1, /*include_partial=*/true)});
             // Try with unsafe inputs if they are allowed. This may spend unconfirmed outputs
             // received from other wallets.
             if (coin_selection_params.m_include_unsafe_inputs) {
-                ordered_filters.push_back({CoinEligibilityFilter(/*conf_mine=*/0, /*conf_theirs*/0, max_ancestors-1, max_descendants-1, /*include_partial=*/true)});
+                ordered_filters.push_back({CoinEligibilityFilter(/*conf_mine=*/0, /*conf_theirs*/0, max_ancestors-1, max_cluster_count-1, /*include_partial=*/true)});
             }
-            // Try with unlimited ancestors/descendants. The transaction will still need to meet
-            // mempool ancestor/descendant policy to be accepted to mempool and broadcasted, but
-            // OutputGroups use heuristics that may overestimate ancestor/descendant counts.
+            // Try with unlimited ancestors/clusters. The transaction will still need to meet
+            // local mempool policy (i.e. cluster limits) to be accepted to mempool and broadcasted, and
+            // limits of other nodes (e.g. ancestor/descendant limits) to propagate, but OutputGroups
+            // use heuristics that may overestimate.
             if (!fRejectLongChains) {
                 ordered_filters.push_back({CoinEligibilityFilter(0, 1, std::numeric_limits<uint64_t>::max(),
                                                                    std::numeric_limits<uint64_t>::max(),
@@ -925,7 +931,7 @@ util::Result<SelectionResult> AutomaticCoinSelection(const CWallet& wallet, Coin
         CAmount total_unconf_long_chain = 0;
         for (const auto& group : discarded_groups) {
             total_discarded += group.GetSelectionAmount();
-            if (group.m_ancestors >= max_ancestors || group.m_descendants >= max_descendants) total_unconf_long_chain += group.GetSelectionAmount();
+            if (group.m_ancestors >= max_ancestors || group.m_max_cluster_count >= max_cluster_count) total_unconf_long_chain += group.GetSelectionAmount();
         }
 
         if (CAmount total_amount = available_coins.GetTotalAmount() - total_discarded < value_to_select) {
diff --git a/src/wallet/test/coinselection_tests.cpp b/src/wallet/test/coinselection_tests.cpp
@@ -53,7 +53,7 @@ static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, Coi
     tx.vout[0].nValue = amount + int(is_eff_value) * fees;
     tx.nLockTime = next_lock_time++;        // so all transactions get different hashes
     OutputGroup group(cs_params);
-    group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /*depth=*/1, /*input_bytes=*/custom_spending_vsize, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/fees), /*ancestors=*/0, /*descendants=*/0);
+    group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /*depth=*/1, /*input_bytes=*/custom_spending_vsize, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/fees), /*ancestors=*/0, /*cluster_count=*/0);
     return group;
 }
 
diff --git a/src/wallet/test/coinselector_tests.cpp b/src/wallet/test/coinselector_tests.cpp
@@ -45,7 +45,7 @@ static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result)
     tx.nLockTime = nextLockTime++;        // so all transactions get different hashes
     COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/-1, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, /*fees=*/ 0);
     OutputGroup group;
-    group.Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*descendants=*/ 0);
+    group.Insert(std::make_shared<COutput>(output), /*ancestors=*/ 0, /*cluster_count=*/ 0);
     result.AddInput(group);
 }
 
@@ -57,7 +57,7 @@ static void add_coin(const CAmount& nValue, int nInput, SelectionResult& result,
     tx.nLockTime = nextLockTime++;        // so all transactions get different hashes
     std::shared_ptr<COutput> coin = std::make_shared<COutput>(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /*depth=*/1, /*input_bytes=*/148, /*solvable=*/true, /*safe=*/true, /*time=*/0, /*from_me=*/false, fee);
     OutputGroup group;
-    group.Insert(coin, /*ancestors=*/ 0, /*descendants=*/ 0);
+    group.Insert(coin, /*ancestors=*/ 0, /*cluster_count=*/ 0);
     coin->long_term_fee = long_term_fee; // group.Insert() will modify long_term_fee, so we need to set it afterwards
     result.AddInput(group);
 }
@@ -131,7 +131,7 @@ inline std::vector<OutputGroup>& GroupCoins(const std::vector<COutput>& availabl
     for (auto& coin : available_coins) {
         static_groups.emplace_back();
         OutputGroup& group = static_groups.back();
-        group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/ 0, /*descendants=*/ 0);
+        group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/ 0, /*cluster_count=*/ 0);
         group.m_subtract_fee_outputs = subtract_fee_outputs;
     }
     return static_groups;
diff --git a/src/wallet/test/fuzz/coinselection.cpp b/src/wallet/test/fuzz/coinselection.cpp
@@ -33,7 +33,7 @@ static void GroupCoins(FuzzedDataProvider& fuzzed_data_provider, const std::vect
     bool valid_outputgroup{false};
     for (auto& coin : coins) {
         if (!positive_only || (positive_only && coin.GetEffectiveValue() > 0)) {
-            output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*descendants=*/0);
+            output_group.Insert(std::make_shared<COutput>(coin), /*ancestors=*/0, /*cluster_count=*/0);
         }
         // If positive_only was specified, nothing was inserted, leading to an empty output group
         // that would be invalid for the BnB algorithm
@@ -167,7 +167,7 @@ FUZZ_TARGET(coin_grinder_is_optimal)
         max_spendable += eff_value;
 
         auto output_group = OutputGroup(coin_params);
-        output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*descendants=*/0);
+        output_group.Insert(std::make_shared<COutput>(temp_utxo_pool.at(0)), /*ancestors=*/0, /*cluster_count=*/0);
         group_pos.push_back(output_group);
     }
     size_t num_groups = group_pos.size();

Original file line number	Diff line number	Diff line change
`@@ -107,7 +107,7 @@ static void add_coin(const CAmount& nValue, int nInput, std::vector<OutputGroup>`
`107`	`107`	`tx.vout[nInput].nValue = nValue;`
`108`	`108`	`COutput output(COutPoint(tx.GetHash(), nInput), tx.vout.at(nInput), /depth=/0, /input_bytes=/-1, /solvable=/true, /safe=/true, /time=/0, /from_me=/true, /fees=/0);`
`109`	`109`	`set.emplace_back();`
`110`		`- set.back().Insert(std::make_shared<COutput>(output), /ancestors=/ 0, /descendants=/ 0);`
	`110`	`+ set.back().Insert(std::make_shared<COutput>(output), /ancestors=/ 0, /cluster_count=/ 0);`
`111`	`111`	`}`
`112`	`112`	`// Copied from src/wallet/test/coinselector_tests.cpp`
`113`	`113`	`static CAmount make_hard_case(int utxos, std::vector<OutputGroup>& utxo_pool)`
Original file line number	Diff line number	Diff line change
`@@ -53,7 +53,7 @@ static OutputGroup MakeCoin(const CAmount& amount, bool is_eff_value = true, Coi`
`53`	`53`	`tx.vout[0].nValue = amount + int(is_eff_value) * fees;`
`54`	`54`	`tx.nLockTime = next_lock_time++; // so all transactions get different hashes`
`55`	`55`	`OutputGroup group(cs_params);`
`56`		`- group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /depth=/1, /input_bytes=/custom_spending_vsize, /solvable=/true, /safe=/true, /time=/0, /from_me=/false, /fees=/fees), /ancestors=/0, /descendants=/0);`
	`56`	`+ group.Insert(std::make_shared<COutput>(COutPoint(tx.GetHash(), 0), tx.vout.at(0), /depth=/1, /input_bytes=/custom_spending_vsize, /solvable=/true, /safe=/true, /time=/0, /from_me=/false, /fees=/fees), /ancestors=/0, /cluster_count=/0);`
`57`	`57`	`return group;`
`58`	`58`	`}`
`59`	`59`