<h3>What issues exist with the mempool data structure?</h3>
<p>The current mempool design organizes each transaction based on its ancestor set. This leads to a <a href="https://delvingbitcoin.org/t/mempool-incentive-compatibility/553" rel="nofollow noreferrer">number of issues</a>, e.g.:</p>
<ul>
<li>Ancestor sets overlap: one transaction can be featured in many ancestor sets. Picking a transaction into a block template requires updating all descendant transactions’ ancestor sets.</li>
<li>We cannot easily determine the effective feerate at which a transaction will be selected into a block. We need to evaluate all related transactions in order to determine the feerate at which a specific transaction would be picked into a block.</li>
<li>We build block templates by repeatedly picking the ancestor set with the highest ancestor set feerate. When our mempool data structure exceeds its limit, we repeatedly evict the descendant set with the lowest descendant set feerate. These two evaluations are not perfect opposites, and it is possible for transactions to be both in an ancestor set with a high feerate and a descendant set with a low feerate. Instead we would like to evict the transactions that will be picked into a block last. We would need to structure the entire mempool into blocks every time we evict to find out which transaction would be picked last. This is computationally expensive and causes is to stick to the imperfect descendant set feerate heuristic.</li>
<li>Given that it is hard to determine at what effective feerate transactions will be picked into blocks, it is difficult to determine whether a potential replacement is better, worse, or incomparable to the original. The current RBF rules allow for some edge cases in which we accept replacements that are not clearly better, and rejects some replacements that are better.</li>
<li>A parent transaction with two higher feerate child transactions is interpreted as two competing ancestor sets.</li>
</ul>
<h4>How does the <a href="https://delvingbitcoin.org/t/an-overview-of-the-cluster-mempool-proposal/393" rel="nofollow noreferrer">Cluster Mempool proposal</a> address these issues?</h4>
<p>Where the old mempool data structure tracked transactions in the context of overlapping ancestor sets, Cluster Mempool tracks transactions in the context of <em>clusters</em>. A cluster is a <a href="https://en.wikipedia.org/wiki/Component_(graph_theory)" rel="nofollow noreferrer">component</a> in the graph of unconfirmed transactions, i.e. a maximal subgraph of transactions connected via child-parent relationships. You can identify a transaction’s cluster by adding all of its ancestors and descendants, and then adding all of the newly added transactions’ relatives until there are no more to add. Each transaction is part of exactly one cluster.</p>
<p>For each cluster, we keep a <a href="https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032" rel="nofollow noreferrer">linearization</a>. The linearization represents a topologically valid (preferably optimal) order in which the transactions would get picked into a block. The linearization is split into chunks of transactions that would get picked into a block together. Each transaction is part of exactly one chunk, and we can calculate the effective feerate of a chunk based on its members by simply adding up their fees and weights.</p>
<ul>
<li>Because transactions are part of exactly one chunk, no other chunks have to be recalculated when a chunk is picked into a block</li>
<li>We can directly read the effective feerate of every transaction per its chunk feerate.</li>
<li>Block building is simplified to comparing the (remaining) first chunks of each cluster, and popping the highest feerate chunk off the cluster into the template. The remaining chunks in the affected cluster do not need to be updated.</li>
<li>As the transactions are all grouped into clusters and the clusters are ordered, we implicitly have an order on the entire mempool. This means we can easily identify the transactions that would get mined last by comparing the last chunks in each cluster. We just need to evict the chunk with the lowest chunk feerate across all clusters.</li>
<li>Tracking transactions in the context of all their relatives in a linearized fashion offers &quot;the feerate diagram&quot; metric for evaluating replacements. This method of comparing is applicable to packages, which has led to breakthroughs in package relay and package-RBF.</li>
<li>A parent transaction with two higher feerate child transactions will be interpreted as a single chunk with a higher chunk feerate than either child’s ancestor set.</li>
</ul>
<h3>Are there any conclusive numbers on how much more transaction fees will be captured with such overhaul or is it just all theoretical at this point?</h3>
<p>This is difficult to answer. If a sequence of transaction submissions were processed into blocks per the ancestor set-based (ASB) mempool design or the cluster mempool design, the total amount of fees would remain the same—just their order would change. If however some miners use ASB mempool and some miners use cluster mempool, the cluster mempool miners may be able to collect a slightly increased block reward by discovering chunks with higher feerates than the ancestor sets ASB miners are considering. Prior related research <a href="https://gist.github.com/murchandamus/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-building-md" rel="nofollow noreferrer">suggests</a> that most blocks would only have a minuscule reward increase, but the new mempool design could encourage transaction patterns that increase the block reward of cluster mempool miners. Simulations suggest that cluster mempool generally performs at least as well as ASB mempool in regards to block rewards.</p>
<h3>How will this be finally rolled out? Opt-in or will be just a replacement in a new node client version?</h3>
<p>Cluster mempool is a drop-in replacement. The most significant changes in mempool policy would be the replacement of the ancestor and descendant limits with cluster size limits (count and total weight). This may affect some users that create long chains of transactions or other large clusters (which IMHO usually are indicators of poor operational practices, e.g. processing a large payment volume but not batching payments). The node itself would perform better at various tasks as outlined above. It may participate in package relay when that ships, and evict transactions in a slightly different order than its peers. If broadly adopted, cluster mempool may make descendants-pay-for-ancestor transaction patterns more viable, i.e. where two child transactions paying for the same parent currently compete, they would compound in a cluster mempool. This may e.g. improve outcomes of transactions spending unconfirmed outputs of batch transactions. Other that that it should not noticeable affect peer interactions, especially I would not expect any issues for nodes with ASB mempools peering with cluster mempool nodes or vice versa.</p>
<h3>Why is restructure of mempool required with cluster mempool?</h3>
<p>I’m not entirely sure how you mean your titular question, so let me cover a few angles:
Cluster mempool is not a <em>required</em> update. Any of the above improvements could be implemented with the existing mempool data structure, but overhauling the data structure allows use to get reasonable run-time performance on the new features. Beyond that,
restructuring the mempool to be designed around clusters instead of ancestor sets provides a superior abstraction that should simplify the code base around interactions with the mempool. There are many reasons why we want to always know the effective feerate of every transaction. Cluster mempool is a compelling upgrade because it provides efficient algorithms to maintain this information as well as making on-going projects like work on package relay easier to reason about.</p>

CC BY-SA 4.0
2024-07-18T15:04:18.063Z
2024-07-19T15:58:07.007Z
2024-07-19T15:58:07.007Z
Murch
<p>This is a follow up question from the comments in the answer of this <a href="https://bitcoin.stackexchange.com/questions/123679/why-do-protocol-developers-work-on-maximizing-miner-revenue/123680#123680">question</a>:</p>
<ul>
<li>What is wrong with the current mempool data structure that it requires a complete overhaul?</li>
<li>Are there any conclusive numbers on how much more transaction fees will be captured with such overhaul or is it just all theoretical at this point?</li>
<li>How will this be finally rolled out? Opt-in or will be just a replacement in a new node client version?</li>
</ul>

<mining-theory><unconfirmed-transactions><mempool>
Why is restructure of mempool required with cluster mempool?
WhoIsNinja
# Why is restructure of mempool required with cluster mempool?

(Asked by: username_0 on 2024-07-17)

This is a follow up question from the comments in the answer of this [question](https://bitcoin.stackexchange.com/questions/123679/why-do-protocol-developers-work-on-maximizing-miner-revenue/123680#123680):

* What is wrong with the current mempool data structure that it requires a complete overhaul?
* Are there any conclusive numbers on how much more transaction fees will be captured with such overhaul or is it just all theoretical at this point?
* How will this be finally rolled out? Opt-in or will be just a replacement in a new node client version?

**Tags:** mining-theory, unconfirmed-transactions, mempool


---

## 1 answers

### Answer by username_1 on 2024-07-18. Score: 9 | Accepted answer

### What issues exist with the mempool data structure?

The current mempool design organizes each transaction based on its ancestor set. This leads to a [number of issues](https://delvingbitcoin.org/t/mempool-incentive-compatibility/553), e.g.:

* Ancestor sets overlap: one transaction can be featured in many ancestor sets. Picking a transaction into a block template requires updating all descendant transactions’ ancestor sets.
* We cannot easily determine the effective feerate at which a transaction will be selected into a block. We need to evaluate all related transactions in order to determine the feerate at which a specific transaction would be picked into a block.
* We build block templates by repeatedly picking the ancestor set with the highest ancestor set feerate. When our mempool data structure exceeds its limit, we repeatedly evict the descendant set with the lowest descendant set feerate. These two evaluations are not perfect opposites, and it is possible for transactions to be both in an ancestor set with a high feerate and a descendant set with a low feerate. Instead we would like to evict the transactions that will be picked into a block last. We would need to structure the entire mempool into blocks every time we evict to find out which transaction would be picked last. This is computationally expensive and causes is to stick to the imperfect descendant set feerate heuristic.
* Given that it is hard to determine at what effective feerate transactions will be picked into blocks, it is difficult to determine whether a potential replacement is better, worse, or incomparable to the original. The current RBF rules allow for some edge cases in which we accept replacements that are not clearly better, and rejects some replacements that are better.
* A parent transaction with two higher feerate child transactions is interpreted as two competing ancestor sets.

#### How does the [Cluster Mempool proposal](https://delvingbitcoin.org/t/an-overview-of-the-cluster-mempool-proposal/393) address these issues?

Where the old mempool data structure tracked transactions in the context of overlapping ancestor sets, Cluster Mempool tracks transactions in the context of *clusters*. A cluster is a [component](https://en.wikipedia.org/wiki/Component_(graph_theory)) in the graph of unconfirmed transactions, i.e. a maximal subgraph of transactions connected via child-parent relationships. You can identify a transaction’s cluster by adding all of its ancestors and descendants, and then adding all of the newly added transactions’ relatives until there are no more to add. Each transaction is part of exactly one cluster.

For each cluster, we keep a [linearization](https://delvingbitcoin.org/t/introduction-to-cluster-linearization/1032). The linearization represents a topologically valid (preferably optimal) order in which the transactions would get picked into a block. The linearization is split into chunks of transactions that would get picked into a block together. Each transaction is part of exactly one chunk, and we can calculate the effective feerate of a chunk based on its members by simply adding up their fees and weights.

* Because transactions are part of exactly one chunk, no other chunks have to be recalculated when a chunk is picked into a block
* We can directly read the effective feerate of every transaction per its chunk feerate.
* Block building is simplified to comparing the (remaining) first chunks of each cluster, and popping the highest feerate chunk off the cluster into the template. The remaining chunks in the affected cluster do not need to be updated.
* As the transactions are all grouped into clusters and the clusters are ordered, we implicitly have an order on the entire mempool. This means we can easily identify the transactions that would get mined last by comparing the last chunks in each cluster. We just need to evict the chunk with the lowest chunk feerate across all clusters.
* Tracking transactions in the context of all their relatives in a linearized fashion offers "the feerate diagram" metric for evaluating replacements. This method of comparing is applicable to packages, which has led to breakthroughs in package relay and package-RBF.
* A parent transaction with two higher feerate child transactions will be interpreted as a single chunk with a higher chunk feerate than either child’s ancestor set.

### Are there any conclusive numbers on how much more transaction fees will be captured with such overhaul or is it just all theoretical at this point?

This is difficult to answer. If a sequence of transaction submissions were processed into blocks per the ancestor set-based (ASB) mempool design or the cluster mempool design, the total amount of fees would remain the same—just their order would change. If however some miners use ASB mempool and some miners use cluster mempool, the cluster mempool miners may be able to collect a slightly increased block reward by discovering chunks with higher feerates than the ancestor sets ASB miners are considering. Prior related research [suggests](https://gist.github.com/murchandamus/5cb413fe9f26dbce57abfd344ebbfaf2#file-candidate-set-based-block-building-md) that most blocks would only have a minuscule reward increase, but the new mempool design could encourage transaction patterns that increase the block reward of cluster mempool miners. Simulations suggest that cluster mempool generally performs at least as well as ASB mempool in regards to block rewards.

### How will this be finally rolled out? Opt-in or will be just a replacement in a new node client version?

Cluster mempool is a drop-in replacement. The most significant changes in mempool policy would be the replacement of the ancestor and descendant limits with cluster size limits (count and total weight). This may affect some users that create long chains of transactions or other large clusters (which IMHO usually are indicators of poor operational practices, e.g. processing a large payment volume but not batching payments). The node itself would perform better at various tasks as outlined above. It may participate in package relay when that ships, and evict transactions in a slightly different order than its peers. If broadly adopted, cluster mempool may make descendants-pay-for-ancestor transaction patterns more viable, i.e. where two child transactions paying for the same parent currently compete, they would compound in a cluster mempool. This may e.g. improve outcomes of transactions spending unconfirmed outputs of batch transactions. Other that that it should not noticeable affect peer interactions, especially I would not expect any issues for nodes with ASB mempools peering with cluster mempool nodes or vice versa.

### Why is restructure of mempool required with cluster mempool?

I’m not entirely sure how you mean your titular question, so let me cover a few angles:
Cluster mempool is not a *required* update. Any of the above improvements could be implemented with the existing mempool data structure, but overhauling the data structure allows use to get reasonable run-time performance on the new features. Beyond that,
restructuring the mempool to be designed around clusters instead of ancestor sets provides a superior abstraction that should simplify the code base around interactions with the mempool. There are many reasons why we want to always know the effective feerate of every transaction. Cluster mempool is a compelling upgrade because it provides efficient algorithms to maintain this information as well as making on-going projects like work on package relay easier to reason about.


---

