← index

LIMO: combining the best parts of linearization search and merging

An archive of delvingbitcoin.org · view original topic →

Pieter Wuille · #1 ·

LIMO: Linearization through Incremental Merging of Optimizations

1. Introduction

Consider the linearization algorithm as suggested in How To Linearize Your Cluster, excluding the approach from Section 1.2 (Bottleneck Splitting). In broad lines:

One might expect that this algorithm will always produce a linearization which is (by the convex-hull feerate diagram metric) at least as good as straight up picking the best ancestor sets of what remains, as this is just additionally doing search on top. It turns out this is not the case. In fact, it may (rarely) be strictly worse.

Consider the following example cluster:

graph BT
  T0["B: 11"];
  T1["C: 7"];
  T2["D: 10"];
  T3["E: 7"];
  T4["A: 1"];
  T0 --> T4;
  T2 --> T1 --> T4;
  T3 --> T4;

Ancestor-set based linearization. The consecutive remaining best ancestor sets are AB (6), CD (8.5), and E (7), and the resulting [A,B,C,D,E] linearization is in fact optimal, chunked as [ABCD (7.25), E (7)].

Computationally-bounded search. However, ACDE (6.25) has higher feerate than AB (but worse than ABCD), and thus a (very) bounded search might end up with ACDE as first set to include. The resulting [A,C,D,E,B] linearization, chunked as [ACDEB (7.2)], is not optimal, and strictly worse than [A,B,C,D,E].

It is not a very satisfactory situation that an algorithm that performs strictly more work can end up with a worse solution.

2. Incremental merging

Of course, we have a good algorithm for combining the best parts of two linearizations already: merging.

With that, it is possible to compute two separate linearizations, one using just ancestor sets, and one using bounded search, and then merging the two. But that has downsides too; either:

Overall, it feels like using merging to address this comes “too late”. Ideally, we would incorporate the findings of ancestor sort as input to the search. This can be accomplished by turning the overall linearization algorithm into a improvement algorithm:

Definition. The notation L \triangleleft S, for a linearization L of graph G and set S is used to mean L[S] + L[G \setminus S], i.e. L but with the subset S moved to the front.

The optimization step above can then be written as \operatorname{merge}(L, L \triangleleft S). This is a strict improvement over the existing linearization algorithm, which can be seen as switching to L \triangleleft S directly. In addition to guaranteeing a result that is as good as the combinations of prefixes of found subsets, the optimization step also guarantees a result that is as good as the initial linearization. And contrary to the merge-at-the-end strategy, the subset searches get to take advantage of the quality of the initial linearization too, as that affects what remains in L (and more, see below).

3. Single-set improvement steps

The approach above requires performing a \operatorname{merge} operation for every search step, which can be up to cubic in complexity, as \operatorname{merge} may take up to \mathcal{O}(n^2) time, and we may need to run it up to n times. This would make the overall operation potentially significantly slower than just merging once at the end.

To address that, observe that the merging algorithm itself works by incrementally moving high-feerate subsets to the front. If instead of performing a full merge in every step, we just determine what the first to-be-moved subset would be for the resulting merge, and output that before continuing with what remains of the linearization, we are back to quadratic complexity.

The result is the LIMO algorithm:

Definition. \Pi(L) denotes the highest-feerate prefix of L (i.e, its first chunk).

As long as the consecutive S sets do not degrade in quality, the resulting linearization will be as good as all its combined prefixes.

For every search step an initial guess l is known: the highest-feerate prefix of what remains of the initial linearization. This l can be used as the initial \operatorname{best} inside the search algorithm (instead of \varnothing), which may allow earlier pruning of work queue items whose \operatorname{pot} isn’t better (see Section 2.2), and can reduce the initial size of \operatorname{imp} (see Section 2.3).

4. Improving existing linearizations

So far, we have considered LIMO as a replacement for a “cold-start” linearizations, for clusters which do not have a linearization already, or for merging as a linearization retry with an existing one. It could however also be used to improve existing linearizations, by passing in that existing linearization as initial L, rather than an ancestor-based linearization.

In that setting, it would be useful if the algorithm could merge in two distinct S sets in every iteration, e.g. one found through ancestor-set linearization and one through search, effectively moving the ancestor-set logic into the algorithm itself rather than using it as an input.

It gets more complicated to have two sets if we want to guarantee a result that’s as good as both, and as good as the initial linearization, but this appears to work (no proof, just a lot of fuzzing…). Let’s call it Double LIMO:

It appears this algorithm even generalizes to higher numbers. E.g. Triple LIMO would involve three subsets and S would loop over their 7 non-empty intersections \{S_1, S_2, S_1 \cap S_2, S_3, S_1 \cap S_3, S_2 \cap S_3, S_1 \cap S_2 \cap S_3\}.

Double LIMO can be used in cluster update situations:

The result will be at least as good as ancestor sort, at least as good as the combination of prefixes found by bounded search, and at least as good as the result of post-processing the remainder of the original linearization after replacements, all while letting the ancestor sort and bounded search operate on the best state so far.

Acknowledgements

Thanks to @ajtowns for the notational suggestions.

Gregory Sanders · #2 ·

Is running this over the non-empty S_i intersections crucial to this strategy or “just” an optimization that takes advantage of multiple searches finding interesting structure in some combined way?

Pieter Wuille · #3 · · in reply to #2

It appears to be necessary to process these intersections too, though I don’t exactly understand why.

I have a fuzz test that implements Double and Triple LIMO, with the S_i sets calculated as “whatever remains of n static fuzz-derived topologically-valid sets”, on a fuzz-derived initial linearization for a fuzz-derived cluster, and then verifies:

If I drop any of the 2^n-1 intersections, the test finds failures in the last condition.

Anthony Towns · #4 · · in reply to #3

I wonder if doing the intersections first would be an optimisation? ie S_1, S_1 \cap S_2, S_2, S_1 \cap S_2 \cap S_3, S_1 \cap S_3, S_2 \cap S_3, S_3

Pieter Wuille · #5 · · in reply to #4

Interestingly not all orderings work. These do not (will update if I find more):

Pieter Wuille · #6 ·

Huh, much simpler construction that also seems to work:

(also generalizes to triple variant)

Pieter Wuille · #7 ·

A few updates:

Pieter Wuille · #8 ·

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:

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:

1.3 The set gathering theorem

This is a variation on the gathering theorem, 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:

Then \operatorname{chunksets}(C') \gtrsim C where C' = (S, c_1 \setminus S, c_2 \setminus S, \ldots, c_n \setminus S).

Proof.

Define:

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

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')).

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:

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

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:

This is equivalent to the description earlier in this thread, 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:

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:

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:

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

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:

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

Pieter Wuille · #9 ·

Actually, there is an even simpler formulation of this. If you want to find a subset S that, which when moved to the front is not incompatible with reaching the cumulative size/fee point corresponding to each set of transactions P = \{p_1, p_2, \ldots, p_n\}, then S needs to have a feerate at least as high as every p_i, and no intersection S \cap p_i can have a higher feerate.

In the case of Double LIMO, P consists of all prefixes of chunks of L, plus S_1 and S_2.

The LIMO theorem:

Given a set P = \{p_1, p_2, \ldots, p_n\} of topological subsets of transactions of a graph G, a topological subset S of transactions of G, and a linearization L_S for S such that:

Then there always exists a linearization L of G for which:

Such an S necessarily exists, e.g. the highest-feerate subset of all combinations of intersections between the p_i sets, though more efficient approaches exist.

EDIT: expanded on these ideas more in Cluster mempool definitions & theory - #14 by sipa.