txgraph: drop NEEDS_SPLIT_ACCEPTABLE (simplification)
What changed, and why it matters
This is a Bitcoin Core code cleanup that removes a special internal quality state called NEEDS_SPLIT_ACCEPTABLE from the transaction graph (txgraph) module. The change simplifies how clusters of related transactions are tracked after transactions are removed or fees change. It does not appear to be a security fix; it is described by the author as a simplification enabled by an upcoming algorithm improvement. There is no disclosed security relevance and no independent researcher credited.
Treat as a routine refactoring/simplification commit. No immediate security action required. If auditing, verify that dropping NEEDS_SPLIT_ACCEPTABLE does not cause performance regressions or incorrect cluster quality transitions in edge cases involving split clusters.
Security signals we found
No security-relevant keywords in commit title or message
No CVE, security advisory, or bug bounty reference present
Change is framed by author as simplification/refactoring
No input validation, cryptography, or network parsing changes
No bounds checks, memory allocations, or locking changes introduced
Removed special-case quality state reduces state-machine complexity
Evidence from the diff
The commit removes the QualityLevel::NEEDS_SPLIT_ACCEPTABLE enum value and collapses related logic. After transaction removals, clusters are now always marked NEEDS_SPLIT instead of conditionally NEEDS_SPLIT_ACCEPTABLE. The Split() function now always produces NEEDS_RELINEARIZE clusters and drops a pre-split PostLinearize() call. IsAcceptable() loses its after_split parameter. SetFee() now only transitions ACCEPTABLE/OPTIMAL clusters to NEEDS_RELINEARIZE and no longer transitions NEEDS_SPLIT clusters to NEEDS_SPLIT (a no-op). These are internal state-machine simplifications in src/txgraph.cpp.
Changed components
src/txgraph.cppGenericClusterImpl::ApplyRemovalsGenericClusterImpl::SplitTxGraphImpl::SplitAllGenericClusterImpl::SetFeeQualityLevel enumInspect captured patch +14 / −49
diff --git a/src/txgraph.cpp b/src/txgraph.cpp
index 274b14a4..492e13c8 100644
--- a/src/txgraph.cpp
+++ b/src/txgraph.cpp
@@ -42,8 +42,6 @@ enum class QualityLevel
OVERSIZED_SINGLETON,
/** This cluster may have multiple disconnected components, which are all NEEDS_RELINEARIZE. */
NEEDS_SPLIT,
- /** This cluster may have multiple disconnected components, which are all ACCEPTABLE. */
- NEEDS_SPLIT_ACCEPTABLE,
/** This cluster has undergone changes that warrant re-linearization. */
NEEDS_RELINEARIZE,
/** The minimal level of linearization has been performed, but it is not known to be optimal. */
@@ -128,10 +126,9 @@ public:
// Generic helper functions.
/** Whether the linearization of this Cluster can be exposed. */
- bool IsAcceptable(bool after_split = false) const noexcept
+ bool IsAcceptable() const noexcept
{
- return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL ||
- (after_split && m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE);
+ return m_quality == QualityLevel::ACCEPTABLE || m_quality == QualityLevel::OPTIMAL;
}
/** Whether the linearization of this Cluster is optimal. */
bool IsOptimal() const noexcept
@@ -145,8 +142,7 @@ public:
/** Whether this cluster requires splitting. */
bool NeedsSplitting() const noexcept
{
- return m_quality == QualityLevel::NEEDS_SPLIT ||
- m_quality == QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
+ return m_quality == QualityLevel::NEEDS_SPLIT;
}
/** Get the smallest number of transactions this Cluster is intended for. */
@@ -1179,37 +1175,20 @@ void GenericClusterImpl::ApplyRemovals(TxGraphImpl& graph, int level, std::span<
to_remove = to_remove.subspan(1);
} while(!to_remove.empty());
- auto quality = m_quality;
Assume(todo.Any());
// Wipe from the Cluster's DepGraph (this is O(n) regardless of the number of entries
// removed, so we benefit from batching all the removals).
m_depgraph.RemoveTransactions(todo);
m_mapping.resize(m_depgraph.PositionRange());
- // First remove all removals at the end of the linearization.
- while (!m_linearization.empty() && todo[m_linearization.back()]) {
- todo.Reset(m_linearization.back());
- m_linearization.pop_back();
- }
- if (todo.None()) {
- // If no further removals remain, and thus all removals were at the end, we may be able
- // to leave the cluster at a better quality level.
- if (IsAcceptable(/*after_split=*/true)) {
- quality = QualityLevel::NEEDS_SPLIT_ACCEPTABLE;
- } else {
- quality = QualityLevel::NEEDS_SPLIT;
- }
- } else {
- // If more removals remain, filter those out of m_linearization.
- m_linearization.erase(std::remove_if(
- m_linearization.begin(),
- m_linearization.end(),
- [&](auto pos) { return todo[pos]; }), m_linearization.end());
- quality = QualityLevel::NEEDS_SPLIT;
- }
+ // Filter removed transactions out of m_linearization.
+ m_linearization.erase(std::remove_if(m_linearization.begin(), m_linearization.end(),
+ [&](auto pos) { return todo[pos]; }),
+ m_linearization.end());
+
Compact();
graph.GetClusterSet(level).m_cluster_usage += TotalMemoryUsage();
- graph.SetClusterQuality(level, m_quality, m_setindex, quality);
+ graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
Updated(graph, level);
}
@@ -1354,17 +1333,7 @@ bool GenericClusterImpl::Split(TxGraphImpl& graph, int level) noexcept
// This function can only be called when the Cluster needs splitting.
Assume(NeedsSplitting());
// Determine the new quality the split-off Clusters will have.
- QualityLevel new_quality = IsAcceptable(/*after_split=*/true) ? QualityLevel::ACCEPTABLE
- : QualityLevel::NEEDS_RELINEARIZE;
- // If we're going to produce ACCEPTABLE clusters (i.e., when in NEEDS_SPLIT_ACCEPTABLE), we
- // need to post-linearize to make sure the split-out versions are all connected (as
- // connectivity may have changed by removing part of the cluster). This could be done on each
- // resulting split-out cluster separately, but it is simpler to do it once up front before
- // splitting. This step is not necessary if the resulting clusters are NEEDS_RELINEARIZE, as
- // they will be post-linearized anyway in MakeAcceptable().
- if (new_quality == QualityLevel::ACCEPTABLE) {
- PostLinearize(m_depgraph, m_linearization);
- }
+ QualityLevel new_quality = QualityLevel::NEEDS_RELINEARIZE;
/** Which positions are still left in this Cluster. */
auto todo = m_depgraph.Positions();
/** Mapping from transaction positions in this Cluster to the Cluster where it ends up, and
@@ -1771,11 +1740,9 @@ void TxGraphImpl::SplitAll(int up_to_level) noexcept
// Before splitting all Cluster, first make sure all removals are applied.
ApplyRemovals(up_to_level);
for (int level = 0; level <= up_to_level; ++level) {
- for (auto quality : {QualityLevel::NEEDS_SPLIT, QualityLevel::NEEDS_SPLIT_ACCEPTABLE}) {
- auto& queue = GetClusterSet(level).m_clusters[int(quality)];
- while (!queue.empty()) {
- Split(*queue.back().get(), level);
- }
+ auto& queue = GetClusterSet(level).m_clusters[int(QualityLevel::NEEDS_SPLIT)];
+ while (!queue.empty()) {
+ Split(*queue.back().get(), level);
}
}
}
@@ -2640,10 +2607,8 @@ void GenericClusterImpl::SetFee(TxGraphImpl& graph, int level, DepGraphIndex idx
m_depgraph.FeeRate(idx).fee = fee;
if (m_quality == QualityLevel::OVERSIZED_SINGLETON) {
// Nothing to do.
- } else if (!NeedsSplitting()) {
+ } else if (IsAcceptable()) {
graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_RELINEARIZE);
- } else {
- graph.SetClusterQuality(level, m_quality, m_setindex, QualityLevel::NEEDS_SPLIT);
}
Updated(graph, level);
}
Why this scored 20/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.