Linearization (Mempool)

What Is Linearization?

Linearization is the process of arranging related mempool transactions into a topologically valid order that maximizes the total fees a miner can capture within block weight constraints. A topologically valid order means every parent transaction appears before its children in the sequence.

The concept is central to cluster mempool, a redesign of how Bitcoin Core manages unconfirmed transactions. In this framework, connected transactions (those linked by spending relationships) form a cluster, and linearization determines the optimal mining order within each cluster. The result directly impacts how blocks are built, which transactions get evicted when the mempool is full, and how accurately wallets can estimate fees.

How It Works

The linearization algorithm takes a cluster of related transactions and produces an ordered list. The process is iterative:

1. Find the highest-feerate topologically valid subset of the remaining transactions
2. Append those transactions to the output in valid topological order
3. Remove the processed transactions from the cluster
4. Repeat until all transactions have been ordered

Each subset extracted at each step becomes a chunk. By always extracting the highest-feerate valid subset first, the resulting linearization maximizes fee revenue when transactions are mined in that order.

Chunks and the Feerate Diagram

Chunks are the atomic units that emerge from linearization. They are derived by plotting each prefix of the linearization on a feerate diagram (cumulative size on the X-axis, cumulative fee on the Y-axis) and computing the convex hull. Each segment of the convex hull corresponds to one chunk.

Key properties of chunks:

• Chunks have strictly non-increasing feerate: each successive chunk has equal or lower feerate than the previous one
• A chunk respects topology: its transactions can only depend on transactions in earlier (higher-feerate) chunks
• Chunks are the unit of inclusion for block building and the unit of removal for mempool eviction
• The chunk feerate is the total fee divided by the total size of all transactions in that chunk

This chunk-based view provides a single consistent ordering for both mining (select highest-feerate chunks first) and eviction (remove lowest-feerate chunks first), eliminating the inconsistencies of the previous system.

The Linearization Algorithm

At a high level, the core algorithm can be expressed as:

Linearize(cluster):
  result = []
  while transactions remain in cluster:
    best_subset = find_highest_feerate_subset(cluster)
    append best_subset to result (in topological order)
    remove best_subset from cluster
  return result

The critical step is find_highest_feerate_subset. Finding the truly optimal subset was initially conjectured to be NP-hard, but researcher Stefan Richter demonstrated in 2025 that it reduces to the maximum-ratio closure problem, which is solvable in polynomial time via parametric min-cut algorithms. Despite this theoretical result, Bitcoin Core still uses heuristic approaches because the polynomial-time exact solution can be too slow for the microsecond-level time budgets required in real-time mempool management.

Bitcoin Core has iterated through several algorithm generations:

• Ancestor-set-based linearization: the simplest approach, repeatedly extracting the highest ancestor-feerate set as a baseline
• Candidate-set search (CSS): a bounded search using work queues with included, excluded, and potential transaction sets
• LIMO (Linearization through Incremental Merging of Optimizations): a meta-algorithm that improves existing linearizations by comparing multiple strategies
• Spanning-Forest Linearization (SFL): the current algorithm, which converts the problem into one addressable through linear programming and consistently outperforms CSS on real mempool data

Bitcoin Core also employs a merge algorithm that combines two linearizations into an output that dominates both, plus a PostLinearize step that further refines the result through front-to-back and back-to-front passes.

Comparison with the Previous Approach

Before cluster mempool, Bitcoin Core used two separate orderings that could conflict:

• For mining (block building): transactions were selected by highest ancestor feerate
• For eviction (mempool full): transactions were removed by lowest descendant feerate

These were independent approximations with different failure modes. The system could evict high-value transactions that should have been kept, or fail to correctly evaluate complex CPFP chains where multiple children pay for the same parent. Additionally, blunt limits of 25 ancestors and 25 descendants constrained legitimate transaction chains.

Cluster mempool replaces these conflicting heuristics with a single chunk-based ordering. Mining selects the highest-feerate chunks; eviction removes the lowest-feerate chunks. The ancestor and descendant count limits are replaced by cluster-level limits (currently 64 transactions and 101 kvB per cluster), which are less restrictive for most use cases.

Use Cases

Block Template Construction

With linearized clusters, building a block template becomes a straightforward merge across cluster chunks. The algorithm iterates through all clusters, picks the chunk with the highest available feerate, and adds it to the block until the block is full. When a chunk does not fit entirely in the remaining block space, sub-chunk granularity allows breaking it into smaller "absorption sets" to fill remaining space more efficiently.

Block revenue improvement from cluster mempool linearization is estimated at 2-5% per block compared to the old ancestor-feerate approach. For more detail on how block construction works, see our research on block template construction.

Fee Estimation

Accurate fee estimation depends on understanding the competitive ordering of transactions in the mempool. Linearization provides the actual order in which transactions are expected to be mined, taking into account the full chunk of transactions that would be included together. This is more faithful to miner behavior than the old ancestor-feerate approximation, leading to more accurate fee predictions for wallet software. See our comparison of fee estimation algorithms for a deeper analysis.

CPFP Handling

Linearization naturally handles child-pays-for-parent scenarios. When a low-fee parent is paired with a high-fee child, they are grouped into the same cluster and typically the same chunk. The chunk feerate reflects their combined economics, so the child's high fee effectively pulls the parent into the block. Complex CPFP chains with multiple children paying for the same parent are evaluated correctly, which was a weakness of the old ancestor-feerate system.

The old CPFP carveout rule (which allowed one additional child to bypass descendant limits) was eliminated in Bitcoin Core 31.0 because the cluster framework handles these cases natively. For background on fee bumping strategies, see our guide to RBF and CPFP.

Replace-By-Fee Evaluation

Linearization enables more precise replace-by-fee evaluation. Bitcoin Core 31.0 requires that a replacement transaction strictly improves the mempool's overall feerate diagram. This is a stronger and more principled criterion than the previous set of ad hoc RBF rules, reducing the risk of transaction pinning attacks.

Mempool Eviction

When the mempool reaches capacity, linearization determines which transactions to remove. The system evicts the lowest-feerate chunks first, ensuring that the most economically valuable transactions are retained. Because this uses the same chunk ordering as mining, eviction decisions are fully consistent with block building priorities.

Why It Matters

Linearization is a foundational improvement to Bitcoin's fee market infrastructure. By providing a unified, consistent ordering for all mempool operations, it solves several long-standing issues:

• Miners capture more revenue from each block through better transaction ordering
• Wallets provide more accurate fee estimates, reducing overpayment and confirmation delays
• Mempool eviction is consistent with mining priority, preventing economically irrational behavior
• Complex transaction topologies (CPFP chains, batched transactions) are evaluated correctly
• The framework creates a foundation for improved relay policies and pinning resistance

For Layer 2 protocols like the Lightning Network and Spark, better linearization translates to more predictable fee bumping for commitment transactions and more reliable on-chain settlement. The removal of ancestor and descendant count limits also benefits protocols that create complex transaction chains. For a comprehensive overview of the cluster mempool redesign, see our cluster mempool explainer.

Risks and Considerations

Computational Overhead

Linearization adds computational work to mempool management. While the current SFL algorithm performs well on real mempool data, clusters with very high dependency density can still be expensive to linearize. Bitcoin Core mitigates this through cluster size limits and time budgets that bound worst-case computation.

Cluster Size Limits

The cluster mempool design imposes limits of 64 transactions and 101 kvB per cluster. While less restrictive than the old 25/25 ancestor/descendant limits for most use cases, these constraints can still affect protocols that create large transaction graphs. Transactions that would exceed cluster limits are rejected from the mempool.

Heuristic Approximations

Despite the theoretical possibility of exact polynomial-time solutions, Bitcoin Core relies on heuristic algorithms for practical performance. This means linearizations are near-optimal rather than guaranteed optimal. The merge and post-processing steps help close the gap, and the LIMO meta-algorithm ensures output quality never degrades below the ancestor-set baseline.

Network-Wide Consistency

Different nodes may produce slightly different linearizations for the same cluster, since the heuristic algorithms are non-deterministic. This does not affect consensus (block validity is independent of mempool ordering), but it means that fee estimation and relay behavior can vary across the network during the transition period as nodes upgrade.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.