# LIMO: combining the best parts of linearization search and merging

**URL:** <https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825>\
**Category:** Implementation\
**Tags:** mempool\
**Created:** [April 23, 2024, 2:43am UTC](https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825 "2024-04-23T02:43:58Z")\
**Posts on this page:** 1\
**Showing post:** 8

<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 2, 2024, 3:22am UTC](https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825/8 "2024-05-02T03:22:34Z")

</div>

In this follows a proof for Double LIMO. More concretely, it shows that in each iteration of the algorithm progress is made towards a linearization which is as good as the input, and as good as the S\_1 and S\_2 found in that same iteration.

## 1. New concepts

First two new concepts (set-linearizations, slope comparison), with associated definitions and theorems, are introduced that will help with analyzing Double LIMO. Then a variant of the gathering theorem is introduced and proven

### 1.1. Set linearizations

_ **Definition.** _ A **set-linearization** is a list of non-overlapping sets of transactions whose prefixes are topological. The **prefixes** of a set-linearization C = (c\_1, c\_2, \ldots, c\_n) are the sets (\cup\_{i=1}^k c\_i)\_{k=0}^n. A chunking is a special case of a set-linearization. Set-linearizations do not require monotonically decreasing feerate. A normal linearization with every list element replaced by a singleton containing it always yields a valid set-linearization.

_ **Definition.** _ Every set-linearization C has a **set-feerate diagram** \operatorname{setdiag}(C), which is the real function through the cumulative (\operatorname{size}, \operatorname{fee}) points of its prefixes. Note that unlike for normal linearizations, we do not implicitly “chunkify” for the diagram. So a set-feerate diagram is not necessarily a concave function.

_ **Definition.** _ Let \operatorname{chunksets}(C) be a function from set-linearizations to set-linearizations, which repeatedly merges pairs of consecutive sets where the latter has a strictly higher feerate than the former, until no such pairs remain.

_ **Definition.** _ The \sim, \gtrsim, and \lesssim operators are defined for set-linearizations as comparing their (unchunked) diagrams.

_ **Theorem.** _ For any set-linearization C, \operatorname{chunksets}(C) \gtrsim C.

_ **Theorem.** _ The diagram for \operatorname{chunksets}(C) is the minimal concave function through the (\operatorname{size}, \operatorname{fee}) points of every prefix of C.

_ **Definition.** _ Given a linearization L, a set-linearization C is **compatible** with L if every prefix of C is also a prefix of L.

_ **Theorem.** _ Given a linearization L and a compatible set-linearization C, then \operatorname{chunksets}(C) is also compatible with L.

_ **Theorem.** _ Given a linearization L and a compatible set-linearization C, then the diagram of C is nowhere better than the (post-chunking) diagram of L.

### 1.2. Slope algebra

To simplify reasoning about points in the diagram and the feerates they correspond to:

- Define the function \operatorname{sfpair}(S) for set S as the real vector (\operatorname{size}(S), \operatorname{fee}(S)).
- Define \operatorname{possize}(P) where P = (s, f) as s \> 0.
- Define (s\_1, f\_1) \succeq (s\_2, f\_2) as f\_1 s\_2 \geq f\_2 s\_1, the “slope comparison”.

If \operatorname{possize}(P\_1) and \operatorname{possize}(P\_2), for P\_1 = (s\_1, f\_1) and P\_2 = (s\_2, f\_2), then P\_1 \succeq P\_2 \iff f\_1 / s\_1 \geq f\_2 / s\_2. Thus, \operatorname{sfpair}(S\_1) \succeq \operatorname{sfpair}(S\_2) \iff \operatorname{feerate}(S\_1) \geq \operatorname{feerate}(S\_2), and \succeq can be thought of as a generalization of the feerate comparisons on (\operatorname{size}, \operatorname{fee}) pairs, to situations where these coefficients do not necessarily correspond to a specific set of transactions, and sizes may even be negative or zero.

The following rules apply:

- **Negation rule** : P\_1 \succeq P\_2 \iff P\_2 \succeq -P\_1.
- **Offset rule** : P\_1 \succeq P\_2 \iff P\_1 + \alpha P\_2 \succeq P\_2 \iff P\_1 \succeq P\_2 + \beta P\_1 for real \alpha, \beta.
- **Transitivity** : P\_1 \succeq P\_2 \, \land \, P\_2 \succeq P\_3 \implies P\_1 \succeq P\_3, if \operatorname{possize}(P\_i) for i = 1 \ldots 3.
- **Line rule** : Geometrically, the point P lies to the left of the (infinite extension of) the line from P\_1 to P\_2 iff P - P\_1 \succeq P\_2 - P\_1. If \operatorname{possize}(P - P\_1) and \operatorname{possize}(P\_2 - P\_1), then P - P\_1 \succeq P\_2 - P\_1 iff P lies above the line from P\_1 to P\_2.

### 1.3 The set gathering theorem

This is a variation on [the gathering theorem](https://delvingbitcoin.org/t/cluster-mempool-definitions-theory/202#transformations-on-linearizations-4), with the difference that it operates on set-linearizations rather than linearizations.

Informally: moving a subset S of transactions to the front of a set-linearization C, and then chunking the result, will not worsen the diagram if the feerate of S is as good as every prefix of C, and as good as every prefix of C intersected with S.

_ **Theorem.** _ Given:

- A set-linearization C = (c\_1, c\_2, \ldots, c\_n)
- A topologically-valid subset S of its transactions (S \subset (\cup\_{j=1}^n c\_j)) for which, ignoring conditions that involve the feerate of an empty set, it holds that:
  - (1) \operatorname{feerate}(S) \geq \operatorname{feerate}(\cup\_{i=1}^k c\_i) for all k = 1 \ldots n
  - (2) \operatorname{feerate}(S) \geq \operatorname{feerate}(S \cap (\cup\_{i=1}^k c\_i)) for all k = 1 \ldots n.

Then \operatorname{chunksets}(C') \gtrsim C where C' = (S, c\_1 \setminus S, c\_2 \setminus S, \ldots, c\_n \setminus S).

_ **Proof.** _

Define:

- P\_k as \operatorname{sfpair}(\cup\_{i=1}^k c\_i), the points making up the diagram of C.
- Q\_k as \operatorname{sfpair}(S \cup (\cup\_{i=1}^k c\_i)), the points making up the diagram of C', excluding (0,0).

Our input conditions can now be stated using vectors and slope comparisons as

- (1) Q\_0 \succeq P\_k for k=1 \ldots n
- (2) Q\_0 \succeq Q\_0 + P\_k - Q\_k for k=1 \ldots n.

To prove that the diagram of \operatorname{chunksets}(C') is nowhere below the diagram of C, we will for every point of C show that a line between two points on C' exists that it lies on or below, as these lines form a lower bound for the concave function that is \operatorname{setdiag}(\operatorname{chunksets}(C')).

- For k = 1 \ldots n:
  - If \operatorname{possize}(P\_k - Q\_0):
    - (3) Q\_0 \succeq P\_k - Q\_k [offset rule with \beta=-1 on (2)]
    - (4) Q\_k - P\_k \succeq Q\_0 [negation rule on (3)]
    - (5) Q\_0 \succeq P\_k - Q\_0 [offset rule with \beta=-1 on (1)]
    - (6) Q\_k - P\_k \succeq P\_k - Q\_0 [transitivity on (4) and (5)]
    - (7) Q\_k - Q\_0 \succeq P\_k - Q\_0 [offset rule with \alpha=1 on (6)]
    - (8) P\_k lies on or below the line from Q\_0 to Q\_k [line rule on (7)]

  - Otherwise (not \operatorname{possize}(P\_k - Q\_0)):
    - (9) Q\_0 - P\_0 \succeq P\_k - P\_0 [subtracting P\_0 = (0, 0) from both sides of (1)]
    - (10) P\_k lies on or below the line from P\_0 to Q\_0 [line rule on (9)]

Thus, every point P\_k of the diagram of C lies on or below either the line from P\_0 to Q\_0 (10) or the line from Q\_0 to Q\_k (8). Since P\_0, Q\_0, and Q\_k are all on \operatorname{setdiag}(C'), this implies that \operatorname{chunksets}(C') \gtrsim C.

_ **Corollary.** _ The normal gathering theorem, under the condition that L[S] chunks to a single set, follows from the set gathering theorem, by applying it to C = \operatorname{chunking}(L), since the conditions follow from:

- (1) S having a higher feerate than L’s first chunk, which has a higher feerate than any other prefix of chunks
- (2) L[S] being a single chunk implies it has no higher-feerate prefix itself.

_ **Corollary.** _ The chunk reordering theorem follows from the set gathering theorem, by applying it to C = \operatorname{chunking}(L), since the conditions follow from:

- (1) Like above
- (2) S \subset c\_1 implying all intersections between S and prefixes of C are identical.

## 2. Double LIMO

Define \operatorname{DoubleLIMO}\_{f\_1,f\_2}(G, L) for a graph G with existing linearization L, and two functions f\_1 and f\_2 that find high-feerate topologically-valid subsets of a given set of transactions as:

- If L = (), return ().
- Otherwise:
  - Let C = (c\_1, c\_2, \ldots, c\_n) = \operatorname{chunking}(L).
  - Let S\_1 = f\_1(G).
  - Let S\_2 = f\_2(G).
  - Let S be the highest-feerate among:
    - (\cup\_{i=1}^k c\_i)\_{k=1}^n, the prefixes of C
    - (S\_1 \cap (\cup\_{i=1}^k c\_i))\_{k=1}^n, the prefixes of C intersected with S\_1
    - (S\_2 \cap (\cup\_{i=1}^k c\_i))\_{k=1}^n, the prefixes of C intersected with S\_2
    - (S\_1 \cap S\_2 \cap (\cup\_{i=1}^k c\_i))\_{k=1}^n, the prefixes of C intersected with S\_1 \cap S\_2

  - Return L[S] + \operatorname{DoubleLIMO}\_{f\_1,f\_2}(G \setminus S, L[G \setminus S]).

This is equivalent to the description [earlier in this thread](https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825/6), except it only considers intersections with linearization prefixes that are aligned to the chunk boundaries of L. In every step, \operatorname{DoubleLIMO} moves transactions to the front of the linearization, and then continues with what remains.

_ **Theorem.** _ The set of transactions S moved to the front by every step of \operatorname{DoubleLIMO} is such that _some_ linearization L^\ast exists such that:

- (a) L^\ast starts with L[S]
- (b) L^\ast \gtrsim L
- (c) \operatorname{diag}(L^\ast)(\operatorname{size}(f\_1(G))) \geq \operatorname{fee}(f\_1(G))
- (d) \operatorname{diag}(L^\ast)(\operatorname{size}(f\_2(G))) \geq \operatorname{fee}(f\_2(G))

Note that there is no guarantee that \operatorname{DoubleLIMO} overall actually finds this L^\ast, because it depends on which S\_1 and S\_2 are returned by f\_1 and f\_2 in future iterations. However, in every iteration progress is made towards some L^\ast satisfying these properties that exists during that individual iteration. In further iterations L^\ast may be different, and progress will be made towards that one instead then (for better or worse).

_ **Proof.** _ To prove this, we will construct this L^\ast for this one iteration explicitlly:

- Let L\_1 = L \triangleleft S\_1.
- Let L\_2 = L \triangleleft S\_2.
- Let L^\ast = \operatorname{merge}(G, \operatorname{merge}(G, L\_1 \triangleleft S, L\_2 \triangleleft S), L \triangleleft S)

This L^\ast satisfies condition (a), starting with L[S], as it is the merging of 3 linearizations which all start with L[S].

L^\ast also satisfies condition (b), L^\ast \gtrsim L, because:

- Let L' = L \triangleleft S
- Let C' = (S, c\_1 \setminus S, c\_2 \setminus S, \ldots, c\_n \setminus S).
- The set gathering theorem holds for set-linearization C and subset S, showing \operatorname{chunksets}(C') \gtrsim C, because:
  - Condition (1) follows from \operatorname{feerate}(S) \geq \operatorname{feerate}(c\_1), and c\_1 has the highest feerate of any prefix of chunks.
  - Condition (2) follows from the fact that for every candidate for S tried, its restriction S \cap (\cup\_{i=1}^k c\_i) for every k is tried as well. Thus, no S \cap (\cup\_{i=1}^k c\_i) can exist with feerate higher than S, as it would have been picked instead of S.

- C is the chunking for L, and \operatorname{chunksets}(C') is compatible with L', thus from \operatorname{chunksets}(C') \gtrsim C it follows that L' \gtrsim L.
- L^\ast is a merging with L', and thus L^\ast \gtrsim L' \gtrsim L.

To show it satisfies condition (c), \operatorname{diag}(L^\ast)(\operatorname{size}(S\_1)) \geq \operatorname{fee}(S\_1) (and analogously, condition (d)):

- Let C\_1 = (S\_1, G \setminus S\_1), a set-linearization whose diagram satisfies the relation in (c).
- Let L'\_1 = L\_1 \triangleleft S.
- Let C'\_1 = (S, S\_1 \setminus S, G \setminus (S \cup S\_1)).
- The set gathering theorem holds for set-linearization C\_1 and subset S, showing \operatorname{chunksets}(C'\_1) \gtrsim C\_1, because:
  - Condition (1) follows from the fact that both prefixes of C\_1, namely S\_1 and G in its entirety, are both candidates for S, thus the feerate of S must be at least as high as the better of those.
  - Condition (2) follows from the fact that for every candidate for S tried, its intersection with all prefixes of C\_1 were tried too (effectively, its intersection with S\_1 as intersecting with G is the identity). Thus it cannot be that (S\_1 \cap S) has a higher feerate than S, as it would have been chosen instead of S.

- \operatorname{chunksets}(C'\_1) is compatible with L'\_1, and thus from \operatorname{chunksets}(C'\_1) \gtrsim C\_1 it follows that the diagram of L'\_1 also satisfies the relation in (c).
- L^\ast is a merging with L'\_1, and thus L^\ast also satisfies this property.

### 2.1. Variations

It does not hurt to use the earlier form of Double LIMO, which considers all prefixes of L[S\_1], L[S\_2] and L[S\_1 \cap S\_2] rather than just the ones that align with chunks of L, as all the necessary properties are still held. More combinations can be tried too, as long as these include:

- S\_1, S\_2, and the first chunk of L (which is necessarily no worse than G itself)
- For every combination tried, also its intersection with the prefixes of the chunking of L.
- For every combination tried, also its intersection with S\_1.
- For every combination tried, also its intersection with S\_2.

In fact, this can be done dynamically, which may be desirable for larger numbers of S\_i sets:

- Set S to be the highest-feerate among S\_1, S\_2, and c\_1 (the first chunk of L).
- While S keeps changing:
  - Replace S with the highest-feerate among:
    - The intersections between the current S and the chunk prefixes of L.
    - The intersection between the current S and S\_1.
    - The intersection between the current S and S\_2.

---

_[View the full topic](https://delvingbitcoin.org/t/limo-combining-the-best-parts-of-linearization-search-and-merging/825)._