# Cluster mempool definitions & theory

**URL:** <https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202>\
**Category:** Implementation\
**Tags:** wg-cluster-mempool\
**Created:** [November 17, 2023, 2:40am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202 "2023-11-17T02:40:41Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [November 17, 2023, 2:40am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/1 "2023-11-17T02:40:41Z")

</div>

# Cluster mempool theory

 

## Transaction graphs and clusters

_ **Definition** _. A **transaction graph** , or in cluster mempool context, just **graph** , is a [directed acyclic graph](https://en.wikipedia.org/wiki/Directed_acyclic_graph) (DAG), with _n_ vertices (also called **transactions** ), where each vertex is labelled with a **fee** (an integer) and a **size** (a strictly positive integer). If an edge from node _c_ to node _p_ exists, _p_ is called a **parent** or **dependency** of _c_, and _c_ a **child** of _p_. In other words, transaction graphs are dependency graph whose vertices point to their dependencies.

_ **Definition** _. Given a graph _G_ and a transaction _x_ in it, the **ancestor set** \operatorname{anc}\_G(x) of _x_ is the set of all transactions which can be [reached](https://en.wikipedia.org/wiki/Reachability) from _x_ (this always includes _x_ itself). For sets S, we define \operatorname{anc}\_G(S) = \cup\_{x \in S} \operatorname{anc}\_G(x), the union of the ancestor sets of all the transactions in the set.

_ **Definition** _. Given a graph _G_ and a transaction _x_ in it, the **descendant set** \operatorname{desc}\_G(x) of _x_ is the set of all transactions from which _x_ can be reached. For sets S, we define \operatorname{desc}\_G(S) = \cup\_{x \in S} \operatorname{desc}\_G(x), the union of the descendant sets of all the transactions in the set.

_ **Definition** _. A **cluster** is a [connected component](https://en.wikipedia.org/wiki/Component_(graph_theory)) of a graph _ignoring direction_. In other words, for any two transactions in a cluster it is possible to go from one to the other by making a sequence of steps, each traveling along an edge in either forward or backward direction. The clusters of a graph form a [partition](https://en.wikipedia.org/wiki/Partition_of_a_set) of its vertices, and the **cluster of a transaction** is the connected component which that transaction is part of. It can be found as the [transitive closure](https://en.wikipedia.org/wiki/Transitive_closure) of the “is parent or child of” relation on the singleton of the given transaction.

Consider the transaction graph below (fees and sizes are omitted):

```mermaid
graph BT
   t5["t<sub>5</sub>"] --> t2["t<sub>2</sub>"];
   t6["t<sub>6</sub>"] --> t2;
   t6 --> t3["t<sub>3</sub>"] --> t1["t<sub>1</sub>"];
   t7["t<sub>7</sub>"] --> t4["t<sub>4</sub>"];

```

In this example there are two clusters: \{t\_1, t\_2, t\_3, t\_5, t\_6\} and \{t\_4, t\_7\}.

_ **Definition** _. Given a subset S of nodes of a graph, define the following functions:

- \operatorname{fee}(S) = \sum\_{x \in S} \operatorname{fee}\_x: the sum of fees of transactions in S.
- \operatorname{size}(S) = \sum\_{x \in S} \operatorname{size}\_x: the sum of sizes of transactions in S.
- \operatorname{feerate}(S) = \operatorname{fee}(S) / \operatorname{size}(S): the sum of the fees divided by the sum of the sizes of transactions in S. Only defined for non-empty sets S.

## Linearizations and chunks

_ **Definition** _. A **topological subset** S of a graph G is a subset of its transactions that includes all ancestors of all its elements. In other words, S is topological subset of G iff \operatorname{anc}\_G(S) = S.

_ **Definition** _. A **linearization** L for a given graph G is a permutation of its transactions in which parents appear before children. In other words, L = (t\_1, t\_2, \ldots, t\_n) is a linearization of G if \{t\_1, t\_2, \ldots, t\_k\} is a topological subset of G for all k = 1 \ldots n. A linearization is thus a [topological sort](https://en.wikipedia.org/wiki/Topological_sorting) of the graph vertices.

In the example above:

- (t\_1, t\_2, t\_3, t\_4, t\_5, t\_6, t\_7) is a valid linearization.
- (t\_2, t\_5, t\_1, t\_3, t\_6, t\_4, t\_7) is a valid linearization.
- (t\_1, t\_3, t\_6, t\_2, t\_5, t\_4, t\_7) is not (t\_6 is included before its parent t\_2).

_ **Definition** _. Given a linearization L for a graph G, and a subset S of G, the **sublinearization** L[S] is the linearization of S which keeps the same internal ordering as those transactions have in L.

_ **Definition** _. A **chunking** C = (c\_1, c\_2, \ldots, c\_n) for a given graph _G_ is a sequence of sets of transactions (called **chunks** ) of _G_ such that:

- The chunks c\_i form a partition of _G_ (no overlap, and their union contains all elements).
- Every prefix of chunks is topological (\cup\_{i=1}^{k} c\_i for k=1 \ldots n are topological subsets of G). Thus, a transaction’s parent can appear in the same chunk as the transaction itself or in an earlier chunk, but not in a later chunk.
- The feerates of the sets are monotonically decreasing.

Note that in practice, we will only work with chunkings of individual clusters, rather than possibly-disconnected graphs. The reasoning for that will come later, so for now, we define chunkings for graphs in general.

_ **Definition** _. The function \operatorname{chunks}(L) for a linearization L = (t\_1, t\_2, \ldots, t\_n) of a graph G returns the **corresponding chunking** of that linearization, defined as:

- If L (and thus G) is empty, \operatorname{chunks}(L) = ().
- Otherwise:
  - Let f\_j = \operatorname{feerate}(\{t\_1, t\_2, \ldots, t\_j) for j = 1 \ldots n.
  - Let k be the smallest integer \geq 1 such that no f\_j \> f\_k exists.
  - Let c = \{t\_1, t\_2, \ldots, t\_k\}.
  - \operatorname{chunks}(L) = (c) + \operatorname{chunks}(L[\{t\_{k+1}, \ldots n\}]).

In other words, \operatorname{chunks} constructs the chunking of a linearization consisting of successively best remaining prefixes of that linearization.

_ **Theorem** _. The corresponding chunking \operatorname{chunks}(L) is a valid chunking for G.

_ **Proof** _. All criteria for a valid chunking are fulfilled:

- All transactions that occurred in L (which are all transactions in G) will appear in \operatorname{chunks}(L) once.
- Every prefix of chunks is topological, because each corresponds to a prefix of L (which are topological for any valid linearization).
- The feerates are monotonically decreasing. If that wasn’t the case, the chosen k would violate the “no f\_j \> f\_k” rule.

_ **Theorem** _. The **feerate of a prefix of a linearization never exceeds its first chunk feerate**. If it did, the first chunk would clearly not be the highest-feerate prefix of the linearization.

_ **Theorem** _. The **feerate of a suffix of a linearization is never less than its last chunk feerate**. This is true within the last chunk, because if there was a suffix of the last chunk with lower feerate than that chunk, that suffix could be split off, and the feerate of the part before it would go up. It is also true across multiple chunks, because if a suffix can’t have a lower feerate than the last chunk, then extended the suffix to a chunk before it (whose maximum suffix feerate is even higher) cannot change that property.

_ **Definition** _. We also define a **corresponding linearization of a chunking** as a linearization consisting of a concatenation of the chunks, in order, and within each chunk ordered topologically. This correspondence is not unique (because there can be multiple topological sorts of the chunk elements), but all corresponding linearizations of a chunking have the original chunking as corresponding chunking (or a strictly better one) Due to the simplicity of converting between chunking and linearization, we can often treat them as the same.

_ **Definition** _. Given a chunking C = (c\_1, c\_2, \ldots, c\_n), its **feerate diagram** \operatorname{diag}\_C is a real function with domain [0, \operatorname{size}(c\_1 \cup c\_2 \cup \ldots c\_n)], defined as follows:

- Let \gamma\_i = \cup\_{j=0}^{i} c\_j for i=0 \ldots n, the union of all transactions in the first i chunks.
- For all i = 0 \ldots n-1 and \alpha \in [0,1]:
  - \operatorname{diag}\_C(\operatorname{size}(\gamma\_i) + \alpha \operatorname{size}(c\_{i+1})) = \operatorname{fee}(\gamma\_i) + \alpha \operatorname{fee}(c\_{i+1}).

- In other words, \operatorname{diag}\_C is a function from cumulative fees to cumulative sizes. When evaluated in the size of a prefix of chunks in C, it gives the fee in that prefix. For other values it linearly interpolates between those points.
- The feerate diagram of a linearization is that of its corresponding chunking.

_ **Theorem** _. The feerate diagram \operatorname{diag}\_L of a linearization L = (t\_1, t\_2, \ldots, t\_n) is the minimal concave function for which for every k = 0 \ldots n it holds that \operatorname{diag}\_L(\operatorname{size}(\{t\_1, t\_2, \ldots, t\_k\}) \geq \operatorname{fee}(\{t\_1, t\_2, \ldots, t\_k\}). As such, it gives an overestimate for the fees in all prefixes of a linearization. In other words, the grouping of transactions performed by \operatorname{chunks} exactly corresponds to the straight line segments resulting from requiring the feerate diagram to be concave. [no proof]

_ **Definition** _. We define a **[preorder](https://en.wikipedia.org/wiki/Preorder)** on linearizations/chunkings for the same graph G by comparing their feerate diagrams:

- Two linearizations are equivalent if their feerate diagrams coincide: L\_1 \sim L\_2 \iff \forall x \in [0, \operatorname{size}(G)]: \operatorname{diag}\_{L\_1}(x) = \operatorname{diag}\_{L\_2}(x).
- A linearization is **at least as good** as another if its feerate diagram is never lower than the other’s: L\_1 \gtrsim L\_2 \iff \forall x \in [0, \operatorname{size}(G)]: \operatorname{diag}\_{L\_1}(x) \geq \operatorname{diag}\_{L\_2}(x).
- A linearization is **at least as bad** as another if its feerate diagram is never higher than the other’s: L\_1 \lesssim L\_2 \iff \forall x \in [0, \operatorname{size}(G)]: \operatorname{diag}\_{L\_1}(x) \leq \operatorname{diag}\_{L\_2}(x).
- A linearization is **better** than another if its feerate diagram is never lower than the other’s, and at least somewhere higher: L\_1 \> L\_2 \iff L\_1 \gtrsim L\_2 and not L\_1 \sim L\_2.
- A linearization is **worse** than another if its feerate diagram is never higher than the other’s, and at least somewhere lower: L\_1 \< L\_2 \iff L\_1 \lesssim L\_2 and not L\_1 \sim L\_2.
- Linearizations L\_1 and L\_2 are **incomparable** when neither L\_1 \gtrsim L\_2 nor L\_1 \lesssim L\_2 (and **comparable** when at least one of those relations holds).
- This is not a [partial order](https://en.wikipedia.org/wiki/Partially_ordered_set), because L\_1 \sim L\_2 does not imply L\_1 = L\_2 (distinct linearizations can be equivalent).

## Transformations on linearizations

_ **Theorem** _. The **chunk reordering theorem** : reordering a linearization with changes restricted to a single chunk results leaves it at least as good, provided the result is still a valid linearization (i.e., its prefixes are topological).

_ **Proof** _. Every prefix of chunks in the original linearization remains a prefix of transactions in the new linearization. Because the new feerate diagram is the minimal concave function not below these points, and these points form the old feerate diagram, the new feerate diagram cannot be below the old one.

_ **Theorem** _. The **prefix stripping theorem** : Given two linearizations L\_1 = (t\_1, t\_2, \ldots, t\_n) and L\_2 = (u\_1, u\_2, \ldots, u\_n) for the same graph with a shared prefix: t\_i = u\_i for all i = 1 \ldots k. In this case:

- If the suffix is at least as good, then the whole linearization is at least as good: (t\_{k+1}, t\_{k+2}, \ldots, t\_n) \gtrsim (u\_{k+1}, u\_{k+2}, \ldots, u\_n) \implies L\_1 \gtrsim L\_2.
- If the suffix is at least as bad, then the whole linearization is at least as bad: (t\_{k+1}, t\_{k+2}, \ldots, t\_n) \lesssim (u\_{k+1}, u\_{k+2}, \ldots, u\_n) \implies L\_1 \lesssim L\_2.

_ **Theorem** _. The **gathering theorem**. Moving a sublinearization of transactions to the front of a linearization never worsens the linearization if the sublinearization’s worst chunk feerate is at least that of the linearization’s best chunk feerate (see discussion in [merging incomparable linearizations](https://delvingbitcoin.org/t/merging-incomparable-linearizations/209)):

- Let L be a linearization of a graph G.
- Let C = (c\_1, c\_2, \ldots, c\_n) = \operatorname{chunks}(L).
- Let S be a topologically valid subset of G.
- Let D = (d\_1, d\_2, \ldots, d\_m) = \operatorname{chunks}(L[S]).
- Let L' = L[S] + L[G \setminus S]), the linearization obtained by moving L[S] to the front.

In this case, \operatorname{feerate}(d\_m) \geq \operatorname{feerate}(c\_1) \implies L' \gtrsim L.

_ **Proof** _.

- Let f = \operatorname{feerate}(c\_1), the feerate of the highest-feerate prefix of L.
- Let e\_j = c\_j \cap S for j=1 \ldots n, the S transactions in chunk j of L. Note that this is distinct from d\_j because e\_j follows the chunk boundaries of L, while d\_j follows the boundaries of L[S].
- Let \gamma\_j = \cup\_{i=1}^{j} c\_i for j=1 \ldots n, the transactions in the first j chunks of L.
- Let \zeta\_j = \cup\_{i=j+1}^{n} e\_i for j = 1 \ldots n, all remaining transactions of S _after_ the first j chunks of L.
- Let P(x) = (\operatorname{size}(x), \operatorname{fee}(x)), the point in 2D space corresponding to the size and fee of set x.
- We know \operatorname{feerate}(c\_j) \leq f for j=1 \ldots n, because chunk feerate decrease monotonically.
- We know \operatorname{feerate}(\zeta\_j) \geq f for j=0 \ldots n-1, because feerates of the suffix of a linearization (L[S] in this case) are never below the last chunk’s feerate.
- Thus, \operatorname{feerate}(\zeta\_j) \geq \operatorname{feerate}(c\_k) for any j, k where those values are defined.
- Define \operatorname{ndiag}(x) as the real function that linearly interpolates through (0,0) and through all (P(\gamma\_j \cup \zeta\_j))\_{j=0}^{n} (the set of chunk prefixes of $L plus all transactions from S).
- \operatorname{ndiag} is not \operatorname{diag\_{L'}}, the feerate diagram of L', because it doesn’t follow the proper chunking of L'. It is however a valid underestimate of it: \forall x \in [0, \operatorname{size}(G)] : \operatorname{ndiag}(x) \leq \operatorname{diag\_{L'}}. This is because:
  - \operatorname{diag\_{L'}} is the minimal concave function through the P points for all prefixes of L'.
  - \operatorname{ndiag} is the minimal concave function through the P points for some prefixes of L' (those corresponding to the chunk prefixes of L, plus all transactions of S).

In what follows, we will show that \forall x \in [0,\operatorname{size}(G)]: \operatorname{ndiag}(x) \geq \operatorname{diag\_L}(x), and thus by extension that \operatorname{diag\_{L'}}(x) \geq \operatorname{diag}(x), or L' \gtrsim L.

In the drawing below, the red line represents \operatorname{diag}\_L, while the blue line (plus the green \zeta\_0 segment) represents \operatorname{ndiag}. Intuitively, the blue line lies above (or on) the red line everywhere because the slope of every the green \zeta\_j segments between red and blue is at least as high as that of any red c\_j segment.

 ![gather_theorem](https://delvingbitcoin.org/uploads/default/original/1X/b79f64bc357702b659cbc32e652091b19d42e874.png)

\operatorname{diag\_L} is a concave function, which means it lies on or below each of its tangents. This implies that a point lies on or above the function iff it lies on or above at least one of its tangents. For every point on \operatorname{ndiag} we will identify a tangent of \operatorname{diag\_L} that it lies on or above. As that function is made up of straight segments, its tangents are exactly these segments, extended to infinity in both directions.

- The points \{\forall \alpha \in [0, 1]: \alpha P(\zeta\_0)\} lie on the first segment of \operatorname{ndiag}. We show they lie on or above the (extension of the) c\_1 segment of \operatorname{diag}(L).
  - For \alpha=0, the functions coincide at (0, 0).
  - For \alpha \> 0, the slope from (0,0) to P(\gamma\_1) is \operatorname{feerate}(c\_1) = f. The slope of the line from (0,0) to \alpha P(\zeta\_0) is \operatorname{feerate}(\zeta\_0) \geq f , which is at least as high.

- For i=0 \ldots n-1, the points \{\forall \alpha \in [0, 1]: (1-\alpha)P(\gamma\_i \cup \zeta\_i) + \alpha P(\gamma\_{i+1} \cup \zeta\_{i+1})\} lie on \operatorname{ndiag}. We show they lie on or above the (extension of the) c\_{i+1} segment of \operatorname{diag}(L).
  - The slope of the c\_{i+1} segment, from P(\gamma\_i) to P(\gamma\_{i+1}), is \operatorname{feerate}(c\_{i+1}) \leq f.
  - For \alpha = 0, the slope of the line from P(\gamma\_i) to (1-\alpha)P(\gamma\_i \cup \zeta\_i) + \alpha P(\gamma\_{i+1} \cup \zeta\_{i+1}) is \operatorname{feerate}(\zeta\_i) \geq f.
  - For \alpha = 1, the slope of the line from P(\gamma\_i) to (1-\alpha)P(\gamma\_i \cup \zeta\_i) + \alpha P(\gamma\_{i+1} \cup \zeta\_{i+1}) is \operatorname{feerate}(\zeta\_{i+1} \cup c\_{i+1}). Since \operatorname{feerate}(\zeta\_{i+1}) \geq \operatorname{feerate}(c\_{i+1}), it follows that \operatorname{feerate}(\zeta\_{i+1} \cup c\_{i+1}) \geq \operatorname{feerate}(c\_{i+1}).
    - The one exception is i = n-1, as \zeta\_n is empty there, and thus has no \operatorname{feerate}; this is not a problem as the functions coincide in this point.

  - The points with 0 \< \alpha \< 1 linearly interpolate between \alpha=0 and \alpha=1. Since both endpoints lie on or above the segment, the points in between also lie on or above the same segment.

Thus, \operatorname{ndiag}, an underestimate for the feerate diagram of L', is always at least as high as \operatorname{diag\_L}, the feerate diagram of L. We conclude that L' \gtrsim L.

## Merging linearizations

_ **Definition** _. Let \operatorname{merge}(G, L\_1, L\_2) be the function on graphs G with valid linearizations L\_1 and L\_2, defined as follows:

- If G (and thus L\_1 and L\_2) are empty, \operatorname{merge}(\{\}, (), ()) = ().
- Otherwise:
  - Let (c\_1, \ldots) = \operatorname{chunks}(L\_1).
  - Let (c\_2, \ldots) = \operatorname{chunks}(L\_2).
  - If \operatorname{feerate}(c\_1) \> \operatorname{feerate}(c\_2), swap L\_1 with L\_2 (and c\_1 with c\_2).
  - Let L\_3 = L\_1[c\_2], the first chunk of L\_2, using the order these transactions have in L\_1.
  - Let (c\_3, \ldots) = \operatorname{chunks}(L\_3).
  - Let L\_4 = L\_3[c\_3] = L\_1[c\_3], the linearization of the first chunk of L\_3.
  - \operatorname{merge}(G, L\_1, L\_2) = L\_4 + \operatorname{merge}(G \setminus c\_3, L\_1[G \setminus c\_3], L\_2[G \setminus c\_3]).

_ **Theorem** _. \operatorname{merge}(G, L\_1, L\_2) \gtrsim L\_1 and \operatorname{merge}(G, L\_1, L\_2) \gtrsim L\_2.

_ **Proof** _.

The theorem is trivially true for empty G. For others, we use induction:

- First note that \operatorname{feerate}(c\_3) \geq \operatorname{feerate}(c\_1):
  - After the optional swapping step it must be the case that \operatorname{feerate}(c\_2) \geq \operatorname{feerate}(c\_1).
  - Further, \operatorname{feerate}(c\_3) \geq \operatorname{feerate}(c\_2), because L\_3 contains the same transactions as c\_2. If the \operatorname{chunks} operation on L\_3 finds nothing better, it will pick the entirety of L\_3 as c\_3, which has the same feerate as c\_2.

- Now define the following:
  - Let L\_1' = L\_4 + L\_1[G \setminus c\_3]. By the gathering theorem, L\_1' \gtrsim L\_1, as it is bringing a topologically valid sublinearization (L\_4 = L\_1[c\_3]) to the front, and it has just a single chunk (c\_3), whose feerate is \geq \operatorname{feerate}(c\_1), the highest feerate in L\_1.
  - Let L\_2' = L\_4 + L\_2[G \setminus c\_3]. By the chunk reordering them, L\_2' \gtrsim L\_2, as L\_2' equals L\_2 apart from its first chunk (c\_3 \subset c\_2).

- By the induction hypothesis, \operatorname{merge}(G \setminus c\_3, L\_1[G \setminus c\_3], L\_2[G \setminus c\_3]) \gtrsim L\_1[G \setminus c\_3], and thus by the stripping theorem, L\_4 + \operatorname{merge}(G \setminus c\_3, L\_1[G \setminus c\_3], L\_2[G \setminus c\_3]) \gtrsim L\_4 + L\_1[G \setminus c\_3] = L\_1'. The same reasoning applies to L\_2'.
- Put together, \operatorname{merge}(G, L\_1, L\_2) \gtrsim L\_1' \gtrsim L\_1 and \operatorname{merge}(G, L\_1, L\_2) \gtrsim L\_2' \gtrsim L\_2.

_ **Variations** _. A number of variations on this algorithm are possible which do not break the proof above:

- Whenever a non-empty prefix P is shared by L\_1 and L\_2, it can be skipped (this follows directly from the stripping theorem), so if L\_1 = P + A and L\_2 = P + B, then one can define \operatorname{merge}(G, L\_1, L\_2) = P + \operatorname{merge}(G \setminus P, A, B).
- Instead of only considering the first chunk of L\_2 in the order of L\_1, it’s possible to also consider the first chunk of L\_1 in the order of L\_2, and then pick the first chunk of the one of those two which has the higher feerate.

## Optimal linearizations

_ **Definition** _. An **optimal linearization/chunking** for a graph is one which sorts higher or equal than every other linearization/chunking for the same graph. Note that this implies that optimal linearizations/chunkings are comparable with every other linearization/chunking. An optimal linearization/chunking is a [greatest element](https://en.wikipedia.org/wiki/Greatest_element_and_least_element) of the set of all linearizations/chunkings of a graph.

_ **Theorem** _. The set of linearizations/chunkings of a graph, with the preorder relation defined above, forms an (upward) **[directed set](https://en.wikipedia.org/wiki/Directed_set)**.

_ **Proof** _. From the properties of the \operatorname{merge} algorithm it follows that for any two linearizations L\_1 and L\_2 there exists a L\_3 = \operatorname{merge}(G, L\_1, L\_2) such that L\_3 \gtrsim L\_1 and L\_3 \gtrsim L\_2.

_ **Theorem** _. **Every graph has at least one optimal linearization/chunking**.

_ **Proof** _. In a directed set, every [maximal element](https://en.wikipedia.org/wiki/Maximal_and_minimal_elements) is a greatest element. Every finite preordered set has at least one maximal element. In a directed set, that element is a greatest element too.

_ **Definition** _. For a given total ordering R\_1 on the set of sets of transactions, and a total ordering R\_2 on the set of sequences of transactions, define the function \operatorname{opt}\_{R\_1,R\_2}(G), for a given graph G as follows:

- If G is empty, return the empty sequence: \operatorname{opt}\_{R\_1,R\_2}(G) = ().
- Otherwise:
  - Let S be the highest-feerate subset of G. If there are multiple, pick the first one according to R\_1.
  - Let L\_S be the first valid linearization of S according to R\_2.
  - \operatorname{opt}\_{R\_1,R\_2}(G) = L\_S + \operatorname{opt}\_{R\_1,R\_2}(G \setminus S).

_ **Theorem** _. \operatorname{opt}\_{R\_1,R\_2}(G) is an optimal linearization of G.

_ **Proof** _. Assume L = \operatorname{opt}\_{R\_1,R\_2}(G) is not an optimal linearization of G. We already know an actual optimal linearization L\_{opt} must exist though, so L\_{opt} \> L.

There must be a first chunk in the chunking of L where the fee-size diagram differs with L\_{opt}. Let p be the set of all transactions in L in chunks before that point. Let L\_{opt}' = L[p] + L\_{opt}[G \setminus p], i.e. the linearization obtained by moving the diagram-equal L chunks to the front in L\_{opt}. By repeatedly applying the gathering and stripping theorem, L\_{opt}' \gtrsim L\_{opt}. Because L\_{opt} is optimal this implies L\_{opt}' \sim L\_{opt} \> L. L\_{opt}' and L both start with the same chunks, so by removing them we get L\_{opt}[G \setminus p] \> L[G \setminus p]. L[G \setminus p] = \operatorname{opt}\_{R\_1,R\_2}(G \setminus p) however, and it starts by picking the highest-feerate subset of (G \setminus p), and yet L\_{opt}[G \setminus p] starts with a better chunk. This is a contradiction.

For how to compute \operatorname{opt}(G) efficiently, see [How to linearize your cluster](https://delvingbitcoin.org/t/how-to-linearize-your-cluster/303).

## Connected chunks

_ **Definition** _. A **connected chunking** is a chunking for which each chunk is connected ignoring direction (i.e., given any transaction in a chunk, every other transaction in the same chunk can be reached when ignoring direction of the edges).

_ **Theorem** _. **In an optimal linearization/chunking, the corresponding chunks have connected components whose feerate is all the same**. This is trivially true if the chunks are all connected.

_ **Proof** _ If not, the chunks could be split in two, which would improve the diagram.

_ **Theorem** _. **Every graph has at least one optimal linearization/chunking whose chunks are connected.**

---

<div class="post-metadata">

**Author:** ![murch](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/murch/32/139_2.png) [@murch](https://delvingbitcoin.org/u/murch)\
**Post date:** [December 10, 2023, 3:22pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/2 "2023-12-10T15:22:28Z")

</div>

> [@sipa](#):
>
> _ **Definition** _. A **chunking** C = (c\_1, c\_2, \ldots, c\_n)C=(c1,c2,…,cn)C = (c\_1, c\_2, \ldots, c\_n) for a given graph _G_ is a list of sets of transactions (called **chunks** ) of _G_ such that:
> 
> - The chunks c\_icic\_i form a partition of _G_ (no overlap, and their union contains all elements).
> - Every prefix of chunks is topological (\cup\_{i=1}^{k} c\_i∪ki=1ci\cup\_{i=1}^{k} c\_i for k=1 \ldots nk=1…nk=1 \ldots n are topological subsets of GGG). Thus, a transaction’s parent can appear in the same chunk as the transaction itself or in an earlier chunk, but not in a later chunk.
> - The feerates of the sets are monotonically decreasing. Thus, the consecutive prefices of chunks form the highest, second-highest, … feerate topological prefices.

I assume you are defining it on a graph so that you can have a chunking across multiple clusters, but it seems to me that this definition would only require that the topology is valid at the chunk borders and would not require the transactions to be topological _within the chunks_. I think it would be correct if you said “every prefix of the chunking is topological” instead of “every prefix of chunks is topological”.

> [@sipa](#):
>
> _ **Theorem** _. The **corresponding chunking is a valid chunking, and is [unique](https://en.wikipedia.org/wiki/Uniqueness_theorem)**. The same chunking is obtained regardless of what order of merge operations is used. Thus, we can talk about _the_ corresponding chunking \operatorname{chunks}(L)chunks(L)\operatorname{chunks}(L) of a linearization LLL. [no proof yet]

> [@sipa](#):
>
> For other values it linearly interpolates between those points.

Would it perhaps be sufficient that a feerate diagram has exactly one “convex hull” for a geometric proof? E.g. if we draw all transactions separately in the feerate diagram instead of their chunks, could we use the approach you use in the _gathering theorem_ to show that all possible subgroupings will always be below the convex hull?

> [@sipa](#):
>
> _ **Theorem** _. The **chunk reordering theorem** : reordering a linearization with changes restricted to a single chunk results leaves it at least as good.

Should this perhaps be restricted to topologically valid reorderings?

> [@sipa](#):
>
> Let e\_j = c\_j \cap Sej=cj∩Se\_j = c\_j \cap S for j=1 \ldots nj=1…nj=1 \ldots n, the SSS transactions in chunk iii of LLL. Note that this is distinct from d\_jdjd\_j because e\_jeje\_j follows the chunk boundaries of LLL, while d\_jdjd\_j follows the boundaries of L[S]L[S]L[S].

This should be “in chunk _j_ of _L_”.

> [@sipa](#):
>
> Let \zeta\_j = \cup\_{i=j+1}^{n} e\_iζj=∪ni=j+1ei\zeta\_j = \cup\_{i=j+1}^{n} e\_i for j = 1 \ldots nj=1…nj = 1 \ldots n, the SSS transactions _after_ the first jjj chunks of LLL.

Maybe “all remaining transactions of _S_ _after_ the first _j_ chunks of _L_” would be clearer.

> [@sipa](#):
>
> Let SSS be the highest-feerate subset of GGG. If there are multiple, choose an arbitrary but consistent to order them.

“choose an arbitrary but consistent **way/approach/method/criteria/something** to order them”?

> [@sipa](#):
>
> _ **Theorem** _. **In an optimal linearization/chunking, the corresponding chunks have connected components whose feerate is all the same**. This is trivially true if the chunks are all connected. _ **Proof** _ If not, the chunks could be split in two, which would improve the diagram.

Linebreak missing before the Proof.

I find that phrasing a bit confusing. What do you mean with “have connected components whose feerate is all the same”? I assume you are referring to the optimal linearization consisting only of chunks that cannot be split further by reordering, i.e. that any valid reordering would not lead to a different chunking, but the “have connected components whose feerate is all the same” makes me think that you are postulating that there are two chunks with the same feerate.

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [December 10, 2023, 6:14pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/3 "2023-12-10T18:14:04Z")

</div>

> [@murch](#):
>
> I assume you are defining it on a graph so that you can have a chunking across multiple clusters

Right. I’ve added a paragraph to elaborate on why that is.

> [@murch](#):
>
> it seems to me that this definition would only require that the topology is valid at the chunk borders and would not require the transactions to be topological _within the chunks_.

Chunks, as defined here, are sets; they don’t have an internal ordering. I’ve gone back and forth in my thinking whether sets or sequences are better. The advantage of sets is that at the chunking level, you don’t need to care about distinct intra-chunk linearization orderings. The disadvantage is that converting back from chunkings to linearizations isn’t as natural.

> [@murch](#):
>
> Would it perhaps be sufficient that a feerate diagram has exactly one “convex hull” for a geometric proof? E.g. if we draw all transactions separately in the feerate diagram instead of their chunks, could we use the approach you use in the _gathering theorem_ to show that all possible subgroupings will always be below the convex hull?

Let me think a bit more about that.

> [@murch](#):
>
> Should this perhaps be restricted to topologically valid reorderings?

Done.

> [@murch](#):
>
> This should be “in chunk _j_ of _L_”.

Fixed.

> [@murch](#):
>
> Maybe “all remaining transactions of _S_ _after_ the first _j_ chunks of _L_” would be clearer.

Agreed, done.

> [@murch](#):
>
> “choose an arbitrary but consistent **way/approach/method/criteria/something** to order them”?

I’ve formalized this a bit more, selecting the ordering before the function definition.

> [@murch](#):
>
> What do you mean with “have connected components whose feerate is all the same”? I assume you are referring to the optimal linearization consisting only of chunks that cannot be split further by reordering, i.e. that any valid reordering would not lead to a different chunking, but the “have connected components whose feerate is all the same” makes me think that you are postulating that there are two chunks with the same feerate.

Consider the following cluster:

```mermaid
graph BT
   T0["B: 7"] --> T1;
   T1["A: 1"];
   T2["D: 5"] --> T3;
   T3["C: 3"];
   T4["E: 1"] --> T0;
   T4 --> T2;

```

- The linearization [ACDBE] has chunking [ACDB,E]
- The linearization [ABCDE] has chunking [AB,CD,E]

As defined so far, both linearizations are equivalent (because their diagram coincides), and optimal. Yet still, chunk ACDB contains two disconnected components. The point of this theorem is showing that in an optimal linearization, chunks are still not necessarily connected, but this is only possible if the connected components all have the same feerate (4 in this example).

What I want to get to here, but haven’t really fleshed out, is a stronger notion of optimality than defined so far, which also requires all chunks to be connected - and that every graph has such a very-optimal linearization too.

Actually, now that you bring it up, I realize that’s not as strong as we’d want yet. Even with requiring connected chunks, it’s still possible that optimal chunkings contain chunks with equal-feerate subsets, so I guess very-optimality should instead be “optimal diagram, and chunks cannot contain topologically-valid strict subsets with equal feerate as the chunk itself” or so?

---

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [December 10, 2023, 10:11pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/4 "2023-12-10T22:11:26Z")

</div>

> [@sipa](#):
>
> What I want to get to here, but haven’t really fleshed out, is a stronger notion of optimality

Isn’t this just about preferring (a) multiple smaller chunks to a single larger chunk, and (b) smaller chunks to be linearised before larger chunks, given the chunks have equal fee rates?

Is it possible to have two chunkings “A,B,C” and “D,E,F” where all have the same feerate, A is smaller than D, and DE is smaller than AB, and there is no alternative chunking “G,H,I” where G is smaller or equal to A and GH is smaller or equal to DE?

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [December 10, 2023, 11:42pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/5 "2023-12-10T23:42:27Z")

</div>

> [@ajtowns](#):
>
> Isn’t this just about preferring (a) multiple smaller chunks to a single larger chunk, and (b) smaller chunks to be linearised before larger chunks, given the chunks have equal fee rates?

I believe that is too strong - while we do want to consider breaking up chunks into multiple equal-feerate ones an improvement, I don’t think there is an objective reason to want the smallest ones first. (in my implementation, I do prefer smaller size when comparing equal-feerate transaction sets, but that’s an arbitrary choice that happens to prevent merging of such equal-feerate chunks).

One possibility, which I think is sufficient, is in the \gtrsim (& co) definitions is to use the total number of chunks as a tie-breaker when the fee-size diagram coincides exactly (more chunks = better). This has the advantage that “optimal linearization” automatically implies chunks which have no non-trivial subsets of the same feerate, and it doesn’t introduce a new source of incomparability. The disadvantage is that (as stated) it breaks the gathering theorem, and I suspect fixing that would complicate matters somewhat. That may also have implications for the prefix-merging algorithm’s proof (I believe the algorithm itself actually keeps its properties under this stronger ordering definition).

An alternative is leaving the preorder on linearizations alone, and instead only incorporate into the “optimal linearization” definition that chunks cannot have non-trivial subsets of higher or equal feerate. Alternatively, it could be a notion of “perfect linearization” which is stronger than optimal (and leave optimal to only be about the feerate diagram). This may be nicer in terms of presentation as the properties can be introduced and proven incrementally.

---

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [December 11, 2023, 1:16am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/6 "2023-12-11T01:16:32Z")

</div>

> [@sipa](#):
>
> I don’t think there is an objective reason to want the smallest ones first.

Oh, actually, I think you want the smallest ones last, if anything? (Or is my guess for getting mildly better performance out of greedy knapsack selection off the mark?)

Is this about optimising for the last few transactions in a block, or choosing a canonical ordering so there’s less uncertainty/ambiguity, or something else?

You can’t get a strictly unique “perfect” linearisation, since if you have txs A, B, C, C spending A and B, and A,B having equal fee and size, but lower feerate than C, then [ABC] and [BAC] are equally good linearisations. You could break the tie by resorting to your arbitrary order R\_2, of course, but that’s still picking a winner arbitrarily…

Your definition of opt seems weird? Shouldn’t that just be \operatorname{opt}(G) = L\_G + \operatorname{opt}(G \setminus S\_G) where S\_G is the highest-feerate subset of G and L\_G is the first valid linearisation of S\_G?

I would have proven the uniqueness claim non-constructively: set f(L) = |\{L\_2 | L \ge L2\}|. Pick a linearisation L\_x where f(L\_x) \ge f(L) for all L. If this value equals the count of all linearisations, then L\_x \ge L for all L, so L\_x is an optimal linearisation. If it’s not the case, then there is some L\_y where L\_x \not\ge L\_y, so calculate L\_z = \operatorname{merge}(L\_x, L\_y) which gives us L\_z \ge L\_x but also L\_z \ge L\_y. But for any L where L\_x \ge L, L\_z \ge L by transitivity, so f(L\_z) \gt f(L\_x) which contradicts our choice of L\_x.

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [December 11, 2023, 3:20am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/7 "2023-12-11T03:20:42Z")

</div>

> [@ajtowns](#):
>
> Oh, actually, I think you want the smallest ones last, if anything? (Or is my guess for getting mildly better performance out of greedy knapsack selection off the mark?)
> 
> Is this about optimising for the last few transactions in a block, or choosing a canonical ordering so there’s less uncertainty/ambiguity, or something else?

It’s about optimizing for the last few transactions in a block; the more chunks clusters are broken up in, the more puzzle pieces there are to use. I don’t think you can - without whole-mempool context - say whether the beginning or the end of a cluster is better to have small pieces, as you don’t know ahead of time where they’ll end up in a block. And I think the splitting itself is more important than the ordering.

> [@ajtowns](#):
>
> You can’t get a strictly unique “perfect” linearisation, since if you have txs A, B, C, C spending A and B, and A,B having equal fee and size, but lower feerate than C, then [ABC] and [BAC] are equally good linearisations. You could break the tie by resorting to your arbitrary order R\_2R2R\_2, of course, but that’s still picking a winner arbitrarily…

Yeah. I don’t think we need to pick a well-defined unique optimal.

> [@ajtowns](#):
>
> Your definition of optoptopt seems weird? Shouldn’t that just be \operatorname{opt}(G) = L\_G + \operatorname{opt}(G \setminus S\_G)opt(G)=LG+opt(G∖SG)\operatorname{opt}(G) = L\_G + \operatorname{opt}(G \setminus S\_G) where S\_GSGS\_G is the highest-feerate subset of GGG and L\_GLGL\_G is the first valid linearisation of S\_GSGS\_G?
> 
> I would have proven the uniqueness claim non-constructively: set f(L) = |{L\_2 | L \ge L2}|f(L)=|{L2|L≥L2}|f(L) = |{L\_2 | L \ge L2}|. Pick a linearisation L\_xLxL\_x where f(L\_x) \ge f(L)f(Lx)≥f(L)f(L\_x) \ge f(L) for all LLL. If this value equals the count of all linearisations, then L\_x \ge LLx≥LL\_x \ge L for all LLL, so L\_xLxL\_x is an optimal linearisation. If it’s not the case, then there is some L\_yLyL\_y where L\_x \not\ge L\_yLx≱LyL\_x \not\ge L\_y, so calculate L\_z = \operatorname{merge}(L\_x, L\_y)Lz=merge(Lx,Ly)L\_z = \operatorname{merge}(L\_x, L\_y) which gives us L\_z \ge L\_xLz≥LxL\_z \ge L\_x but also L\_z \ge L\_yLz≥LyL\_z \ge L\_y. But for any LLL where L\_x \ge LLx≥LL\_x \ge L, L\_z \ge LLz≥LL\_z \ge L by transitivity, so f(L\_z) \gt f(L\_x)f(Lz)\>f(Lx)f(L\_z) \gt f(L\_x) which contradicts our choice of L\_xLxL\_x.

Yeah, that’s proving the existence of optimality through \operatorname{merge}. My thinking was to prove existence of optimality before introducing merging (because proving that “move best subset to the front, continue” is optimal seems more intuitive than through merging), but perhaps that’s an unnecessary detour.

An alternative way to prove that, I think, is as follows. Let M be the set of maximal elements of the set of valid linearizations for a given graph (maxima have no elements that compare strictly higher than them, but may have elements incomparable to them).

- If M = \{\}: impossible in a finite set (start with any element and keep picking a strictly larger element, eventually you end up in a cycle, which is impossible as it implies elements strictly larger than themselves).
- If M = \{m\}, then m is optimal. Again start with any element, and keep picking strictly larger elements. Each of these chains must end with m as it’s the only element with no larger ones. Thus, m \> everything else.
- Otherwise M consists of two or more elements: merge them, and end up with something better than both. This is in contradiction with them being maximal elements.

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [December 12, 2023, 4:09am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/8 "2023-12-12T04:09:42Z")

</div>

TIL about [directed sets](https://en.wikipedia.org/wiki/Directed_set): sets with a preorder \geq and the additional property that for any pair of elements (a, b) an element c exists such that c \geq a and c \geq b.

In a directed set, every maximal element (m is maximal if no x \> m exists) is a greatest element (m is greatest if for every x it holds that m \geq x).

Linearizations (and chunkings) of graphs/clusters are directed sets (with \gtrsim as the direction). The merge-intersection algorithm computes the c mentioned above given a and b. The “move highest feerate subset to front, continue with remainder” algorithm by construction computes a maximal element, which is thus a greatest element. “Optimal linearization” is the name we have for greatest element.

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [December 24, 2023, 1:51am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/9 "2023-12-24T01:51:21Z")

</div>

I’ve incorporated this “directed set” idea. Existence of an optimal linearization now follows from the merging algorithm, and with that knowledge, a simpler proof is possible that \operatorname{opt}(G) is optimal.

---

<div class="post-metadata">

**Author:** ![Crypt-iQ](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/crypt-iq/32/306_2.png) [@Crypt-iQ](https://delvingbitcoin.org/u/Crypt-iQ)\
**Post date:** [February 26, 2024, 11:36pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/10 "2024-02-26T23:36:49Z")

</div>

> [@sipa](#):
>
> By repeatedly applying the gathering and stripping theorem, L\_{opt}' \gtrsim L\_{opt}.

I’m a bit confused here; could you elaborate on how the gathering and stripping theorems are used here? Since the gathering theorem applies when a sublinearization is moved to the front, it alone doesn’t prove that L\_{opt}' \gtrsim L\_{opt} since L[p] is the ordering from L rather than from L\_{opt}. I’m not sure where the prefix stripping theorem comes in, so I must be missing something.

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [February 27, 2024, 9:19am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/11 "2024-02-27T09:19:52Z")

</div>

You’re right, I’m skipping over a few steps here.

What is happening is that we’re starting from L\_{opt}, and moving the prefix of L that feerate-diagram-coincides with it to the front of L\_{opt} so that we can skip over that, and just compare the part where the diagram actually differs. If it were any more obvious than it is, it would suffice to say “without loss of generality, assume L and L\_{opt} have a distinct first chunk feerate”. This part of the argument is just to show that it indeed is without loss of generality, because if there is a coinciding prefix, then applying the theorem to just the transactions not in that prefix still leads to a contradiction.

This prefix p may consists of multiple chunks of L. If it consisted of 0 chunks, there is nothing to do, as L'\_{opt} = L\_{opt} in that case. If p consists of a single L-chunk, then just applying the gathering theorem gives our desired result (because in that case p has a feerate at least as much (and in fact, exactly equal to) the first chunk of L\_{opt}).

The difficulty is only when p consists of multiple chunks. But in this case, repeatedly applying the gathering theorem (to move one L-chunk worth of p subset to the front of L\_{opt}) and the stripping theorem (to skip over the just moved part) gets the result. I’m happy to write it out more formally, but this informal description is perhaps more enlightening?

---

<div class="post-metadata">

**Author:** ![Crypt-iQ](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/crypt-iq/32/306_2.png) [@Crypt-iQ](https://delvingbitcoin.org/u/Crypt-iQ)\
**Post date:** [February 27, 2024, 8:12pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/12 "2024-02-27T20:12:35Z")

</div>

> [@sipa](#):
>
> If p consists of a single L-chunk, then just applying the gathering theorem gives our desired result (because in that case p has a feerate at least as much (and in fact, exactly equal to) the first chunk of L\_{opt}).

This is the part I’m having trouble with. Can the gathering theorem be used here even though L\_{opt}' is moving a sublinearization of L to the front of L\_{opt} rather than moving a sublinearization of L\_{opt} to the front of L\_{opt}?

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [February 27, 2024, 8:25pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/13 "2024-02-27T20:25:17Z")

</div>

Oh, you need to use the chunk reordering theorem too, I forgot that was a separate thing in my writeup.

So you move (a chunk of) p to the front of L\_{opt}, and then reorder it according the order those transaction have in L (which is allowed as they form a chunk).

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [May 6, 2024, 6:52pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/14 "2024-05-06T18:52:40Z")

</div>

Given some of the insights from the [LIMO](https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825/9) thread, I think there is a simpler way to formalize things. Here is an attempt with just sketches. If people are interested I can expand on it.

The biggest changes are:

- A new concept “guide” of a cluster is introduced, which covers both linearizations and set-linearizations.
- Guides use a different representation: they’re not lists, but a set of topological subsets, each one being a subset of the next one.
- The gathering theorem is replaced with a much simpler variant, and then used to prove a new “composition” theorem, which describes how given a set of topologically valid subsets one can produce a guide that is as good as all of them. Merging and LIMO can be seen as instances/variants of composition.

### Graphs (unchanged):

- Transactions graphs are defined as before: nodes that have a integer \operatorname{fee} and a strictly positive \operatorname{size}, and directed edges representing dependencies pointing from child to parent.
- The functions \operatorname{fee}, \operatorname{size}, and \operatorname{feerate} are defined for sets of nodes as respectively the sum of the fees, the sum of the sizes, and the sum of the fees divided by the sum of the sizes.
- The ancestors and descendants of a set are defined as before: \operatorname{anc}\_G(S) is the transitive closure of S under the parent relation. Similarly, \operatorname{desc}\_G(S) is the transitive closure of S under the child relation.
- A subset S of the nodes of a graph G is said to be **topological** if \operatorname{anc}\_G(S) = S.

### Guides

- A **guide** of a graph G is defined differently: it is a set of topological subsets of G, where each is either a subset or superset of every other, and which includes \varnothing and G itself as elements.
- A guide is said to be **full** if it contains a subset for each size from 0 to the size of the graph inclusive (i.e., has n+1 elements for a graph with n transactions). If not, a guide is said to be **partial**. Guides are isomorphic with set-linearizations, and full guides are isomorphic with linearizations.
- A guide a is said to be a **weakening** of guide b if a \subseteq b, and said to be a **strengthening** of b if a \supseteq b.
- **Full strengthening theorem** : every guide has a full strengthening. For any two c\_1 \subset c\_2 \in L, topologically sort c\_2 \setminus c\_1 and for each include a new subset, in order.

### Preordering of guides

- The diagram \operatorname{diag}\_L of a guide L of graph G is the real function defined for all inputs x \in [0,\operatorname{size}(G)]: \operatorname{diag}\_L(x) is the maximum value of \operatorname{fee}(a) + (x - \operatorname{size}(a))\operatorname{feerate}(b \setminus a) over all a and b in L such that \operatorname{size}(a) \leq x and \operatorname{size}(b) \geq x. It is the minimal concave function through all the (\operatorname{size}(p), \operatorname{fee}(p))\_{p \in L} points.
- The **chunking** \operatorname{chunk}(L) of a guide L is the weakening (subset) of L containing those x for which \operatorname{diag}\_L(\operatorname{size}(x)) = \operatorname{fee}(x). It consists of those graph subsets whose size/fee pairs make up the vertices of the convex hull shape that the diagram has, and is the minimal weakening with the same diagram as L.
- A preorder \gtrsim is defined between guides of the same graph G as: L\_1 \gtrsim L\_2 iff for all x \in [0,\operatorname{size}(G)] it holds that \operatorname{diag}\_{L\_1}(x) \geq \operatorname{diag}\_{L\_2}(x). As chunking does not change diagrams, L\_1 \gtrsim L\_2 \iff \operatorname{chunk}(L\_1) \gtrsim L\_2 \iff L\_1 \gtrsim \operatorname{chunk}(L\_2).
- **Strengthening improvement theorem** : if L\_1 is a strengthening of L\_2, then L\_1 \gtrsim L\_2.

### Improving guides

- **Common subset theorem** : given two guides L\_1 and L\_2 for a graph G, both of which have the same smallest non-empty element s. Let L\_1' and L\_2' be guides of G \setminus s obtained by removing s from all elements of L\_1 resp. L\_2. Then L\_1' \gtrsim L\_2' \implies L\_1 \gtrsim L\_2.
  - Proof: Going from the diagrams of L\_1' and L\_2' to those of L\_1 and L\_2 is just shifting the convex hulls by s, and then adding a point (0,0) to both hulls.

- **Simple gathering theorem** : given topological subsets s \subseteq G and c \subseteq G such that \operatorname{feerate}(s) \geq \operatorname{feerate}(c) (or s = \varnothing or c = \varnothing) and \operatorname{feerate}(s) \geq \operatorname{feerate}(s \cap c) (or s \cap c = \varnothing), it holds that \{\varnothing, s, c \cup s, G\} \gtrsim \{\varnothing, c, G\}.
  - Proof: this is a simplification to 2 sets of the earlier [set gathering theorem](https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825/8#h-13-the-set-gathering-theorem-4), plus covering the case where \operatorname{feerate}(c) \< \operatorname{feerate}(G) which is trivial.

- **Supreme subset theorem** : given a set C = \{c\_1, c\_2, \ldots, c\_n\} of c\_i that are all topological subsets of a non-empty graph G, there always exists a non-empty topological subset s of G such that \{\varnothing, s, c\_i \cup s, G\} \gtrsim \{\varnothing, c\_i, G\} for all i = 1 \ldots n.
  - Proof: pick s to be the highest feerate non-empty intersection between any combination of c\_i’s, plus G, and apply the simple gathering theorem (no intersection between s and c\_i can have higher feerate than s, because that intersection would have been picked as s instead).
  - Note that this is not necessarily the only set which satisfies the \{\varnothing, s, c\_i \cup s, G\} \gtrsim \{\varnothing, c\_i, G\} conditions, and others may be computationally cheaper to find.

- **Composition algorithm** : Define \operatorname{compose}(G, C) for a graph G and a set of topologically valid subsets C = \{c\_1, c\_2, \ldots, c\_n\} for it as follows:
  - If G = \varnothing, return \{\varnothing\}, the only valid guide for G.
  - Otherwise, find a non-empty topological s such that \{\varnothing, s, c\_i \cup s, G\} \gtrsim \{\varnothing, c\_i, G\} for all i, which by the supreme subset theorem always exists. Let C' = \{c\_1 \setminus s, c\_2 \setminus s, \ldots, c\_n \setminus s\}. Let L' = \operatorname{compose}(G \setminus s, C'). Return L = \{\varnothing\} \cup \{\forall x \in L' : x \cup s\}.

- **Composition theorem** : Given C = \{c\_1, c\_2, \ldots, c\_n\} of topological subsets of a graph G, \operatorname{compose}(G, C) \gtrsim \{\varnothing, c\_i, G\} for all i = 1 \ldots n. In other words, \operatorname{diag}\_{\operatorname{compose}(G, C)}(\operatorname{size}(c\_i)) \geq \operatorname{fee}(c\_i) for all i.
  - Proof: we know by induction that L' \gtrsim \{\varnothing, c\_i \setminus s, G \setminus s\} for all i. From the common subset theorem it follows that L \gtrsim \{\varnothing, s, c\_i \cup s, G\}. Because of the properties of s we know that \{\varnothing, s, c\_i \cup s, G\} \gtrsim \{\varnothing, c\_i, G\}. Together it follows that L \gtrsim \{\varnothing, c\_i, G\}.
  - Merging of two guides L\_1 and L\_2 is now effectively applying composition to C = L\_1 \cup L\_2, with a specialized \mathcal{O}(n) complexity s-finding algorithm.
  - LIMO can be seen as a variant of composition, with C = L \cup \{S\_1, S\_2, \ldots\}, but where the recursion doesn’t operate on exactly C', but the S\_i get replaced with (hopefully better) subsets every iteration.

---

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [May 7, 2024, 7:17am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/15 "2024-05-07T07:17:36Z")

</div>

> [@sipa](#):
>
> A linearization is said to be **full** (formerly: a linearization)

I don’t think this terminology is really helping any more? Everything other than a full linearisation doesn’t really sound very linear anymore. As it stands, {\emptyset, ABC} would be called a linearisation even though it does nothing to put the elements A,B,C in a line or an order, eg. Something like “escalating grouping” seems clearer: that is you select some groups of transactions, such that you can order them so that every group earlier than g is a proper subset of g and every group later than g is a proper superset of g, with \emptyset being the trivial first group and G being the trivial final group.

You could still distinguish “fully escalating groupings” from “partially escalating groupings”. Calling a fully escalating grouping a linearisation might be okay, but adding an extra term might not be helpful. (I’m surprised you’d go with “partial linearisation”, when, given it’s a smaller set than a full linearisation, you could call it a minilinearisation)

The new formulation looks like it makes sense, whatever it’s called though!

Having diag() auto chunk feels like cheating 🥹

Shouldn’t compose return \{ \emptyset, s \} \cup \{\forall x \in L^\prime : x \cup s\} ? (Shouldn’t s be specified as topologically valid here as well?)

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [May 7, 2024, 11:56am UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/16 "2024-05-07T11:56:13Z")

</div>

> [@ajtowns](#):
>
> I don’t think this terminology is really helping any more? Everything other than a full linearisation doesn’t really sound very linear anymore.

Fair enough. My thinking when merging the two concepts was that the distinction doesn’t matter for any of the theory really. We don’t need to reason about “all possible linearizations whose diagram is at least as good as one gets when grouping these transactions together”, we can reason about the groupings directly.

And from an implementation perspective, specializing a grouping to a full linearization is trivial, and does not worsen the diagram, so any procedure that yields a grouping whose diagram is desirable can be trivially turned into one that produces a full linearization with an equal or better diagram.

That said, I agree it’s probably better to just have a different term altogether, because \{\varnothing, G\} indeed doesn’t convey any actual order. “escalating grouping” is a bit long though, and more an “implementation detail” than functional describing what it accomplishes. How about calling it a **guide** for a cluster? A linearization would then be a full guide, or if we keep thinking of linearizations as lists, they’d be isomorphic with full guides.

> [@ajtowns](#):
>
> (I’m surprised you’d go with “partial linearisation”, when, given it’s a smaller set than a full linearisation

Well the result is still only a partial ordering on the elements (which needs to be combined with the partial ordering imposed by the graph structure).

> [@ajtowns](#):
>
> , you could call it a minilinearisation)

😡

> [@ajtowns](#):
>
> Shouldn’t compose return \{ \emptyset, s \} \cup \{\forall x \in L^\prime : x \cup s\} ?

That’s unnecessary because L' necessarily includes \varnothing as element.

> [@ajtowns](#):
>
> (Shouldn’t s be specified as topologically valid here as well?)

Indeed.

---

<div class="post-metadata">

**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\
**Post date:** [May 7, 2024, 1:07pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/17 "2024-05-07T13:07:29Z")

</div>

Guide sounds fine. “How do I order my transactions? Please, give me some guidance!”

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [May 7, 2024, 1:18pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/18 "2024-05-07T13:18:42Z")

</div>

- Linearization → guide
- Generalization → weakening
- Specialization → strengthening

---

<div class="post-metadata">

**Author:** ![instagibbs](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/instagibbs/32/28_2.png) [@instagibbs](https://delvingbitcoin.org/u/instagibbs)\
**Post date:** [May 7, 2024, 4:09pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/19 "2024-05-07T16:09:46Z")

</div>

> [@sipa](#):
>
> A guide is said to be **full** if it contains a subset for each size from 000 to the size of the graph, inclusive.

I got caught up on this too long without realizing size here means count of nodes in the graph, not the transaction sizes of the selected nodes. i.e. a full guide contains n+1 elements.

---

<div class="post-metadata">

**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\
**Post date:** [May 10, 2024, 1:02pm UTC](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202/20 "2024-05-10T13:02:41Z")

</div>

The \operatorname{compose} operator as defined above actually captures a ton of things:

- Chunking is the composition of a single linearization.
- ~~Pure ancestor sort is the composition of all ancestor sets in a cluster, because the intersection of two ancestor sets is again an ancestor set.~~ EDIT: this is not true, the intersection of two ancestor sets may be the union of more than one ancestor set.
  - The current sorting algorithm (which includes the highest-feerate ancestor set among those for which the bottom transaction has a higher feerate than its ancestry) isn’t exactly a composition, because the intersection of two such sets may have a bottom with low feerate.

- Merging is the composition of the union of two linearizations (with a specialized supreme subset finding algorithm).
- LIMO is a variant of composition of the input linearization plus the S\_i set(s), though these sets get recomputed every iteration.

[Next page](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202.md?page=2)