[doc] coin selection filters by max cluster count, not descendant
What changed, and why it matters
This commit only renames variables and updates comments in Bitcoin Core's coin selection code. It changes names like 'descendants' to 'cluster_count' to make the code match what it actually does, with no change in behavior. There is no security issue here.
No action required. This is a non-security documentation and naming refactor.
Security signals we found
No strong security signals were identified.
Evidence from the diff
The patch is a pure documentation/variable rename refactor in the wallet coin selection module. It renames descendants/m_descendants/max_descendants to cluster_count/m_max_cluster_count/max_cluster_count across coinselection.cpp/h, spend.cpp, benchmarks, and tests. The commit message explicitly states ‘No behavior change.’ The logic remains identical: the value still comes from getTransactionAncestry and is compared against the same package-limit-derived threshold. No functional code paths were altered.
Changed components
src/wallet/coinselection.cppsrc/wallet/coinselection.hsrc/wallet/spend.cppsrc/bench/coin_selection.cppsrc/wallet/test/coinselection_tests.cppsrc/wallet/test/coinselector_tests.cppsrc/wallet/test/fuzz/coinselection.cppInspect captured patch +48 / −41
diff --git a/src/bench/coin_selection.cpp b/src/bench/coin_selection.cpp
index 72b3d70e..2f108a31 100644
--- 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
index 8977d999..d7fde389 100644
--- 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
index 22103de1..2457cf95 100644
--- 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
index c91d0f47..70044da1 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -582,12 +582,12 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet,
for (const auto& [type, outputs] : coins.coins) {
for (const COutput& output : outputs) {
// Get mempool info
- size_t ancestors, descendants;
- wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, descendants);
+ size_t ancestors, cluster_count;
+ wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, cluster_count);
// Create a new group per output and add it to the all groups vector
OutputGroup group(coin_sel_params);
- group.Insert(std::make_shared<COutput>(output), ancestors, descendants);
+ group.Insert(std::make_shared<COutput>(output), ancestors, cluster_count);
// Each filter maps to a different set of groups
bool accepted = false;
@@ -611,7 +611,7 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet,
// OUTPUT_GROUP_MAX_ENTRIES COutputs, a new OutputGroup is added to the end of the vector.
typedef std::map<std::pair<CScript, OutputType>, std::vector<OutputGroup>> ScriptPubKeyToOutgroup;
const auto& insert_output = [&](
- const std::shared_ptr<COutput>& output, OutputType type, size_t ancestors, size_t descendants,
+ const std::shared_ptr<COutput>& output, OutputType type, size_t ancestors, size_t cluster_count,
ScriptPubKeyToOutgroup& groups_map) {
std::vector<OutputGroup>& groups = groups_map[std::make_pair(output->txout.scriptPubKey,type)];
@@ -632,24 +632,24 @@ FilteredOutputGroups GroupOutputs(const CWallet& wallet,
group = &groups.back();
}
- group->Insert(output, ancestors, descendants);
+ group->Insert(output, ancestors, cluster_count);
};
ScriptPubKeyToOutgroup spk_to_groups_map;
ScriptPubKeyToOutgroup spk_to_positive_groups_map;
for (const auto& [type, outs] : coins.coins) {
for (const COutput& output : outs) {
- size_t ancestors, descendants;
- wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, descendants);
+ size_t ancestors, cluster_count;
+ wallet.chain().getTransactionAncestry(output.outpoint.hash, ancestors, cluster_count);
const auto& shared_output = std::make_shared<COutput>(output);
// Filter for positive only before adding the output
if (output.GetEffectiveValue() > 0) {
- insert_output(shared_output, type, ancestors, descendants, spk_to_positive_groups_map);
+ insert_output(shared_output, type, ancestors, cluster_count, spk_to_positive_groups_map);
}
// 'All' groups
- insert_output(shared_output, type, ancestors, descendants, spk_to_groups_map);
+ insert_output(shared_output, type, ancestors, cluster_count, spk_to_groups_map);
}
}
@@ -871,11 +871,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
@@ -900,20 +905,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(),
@@ -930,7 +936,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
index 6aa473bc..4a0eed8f 100644
--- 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
index 7f55d765..04d64ae2 100644
--- a/src/wallet/test/coinselector_tests.cpp
+++ b/src/wallet/test/coinselector_tests.cpp
@@ -43,7 +43,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);
}
@@ -55,7 +55,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);
}
@@ -129,7 +129,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
index 084777f8..8b30423c 100644
--- 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();
@@ -264,7 +264,7 @@ FUZZ_TARGET(bnb_finds_min_waste)
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();
Why this scored 15/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.