Advanced Mempool & Policy

Cluster Mempool

Chapter 6 introduced the mempool as a pool of unconfirmed transactions. This chapter goes deeper into how the mempool actually orders those transactions for mining, eviction, and relay. The modern approach is called cluster mempool.

The Problem with Ancestor Sets

The traditional mempool tracked "ancestor fee rate" for each transaction: the combined fee rate of a transaction and all its unconfirmed ancestors. This had serious problems:

• Ancestor fee rate is not optimal: it can overcount or undercount the actual mining priority when transactions have complex dependency structures.
• Eviction was inconsistent with mining: the mempool might evict a transaction that a miner would have included, or keep one a miner would skip.
• RBF incentive checks were fragile: determining whether a replacement truly improves the mempool required heuristics that could fail.

Clusters and Connected Components

The cluster mempool redesign groups transactions into clusters: connected components in the dependency graph. If transaction A is an ancestor or descendant of transaction B (through any chain of parent-child relationships), they belong to the same cluster.

Bitcoin Core enforces a cluster size limit (currently 64 transactions). This bounds the computational cost of optimizing transaction ordering within each cluster.

Transaction Linearization

Once transactions are grouped into clusters, each cluster needs a linearization: a total ordering of its transactions that respects dependencies (parents before children) and optimizes for fee rate.

Why Linearization Matters

A miner filling a block wants to include the highest-fee-rate transactions first. But dependencies complicate this: you can't include a child without its parent. Linearization solves this by finding the best order to process transactions.

Chunks

A linearization is divided into chunks: groups of consecutive transactions that would be mined together. Each chunk has a fee rate (total fees / total size), and chunks are ordered by decreasing fee rate.

The DepGraph Data Structure

The linearization algorithms work on a DepGraph (dependency graph): a template class in cluster_linearize.h that stores:

• Fee and size: for each transaction (as a FeeFrac)
• Ancestor sets: bitmask of all ancestors (including self)
• Descendant sets: bitmask of all descendants (including self)

Using bitmasks (SetType) for ancestor/descendant sets allows extremely fast subset operations, intersections, and unions: all O(1) with bitwise operators.

The Search Algorithm

Finding the optimal linearization is NP-hard in general. Bitcoin Core uses a bounded search algorithm that:

1. Starts with a seed: the highest individual fee rate transaction (plus its ancestors) as the initial "best" chunk candidate.
2. Explores improvements: tries adding/removing transactions to find a higher fee rate subset.
3. Respects a budget: the search is bounded by an iteration limit to keep it fast.
4. Produces optimal or near-optimal results: for small clusters (≤ ~16 transactions), the search finds the true optimum; for larger clusters, it produces a good approximation.

TxGraph: The Mempool's Core Data Structure

TxGraph (defined in txgraph.h) is the data structure that manages all the clusters, their linearizations, and the transactions within them.

Key Design Features

• Staging: TxGraph supports a "staging" layer, a tentative set of changes (additions, removals) that can be committed or discarded atomically. This is essential for evaluating whether an RBF replacement actually improves the mempool before committing to it.
• Lazy evaluation: linearizations are recomputed only when needed, not on every transaction addition.
• Ref-based ownership: each transaction has a TxGraph::Ref object; destroying the Ref removes the transaction. Users can inherit from Ref to attach application-specific data.

Core Operations

TRUC (v3) Transactions

TRUC transactions (Topologically Restricted Until Confirmation), defined in BIP 431, are a special transaction version (nVersion = 3) with strict topology rules that make RBF replacements more predictable.

The Problem TRUC Solves

Lightning Network and other Layer 2 protocols need to broadcast "commitment transactions" that can be fee-bumped reliably. With normal transactions, complex dependency chains (parent-child-grandchild) make RBF unpredictable and sometimes impossible. TRUC constrains the topology to make fee-bumping always work.

TRUC Rules

How TRUC Enables Fee Bumping

Because a TRUC transaction can only have one child, replacing that child (via RBF) is simple and always works:

Sibling Eviction

If a TRUC parent already has a child, and a new higher-fee child arrives, the mempool can evict the existing child to make room for the new one. This "sibling eviction" is safe because TRUC guarantees only one child exists.

Ephemeral Anchors

Ephemeral anchors build on TRUC to enable a powerful fee-bumping pattern for Layer 2 protocols. The idea is simple: a parent transaction can have zero fees and a dust output, as long as a child immediately spends that dust.

How It Works

1. Parent transaction (0 fee): creates a dust output (the "anchor") using an OP_TRUE or anyone-can-spend script. The parent has no fee, making it unmineable on its own.
2. Child transaction (brings fee): spends the anchor output, providing all the fees for both transactions. The child must spend ALL dust outputs from the parent.

Safety Guarantees

• Dust never enters UTXO set: the parent can't be mined without its child (it has zero fee), and the child must spend the dust, so the dust output is created and consumed in the same block.
• Single child only: enforced by TRUC rules, preventing partial dust spending.
• PreCheckEphemeralTx: rejects any transaction with non-zero fee that contains dust outputs. Zero fee + dust is only allowed because it requires a fee-paying child.

Package RBF

Package RBF extends Replace-By-Fee from single transactions to packages (parent + child submitted together). This solves the problem where a parent transaction's fee is too low to enter the mempool on its own.

How Package RBF Works

1. Submit parent + child as a package: the parent may be below the minimum relay fee, but the child's fee compensates.
2. Evaluate as a unit: the package fee rate (combined fee / combined size) is checked against what it replaces.
3. Replace existing conflicts: if the package fee rate is high enough, it replaces conflicting transactions.

Why This Matters for Layer 2

TRUC + ephemeral anchors + package relay together solve one of the hardest problems in Layer 2 protocol design: reliable fee bumping for pre-signed transactions.