delvingbitcoin

## Cluster mempool definitions & theory

### Posted on: December 18, 2023 18:11 UTC

Transaction graphs in cluster mempool theory are directed acyclic graphs (DAGs) where vertices represent transactions with associated fees and sizes, connected to denote dependencies.

Clusters within these graphs are connected components allowing bidirectional traversal of transactions. The cumulative fee and size for a subset of transactions are determined by summing individual fees and sizes, from which the feerate is calculated as the total fee divided by the total size.

Linearization is a topologically sorted permutation of transactions, and chunking involves partitioning linearizations into non-overlapping segments adhering to specific conditions, including topological ordering and declining feerates. A corresponding linearization can be derived from chunking and vice versa, with both maintaining order within chunks. Feerate diagrams, representing the relationship between cumulative fees and sizes, are used to compare linearizations or chunkings, with equivalent ones having coinciding diagrams.

Linearizations are evaluated based on their feerate diagrams. A linearization is considered at least as good as another if its diagram is never lower across all sizes. Theorems such as the chunk reordering theorem, prefix stripping theorem, and gathering theorem clarify how modifications to linearizations affect their quality, focusing on preserving topological order and not degrading feerate diagrams. Although merging incomparable linearizations is mentioned, details of this process are not provided.

The merge function combines two linearizations of a graph based on feerates, ensuring that the resulting linearization matches or exceeds the original ones. Variations in the merge algorithm are permissible, as long as they maintain the integrity of the comparison principles established by related theorems. Optimal linearizations and chunkings are defined as those that are superior or equal to all others for a graph, with the existence of an optimal configuration for every graph assured. An optimal linearization can be found using a function that selects the highest-feerate subset and valid linearization based on consistent orderings. Connected chunking must contain components with identical feerates in an optimal configuration, or else the chunk could be split for further optimization.