AI-generated analysisPublished automatically and not human-verified. Validated context appears in community notes below.
← Watch feed
Informational 21 Bitcoin

clusterlin: make optimal linearizations deterministic (feature)

Public commit record

What the developer wrote

Authored by Pieter Wuille

78/100 · Adequate
clusterlin: make optimal linearizations deterministic (feature)

This allows passing in a fallback order comparator to Linearize(), which
is used as final tiebreak when deciding the order of chunks and
transactions within a chunk, rather than a random tiebreak.

The order of transactions within a chunk becomes:
1. Topology (parents before children)
2. Individual transaction feerate (high to low)
3. Weight (small to large)
4. Fallback (low to high fallback order)

The order of chunks within a cluster becomes:
1. Topology (chunks after their dependencies)
2. Feerate (high to low)
3. Weight (small to large)
4. Max-fallback (chunk with lowest maximum-fallback-tx first)

For now, txgraph passes a naive comparator to Linearize(), which makes
the cluster order deterministic when treating the input transactions as
identified by the DepGraphIndex. However, since DepGraphIndexes are the
result of possibly-randomized operations inside txgraph, this doesn't
actually make txgraph's per-cluster ordering deterministic. That will be
changed in a later commit, by using a txid-based fallback instead.
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Names security-relevant behavior explicitly
The short version

What changed, and why it matters

This commit removes random tie-breaking when Bitcoin Core's transaction-cluster linearization algorithm orders equal-feerate transactions or chunks. It replaces the random choice with a deterministic fallback comparator. The change is described by the author as a feature, not a security fix, and the commit message explicitly notes that txgraph's overall ordering is still not fully deterministic because internal indexes can still be assigned randomly. Tests are updated to expect exact orderings instead of just comparing fee-rate diagrams.

Recommended action

No immediate security action is required. Treat this as a normal feature/refactoring commit. Reviewers may want to verify that the new comparator is indeed a strict weak ordering and that fuzz/bench callers supply a valid comparator, but the change reduces non-determinism rather than introducing a vulnerability.

Security signals we found

01

Removal of random tie-breaking in mempool transaction ordering

02

Introduction of deterministic fallback comparator for linearization

03

Test expectations changed from feerate-diagram equivalence to exact permutation equality

04

Author explicitly labels change as a feature, not a security fix

05

Author notes remaining non-determinism in txgraph because DepGraphIndexes may still be randomized

Risk score

Why this scored 21/100

Our methodology →
Potential impact 2/30
Exploitability 1/25
Stealth signal 1/15
Affected reach 3/15
Confidence 9/10
Evidence quality 5/5
Human-validated context

Community notes

Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.

No validated notes yet.

The AI analysis stands alone for now. Submit a note if you can add evidence or important context.