arXiv CSopen access

Bitcoin Mempool Linearization

Bitcoin Mempool Linearization

arXiv:2607.23787v1 [cs.DS] 26 Jul 2026

Arman Mollakhani1 , Pieter Wuille2 , and Dongning Guo1 1 Northwestern University, Evanston, IL {arman.mollakhani, dguo}@northwestern.edu 2 Chaincode Labs, New York City, NY [email protected]

We say a transaction in a node’s mempool is valid if all of its ancestors are either in the same mempool or are already in the node’s blockchain or ledger. Each transaction has an associated size (called weight in Bitcoin) and a fee paid to the miner of its host block. For any subset of transactions, the ratio between total fee and total size is referred to as its fee rate. The mempool linearization problem consists of partitioning the transactions in a mempool dependency graph into an ordered sequence of disjoint dependency-respecting subsets, or chunks, arranged in descending order of aggregate fee rate. Dependency-respecting means that every transaction’s ancestors within the mempool must appear in earlier chunks. An optimal linearization is important not only for highrevenue block construction, but more broadly for maintaining the efficiency and decentralization of the network itself. Nodes must continuously reason about transaction profitability throughout a transaction’s lifecycle, including fee estimation before the transaction is fully constructed, relay prioritization during propagation, eviction decisions under mempool congestion, block template construction by miners, and mempool reconciliation after blockchain reorganizations. These decisions affect whether the public peer-to-peer network can reliably propagate transactions that miners are economically motivated to include. This is directly tied to Bitcoin’s long-term censorship resistance. If the public relay network cannot efficiently communicate profitable transactions, economic incentives favor the creation of private relay systems and privileged transaction distribution channels, as has occurred in other blockchain ecosystems [1]. Over time, reliance on private relay infrastructure can increase centralization by making it more difficult for new or smaller miners to compete without access to proprietary transaction flows. By contrast, a decentralized mining ecosystem requires that miners be able to obtain sufficiently accurate market information directly from the public peerto-peer network. The mempool serves precisely this role: it is the distributed marketplace through which transaction demand, fee pressure, and profitability information are publicly disseminated. Efficient and accurate transaction prioritization is not merely a performance optimization problem, but also a core mechanism for preserving open miner participation and decentralized block production. The present work focuses on the mempool linearization problem itself rather than the computationally intractable task of selecting an optimal subset of transactions under the strict block-size knapsack constraint. This distinction is primarily

Abstract—In the Bitcoin system, transactions arrive continuously at miners’ mempools and await inclusion in future blocks. Every non-coinbase transaction must spend one or more unspent outputs created by previous transactions, inducing dependency constraints among transactions in the mempool. At the same time, miners are economically incentivized to prioritize transactions with higher fee rates, measured as transaction fee per unit size. This paper formulates the mempool linearization problem: given a set of transactions with associated fees, sizes, and dependency relationships, compute a dependency-respecting transaction ordering that maximizes fee-rate efficiency while supporting efficient updates as the mempool evolves dynamically. The problem is characterized through a partition of transactions into disjoint dependency-respecting subsets ordered by decreasing aggregate fee rate, together with an equivalent LP formulation. Motivated by structural properties of basic feasible solutions in the simplex method, a new algorithm called spanning forest linearization (SFL) is developed. Operating directly on the transaction dependency graph, SFL iteratively merges and splits chunks of transactions to refine a global ordering, and is guaranteed to terminate at an optimal solution. Evaluation on both synthetic and real-world Bitcoin mempool data shows that SFL consistently computes optimal linearizations with substantially lower runtime than competing approaches, including a method based on the parametric preflow algorithm of Gallo, Grigoriadis, and Tarjan. These results indicate that SFL provides a practical and scalable framework for transaction prioritization by decentralized miners in large and rapidly evolving mempools. SFL has also been incorporated into the Bitcoin Core codebase for transaction cluster linearization.

I. I NTRODUCTION Efficient management of unconfirmed transactions is a fundamental challenge in blockchain systems such as Bitcoin. Newly created transactions are propagated through the peer-topeer network and temporarily reside in each node’s mempool while awaiting inclusion into future blocks. Because block space is limited and transaction fees provide economic incentives for prioritization, nodes must continuously determine which transactions are most profitable to relay, retain, evict, or include in blocks. As block construction and mempool management diretly affect mining profitability, network performance, and security, efficient transaction ordering has become a fundamental algorithmic primitive in Bitcoin and related blockchain systems. This task is complicated by transaction dependencies: every non-coinbase transaction must spend one or more unspent outputs created by previous transactions, and therefore cannot be included in a blockchain before all of its ancestors. In this paper, we formally define the mempool linearization problem. 1

2

motivated by practical considerations. In realistic mempools, optimal chunks are typically much smaller than the overall block capacity, making the determination of the full chunk ordering more important than fine-grained optimization for specific block boundaries. Moreover, profitability reasoning frequently occurs before mining time, when the eventual block boundary is unknown because future transaction arrivals cannot be predicted. The quest for optimal mempool linearization can draw upon established paradigms in computer science and operations research. One approach reduces linearization to a sequence of maximum-ratio closure problems solvable using parametric preflow techniques, such as the Gallo-Grigoriadis-Tarjan (GGT) framework [2]. Another formulation casts the problem as an integer linear program, for which we demonstrate that an exact binary solution can be recovered from an optimum of linear programming (LP) with relaxations. While these approaches provide useful theoretical foundations, practical demands of real-time mempool management impose strict runtime requirements because the mempool evolves continuously under highly dynamic and potentially adversarial conditions, necessitating solutions that are exceptionally fast. To address these challenges, this paper develops a new algorithmic framework called spanning forest linearization (SFL). Inspired by the structural properties of basic feasible solutions in the simplex method, SFL operates directly on the transaction dependency graph and iteratively refines a global ordering through local merge and split operations on chunks of transactions. The algorithm is guaranteed to terminate at an optimal linearization. In addition, SFL naturally functions as an “anytime” algorithm, producing valid progressively improving linearizations through execution. This property is particularly important in adversarial settings, where computational budgets may be limited and attackers may attempt to construct pathological dependency structures. Because SFL distributes computational effort across the transaction graph and can incorporate randomized refinement strategies, it avoids concentrating optimization effort on only a small portion of the mempool, thereby improving robustness against adversarial manipulation. Extensive numerical evaluations on both synthetic and realworld Bitcoin mempool data demonstrate that SFL consistently computes optimal linearizations with substantially lower runtime than competing methods, including approaches based on the GGT parametric preflow algorithm. SFL has also been incorporated into the Bitcoin Core codebase1 for transaction cluster linearization, demonstrating its practical suitability for deployment in production blockchain systems. The remainder of this paper is organized as follows. Sec. II reviews related work. Sec. III formally defines the mempool linearization problem. Secs. IV and V describe the LP and SFL approaches in detail, respectively. Sec. VI presents numerical results. Sec. VII summarizes our findings and discusses future research. 1 See https://github.com/bitcoin/bitcoin/pull/32545 for the patch introducing

it.

II. R ELATED W ORK The problem of optimally ordering a set of transactions to maximize fee efficiency is mathematically equivalent to the classical single-machine non-preemptive scheduling P problem with precedence constraints, denoted (1 | prec | j wj Cj ). The foundational version of this scheduling problem was first studied by Smith [3]. In this equivalent formulation, transaction sizes correspond to job processing times, and transaction fees correspond to job weights (or penalties for delay). Finding the exact optimal sequence for this problem is fundamentally NP-hard [4]. To tackle this intractability, Sidney [5] introduced a foundational decomposition algorithm that partitions the jobs into an ordered sequence of subsets, ensuring that jobs in earlier subsets always precede those in later ones in any optimal schedule. While finding the optimal sub-ordering within each subset remains NP-hard, Sidney’s decomposition provides a rigorous framework for simplifying the broader sequencing task. Potts [6] proposed a branch and bound algorithm for this scheduling problem, deriving new lower bounds from a zero-one programming relaxation. Chudak and Hochbaum [7] presented a simplified LP relaxation for this scheduling problem that can be solved via a minimum cut computation. The classical formulation of maximum flow in networks was first developed by Ford and Fulkerson [8], who introduced augmenting path algorithms and established the maxflow min-cut theorem. An important shift in maximum flow algorithms came with the introduction of the preflow concept by Goldberg and Tarjan [9], which allows temporary violations of flow conservation and guides excess flow using valid distance labels. This method laid the foundation for the development of efficient preflow-push algorithms. Cheriyan and Maheshwari [10] provided a detailed analysis of the preflow-push paradigm, introducing optimizations based on vertex selection strategies that improve practical performance. Picard and Queyranne [11] explored applications of minimum cuts in combinatorial optimization, including closure and separation problems, and demonstrated their relevance in dynamic settings. These network flow and cut concepts are fundamental to one of the approaches we explore. Gallo, Grigoriadis, and Tarjan [2] introduced a fast algorithm for solving parametric maximum flow problems. Their technique solves a sequence of related minimum cut instances by incrementally updating the flow and label states, leveraging the structural monotonicity across parameter values. This strategy is particularly effective for problems where a parameter (e.g., a fee rate) evolves incrementally, as in our setting. Notably, the breakpoints identified by the GGT algorithm in our problem setting correspond to the Sidney decomposition [5] when the problem is viewed as a single-machine scheduling instance, and thus to what we call chunks in the mempool linearization. A recent line of work [12] introduces a simpler algorithm for monotone parametric minimum cut that identifies breakpoints in order without relying on dynamic trees or advanced flow computations. This method provides a conceptually cleaner alternative to classical parametric flow approaches and has been shown to perform well in practice

3

for sparse graphs. The maximum-ratio closure problem, central to the GGTbased approach is a specific case of fractional combinatorial optimization, a well-studied class of problems involving the maximization of ratio-type objectives. Foundational ideas in this space were introduced by Isbell and Marlow [13], who studied ratio-based objectives in discrete optimization. Building on this direction, Pardalos and Phillips [14] developed a globally convergent algorithm for fractional programming problems, establishing theoretical bounds and exploring both linear and quadratic cases. The reduction of the maximumratio closure problem to a sequence of min-cut computations, as employed in the GGT approach is inspired by these prior works. Another relevant line of work addresses the maximum weight closure problem, which forms the basis for solving the more general maximum-ratio closure problem. A key algorithm in this area was introduced by Hochbaum [15], inspired by the seminal Lerchs-Grossmann (LG) algorithm originally developed for the open-pit mining problem [16]. Hochbaum provides a detailed analysis and presents powerful new variants of the LG algorithm, which solves the maximum closure problem directly, without explicitly computing or maintaining a feasible flow. Instead, the algorithm operates on a “normalized tree” structure, iteratively merging and renormalizing branches that represent sets of nodes. Beyond specialized flow and fractional programming techniques, LP offers a general and powerful framework for solving optimization problems. The seminal simplex algorithm [17], though potentially exponential in its worstcase [18], is highly efficient for a wide range of practical problems. For many combinatorial optimization problems, LP relaxations can be exact, meaning their optimal solutions are integral and directly solve the original discrete problem. The LP approach leverages this by formulating the mempool linearization problem as an LP and proving that an optimal binary solution can be recovered, thus allowing the use of standard LP solvers. These diverse optimization paradigms—parametric network flows, fractional programming, and LP—provide the theoretical underpinnings for the algorithms we develop and analyze for the mempool linearization problem. Each offers distinct advantages and insights into structuring and solving this complex task. III. P ROBLEM F ORMULATION A. Mempool Linearization Problem If transaction c spends an output of transaction p, then transaction c is said to depend on transaction p, or, equivalently, transaction p is a parent of transaction c. Since transactions with missing parents cannot be included in a block, we assume no transaction misses any parents without loss of generality. A transaction may have multiple children and/or multiple parents. Since transactions cryptographically commit to their parents, we can assume that valid transaction dependencies cannot form cycles. Consider a node’s mempool consisting of n distinct transactions, indexed by 1, . . . , n. We disregard dependencies on other

transactions already included in the node’s current longest chain of blocks, as those dependencies are already respected. We further assume that if multiple transactions spend the same output, at most one of them resides in the mempool. Consequently, when assembling blocks using transactions in the mempool, it is both sufficient and necessary to respect only the dependencies within the mempool. Let V = {1, . . . , n}. These dependencies are represented by a DAG (V, E). Throughout this paper, we use the terms vertex and transaction interchangeably. There are two equivalent but oppositely oriented ways to draw edges in this DAG: • Parent-to-child representation: An edge (i, j) ∈ E means transaction i is a parent of transaction j. • Child-to-parent representation: An edge (i, j) ∈ E means transaction j is a parent of transaction i. Both conventions appear in the literature for historical reasons. In the remainder of this paper, we explicitly state which orientation is used in each algorithmic context. Definition 1 (mempool). A mempool consists of a collection of n transactions whose dependencies are represented by a DAG (V, E), where each transaction i ∈ V = {1, . . . , n} is associated with a fee fi ≥ 0 and a size si > 0. We denote the mempool as the tuple (V, E, f, s) where f = (f1 , . . . , fn ) and s = (s1 , . . . , sn ). The total fee and size ofPa subset of transactionsPU ⊆ V are denoted as f (U ) = i∈U fi and s(U ) = i∈U si , respectively. Further, if U is non-empty, its fee rate is r(U ) =

f (U ) . s(U )

(1)

As a convention, we set r(∅) = 0. For two sets of transactions A and B, we write A ⪰ B if r(A) ≥ r(B), and A ⪯ B if r(A) ≤ r(B). The strict versions A ≻ B and A ≺ B are defined analogously. The notion of fee rate extends to graphs: Given a graph G′ = (V ′ , E ′ ), we let r(G′ ) = r(V ′ ). Definition 2 (closure). A non-empty subset U ⊆ V is called a closure in graph G = (V, E) if, for every i ∈ U , all parents of i are also contained in U . The fundamental problem facing a node is to determine the order in which transactions should be included in future blocks. We formalize this as follows. Definition 3 (valid ordering). A valid ordering of a set of transactions U ⊆ V with respect to DAG (V, E) is a bijection σ : U → {1, . . . , |U |} such that for every edge (i, j) ∈ E with i, j ∈ U (in the parent-to-child representation), the parent appears before the child: σ(i) < σ(j). A valid ordering of mempool (V, E, f, s) is a valid ordering of V with respect to (V, E). Given a valid ordering σ of mempool (V, E, f, s), we define the completion size of transaction i as X Ci (σ) = sj , (2) j∈V : σ(j)≤σ(i)

which is the cumulative size of all transactions occupying positions 1 through σ(i) in the ordering.

4

Consider assembling a block according to the order σ, stopping when including the next transaction would exceed the block size limit W > 0. Transaction i is included in the block if and only if Ci (σ) ≤ W , so the total fee income is X Π(σ, W ) = fi 1{Ci (σ)≤W } (3) i∈V

where 1{C} denotes the indicator2 of condition C. To evaluate an ordering independently of the actual block size, suppose W is modeled as a uniform random variable on the interval [0, s(V )]. Let us define the weighted completion size as X Γ(σ) = fi Ci (σ). (4) i∈V

The expected fee income can be expressed as X   E[Π(σ, W )] = fi Pr Ci (σ) ≤ W =

i∈V

An optimal linearization can be computed by iteratively selecting a maximum-ratio closure from the remaining subgraph until no transactions remain. Specifically, at step k, we solve

(5) maximize r(U ).

i∈V

X

for every k ∈ {1, . . . , m}, Uk is a closure in the subgraph of G induced by V \Bk−1 , where Bk−1 = U1 ∪· · ·∪Uk−1 . Let Ck denote the entire set of closures in the subgraph of (V, E) induced by V \ Bk−1 . The linearization is optimal if, for every k, Uk achieves the maximum possible fee rate among all closures in Ck . An optimal linearization is minimal if, for every k, Uk is a closure of minimum size s(Uk ) among those achieving the maximum fee rate in Ck . We extend the notion of linearization to allow graphs (and
trees in particular): We say graphs (U1 , E1 ), . . . , (Um , Em ) form a linearization of (V, E, f, s) if (U1 , . . . , Um ) is a linearization. •

 fi

Ci (σ) 1− s(V )

1 = f (V ) − Γ(σ). s(V )

(6) (7)

Minimizing Γ(σ), which is equivalent to maximizing the expected fee income, is precisely the single-machine nonpreemptive scheduling problem with precedence constraints, where transaction sizes correspond to job processing times and transaction fees correspond to job weights. For general precedence constraints, this problem is NP-hard [4]. Sidney [5] established that in any instance of this problem, there exists an optimal valid ordering and a sequence of sets ∅ = B0 ⊂ B1 ⊂ · · · ⊂ Bm = V such that: • B1 , . . . , Bm are closures in G; • defining Uk = Bk \ Bk−1 , the sets are ordered by fee rates: U1 ⪰ U2 ⪰ · · · ⪰ Um ; and • in the valid ordering, all transactions in Uk appear before all transactions in Uk+1 , for every k. This decomposition reduces the global ordering problem into two subproblems: (i) identifying the sets and their ordering, and (ii) ordering transactions optimally within each set. The second subproblem remains NP-hard in general, since each set with its internal dependencies is itself an instance of a singlemachine non-preemptive scheduling problem. However, in the Bitcoin mempool setting, where the transaction dependency graph typically consists of many small independent clusters, the inter-group ordering captures the dominant structure of the problem. We therefore focus on formalizing and solving this decomposition, which we refer to as the mempool linearization problem. Definition 4 (partition). A partition of set V is a sequence of disjoint, non-empty subsets (U1 , . . . , Um ) of V such that U1 ∪ · · · ∪ Um = V . Definition 5 (mempool linearization and optimality). A linearization of mempool (V, E, f, s) is a partition of V into (U1 , . . . , Um ), such that: • U1 ⪰ U2 ⪰ · · · ⪰ Um , and 2 If C holds, 1 {C} = 1; if C does not hold, 1{C} = 0.

(8)

U ∈Ck



The ordered sequence of closures produced by this greedy procedure coincides with the Sidney decomposition [5] of the corresponding single-machine scheduling instance. A minimal optimal linearization is obtained by selecting in (8), at each step k, a closure of smallest size s(U ) among those attaining the maximum fee rate. Definition 6 (valid ordering induced by a linearization). Let (U1 , . . . , Um ) be a linearization of mempool (V, E, f, s), and let σk be a valid ordering of transactions in Uk with respect to the subgraph induced by Uk for each k ∈ {1, . . . , m}. The induced valid ordering is defined by

σ(i) = σk (i) +

k−1 X

|Uj |,

∀i ∈ Uk .

(9)

j=1

This extends to graph linearizations via Definition 5. A valid ordering σ can also provide a trivial linearization consisting of singletons: ({σ(1)}, . . . , {σ(n)}). Throughout this paper, we use the shorthand U m = k (U1 , . . . , Um ) for a sequence Pk of sets. Accordingly, f (U ) = P k k i=1 f (Ui ) and s(U ) = i=1 s(Ui ) for k = 1, . . . , m, with the convention that f (U 0 ) = s(U 0 ) = 0. To provide a quantitative metric for comparing linearizations, we introduce the geometric representation of the partitioned transaction sequence. Definition 7 (cumulative fee-size diagram). Given a partition of transactions (which may or may not be a linearization), denoted as U m = (U1 , . . . , Um ), let CU m be the continuous piecewise-linear function obtained by linearly connecting the sequence of points (s(U k ), f (U k )), k = 0, 1, . . . , m. The cumulative fee-size diagram of U m is the diagram formed by the graph of function CU m over its domain [0, s(U m )]. Definition 8 (area under the curve (AUC)). Given a partition of transactions, denoted as U m = (U1 , . . . , Um ), the area

5

under the curve is defined as the definite integral of its cumulative fee-size diagram. It can be computed as Z s(U m ) m CU m (x) dx (10) A(U ) = 0   m X 1 = s(Uk ) f (U k−1 ) + f (Uk ) . (11) 2 k=1

To establish the relationship between the AUC and optimal linearizations, we first establish several properties. Lemma 1. The non-empty intersection and union of two closures are also closures. Proof. Let U1 and U2 be two closures. To prove that U1 ∩U2 ̸= ∅ is a closure, consider an arbitrary node i in both U1 and U2 and a child of i, denoted as j. Since U1 is a closure, j ∈ U1 . Since U2 is a closure, j ∈ U2 . Thus j ∈ U1 ∩ U2 . To prove that U1 ∪ U2 is a closure, consider an arbitrary node i and its child j. If i ∈ U1 , then j ∈ U1 . If i ∈ U2 , then j ∈ U2 . In either case, j ∈ U1 ∪ U2 . Lemma 2 (prefix closure property). Let (U1 , . . . , Um ) be a linearization of (V, E, f, s). For every k ∈ {1, . . . , m}, the set U1 ∪ · · · ∪ Uk is a closure in (V, E). Proof. Let Bk = U1 ∪· · ·∪Uk for every k. Let v be an arbitrary vertex in Bk . Evidently, v ∈ Uj for some j ∈ {1, . . . , k}. Since Uj is a closure in the subgraph induced by V \ Bj−1 , every parent of v must either be in Uj or in Bj−1 . Hence all v’s parents are in Uj ∪ Bj−1 = Bj ⊆ Bk , which implies that Bk is a closure in (V, E). Lemma 3 (closure difference property). Let U and W be two closures in (V, E) such that W \ U ̸= ∅. Then W \ U is a closure in the subgraph induced by V \ U . Proof. Let v be an arbitrary vertex in W \ U and u be an arbitrary parent of v in V \ U . Since W is a closure, u must be in W . Therefore, u ∈ W ∩ (V \ U ) = W \ U . Theorem 1 (AUC as an optimality metric). Let L∗ = (U1∗ , . . . , Up∗ ) be an optimal linearization of mempool (V, E, f, s). Let L = (U1 , . . . , Uq ) be any other valid linearization of the same mempool. Then the cumulative feesize diagram of L∗ dominates that of L everywhere; that is, CL∗ (x) ≥ CL (x) for all x ∈ [0, s(V )], which implies the AUC dominance: A(L∗ ) ≥ A(L). Consequently, L∗ maximizes the AUC among all linearizations of the mempool. Theorem 1 is proved in Appendix A. B. Desirable Algorithmic Properties An effective algorithm for mempool linearization should exhibit several key properties to perform well in a real-world, dynamic, and potentially adversarial environment. First, it should function as an anytime algorithm, producing a valid and progressively improving linearization throughout its execution. In practice, the algorithm is typically subject to strict time limits and may be terminated before reaching the global optimum. In such settings, the rate of quality

improvement per unit of time is more important than the total time required to find the absolute optimum. Second, the algorithm should exhibit granularity. If multiple closures achieve the same maximum fee rate, a smallest closure is more desirable. Smaller closure reduce the approximation gap between simple greedy ordering and the exact NP-hard knapsack-like block-packing problem, enabling more precise utilization of each block’s capacity. Hence we shall seek a minimal optimal linearization. Third, the solution must demonstrate robustness against mempool manipulations. Specifically, an attacker could construct complex transaction dependency graphs designed to exploit specific algorithmic weaknesses. For example, by attaching adversarial transactions with specific fees, sizes, and dependencies to a cluster of honest transactions, the algorithm may be tricked into spending all available time attempting to improve the ordering of some selected transactions, leaving simple improvements to many other honest transactions unperformed when the time budget expires. To mitigate this, the algorithm should incorporate randomization and distribute computational effort fairly across all parts of the transaction graph, so that when execution is terminated early, all regions of the graph have received some optimization attention. C. Overview of Solutions We investigate three distinct algorithmic paradigms for solving the mempool linearization problem, each offering a unique perspective on balancing optimality, performance, and practical utility. We first describe an equivalent LP formulation for the maximum-ratio closure problem (8), so that the full suite of LP solvers, including the simplex method and interior-point methods, can be applied to solve the mempool linearization problem exactly. Our primary algorithmic innovation in this paper is the development of SFL, which is inspired by the structural properties of basic feasible solutions in the simplex method. SFL operates directly on the transaction graph, iteratively merging and splitting groups of transactions to refine a global linearization. SFL is explicitly designed to satisfy all the desirable algorithmic properties outlined in Sec. III-B. Our empirical results show that SFL is exceptionally fast in practice, making it a strong candidate for real-time deployment. To provide a theoretical foundation and benchmark for comparison, we also consider solving the maximum-ratio closure problem using the GGT parametric maximum flow framework. Since GGT’s parametric breakpoint algorithm can be straightforwardly applied to our problem setting, we describe it in Appendix E and focus on benchmarking its performance against SFL. These approaches are compared empirically in Sec. VI, where we benchmark their performance on both synthetic and real-world mempool data. IV. L INEARIZATION VIA LP In this section, we present a solution to mempool linearization based on LP. We first formulate the search for a maximumratio closure 8 in each step as a binary program and then

6

show that it can be reduced to an equivalent linear program. Throughout this section, we consider the graph G = (V, E) with the parent-to-child representation.

tx 1 0/1

tx 2 20/1

tx 3 0/1

tx 4 20/1

A. Reduction to LP Without loss of generality, we consider the search for the first closure U1 ⊆ V that maximizes the fee rate. Let zi ∈ {0, 1} indicate whether transaction i is included in U1 . Problem 8 can be reformulated as a binary program (BP): P fi zi ∗ rBP = maximize Pi∈V (12a) z1 ,...,zn i∈V si zi subject to zi ∈ {0, 1}, ∀i ∈ V (12b) X zi > 0 (12c) i∈V

zi ≥ zj ,

∀(i, j) ∈ E.

(12d)

We require zi ≥ zj for every parent-child pair (i, j), ensuring that no transaction is included without its parents. Consider the following fractional program (FP): P fi yi ∗ (13a) rFP = maximize Pi∈V y1 ,...,yn i∈V si yi subject to yi ≥ 0, ∀i ∈ V (13b) X yi > 0 (13c) i∈V

yi ≥ yj ,

∀(i, j) ∈ E.

(13d)

This FP can be viewed as the BP in (12) with the binary constraints relaxed. In Appendix B, we show that the relaxation yields no increase in the maximum fee rate. Furthermore, we transform the FP to an equivalent linear program an destablish the following result: Theorem 2. Given any strictly positive real numbers s1 , ..., sn and nonnegative numbers f1 , ..., fn , if (x1 , ..., xn ) solves the following LP, X ∗ rLP = maximize fi xi (14a) x1 ,...,xn

subject to

i∈V

X

si xi = 1

(14b)

Fig. 1: An example of a transaction dependency graph. Each transaction i is shown as a circle annotated with its fee and size: “fi /si ”. The dotted boundaries enclose the minimal optimal closure and a larger optimal closure; both have the same fee rate.

E = {(1, 2), (2, 3), (3, 4)}. Let all sizes be si = 1, and the fees be f1 = 0, f2 = 20, f3 = 0, and f4 = 20. The maximum optimal fee rate is r∗ = 10. This is achieved by two valid closures: the minimal closure {1, 2}, and the larger closure {1, 2, 3, 4}. The optimal value is achieved along a flat face of the feasible polytope. The vertices defining this optimal face are: • vertex 1: x1 = x2 = 1/2, x3 = x4 = 0, and • vertex 2: x1 = x2 = x3 = x4 = 1/4. Any convex combination of these vertices, such as the edge midpoint (x1 = x2 = 3/8, x3 = x4 = 1/8), is also an optimal solution. The specific xi values returned depend entirely on the solver mechanism. For instance, an interior-point method might terminate on the midpoint; applying the exact extraction rule (15) successfully isolates the minimal closure {1, 2}. However, the Simplex method exclusively explores the vertices of the polytope and will not return an intermediate edge value. It has no inherent preference to terminate on either vertex 1 or vertex 2. If it terminates on vertex 1, the extraction rule isolates {1, 2} (minimal). If it terminates on vertex 2, the maximum value is 1/4 for all variables, meaning the extraction rule isolates the entire set {1, 2, 3, 4} (not minimal). One way to isolate a minimal optimal closure is via a two∗ stage approach. Once the maximum optimal fee rate rLP is found from the primary LP, we can formulate a secondary BP to explicitly minimize the total size of the closure, subject to the dependency constraints and the requirement that it achieves the optimal rate:

i∈V

xi ≥ 0,

∀i ∈ V

(14c)

xi ≥ xj ,

∀(i, j) ∈ E,

(14d)

minimize z1 ,...,zn

then (z1 , . . . , zn ) defined by zi = 1{xi ≥xj ,∀j∈V }

(15)

solves BP (12). Theorem 2 is proved in Appendix B. In 14, each transaction i ∈ V is associated with a nonnegative real-valued variable xi ≥ 0 (called transaction variable), where xi = maxj∈V (xj ) indicates that transaction i is included in the solution set, and excluded otherwise. The LP formulation does not inherently guarantee a minimal optimal closure. To see this, consider an example transaction graph, illustrated in Fig. 1, consisting of a set of four transactions, V = {1, 2, 3, 4}, with parent-to-child dependencies

subject to

X

si zi

(16a)

i∈V

X

∗ fi zi ≥ rLP

X

si zi

(16b)

zi ≥ zj , ∀(i, j) ∈ E X zi ≥ 1

(16c)

i∈V

i∈V

(16d)

i∈V

zi ∈ {0, 1},

∀i ∈ V.

(16e)

The constraint (16d) ensures the solution is non-empty. This formulation strictly returns the indicator variables zi for a smallest valid closure that matches the maximum fee rate. In Sec. V-F, we introduce a technique involving perturbation to guarantee the retrieval of a minimal optimal closure.

7

B. Simplex Algorithm for Mempool Linearization The simplex algorithm for solving LPs operates on the vertices of the feasible polytope [17]. Despite its exponential worst-case time complexity, the simplex algorithm is remarkably efficient in practice, often exhibiting polynomial-time behavior on real-world problems [19]. The deterministic simplex algorithm’s exponential complexity arises from pathological inputs [18], where a fixed pivot rule is forced to traverse a long path of vertices. Randomized variants of the simplex algorithm circumvent this issue by modifying the pivot rule to incorporate randomness, for example, by choosing a variable uniformly at random from all eligible candidates that improve the objective function [20], [21]. To apply the simplex method, we first convert the inequality constraints (14d) into the standard form. Specifically, for each dependency (p, c) ∈ E, a slack variable dp,c is introduced to replace the constraint as dp,c = xp − xc

(17)

dp,c ≥ 0.

(18)

Let m = |E| denote the number of dependencies. Along with the normalization constraint (14b), we obtain a system with n + m variables and m + 1 equations. At each step, the simplex algorithm maintains a basic feasible solution (BFS), corresponding to a vertex of the feasible polytope, by partitioning the variables into two disjoint sets: • n − 1 non-basic (free) variables: These are not currently in the basis and set to zero. They are considered “free” because they are eligible to enter the basis during pivot steps. • m + 1 basic variables: These are part of the current basis (solution), which are uniquely determined by the system of m + 1 equations with the free variables set to zero. At each iteration, the algorithm performs a pivot operation by selecting one non-basic variable to enter the basis (become basic and potentially positive) and one basic variable to leave the basis (become non-basic and set to zero). This transition moves from one vertex of the feasible polytope to an adjacent vertex, ideally improving the objective function value. Lemma 4 (uniformity). At any BFS of LP (14), all strictly positive variables take the exact same value. Proof. At any BFS, exactly n + m linearly independent constraints must be active in the LP’s standard form with n transaction variables and m slack variables. Since the m+1 equality constraints are always active, exactly (n+m)−(m+1) = n−1 of the non-negativity constraints (on both transaction and slack variables) must be active [22]. Let Z ⊆ V be the index set of active transaction constraints (xi = 0), and let D ⊆ E be the set of edges which correspond to active slack constraints (dp,c = 0), such that |Z| + |D| = n − 1. For every (p, c) ∈ D, substituting dp,c = 0 into (17) yields an equation xp − xc = 0. For the basis of the BFS to be linearly independent, the edge set D cannot contain cycles. If a cycle existed linking vertices v1 , . . . , vk , the sum of their corresponding active slack equations (xv1 − xv2 ) + · · · + (xvk − xv1 ) = 0 would demonstrate

linear dependence. Thus, D forms a forest on the vertices of V . The forest with n vertices and |D| edges contains exactly n − |D| trees [23]. Substituting |D| = n − 1 − |Z| yields exactly |Z| + 1 trees. Within each tree, the active constraints xp − xc = 0 force all transaction variables xi to a single uniform value. To maintain linear independence of the basis, no two of the |Z| active constraints xi = 0 can fall in the same tree. Thus, exactly |Z| distinct trees are forced to have xi = 0, leaving exactly one tree, denoted C ∗ , to have a strictly positive uniform transaction value v > 0. Moreover, for any dependency (p, c) ∈ E, the slack variable dp,c = xp − xc is strictly positive if and only if p ∈ C ∗ and c ∈ / C ∗ , which yields dp,c = v − 0 = v. Therefore, every strictly positive variable in the BFS evaluates to the exact same value v. Given a BFS, we say two transactions p and c are in the same “chunk” if dp,c is a free slack variable, i.e., dp,c = 0 is an active dependency constraint. By extension, a chunk includes a set of transactions that are connected through free slack variables. Due to additional structural constraints imposed by the simplex algorithm, several properties follow. By Lemma 4, a BFS determines the roles of each variable. A transaction variable xi > 0 is included in the current best closure, while xi = 0 is excluded from it. A slack variable with dp,c = 0 enforces that the corresponding parent and child transactions (p, c) are either both included in or both excluded from a chunk. A slack variable with dp,c > 0 indicates that the parent is included in the current best closure, but the child is not. Additionally, all chunks, except for one, contain a free transaction variable, and are thus excluded from the current best closure. Overall, this means that each BFS of the LP corresponds to a unique partitioning of the DAG into chunks. Each chunk internally forms a spanning tree. Among these chunks, exactly one (the one with no free transaction variable) attains the highest fee rate possible. Each pivot operation in the simplex algorithm corresponds to a structural modification of the chunks: 1. A free variable is selected to enter the basis: This choice is guided by seeking to improve the objective function (overall fee rate). • If a transaction variable xi is chosen to enter: An entire chunk that was previously excluded (because xi was free, setting all its chunk transaction values to 0) is now targeted. This previously-excluded chunk has a fee rate higher than that of the current ‘included’ chunk (the current best solution candidate). It may become included, or end up being merged with another (included or excluded) chunk. • If a slack variable dj is chosen to enter: A dj variable that was free (which enforced xpj = xcj for its associated parent pj and child cj , keeping them in the same chunk) becomes basic. This effectively splits the original chunk into two separate sub-chunks: one containing pj , and the other cj . Such a pivot may be selected if the sub-chunk containing pj has a higher fee rate than the currently

8

included chunk, or if the one containing cj has a lower fee rate than the currently included chunk. 2. A basic variable is selected to leave the basis (becoming free): This step maintains the correct number of free and basic variables and adjusts the solution structure. • If a transaction variable xi is chosen to leave: The xi variable associated with the previously ‘included’ chunk becomes free. This forces its value to 0, thereby excluding that entire chunk from the solution. This occurs if the chunk that was “made non-excluded”, or split off as described above, has no (basic) dependencies on another chunk. • If a dependency slack variable dj is chosen to leave: This enforces xpj = xcj for the transactions pj and cj linked by this dj . The effect is to merge the “non-excluded” or newly split-off chunk with an adjacent chunk it depends on. Through this process, the simplex algorithm systematically explores the space of valid chunk decompositions, moving from one vertex of the feasible polytope to another, until it identifies the dependency-respecting subset of transactions with the highest fee rate. Based on the understanding established in this section, the next section introduces an alternative approach to solving the mempool linearization problem. V. S PANNING F OREST L INEARIZATION This section introduces the SFL algorithm, which computes a linearization by iteratively refining a partition of the transaction graph G = (V, E) into disjoint chunks. Inspired by the chunking behavior of BFS in the simplex method, SFL begins with all transactions as singletons and proceeds through a sequence of merge and split operations guided by local fee rate comparisons. The algorithm first produces an optimal linearization and subsequently performs a minimization phase to obtain a minimal optimal linearization. The parent-to-child representation is used throughout this section. A. Basic SFL Algorithm The basic algorithm maintains a subset of “active” dependencies in E. Each active dependency corresponds to a free slack variable from the simplex formulation. A crucial invariant of the algorithm is that the set of active dependencies must remain acyclic when their directions are ignored. Definition 9 (active forest and tree). Let (V, E) denote a transaction dependency graph. Let A ⊆ E denote a set of active dependencies such that (V, A) contains no undirected cycles (i.e., its underlying undirected graph is a forest). Let {T1 , . . . , Tm } denote the set of weakly connected components of (V, A); each Ti is a polytree, i.e., its underlying undirected graph is a tree. We refer to Ti as an active tree (or, with slight abuse of terminology, simply as a tree). We call (V, A) the active forest and write T ∈ (V, A) to denote that T is one of the active trees of (V, A), and write v ∈ T to denote that transaction v belongs to active tree T .

Algorithm 1 Basic SFL 1: Input: A mempool (V, E, f, s) 2: Initialize: Set of active dependencies A ← ∅ 3: repeat 4: Esplit ← {(p, c) ∈ A | Hp ≻ Hc } 5: Emerge ← {(p, c) ∈ E \ A | Hc ⪰ Hp } 6: Pick arbitrary e ∈ Emerge ∪ Esplit 7: Add e to A if e ∈ Emerge ; remove e from A if e ∈ Esplit 8: until Emerge ∪ Esplit = ∅ 9: (T1 , . . . , Tm ) ← active trees of (V, A),

sorted by descending fee rate, with ties broken arbitrarily 10: σ ← a valid ordering induced by (T1 , . . . , Tm ) 11: Return: (T1 , . . . , Tm ), σ

Definition 10 (parent and child trees). Let (V, A) be the active forest of a mempool (V, E, f, s). Let A′ = A \ {(p, c)}, so (p, c) is inactive in (V, A′ ). We use Hp to denote the active tree in (V, A′ ) that includes p, called the parent tree, and use Hc to denote the active tree in (V, A′ ) that includes c, called the child tree. The basic SFL outlined in Algorithm 1 proceeds by repeatedly applying two operations: • Merge: For any inactive dependency (p, c), if Hc ⪰ Hp , then activate the dependency to merge the parent and child trees into one. • Split: For any active dependency (p, c), if Hp ≻ Hc , then deactivate the dependency to split the tree into two trees. This process continues until no further merges or splits are possible. At that point, the set of chunks corresponding to the final forest of trees is sorted in descending order of fee rate to produce the linearization. If two chunks have equal fee rates, they can be ordered arbitrarily. Lemma 5 (boundary partition). In an active tree (H, EH ), let I denote a closure that is a non-empty proper subset of H, and let J = H \ I. Let B = {(p, c) ∈ EH | p ∈ I, c ∈ J}. Then the sets {Hc }(p,c)∈B are pairwise disjoint and [ J= Hc . (19) (p,c)∈B

Proof. Since I is a closure in (H, EH ), no edge of EH enters I from J; hence every edge with one endpoint in I and one in J lies in B, and removing the |B| edges in B severs all paths between I and J, partitioning H into exactly |B| + 1 disjoint connected componenets. Since I remains exactly one of these components, the remaining |B| components are precisely the child trees Hc for each (p, c) ∈ B, establishing the disjoint union (19). Definition 11 (q-function). For any two sets of transactions, A and B, we define the q-function as: q(A, B) ≜ f (A)s(B) − f (B)s(A).

(20)

It is easy to see that the q-function is antisymmetric, i.e., q(A, B) = −q(B, A) for all A and B, which implies that q(A, A) = 0. Moreover, for non-empty A and B, q(A, B) > 0 if and only if r(A) > r(B).

9

Lemma 6 (bilinearity of q-function). The q-function is bilinear over disjoint unions, i.e., q(A ∪ B, H) = q(A, H) + q(B, H)

(21)

q(H, A ∪ B) = q(H, A) + q(H, B)

(22)

for all A, B, and H satisfying A ∩ B = ∅. In particular, q(A ∪ B, B) = q(A, B).

(23)

Proof. Because A and B are disjoint, we have f (A ∪ B) = f (A) + f (B) and s(A ∪ B) = s(A) + s(B). This results in:

which includes a summation over all (ordered) pairs of transactions, including pairs that belong to the same chunk. The chunk decomposition thus retains exactly the cross-chunk contributions while discarding the intra-chunk ordering terms. These discarded terms constitute the NP-hard residue identified by the Sidney decomposition. Lemma 8 (boundary q-sum). Let B, H, I, and J be defined as in Lemma 5. Then X q(Hp , Hc ) = q(I, J). (33) (p,c)∈B

q(A ∪ B, H) = f (A ∪ B)s(H) − f (H)s(A ∪ B) (24)

= f (A) + f (B) s(H) − f (H) s(A) + s(B) (25) = q(A, H) + q(B, H).

(26)

Hence (21) is established, and (22) is then easily proved using the antisymmetric property of q. Applying (21) with H = B and using the fact that q(B, B) = 0 lead to (23). Lemma 7 (AUC in terms of q-values). For any partition U m = (U1 , . . . , Um ) of V , 1 1 X A(U m ) = f (V ) s(V ) + q(Ul , Uk ). (27) 2 2 1≤l<k≤m P P Proof. proof, l<k abbreviates 1≤l<k≤m P Throughout thisP and l̸=k abbreviates 1≤l,k≤m, l̸=k . Expanding the definition of the AUC (11), we have m

A(U m ) =

X

f (Ul )s(Uk ) +

1X f (Uk )s(Uk ). 2

(28)

k=1

l<k

Proof. For every (p, c) ∈ B, the sets Hp and Hc disjointly partition H. By Lemma 5, the child trees {Hc } disjointly partition J. We repeatedly apply Lemma 6 to write X X q(Hp , Hc ) = q(Hp ∪ Hc , Hc ) (34) (p,c)∈B

(p,c)∈B

=

X

q(H, Hc )

(35)

(p,c)∈B



 [

= q H,

Hc 

(36)

(p,c)∈B

= q(H, J)

(37)

= q(I ∪ J, J)

(38)

= q(I, J)

(39)

where (34) follows from (23) of Lemma 6, and (36) uses the fact that the child trees {Hc }(p,c)∈B are pairwise disjoint by Lemma 5.

1X = f (Ul )s(Uk ) + f (Uk )s(Ul ) 2 l<k

m
1X f (Uk )s(Uk ) + q(Ul , Uk ) + 2

(29)

k=1

m

m

1 XX 1X = f (Ul )s(Uk ) + q(Ul , Uk ) 2 2 l=1 k=1

(30)

l<k

where (29) is due to Definition 11, and rearranging the terms yields (30), which becomes (27). Lemma 7 sheds further light on the relationship between AUC and the valid ordering objective in (7). By the bilinearity of q (Lemma 6), the sum in (30) can be expressed as X X X q(Ul , Uk ) = q({i}, {j}), (31) l<k i∈Ul , j∈Uk

l<k

which shows that the AUC depends only on pairs of transactions belonging to different chunks. In contrast, for a complete ordering σ, Appendix C shows that the expected fee income (7), multiplied by the constant s(V ), can be written as f (V )s(V ) − Γ(σ) 1 1X 1 = f (V )s(V ) − fi si + 2 2 2 i∈V

X i,j∈V σ(j)>σ(i)

q({i}, {j}), (32)

Theorem 3 (SFL correctness). If Algorithm 1 terminates, it outputs an optimal linearization. Proof. The proof proceeds in two steps. We first show the algorithm produces a valid linearization per Definition 5 and then prove this linearization is optimal. Let U1 , . . . , Um denote the corresponding sets of transactions in the trees T1 , . . . , Tm , sorted by fee rate. Suppose, for contradiction, (U1 , . . . , Um ) is not a linearization. Since the chunks form a partition of V and satisfy r(U1 ) ≥ · · · ≥ r(Um ), there must exist a chunk Uk that is not a closure in the subgraph induced by V \Bk−1 where Bk−1 = U1 ∪· · ·∪Uk−1 . This implies there must exist a transaction c ∈ Uk and its parent transaction p ∈ Uj for some j > k. Since p and c are in different chunks, the dependency (p, c) must be inactive. Moreover, since the merge condition (line 5) Hc ⪰ Hp is satisfied, (p, c) needs to be activated according to Algorithm 1, which contradicts the assumption of termination. Hence the output must be a valid linearization. We next show that U1 has the highest fee rate among all closures in B1 = V . Since every closure in (V, E) is a closure in (V, A), it suffices to show that U1 is a highest-fee-rate closure in (V, A). Suppose, for contradiction, that some closure U ⊆ V in (V, A) satisfies r(U ) > r(U1 ). Since r(U ) is the weighted

10

average of {r(U ∩ Ui )}m i=1 and r(U1 ) ≥ r(Ui ) for all i, some k satisfies r(U ∩ Uk ) > r(U1 ) ≥ r(Uk ).

(40)

Set I = U ∩ Uk and J = Uk \ I. By Lemma 1, I is a closure in (V, A), and (40) forces I to be a non-empty proper subset of Uk . Let B = {(p, c) ∈ EA | p ∈ I, c ∈ J}. From (40), r(I) > r(Uk ) > r(J), so by Definition 11, q(I, J) > 0. Lemma 8 then yields X q(Hp , Hc ) = q(I, J) > 0, (41) (p,c)∈B

so some (p, c) ∈ B has Hp ≻ Hc , satisfying the split condition (line 4) and contradicting termination. Thus U1 is a highestfee-rate closure in (V, A), hence also in (V, E). The same argument applied recursively shows Uk is a highest-fee-rate closure in the subgraph induced by V \ Bk−1 for every k, so (U1 , . . . , Um ) is an optimal linearization. In contrast to the simplex method of Sec. IV-B, SFL does not track the identity of the free transaction variable within each excluded chunk, as it has no bearing on the chunk decomposition. Nor does SFL have a counterpart to the ‘included’ chunk, since it seeks all successive optimal chunks rather than a single highest-fee-rate closure. Merge and split decisions therefore rely on local fee rate comparisons: the two chunks involved (or, for a split, the two would-be chunks) are compared directly with each other rather than against an included chunk. In a way, SFL adopts the operational logic of the simplex method while discarding details irrelevant to the chunk structure. The basic SFL algorithm leaves several choices unspecified. In the next subsection, we identify these ambiguities and propose refinements to address them. B. Initialization We next describe a procedure for constructing a valid initial state from which the algorithm can begin optimization. The procedure L INEARIZE (Algorithm 2) starts with all dependencies inactive, so that each transaction forms its own singleton chunk, and then merges chunks until the resulting decomposition forms a valid linearization. A single merge step (M ERGE S TEP) attempts to merge a given chunk H in a specified direction by finding a neighboring chunk connected through an inactive dependency: when merging upward, it selects the lowest-fee-rate chunk that H depends on among those with fee rates lower than or equal to that of H; when merging downward, it selects the highestfee-rate chunk that depends on H among those with fee rates higher than or equal to that of H. If multiple candidates have equal fee rates, one is chosen uniformly at random. The merge is performed by activating a uniformly random inactive dependency between the two chunks. When an existing valid ordering is provided, the procedure processes each transaction from first to last in that order. For each transaction, it repeatedly applies upward merge steps on its chunk until no further merge is possible. This guarantees

Algorithm 2 Initial Linearization 1: Procedure: M ERGE S TEP(H, d, A): 2: if d = up then 3: C ← { (p, c) ∈ E \ A | Hc = H, Hp ⪯ H } 4: else 5: C ← { (p, c) ∈ E \ A | Hp = H, Hc ⪰ H } 6: end if 7: if C = ∅ then 8: return ⊥ 9: end if 10: if d = up then 11: Emerge ← { (p, c) ∈ C | r(Hp ) = min(p′ ,c′ )∈C r(Hp′ ) } R

(p, c) ← − Emerge ; H ′ ← Hp 13: else 14: Emerge ← { (p, c) ∈ C | r(Hc ) = max(p′ ,c′ )∈C r(Hc′ ) } 12:

R

15: (p, c) ← − Emerge ; 16: end if

H ′ ← Hc

17: Add (p, c) to A 18: return H ∪ H ′ , A

L INEARIZE(mempool (V, E, f, s), optional valid ordering σ) 20: A ← ∅ 21: if valid ordering σ = (v1 , . . . , vn ) is provided then 22: for i = 1, . . . , n do 23: H ← {T ∈ (V, A) | vi ∈ T } 24: (H, A) ← M ERGE S TEP(H, up, A) 25: while H ̸= ⊥ do 26: (H, A) ← M ERGE S TEP(H, up, A) 27: end while 28: end for 29: else 30: Q ← random permutation of active trees of (V, A) 31: repeat 32: H ← Q.pop() 33: if H ∈ (V, A) then 34: (d1 , d2 ) ← random permutation of {up, down} 35: for i = 1, 2 do 36: (H, A) ← M ERGE S TEP(H, di , A) 37: if H ̸= ⊥ then 38: Push H onto Q 39: break 40: end if 41: end for 42: end if 43: until Q = ∅ 44: end if 45: (T1 , . . . , Tm ) ← sort active trees of (V, A) by descending fee rate, breaking ties uniformly at random 46: σout ← valid ordering induced by (T1 , . . . , Tm ) 47: Return: (T1 , . . . , Tm ), σout , A 19: Procedure:

11

that the resulting linearization is at least as good as the input ordering, since each merge maintains or improves the AUC. When no existing valid ordering is available, the procedure processes a randomly-shuffled queue of chunks. Each chunk that is popped from the queue attempts a merge step in each of two randomly ordered directions, stopping at the first successful merge. When a merge succeeds, the resulting chunk is re-enqueued for further processing. If neither direction yields a merge, the chunk is simply discarded from the queue. The procedure terminates when the queue is empty, at which point sorting the chunks by decreasing fee rate yields a valid linearization. Lemma 9 (validity of initial linearization). Upon termination, Algorithm 2 outputs a valid linearization. Proof. Since the algorithm only adds active edges to A, it is guaranteed to terminate. By line 45, it suffices to show that at termination, Hp ⪰ Hc ,

∀(p, c) ∈ E \ A.

(42)

Suppose, for contradiction, ∃(p, c) ∈ E \ A with Hc ≻ Hp at termination. Mode 1 (lines 21–28): Suppose the algorithm calls M ERGE S TEP N times before terminating. Index the successive M ERGE S TEP calls executed during Mode 1 by k = 1, . . . , N , (k) (k) and let Hp , Hc denote parent and child trees of (p, c) after (0) (0) the k-th call; set Hp , Hc to the singletons {p}, {c}. Thus (N ) (N ) Hp = Hp and Hc = Hc . Let k ∗ ∈ {0, 1, . . . , N } be the largest index at which the ∗ k -th call modifies the tree containing c∗ (or k ∗ = 0 if no such (k ) = Hc . We claim call exists). By maximality of k ∗ , Hc ∗

Hp(k ) ≻ Hc . ∗

(43)

Indeed, immediately after call k the inner while loop (lines 25-27) reattempts M ERGE S TEP(Hc , up, A), which by maximality of k ∗ leaves Hc unchanged, hence returns ⊥ with C = ∅. Since (p, c) ∈ E \ A at termination∗ (and hence (k ) throughout, as A only grows), ∗line 3 forces Hp ≻ Hc . (k) (k ) for all k ≥ k ∗ by induction We now show Hp ⪰ Hp ∗ on k. The base k = k is trivial. For the inductive step k → k + 1, if call k + 1 does not modify the tree containing p, (k+1) (k) (k+1) then Hp = Hp and we are done. Otherwise Hp = (k) Hp ∪ H̄, where H̄ is the other tree involved in the (k + 1)-th M ERGE S TEP call. We split into two cases: (k) • Hp is the selected parent in the call: line 3 gives H̄ ⪰ (k) (k∗ ) Hp ⪰ Hp . (k) (k) • Hp is the initiator: line 3 gives H̄ ⪯ Hp , where ∗H̄ (k) (k ) is an inactive parent of Hp . We claim H̄ ⪰ Hp . ∗ ∗ Otherwise, let k0 > k be the first call after k that modifies the tree containing p by an upward merge with an (k∗ ) inactive parent H̄0 satisfying H̄0 ≺ Hp . By minimality (k −1) (k∗ ) of k0 and the induction hypothesis, Hp 0 ⪰ Hp . (k −1) Hence H̄0 ≺ Hp 0 , so H̄0 belongs to the upward (k −1) (k −1) candidate set C of Hp 0 . But when Hp 0 was formed, Mode 1 exhausted upward merges from it, so no such inactive ∗parent could remain. This contradiction (k ) proves H̄ ⪰ Hp .

(k∗ )

(k)

(k∗ )

In both cases H̄ ⪰ Hp ∗ , and combined with Hp ⪰ H∗p , (k+1) (k ) (N ) (k ) we get Hp ⪰ Hp . Therefore Hp = Hp ⪰ Hp ≻ Hc by (43), contradicting Hc ≻ Hp . Mode 2 (lines 29–43): Let Hℓ ∈ {Hp , Hc } be whichever is formed last (line 30 or 38). Hℓ is enqueued at formation and never subsequently modified, so it is eventually popped (line 32) with Hℓ ∈ (V, A) and both directions are attempted (lines 35–41). The dependency (p, c) ∈ E \ A satisfies: direction up on Hc : (p, c) ∈ C since Hp ≺ Hc , direction down on Hp : (p, c) ∈ C since Hc ≻ Hp . So whichever direction matches Hℓ , C ̸= ∅ and M ERGE S TEP succeeds, modifying Hℓ , a contradiction. •

•

C. Refining the Basic SFL Algorithm Until now, we have left unspecified the strategy for selecting which dependencies to activate or deactivate. The building blocks for the refined SFL algorithm, including the M ERGE U PWARDS, M ERGE D OWNWARDS, and I MPROVE procedures, are presented in Algorithm 3. Although it appears that making arbitrary valid choices can still yield an optimal result, such random selection may lead to revisiting previous states and performing redundant work. To avoid this inefficiency, we will introduce some heuristics and strategies to guide the algorithm and improve its convergence. One simple yet effective refinement is to prioritize merging over splitting. Conceptually, merging serves to enforce dependency constraints by joining chunks, whereas splitting serves to improve the overall fee rate by refining chunk structure. By ensuring that, after each improving split, all possible merges are performed immediately, the algorithm quickly restores a valid linearization state. This prioritization has a practical benefit: if the algorithm is interrupted early (e.g., due to a time limit), the current state remains a valid linearization, even if it is not optimal. Let us define an improvement step as one application of the splitting rule (selected by any criterion), followed by all possible merges. Let (U1 , . . . , Um ) be a valid linearization, and let (p, c) be an active dependency within some chunk Uk whose deactivation yields a parent-side chunk Hp and a childside chunk Hc with r(Hp ) > r(Hc ). Definition 12 (improvement step). An improvement step on (p, c) follows the logic of the I MPROVE procedure (Algorithm 3, lines 13–25): 1) Split: Deactivate the dependency (p, c), splitting Uk into Hp and Hc (line 18). 2) Resolution: Proceed with one of the following operations based on dependency constraints: a) Immediate Re-merge: If an inactive dependency exists such that the parent tree Hp depends on the child tree Hc , activate it (lines 17–21). This results in a selfmerge where the linearization remains unchanged. b) Restoration: Otherwise, apply M ERGE U PWARDS to Hp and M ERGE D OWNWARDS to Hc until no further merges are possible (lines 23–24). Sorting the new set of chunks results in a new valid linearization.

12

Algorithm 3 Refined SFL Building Blocks 1: Procedure: M ERGE U PWARDS(t, A): 2: H ← active tree in (V, A) containing t 3: repeat 4: (H, A) ← M ERGE S TEP(H, up, A) 5: until H = ⊥ 6: return A 7: Procedure: M ERGE D OWNWARDS(t, A): 8: H ← active tree in (V, A) containing t 9: repeat 10: (H, A) ← M ERGE S TEP(H, down, A) 11: until H = ⊥ 12: return A 13: Procedure: I MPROVE ((p, c), A): 14: if Hc ≻ Hp then 15: return A 16: end if 17: Eremerge ← {(u, v) ∈ E \ A | u ∈ Hc , v ∈ Hp } 18: A ← A \ {(p, c)} 19: if Eremerge ̸= ∅ then 20: Pick arbitrary e ∈ Eremerge 21: A ← A ∪ {e} 22: else 23: A ← M ERGE U PWARDS(p, A) 24: A ← M ERGE D OWNWARDS(c, A) 25: end if 26: return

A

When a split occurs in the improvement step, two possibilities arise: 1) If the higher-fee-rate chunk (the parent side), through another inactive dependency, depends on the lower-fee-rate chunk (the child side), the rule causes them to re-merge. The chunk remains the same as before the split, albeit with a different internal active tree. Whether this behavior can lead to infinite loops, or how many times it can repeat, is a concern that is addressed in Secs. V-D and V-E, where we introduce specific rules for selecting which dependency to split so that the algorithm is guaranteed to terminate. 2) If no such self-merge happens (because the split-off parent chunk does not depend on the split-off child), the parent and child chunks initially occupy adjacent positions in the ordered list, which may no longer be properly sorted. With a higher fee rate, the parent can only depend on chunks that preceded it, but it may have a higher fee rate than them. The rule now reduces to the chunk “bubbling up” until it either reaches a position where its fee rate is no longer higher than the preceding chunk or it encounters a lower-fee-rate dependency, merges with it, and continues bubbling upward. A reversed process occurs for the split-off child. Its fee rate is now lower than the original chunk’s, so it may be surpassed by successors. The child chunk “bubbles down” until it reaches a position where its fee rate exceeds that of the next chunk, or it encounters a higher-fee-rate dependent, merges with it, and possibly continues downward.

Lemma 10 (area gain from split or merge). Let S = (U1 , . . . , Um ) be a partition of V . Let S ′ = (U1 , . . . , Uk−1 , Uk′ , Uk′′ , Uk+1 , . . . , Um )

(44)

where Uk′ ∪ Uk′′ = Uk is a partition of Uk into two disjoint, non-empty subsets. Then: 1 A(S ′ ) − A(S) = q(Uk′ , Uk′′ ). (45) 2 Consequently, splitting Uk into (Uk′ , Uk′′ ) where Uk′ ≻ Uk′′ yields a strict increase in AUC of 12 q(Uk′ , Uk′′ ) > 0. Conversely, given a sequence containing the adjacent pair (Uk′ , Uk′′ ) where Uk′′ ≻ Uk′ , merging them into a single set Uk = Uk′ ∪ Uk′′ yields a strict increase in AUC of 1 ′′ ′ ′′ ′ 2 q(Uk , Uk ) > 0. If r(Uk ) = r(Uk ), merging them yields no change in the AUC. Proof. Since all sets except for Uk , Uk′ , and Uk′′ are identical in S and S ′ , and share the same cumulative fees from their predecessors, we have
A(S ′ )−A(S) = s(Uk′ ) f (U k−1 ) + 12 f (Uk′ )
(46) + s(Uk′′ ) f (U k−1 ) + f (Uk′ ) + 12 f (Uk′′ )
− s(Uk ) f (U k−1 ) + 12 f (Uk ) . Substituting s(Uk ) = s(Uk′ ) + s(Uk′′ ) and f (Uk ) = f (Uk′ ) + f (Uk′′ ) into (46) yields A(S ′ ) − A(S) (47) = s(Uk′′ )f (Uk′ ) − 12 s(Uk′ )f (Uk′′ ) − 12 s(Uk′′ )f (Uk′ )
1 = f (Uk′ )s(Uk′′ ) − f (Uk′′ )s(Uk′ ) (48) 2 1 = q(Uk′ , Uk′′ ). (49) 2 For a split where Uk′ ≻ Uk′′ , according to Definition 11, it holds that q(Uk′ , Uk′′ ) > 0, hence the AUC increases by 12 q(Uk′ , Uk′′ ) > 0. For a merge where Uk′′ ≻ Uk′ , we transition from the sequence S ′ to S, so the gain is A(S) − A(S ′ ) = − 12 q(Uk′ , Uk′′ ) = 12 q(Uk′′ , Uk′ ) > 0. If r(Uk′′ ) = r(Uk′ ), merging them results in no change in the AUC since 12 q(Uk′′ , Uk′ ) = 0. Lemma 11 (area gain from swapping). Let S = (U1 , . . . , Um ) be a partiton of V . Suppose Uk+1 ≻ Uk for some k ∈ {1, . . . , m − 1}. Let S ′ be the sequence obtained by swapping Uk and Uk+1 : S ′ = (U1 , . . . , Uk−1 , Uk+1 , Uk , Uk+2 , . . . , Um ).

(50)

Then, the AUC strictly increases by: A(S ′ ) − A(S) = q(Uk+1 , Uk ) > 0.

(51)

Proof. We prove this result by using Lemma 10 twice. Specifically, S ′ is obtained from S by first merging Uk and Uk+1 to obtain R and then splitting their union in R to Uk+1 followed by Uk . We have A(S ′ ) − A(S) = (A(S ′ ) − A(R)) − (A(S) − A(R)) (52) 1 1 = q(Uk+1 , Uk ) − q(Uk , Uk+1 ) (53) 2 2 = q(Uk+1 , Uk ) (54)

13

where we have also used the antisymmtry of q(·, ·) by Definition 11. Theorem 4 (strict improvement). Let L be a valid linearization. Let L′ be the linearization resulting from an improvement step on a chunk U ∈ L. If a self-merge does not occur (i.e., L′ ̸= L), then the AUC strictly increases: A(L′ ) > A(L).

(55)

Proof. The improvement step consists of a split phase followed by a resolution phase. First, in the split phase, the chunk U is replaced by the subsequence (Hp , Hc ) with Hp ≻ Hc . By Lemma 10, this operation strictly increases the AUC by 12 q(Hp , Hc ) > 0. Second, in the resolution phase (specifically the restoration case, as no self-merge occurred), the algorithm iteratively restores the sorted order of closures. This process involves examining adjacent chunks (A, B) that violate the sorting condition (i.e., B ≻ A ) and applying one of two operations: • Swapping: If A and B are independent (neither depends on the other), they are swapped to (B, A). By Lemma 11, this strictly increases the AUC by q(B, A) > 0. • Merging: If they cannot be swapped because A is a parent of B, they are merged into M = A ∪ B. By Lemma 10, this increases the AUC by 21 q(B, A) ≥ 0 (strictly positive if r(B) > r(A), or zero if r(B) = r(A)). Since the initial split yields a strictly positive gain, and every operation in the resolution phase yields a non-negative gain, the total change in AUC is strictly positive. Whenever a self-merge does not occur, the fee rate diagram strictly improves: a high-fee-rate chunk moves up, and a lowfee-rate one moves down. Thus, the barrier to guaranteed termination is the possibility of indefinite self-merging following a split. When multiple split options are available during an improvement step, a natural question is how to choose among them. Several strategies are possible. One deterministic heuristic, the maximum-q rule, selects the split maximizing q, which corresponds to the largest derivative of the LP objective with respect to the corresponding slack variable. While this heuristic tends to reduce the number of iterations in typical cases, it does not prevent cycling and can worsen adversarialcase performance; we discuss it further in Appendix D. In Secs. V-D and V-E, we introduce alternative split selection rules that provide formal termination guarantees. D. SFL Algorithm with Guaranteed Termination An algorithm constructed from the operations in Algorithm 3 may pivot indefinitely among equivalent suboptimal forests without meaningful improvement in the AUC. To prevent such cycling, we adopt a tie-breaking strategy inspired by Bland’s rule for the simplex algorithm [24]. The rule enforces a strict lexicographic ordering: whenever multiple valid candidates exist for a self-merge or split operation, the algorithm selects the edge with the lowest index. Specifically, we assign a unique, fixed index ι(e) to every dependency

Algorithm 4 SFL with Guaranteed Termination 1: Procedure: I MPROVE ((p, c), A, ι): 2: Eremerge ← {(u, v) ∈ E \ A | u ∈ Hc , v ∈ Hp } 3: A ← A \ {(p, c)} 4: if Eremerge ̸= ∅ then 5: A ← A ∪ {arg mine′ ∈Eremerge ι(e′ )} 6: else 7: A ← M ERGE U PWARDS(p, A) 8: A ← M ERGE D OWNWARDS(c, A) 9: end if 10: return A 11: Procedure: D ETERMINISTIC SFL(Mempool (V, E, f, s),

optional valid ordering σ): 12: Assign unique indices ι(e) ∈ {1, . . . , |E|} for ∀e ∈ E 13: (·, ·, A) ← L INEARIZE((V, E, f, s), σ) 14: repeat 15: Esplit ← {(p, c) ∈ A | Hp ≻ Hc } 16: if Esplit ̸= ∅ then 17: A ← I MPROVE(arg mine∈Esplit ι(e), A, ι) 18: end if 19: until Esplit = ∅ 20: (T1 , . . . , Tm ) ← active trees of (V, A), sorted by descend-

ing fee rate, ties broken arbitrarily 21: σout ← a valid ordering induced by (T1 , . . . , Tm ) 22: Return: (T1 , . . . , Tm ), σout , A

edge e ∈ E to enable lexicographical tie-breaking in edge comparisons. We present the complete SFL procedure with this indexing convention in Algorithm 4. In the remainder of this subsection, we prove Algorithm 4 is guaranteed to terminate at the optimal linearization. For a mempool (V, E, f, s), let U ⊆ V , and let F = {(u, v) ∈ E | u ∈ U, v ∈ U } denote the set of dependencies internal to U . Assume (U, F ) is weakly connected. An active tree that spans all vertices of U can be represented by T = (U, ET ), where ET ⊆ F ; we call T an active tree of (U, F ). Definition 13 (tree flow). Let T = (U, ET ) be an active tree of a connected graph (U, F ) and e = (p, c) ∈ ET . Let PeT denote the parent tree of (p, c) in T . The flow on e with respect to T is denoted as xTe = q(PeT , U )

(56)

By Definition 11, q(PeT , U ) > 0 if and only if PeT ≻ U , which is equivalent to PeT ≻ U \ PeT . Thus, q(PeT , U ) gauges the “split potential” across edge e: the tree flow of an edge indicates the result of fee rate comparisons for potentially splitting across it. Given S ⊆ U , the boundary sets of S in the active tree T = (U, ET ) of (U, F ) are denoted as: T δout (S) = {(u, v) ∈ ET | u ∈ S, v ∈ / S},

(57)

T δin (S) = {(u, v) ∈ ET | u ∈ / S, v ∈ S}.

(58)

14

Lemma 12 (conservation of potential). For any S ⊆ U , X X xTe . (59) xTe − q(S, U ) = T (S) e∈δin

T (S) e∈δout

Proof. We first prove the special case S = {v} for a single vertex v ∈ U . Removing v and its incident edges in T partitions U \ {v} into disjoint connected components {C1 , . . . , Ck }, where each component Ci connects to v via exactly one edge ei ∈ ET . For each ei : T T T • If ei ∈ δin ({v}), then Pei = Ci , so xei = q(Ci , U ). T T • If ei ∈ δout ({v}), then Pei = U \ Ci , so by Lemma 6, xTei = q(U \ Ci , U ) = q(U, U ) − q(Ci , U ) = −q(Ci , U ). (60) In both cases, the contribution of ei to the net flow leaving {v} equals −q(Ci , U ). Hence, using Lemma 6, X

X

xTe −

T ({v}) e∈δout

xTe = −

k X

q(Ci , U )

(61)

i=1

T ({v}) e∈δin

= −q

k [

! Ci , U

(62)

= −q(U \ {v}, U )

(63)

= q({v}, U ).

(64)

For arbitrary S ⊆ U , by Lemma 6 and (64), X q(S, U ) = q({v}, U )

(65)

i=1

v∈S

 =

X

T ({v}) e∈δout

X X T (S) e∈δout

X

xT(v,u) − xTe −

xTe 

(66)

T ({v}) e∈δin

v∈S, (v,u)∈ET

=

X

xTe −

 v∈S

=

 X

xT(u,v)

(67)

v∈S, (u,v)∈ET

X

xTe

(68)

T (S) e∈δin

where (68) follows from (67) because any edge e = (u, w) ∈ ET with both endpoints in S appears once as outgoing (from u) and once as incoming (at w), so its contributions cancel; only edges with exactly one endpoint in S survive. Theorem 5. The Refined SFL, Algorithm 4, terminates in a finite number of steps. Proof. Since all sub-routines’ loops in Algorithm 4 terminate in at most |V | steps, it suffices to show that the repeat-loop in the main algorithm terminates in finite steps, i.e., I MPROVE(.) in line 17 is called a finite number of times. Each improvement step consists of one split (deactivating eout ) and possibly some merges (activating edges). We distinguish two improvement step types based on their effect on the linearization L: Type 1: Linearization change. The improvement step results in a new linearization L′ ̸= L. By Theorem 4, the total AUC strictly increases. Since the number of possible linearizations is finite, there are at most a finite number of type 1 improvement steps.

Type 2: Basis exchange. The split of some active tree with vertex set U in the improvement step creates parent and child trees, but a subsequent merge immediately reconnects them via some edge ein without altering U . The linearization remains L, but the active tree changes. Let F = {(u, v) ∈ E | u ∈ U, v ∈ U } denote the internal dependencies of U , and let Tt = (U, Et ) and Tt+1 = (U, Et+1 ) denote the active trees of (U, F ) at the start of improvement steps t and t + 1, respectively, where we abbreviate ETt as Et . Then (t) Et+1 = (Et \ {eout }) ∪ {ein }. We similarly write xe to (t) (t) Tt Tt (·) and δout (·), denote xTe t , and δin (·) and δout (·) to denote δin respectively. Assume, for contradiction, that the algorithm enters an infinite cycle of type 2 improvement steps. A cycle is defined as a sequence of improvement steps where the algorithm transitions from an active forest F1 through a sequence of states and returns to F1 without altering the linearization. Let C ⊆ F be the set of edges that toggle (enter or leave) the active tree of (U, F ) during this cycle. Let emax be the highest-index edge in C. Analysis at Improvement Step t: Consider the improvement step t in the cycle where emax is chosen to split U . According to the split rule (line 17), emax was chosen because it was the valid split candidate with the minimum index and (t) xemax > 0. Therefore, every other toggling edge f ∈ C ∩ Et (t) (t) satisfies ι(f ) < ι(emax ) and xf ≤ 0 (if xf > 0, f would have been chosen). Analysis at Improvement Step s: Consider the improvement step s > t in the cycle where, immediately after some (s) edge g ∈ Es is split, dividing U into S = Hp (parent(s) side) and Hc (child-side), emax is chosen to merge them (s) back into U . Since g was a valid split, q(S, U ) = xg > 0. According to the remerge rule (line 5), emax is chosen because (s) it is the candidate with the minimum index crossing from Hc (s) to Hp . Therefore, no other toggling edge f ∈ C \ Es crosses (s) the boundary of Hp in the merging direction (otherwise its lower index would trigger selection over emax ). The Contradiction: We evaluate q(S, U ) for the set S = (s) Hp using the flows from tree Tt . By Lemma 12, q(S, U ) equals the net flow out of S in Tt : X X q(S, U ) = x(t) x(t) (69) e − e . (t)

e∈δout (S) (s)

(t)

e∈δin (S)

We know q(S, U ) = xg > 0. We examine the edges contributing to the right-hand side of (69). These must be edges in Et that cross S. Since Es and Et differ only by edges in C (i.e., edges that toggle), and the only edge in Es crossing S is g, any edge in Et crossing S must be either g (if g ∈ Et ) or an edge in C. All edges that contribute to (69) must be in Et ∩ C and cross S. They must be in one of the following three groups: 1. Edge emax ∈ Et ∩C. At improvement step s, we identified (s) (s) that emax = (u, v) connects u ∈ Hc to v ∈ Hp = S. Thus, (t) (t) emax ∈ δin (S). Its contribution to (69) is −xemax < 0. 2. Edge g contributes to (69) if g ∈ Et . As g toggles, we have g ∈ C, so ι(g) < ι(emax ). By the logic at improvement

15

(t)

(t)

step t, xg ≤ 0. Since g ∈ δout (S), its contribution to (69) is not positive. 3. Any other edge f ∈ Et ∩ C (with f ̸= emax and f ̸= g): Since f crosses S and g is the only edge of Es crossing S, f ∈ / Es . By the merge rule at step s, if f also pointed into S, it would be a valid merge candidate and would have been (t) chosen over emax since ι(f ) < ι(emax ); hence f ∈ δout (S). (t) (t) We also know xf ≤ 0. Its contribution to (69) is xf ≤ 0. Summing the contributions yield a nonpositive right hand (s) side of (69). This contradicts the fact that q(S, U ) = xg > 0. This proves that the maximal-index edge emax cannot satisfy the conditions to both leave at t and enter at s > t under the minimum-index rule. Consequently, the cycle cannot exist. By Theorem 3 and Theorem 5, the refined SFL algorithm (Algorithm 4) is guaranteed to terminate and puts out an optimal linearization. E. Randomizing the SFL Algorithm While the deterministic variant of Sec. V-D provides guaranteed termination, its reliance on fixed tie-breaking rules makes its behavior fully predictable. In order to achieve the desirable algorithmic properties discussed in Sec. III-B, especially robustness and fairness, we introduce randomization into the SFL algorithm. The key design principle is that every choice point in the algorithm, including which chunks to merge, which dependency to activate or deactivate, and the order in which to process chunks, should incorporate uniform randomness. Specifically, the randomized SFL algorithm incorporates the following elements: • Random merge target selection: When merging a chunk upwards or downwards, if multiple candidate chunks have the same fee rate (i.e., are equally valid merge targets), a uniformly random one among them is chosen. • Random dependency activation: After selecting two chunks to merge, a uniformly random dependency between them is activated, rather than selecting one by a fixed rule. • Random chunk processing order: The queue of chunks to be optimized is initialized in a uniformly random order. This ensures that no particular region of the transaction graph is systematically prioritized over others. • Random split selection: When selecting which active dependency to deactivate (split) within a chunk, a uniformly random dependency is chosen among those whose parent fee rate is strictly higher than the child fee rate. This ensures that all valid split candidates receive equal attention. Together, these randomized elements ensure that the algorithm avoids predictable behavior and distributes computational work equitably across all transactions, making it resistant to adversarial manipulation. Since non-adversariallycreated clusters are almost always linearized optimally in negligible time, the slight overhead of randomization is an acceptable trade-off for robustness. The complete randomized SFL is presented in Algorithm 5.

Algorithm 5 Randomized SFL 1: Procedure: I MPROVE ((p, c), A): 2: Eremerge ← {(u, v) ∈ E \ A | u ∈ Hc , v ∈ Hp } 3: A ← A \ {(p, c)} 4: if Eremerge ̸= ∅ then R

5: e′ ← − Eremerge ; 6: else

A ← A ∪ {e′ }

7: A ← M ERGE U PWARDS(p, A) 8: A ← M ERGE D OWNWARDS(c, A) 9: end if 10: return A

R ANDOMIZED SFL(Mempool (V, E, f, s), optional valid ordering σ): 12: (·, ·, A) ← L INEARIZE((V, E, f, s), σ) 13: Q ← random permutation of active trees of (V, A) 14: while Q ̸= ∅ do 15: T ← first active tree in Q 16: if T ∈ (V, A) then 17: Esplit ← {(p, c) ∈ A | p, c ∈ T, Hp ≻ Hc } 18: if Esplit ̸= ∅ then R 19: e∗ ← − Esplit 20: A ← I MPROVE(e∗ , A) 21: Q ← random permutation of active trees of (V, A) 22: end if 23: end if 24: end while 25: (T1 , . . . , Tm ) ← active trees of (V, A), sorted by descending fee rate, ties broken uniformly at random 26: σout ← a valid ordering induced by (T1 , . . . , Tm ) 27: Return: (T1 , . . . , Tm ), σout , A 11: Procedure:

We now prove that the randomized SFL algorithm terminates with probability 1. The proof relies on showing that from any state, the deterministic variant (Algorithm 4) provides a finite path to either an unblocked split or termination, and that randomized SFL follows this path with positive probability. Definition 14 (forest plateau). Let L = (U1 , . . . , Um ) be a valid linearization of mempool (V, E, f, s). We define the forest plateau F(L) as the set of all valid active forests A ⊆ E such that the active trees of (V, A) correspond exactly to the chunks {U1 , . . . , Um }. Any operation that modifies A without changing the linearization L (i.e., a self-merge) constitutes a transition between states within the same plateau F(L). We distinguish two kinds of improvement steps: a blocked split occurs when the resolution phase results in an immediate re-merge (leaving the linearization unchanged), and an unblocked split occurs otherwise. Theorem 6 (almost sure termination). The randomized SFL algorithm, Algorithm 5, terminates with probability 1. Proof. The set of possible linearizations of a finite mempool (V, E, f, s) is finite, and by Theorem 4, each unblocked split strictly increases the AUC. Therefore, at most finitely many unblocked splits can occur over the course of the algorithm. It suffices to show that from any linearization, the algorithm

16

performs only finitely many blocked splits before either terminating or reaching a strictly better linearization. Let Lt be the linearization at improvement step t. We show that there exists a natural number h such that, with probability 1, within h improvement steps the algorithm either terminates or reaches a new linearization Lt+h with A(Lt+h ) > A(Lt ). Let F (Lt ) denote the (finite) set of active forests whose active trees correspond to the chunks of Lt (Definition 14). While the algorithm performs only blocked splits (selfmerges), it transitions between states within F (Lt ) without changing Lt . An unblocked split causes a transition to a new linearization Lt+h ̸= Lt with A(Lt+h ) > A(Lt ) by Theorem 4. Consider any state A ∈ F(Lt ). The deterministic variant of SFL (Algorithm 4), which uses Bland’s rule for all edge selections, terminates in a finite number of steps from any initial valid linearization by Theorem 5. In particular, starting from A, the deterministic algorithm produces a finite sequence of improvement steps (each comprising a split selection and, for a blocked split, the subsequent remerge selection) that leads to either an unblocked split or termination (when no valid split candidates remain). Let N (A) denotes the number of steps the deterministic algorithm takes from A to reach this outcome. Since F (Lt ) is finite, the quantity N ∗ = maxA∈F (Lt ) N (A) is also finite. The randomized algorithm draws its split from the first candidate-bearing tree in Q, whereas the deterministic algorithm selects the globally minimum-index candidate, possibly in a different tree. Since Q is a uniformly random permutation of the active trees after every I MPROVE (line 21), the deterministic candidate’s tree precedes all other candidate-bearing trees with probability at least 1/|V |; this also holds midscan, as conditioned on the popped prefix (which contains no split candidates), the remainder of Q is a uniformly random permutation of the remaining trees. Given the correct tree, the uniform draws from Esplit (line 17) and Eremerge (line 5) each match the deterministic choice with probability at least 1/|E|. Hence, each step reproduces the deterministic step with probability at least (|V | · |E|2 )−1 , and from any A ∈ F(Lt ), the randomized algorithm follows the full deterministic path with probability at least
−N ∗ δ = |V | · |E|2 > 0. (70) If the randomized algorithm deviates from this path at any step, it either performs an unblocked split (reaching a strictly better linearization, which is an even more favorable outcome) or arrives at a different state A′ ∈ F(Lt ), from which the same argument applies: the deterministic algorithm provides a path of length at most N ∗ to either an unblocked split or termination, and the randomized algorithm follows it with probability at least δ. Here “termination” of the deterministic variant means it reaches a state with Esplit = ∅, i.e., no active tree admits an improving split. Suppose this coincides with the randomized algorithm’s halting condition of an empty queue Q (we shall verify this shortly). In every consecutive window of N ∗ steps spent on the plateau F(Lt ), the probability of either escaping the plateau or terminating is at least δ > 0. The

probability of remaining on the plateau without terminating for k such windows is at most (1 − δ)k → 0 as k → ∞. Therefore, with probability 1, within finitely many steps, h, the algorithm either terminates or reaches a new linearization Lt+h with A(Lt+h ) > A(Lt ). It remains to confirm that the randomized algorithm’s queue Q eventually empties. After every successful I MPROVE, Q is reset to all active trees (line 21), and a tree is popped without re-enqueueing (line 15) exactly when it has Esplit = ∅. Thus Q becomes empty precisely when every active tree has no split candidate, which is the deterministic termination condition. As shown above, the algorithm almost surely reaches such a state in finitely many steps; there, every remaining tree is popped without re-enqueueing and Q empties. Hence the randomized algorithm terminates with probability 1. Since the total number of distinct linearizations is finite and the AUC strictly increases with each plateau escape, the algorithm must terminate with probability 1. F. Granularity via Perturbation As outlined in Sec. III-B, a robust linearization algorithm should provide granularity: when multiple closures achieve the same maximum fee rate, the algorithm should systematically prefer the smallest among them. To enforce this property, we employ perturbation. By adding an infinitesimal, transactionspecific offset to each fee, ordered lexicographically, we ensure that no two distinct subsets of transactions possess the exact same effective fee rate. This approach is inspired by Charnes’ lexicographic perturbation method for resolving degeneracy in the simplex algorithm, where infinitesimal objective perturbations are used to impose a strict ordering among otherwise equivalent optima [25]. As a result, the selection of the “best” closure becomes unique and well defined. Granularity is achieved in a separate minimization phase that runs after SFL. We assign a unique, fixed integer index ι(i) ∈ {1, . . . , n} to every transaction i ∈ V . To promote fairness and robustness, these indices are assigned uniformly at random, so that in case of early termination during the minimization phase, all chunks receive equal effort. We conceptually replace the scalar fee fi with a polynomial in a symbolic variable ϵ, where ϵ is strictly positive but infinitesimally small. We define two perturbed fee functions: fi+ (ϵ) = fi + ϵι(i) ,

(71)

fi− (ϵ) = fi − ϵι(i) .

(72)

The size si remains unchanged. The perturbed fee rates of a subset U for the positive and negative cases are given by: P (fi ± ϵι(i) ) 1 X ι(i) P rϵ± (U ) = i∈U = r(U ) ± ϵ . (73) s(U ) i∈U si i∈U

Comparing two perturbed fee rates is equivalent to a lexicographical comparison. We define the strict positive ordering − A >+ lex B and the strict negative ordering A >lex B as follows: 1) If the scalar fee rates differ (r(A) ̸= r(B)), then both − A >+ lex B and A >lex B hold if and only if A ≻ B.

17

2) If r(A) = r(B), we compare the coefficients of the 1 } polynomials in ϵ. Let ck (U ) = {k∈U be the absolute s(U ) k coefficient of the ϵ term for a subset U . We identify the smallest transaction index k such that ck (A) ̸= ck (B). + • A >lex B if and only if ck (A) > ck (B). − • A >lex B if and only if ck (A) < ck (B). When comparing disjoint sets A and B, this rule simplifies to identifying the transaction k ∗ = min{i | i ∈ A ∪ B}. For the positive (resp. negative) perturbation, the set containing k ∗ is strictly greater (resp. smaller). Lemma 13 (Uniqueness). For any two distinct subsets A, B ⊆ V , it holds that rϵ+ (A) ̸= rϵ+ (B) and rϵ− (A) ̸= rϵ− (B). Proof. Suppose rϵ+ (A) = rϵ+ (B) or rϵ− (A) = rϵ− (B). In either case, this implies that for every power of ϵ (i.e., for every transaction index k ∈ {1, . . . , n}), the absolute coefficients must be identical: 1{k∈B} 1{k∈A} = . (74) s(A) s(B) |A| s(A)

|B| s(B) . More

Summing these terms over all k yields = importantly, since the denominators are constants, the indicator 1{k∈A} can only equal 1{k∈B} for all k if the sets of indices are identical. Thus, A and B must be the same set. Since no two distinct subsets share the same perturbed fee rate (Lemma 13), we may assume strict inequality in all perturbed fee rate comparisons between distinct subsets. Algorithm 6 Minimization 1: Procedure: M INIMIZE(A, (V, E, f, s)): 2: Q ← active trees of (V, A) 3: while Q ̸= ∅ do 4: T ← Q.pop() 5: U ← vertex set of T

EU ← {(u, v) ∈ E | u, v ∈ U } sU ← (si )i∈U Assign unique indices ι(i) ∈ {1, . . . , |U |} for ∀i ∈ U for δ ∈ {+, −} do fUδ ← (fiδ (ϵ))i∈U 11: (·, ·, AU ) ← R ANDOMIZED SFL((U, EU , fUδ , sU )) 12: if (U, AU ) has more than one active tree then 13: A ← (A \ EU ) ∪ AU 14: Push active trees of (U, AU ) onto Q; break 15: end if 16: end for 17: end while 18: (T1 , . . . , Tm ) ← active trees of (V, A), sorted by descending fee rate, ties broken by ascending size s(·), subject to parent trees preceding their child trees 19: σout ← a valid ordering induced by (T1 , . . . , Tm ) 20: Return: (T1 , . . . , Tm ), σout , A 6: 7: 8: 9: 10:

To enforce granularity, we introduce a minimization phase (Algorithm 6) following the execution of the randomized SFL algorithm (with unperturbed fees). When evaluating a candidate split that partitions a chunk into a parent chunk and a child

chunk, the transaction possessing the absolute lowest index, which exerts the strictly dominant lexicographical influence, must reside in exactly one of these two disjoint sets. It cannot be known a priori whether this dominating transaction falls into the parent or the child side of the boundary. Therefore, we independently evaluate the graph under both a positive perturbation, which successfully exposes the split if the lowest index is in the parent side, and a negative perturbation, which exposes the split if the lowest index is in the child side. By alternating these two perturbation passes, we guarantee that any valid equal-fee-rate boundary will be exposed. Theorem 7 (minimality of linearization). Given (V, A) corresponding to an optimal linearization, Algorithm 6 produces an updated (V, A) whose active trees form a minimal optimal linearization. That is, for any active tree T of the output (V, A), there exists no valid split candidate (p, c) that partitions T into Hp and Hc without triggering a self-merge such that r(Hp ) = r(Hc ) = r(T ). Proof. Suppose, for contradiction, that an active tree T of the output (V, A) is not minimal. Thus, there exists a valid split candidate (p, c) that partitions T into Hp and Hc such that r(Hp ) = r(Hc ) = r(T ). Because T remains an active tree in the output (V, A), it must have survived both perturbation passes intact. Let i∗ = arg mini∈T ι(i) be the transaction with the lowest index in T . It must reside in exactly one of Hp or Hc . Case 1 (i∗ ∈ Hp ): Under the positive perturbation f + (ϵ), Hp receives the strictly dominant positive coefficient. Thus, rϵ+ (Hp ) > rϵ+ (Hc ). SFL must split T during the δ = + pass, yielding a contradiction. Case 2 (i∗ ∈ Hc ): Under the negative perturbation f − (ϵ), Hc receives the strictly dominant negative index. Thus, rϵ− (Hp ) > rϵ− (Hc ). SFL must split T during the δ = − pass, yielding a contradiction. Hence, T is guaranteed to split in at least one pass. Therefore, no non-minimal active tree can remain in the output of the algorithm. Since the original randomized SFL algorithm terminates with probability 1, and each successful split in Algorithm 6 strictly decreases the finite size of the evaluated chunks, this minimization process is also guaranteed to terminate with probability 1. VI. C OMPARING THE A PPROACHES To evaluate the performance of different linearization algorithms, we conducted a series of benchmarks across diverse datasets. Each dataset was evaluated under four distinct linearization settings.3 We compared the randomized SFL algorithm4 when run from scratch and when initialized with an optimal linearization (whose optimality is unknown to 3 See https://github.com/sipa/bitcoin mempool linearization artefacts/ for the algorithm implementations, benchmark code, datasets, and results. 4 The SFL implementation used in our experiments is very close to the production code deployed in Bitcoin Core 31.0. It is limited to 64 transactions, and exploits the ability to represent subsets of such clusters in a single machine integer.

18

SFL) against the GGT approach5 in both its full bidirectional form and a variant that processes each maximum-ratio closure subproblem in a uniformly random direction (forward or backward). The benchmarking methodology was as follows: For a list of N clusters within a dataset, each cluster underwent the following process 1024 times: 100 random number generator seeds were generated for the linearization algorithm. For each seed, the optimal linearization was benchmarked 7 times, and the median of these 7 runs was recorded to mitigate variance from system-level task swapping. The average of these 100 medians was then calculated, aiming to represent the typical duration for linearizing many clusters. Finally, for each cluster size, three statistics were reported over all clusters of that size and all 1024 repetitions, with all times converted to microseconds (µs): the average of the averageof-medians (“avg”), representing typical performance; their maximum (“max-of-avg”), representing aggregate worst-case behavior over many clusters, which is the most relevant measure in practice; and the maximum over all individual medians (“max”), representing the worst-case behavior of a single instance. All benchmarks were written in C++20, compiled with GCC 15.2, and executed on a 64-core AMD Ryzen Threadripper 9980X system running Ubuntu 26.04, 62way parallel; each core processed a random subset of the cases in random order, so that cross-core interference largely cancels out in the reported medians. The benchmarks were performed on several types of cluster data: •

Simulated 2023 Mempools: These clusters were generated by replaying a Bitcoin’s 2023 P2P network activity dump into a cluster-mempool-patched version of Bitcoin Core.6 This dataset included 199,076 clusters with sizes ranging from 26 to 64 transactions.7 Fig. 2 presents the results for this dataset. SFL from scratch is roughly two times faster than both GGT variants in both average and seed-averaged worst-case runtime, and starting from an optimal linearization roughly halves its runtime again. On the worst individual instances (Fig. 2 (bottom)), the from-

5 The specific algorithm is the paragraph 3.3 “Finding all breakpoints of κ(λ)” algorithm from the Gallo, Grigoriadis, and Tarjan paper [2], applied to the flow network defined in the same paper in paragraph 4.2 “Fractional programming applications”, under “Maximum-ratio closure problem”. See Appendix E for more P information. Flows are represented as integers after multiplying with 2( si )2 , which is sufficient to guarantee distinct flows are distinct. The minimal optimal chunks can be found as the strongly-connected components of the residual flow graph within each found chunk, after running the push-relabel algorithm in them to completion, to find maximal flows rather than just pre-flows. Like the SFL implementation, several optimizations exploit the fact that transaction sets in clusters up to 64 transactions can be represented by a single machine integer. 6 This is a replay using a modern version of the codebase with cluster-based limits (up to 64 transactions), while the data being replayed is from a time when no cluster limits were enforced on the network (instead there was a limit of 24 ancestors and 24 descendants per transaction). This means that this replay is not necessarily representative of what transaction traffic would have looked like if cluster limits had been in place at the time. 7 Bitcoin’s previous policy (of max 24 ancestors/descendants per transaction) was introduced in September 2015 (https://github.com/bitcoin/bitcoin/ pull/6654). The mempool cluster size limit is likely to remain within 64 in the foreseeable future.

scratch algorithms are largely comparable, while SFL with an optimal input retains a clear advantage. 8 • Randomly-Generated Tree-Shaped Clusters: For each cluster size n from 26 to 64 transactions, we generated 100 random tree-shaped clusters. These clusters represent connected graphs with exactly n − 1 dependencies. Fig. 3 presents the results for this dataset. SFL is the clear winner across all three metrics by a factor of roughly 2–3 times over both GGT variants. • Randomly-Generated Medium-Density Clusters: For each cluster size n between 26 and 64 transactions, 100 random clusters with approximately 3 dependencies per transaction were generated. Fig. 4 presents the results for this dataset. Here, SFL’s runtime inherently scales with the number of dependencies: while SFL from scratch remains fastest on average for smaller clusters, it is overtaken by both GGT variants as the cluster size approaches 64, and its individual worst case (Fig. 4 (bottom)) is several times higher than GGT’s. Starting SFL from an optimal linearization, however, keeps its average runtime well below all alternatives. Note also that randomizing GGT’s direction visibly improves its performance across all metrics. • Randomly-Generated Complete Bipartite Clusters: For each cluster size n from 26 to 64 transactions, 100 random complete-connected bipartite clusters were generated, featuring approximately n/4 dependencies per transaction. These clusters are notable for their high number of dependencies. For instance, a 64-transaction cluster where all inputs and outputs are key-path Pay-toTaproot (P2TR) would require approximately 103 kvB in transaction input and output data. Fig. 5 presents the results for this dataset. With even more dependencies per transaction, SFL’s dependency-driven scaling is most visible: average runtimes of all algorithms remain within a narrow band, but in both worst-case metrics, GGT clearly outperforms SFL, whose two variants become nearly indistinguishable, as an optimal starting linearization no longer offsets the per-dependency cost. These results demonstrate that the SFL algorithm is highly efficient in practice. On realistic mempool data and sparse synthetic clusters, it consistently outperforms the GGT-based approaches in average runtime, aggregate worst-case runtime, and frequently on individual worst-case instances. While GGT exhibits superior worst-case performance on dense synthetic clusters, pure worst-case performance is not the deciding criterion for deployment. SFL’s ability to leverage an existing linearization—which the benchmarks show to be visibly beneficial—alongside its fairness and anytime properties discussed in Sec. III-B, are more relevant in a practical setting. In such environments, per-cluster computation must be bounded, and no participant’s transactions should be starved. Moreover, as the algorithm’s internal randomness is insulated from 8 Due to the ancestors and descendants limit of 24 transactions at the time this data was captured, clusters of up to 49 likely consists primarily of two largely independent groups of up to 25 transactions, with a shared transaction connecting them. This may explain the sudden decline at size 49, where the captured clusters transition to three independent transaction groups.

19

SFL from scratch SFL with optimal input 50

GGT (bidirectional) GGT (random direction)

SFL from scratch SFL with optimal input

Average

50

20

GGT (bidirectional) GGT (random direction)

Average

20

10

10

5 5 2

50

Maximum over averaged randomness

50

Time (μs)

Time (μs)

20

10

Maximum over averaged randomness

20

10

5 5 2

50

Maximum

50

20

Maximum

20

10

10

5 5 2 28

32

36

40

44

48

52

Cluster size (transactions)

56

60

64

Fig. 2: Runtime of SFL and GGT on the replayed 2023 mempool dataset.

28

32

36

40

44

48

52

Cluster size (transactions)

56

60

64

Fig. 3: Runtime of SFL and GGT on a dataset of randomly generated tree-shaped clusters.

20

SFL from scratch SFL with optimal input 500

GGT (bidirectional) GGT (random direction)

SFL from scratch SFL with optimal input 200

Average

200

GGT (bidirectional) GGT (random direction)

Average

100

100

50

50 20

20 10

500

10

200

Maximum over averaged randomness

200

100

Time (μs)

Time (μs)

100 50

50

20

20 10

500

Maximum over averaged randomness

10

200

Maximum

200

Maximum

100

100

50

50 20

20 10

10 28

32

36

40

44

48

52

Cluster size (transactions)

56

60

64

Fig. 4: Runtime of SFL and GGT on a dataset of randomly-generated medium-density clusters.

28

32

36

40

44

48

52

Cluster size (transactions)

56

60

64

Fig. 5: Runtime of SFL and GGT on a dataset of randomly-generated complete bipartite clusters.

21

external exploitation, the seed-averaged worst case (middle plots in Figs. 2–5) serves as the practically relevant measure. Under this metric, SFL remains competitive with GGT even on the densest clusters while being on average often faster. Combined, these properties make SFL well-suited for realworld deployment. Note however that none of the benchmarked datasets are actual worst cases for any of the tested algorithms, as we do not know what they are. In the case of GGT we can however extrapolate from the benchmarked time per iteration to the known upper bound on iteration count. This predicts a time up to 10 ms for 64-transaction clusters, far too slow for our application. If this bound were tight, it would be a further justification for relying on randomized and fairness, rather than aiming to always achieve optimality. VII. C ONCLUSION This paper has introduced the mempool linearization problem: determining an optimal partition of the set of transactions and their ordering that maximizes fee efficiency while respecting parent-child dependencies. We have established several theoretical characterizations of the problem. In particular, we showed that mempool linearization admits an LP formulation from which an exact optimal solution can be recovered, and that it is equivalent to a sequence of maximum-ratio closure problems solvable via the classical GGT parametric preflow algorithm. Our main algorithmic contribution is the SFL algorithm, a method that iteratively refines a partition of transactions through merge and split operations guided by fee-rate comparisons. Extensive evaluation on both synthetic and real Bitcoin mempool data demonstrates that SFL consistently produces optimal linearizations while remaining competitive with the GGT-based approach in runtime. Moreover, SFL naturally supports randomized execution, allowing computational effort to be distributed across the transaction graph and providing robustness under time constraints or early termination. Beyond its algorithmic value, efficient mempool linearization has broader implications for blockchain decentralization. By enabling all participants to compute high-quality transaction orderings with modest computational resources, it reduces the advantage of proprietary infrastructure and private relay networks, thereby supporting a more open and censorshipresistant mining ecosystem. Several directions remain for future work. On the theoretical side, it would be valuable to further analyze the complexity of SFL and develop stronger performance guarantees for its randomized variants. On the practical side, extending the framework to handle adversarially constructed transaction graphs and conflicting transactions would provide a more realistic model of mempool dynamics. More broadly, our results suggest that mempool linearization is not merely an implementation detail, but a core optimization problem at the intersection of economics, networking, and consensus. Developing efficient and robust algorithms for this problem will remain important for the continued scalability and decentralization of blockchain systems.

ACKNOWLEDGEMENT The authors would like to thank Suhas Daftuar, Ittay Eyal, Gregory Maxwell, Clara Shikhelman, Anthony Towns, Aviv Yaish, and Aviv Zohar for stimulating discussions, technical suggestions, and feedback. This work was supported in part by the National Science Foundation under Grant Nos. 2132700, 2216970, and 2434044. R EFERENCES [1] V. Pahari and A. Canidio, “How exclusive are ethereum transactions? evidence from non-winning blocks,” arXiv preprint arXiv:2509.16052, 2025. [2] G. Gallo, M. D. Grigoriadis, and R. E. Tarjan, “A fast parametric maximum flow algorithm and applications,” SIAM Journal on Computing, vol. 18, no. 1, pp. 30–55, 1989. [3] W. E. Smith, “Various optimizers for single-stage production,” Naval Research Logistics Quarterly, vol. 3, pp. 59–66, 1956. [Online]. Available: https://api.semanticscholar.org/CorpusID:120614124 [4] E. L. Lawler, “Sequencing jobs to minimize total weighted completion time subject to precedence constraints,” in Annals of discrete mathematics. Elsevier, 1978, vol. 2, pp. 75–90. [5] J. B. Sidney, “Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs,” Operations Research, vol. 23, no. 2, pp. 283–298, 1975. [6] C. N. Potts, “An algorithm for the single machine sequencing problem with precedence constraints,” in Combinatorial optimization ii. Springer, 2009, pp. 78–87. [7] F. A. Chudak and D. S. Hochbaum, “A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine,” Operations Research Letters, vol. 25, no. 5, pp. 199–204, 1999. [8] L. R. Ford and D. R. Fulkerson, Flows in networks. Princeton University Press, 1962. [Online]. Available: https://api.semanticscholar. org/CorpusID:260503522 [9] A. V. Goldberg and R. E. Tarjan, “A new approach to the maximumflow problem,” J. ACM, vol. 35, no. 4, p. 921–940, Oct. 1988. [Online]. Available: https://doi.org/10.1145/48014.61051 [10] J. Cheriyan and S. N. Maheshwari, “Analysis of preflow push algorithms for maximum network flow,” in Proceedings of the Eighth Conference on Foundations of Software Technology and Theoretical Computer Science. Berlin, Heidelberg: Springer-Verlag, 1988, p. 30–48. [11] J.-C. Picard and M. Queyranne, “Selected applications of minimum cuts in networks,” INFOR: Information Systems and Operational Research, vol. 20, no. 4, pp. 394–422, 1982. [Online]. Available: https://doi.org/10.1080/03155986.1982.11731876 [12] A. Beines, M. Kaibel, P. Mayer, P. Mutzel, and J. Sauer, “A simpler approach for monotone parametric minimum cut: Finding the breakpoints in order,” in 2025 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), 2025, pp. 29–41. [Online]. Available: https://epubs.siam.org/doi/abs/10.1137/1. 9781611978339.3 [13] J. R. Isbell and W. H. Marlow, “Attrition games,” Naval Research Logistics Quarterly, vol. 3, no. 1-2, pp. 71–94, 1956. [Online]. Available: https://onlinelibrary.wiley.com/doi/abs/10.1002/nav.3800030108 [14] P. M. Pardalos and A. T. Phillips, “Global optimization of fractional programs,” Journal of Global Optimization, vol. 1, no. 2, pp. 173–182, 1991. [Online]. Available: https://doi.org/10.1007/BF00119990 [15] D. S. Hochbaum, “A new—old algorithm for minimum-cut and maximum-flow in closure graphs,” Networks: An International Journal, vol. 37, no. 4, pp. 171–193, 2001. [16] H. Lerchs and I. F. Grossmann, “Optimum design of open-pit mines,” Transactions of the Canadian Institute of Mining and Metallurgy, vol. 68, pp. 17–24, 1965. [17] J. Nocedal and S. J. Wright, Numerical optimization. Springer, 2006. [18] V. Klee and G. J. Minty, “How good is the simplex algorithm?” in Inequalities, O. Shisha, Ed. New York: Academic Press, 1972, pp. 159–175. [19] D. A. Spielman and S.-H. Teng, “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time,” Journal of the ACM (JACM), vol. 51, no. 3, pp. 385–463, 2004. [20] G. Kalai, “A subexponential randomized simplex algorithm,” in Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, 1992, pp. 475–482.

22

[21] J. Matoušek, M. Sharir, and E. Welzl, “A subexponential bound for linear programming,” in Proceedings of the eighth annual symposium on Computational geometry, 1992, pp. 1–8. [22] D. Bertsimas and J. N. Tsitsiklis, Introduction to linear optimization. Athena scientific Belmont, MA, 1997, vol. 6. [23] R. Diestel, Graph Theory, 5th ed., ser. Graduate Texts in Mathematics. Springer, 2017, vol. 173. [24] R. G. Bland, “New finite pivoting rules for the simplex method,” Mathematics of Operations Research, vol. 2, no. 2, pp. 103–107, 1977. [25] A. Charnes, “Optimality and degeneracy in linear programming,” Econometrica, vol. 20, no. 2, pp. 160–170, 1952. [26] A. Charnes and W. W. Cooper, “Programming with linear fractional functionals,” Naval Research logistics quarterly, vol. 9, no. 3-4, pp. 181–186, 1962.

Since Wj ⊆ Uj∗ implies s(Wj ) ≤ s(Uj∗ ), letting xj = s(Wj ) for j = 1, . . . , p is a feasible solution. Therefore, p X

s(Wj )r(Uj∗ ) ≤ CL∗ (s(W )).

By (77) and (79), we obtain f (W ) ≤ CL∗ (s(W )) for every k = 1, . . . , q. Finally, since every breakpoint of CL is dominated by CL∗ , which is a piece-wise linear concave function, the entire function CL is dominated by CL∗ . Therefore, the AUC of L∗ also dominates the AUC of L.

A PPENDIX A P ROOF T HEOREM 1

A PPENDIX B P ROOF T HEOREM 2

Given any closure W in G = (V, E), we let Wj = W ∩ Uj∗ for j = 1, . . . , p. We claim f (Wj ) ≤ s(Wj )r(Uj∗ )

(75)

holds for all j = 1, . . . , p. We prove (75) by induction. We begin with j = 1. If W1 = ∅, (75) holds trivially for j = 1. As W and U1∗ are closures in G, their intersection W1 , if non-empty, is a closure in G by Lemma 1. Because U1∗ is a highest-fee-rate closure, r(W1 ) ≤ r(U1∗ ), which implies (75) for j = 1. Next, assume that for some m ∈ {1, . . . , p}, Smr(Wj ) ≤ ∗ ′ = W \ r(UjS ) for all j = 1, . . . , m. Let W m j=1 Wj = Sm m W \ j=1 Uj∗ . By Lemma 2, j=1 Uj∗ is a closure in G. Hence, ′ by Lemma 3, Wm is a closure in the subgraph S,mif non-empty, ∗ induced by V \ j=1 Uj∗ . We have Wm+1 = W ∩ Um+1 = ∗ ∗ ′ . Since U is a closure in the subgraph induced Wm ∩US m+1 m+1 m by V \ j=1 Uj∗ , the intersection Wm+1 , if non-empty, is also ∗ a closure in that same subgraph (Lemma 1). Since Um+1 is the optimal closure in that subgraph, it must hold that ∗ r(Wm+1 ) ≤ r(Um+1 ), i.e., (75) holds for j = m + 1. By induction, (75) holds for all j = 1, . . . , p. Summing (75) over j = 1, . . . , p yields f (W ) = ≤

p X j=1 p X

f (Wj )

(76)

s(Wj )r(Uj∗ ).

(77)

j=1

We next show that every breakpoint of CL lies on or below CL∗ . The k-th breakpoint of CL takes the form of Sk (s(W ), f (W )) with W = i=1 Ui . By Lemma 2, W is a closure in G. It suffices to show f (W ) ≤ CL∗ (s(W )). The value CL∗ (s(W )) is the cumulative fee of the first s(W ) size units of L∗ . Since r(U1∗ ) ≥ r(U2∗ ) ≥ . . . by Definition 5, CL∗ (s(W )) is the result of the following maximization: p X maximize xj r(Uj∗ ) (78a) x1 ,...,xp

subject to

j=1 p X

xj = s(W ),

(78b)

j=1

0 ≤ xj ≤ s(Uj∗ ),

j = 1, . . . , p.

(78c)

(79)

j=1

Let x1 , ..., xn be a solution to LP 14. For convenience, let A consist of indices of the x-variables that are positive, i.e., A = {i ∈ V : xi > 0}. Let u = max{xj | j ∈ V }

(80)

denote the maximum value of the x-variables. Let B = {i ∈ V | xi = u}, i.e., the set of indices for which the x-variable attains the maximum. Evidently, zi = 1{i∈B} . We first show that x′1 , ..., x′n defined as x′i = P

1

i∈B si

· 1{i∈B} ,

i = 1, ..., n

(81)

also solves the LP in two separate Pcases: i) A = B and ii) A ̸= B. One can readily verify that i∈V si x′i = 1 and that x′i ≥ x′j for all (i, j) ∈ E. Thus, x′1 , . . . , x′n satisfies all constraints of the LP. The claim that x′1 , . . . , x′n solves the LP is trivial in case (i), when all strictly positive entries in x1 , . . . , xn are identical. In case (ii), A ̸= B, we let w = max{xj | j ∈ A\B}, which denotes the second highest value the x-variables attain, which must satisfy w > 0. Consider x′′1 , ..., x′′n defined by ( w/q, if i ∈ B, ′′ xi = (82) xi /q, otherwise, P P where si xi . It is easy to verify Pq = ( ′′i∈B si )w + ′′ i∈V \B that i∈V si xi = 1 and xi ≥ x′′j for all (i, j) ∈ E. Hence x′′1 , ..., x′′n satisfies all the constraints of the LP. The result of the LP can be expressed as X ∗ rLP = fi xi (83) i∈V

P fi xi = Pi∈V i∈V si xi P P (u − w)( i∈B fi ) + q i∈V fi x′′i P P = . (u − w)( i∈B si ) + q i∈V si x′′i

(84) (85)

We show that P P ′′ fi i∈V fi xi P Pi∈B ′′ = s x i∈V i i i∈B si

(86)

by contradiction: If either side of (86) is strictly greater than ∗ the other side, then (85) implies that rLP is strictly in between

23

those two sides. Since the right hand side of (86) is the fee rate achieved by x′i defined by (81) due to P P fi fi x′i Pi∈B = Pi∈V (87) ′, i∈B si i∈V si xi and the left-hand side is the fee rate achieved by x′′i defined ∗ by (82), rLP cannot be the maximum fee rate, contradicting its definition. With (86) established, it is straightforward to see ∗ that x′i achieves the highest fee rate rLP , i.e., it also solves the same LP. By (15) and (81), we have zi = 1{x′i >0} for all i ∈ V . To establish the theorem, it suffices to show that z1 , ..., zn thus defined solves the BP in (12). Since FP (13) can be viewed as the BP in (12) with the binary constraints relaxed, we have ∗ ∗ rFP ≥ rBP .

(88)

Meanwhile, the FP is equivalent to the LP in (14) via the Charnes-Cooper transformation [26], in the sense that there is a one-to-one correspondence between their solutions in the form of .X xi = yi sk yk , ∀i ∈ V (89) k∈V

which implies that they achieve the same maximum: P X fi yi . fi xi = Pi∈V i∈V si yi

(90)

i∈V

This, together with (88), leads to ∗ ∗ ∗ rLP = rFP ≥ rBP .

(91)

Note that if y1 , ..., yn solves the FP, scaling all yi ’s by the same positive constant still solves the FP. Since x′1 , ..., x′n solves the LP, z1 , ..., zn which are defined by (15), must solve the FP to achieve rF∗ P . Evidently, z1 , ..., zn also satisfies all the ∗ ≥ rF∗ P . constraints of the BP in (12), which implies that rBP ∗ ∗ ∗ This, together with (91) implies that rBP = rFP = rLP . Therefore, the same z1 , ..., zn must also solve the BP. A PPENDIX C P ROOF OF (32) The left hand side of (32) is equal to X X fi sj − fi sj i,j∈V

i,j∈V :σ(j)≤σ(i)

X

=

i,j∈V :i̸=j

=

1 2

X i,j∈V :i̸=j

fi sj

(92)

i,j∈V :σ(j)<σ(i)

1 X 1 fi sj + 2 2 i,j∈V i̸=j

=

X

fi sj −

X

fi sj −

i,j∈V σ(j)>σ(i)

fi sj +

1 2

1 2

X

X

fi sj

(93)

(fi sj − fj si )

(94)

i,j∈V σ(j)<σ(i)

i,j∈V :σ(j)>σ(i)

which is equal to the right hand side of (32).

A PPENDIX D R EFINED SFL WITH M AXIMUM -q H EURISTIC This appendix describes the maximum-q heuristic for split selection in the refined SFL algorithm, referenced in Sec. V-B. This deterministic rule selects, at each improvement step, the active dependency that maximizes the q-function value among all valid split candidates. Algorithm 7 Refined SFL with Maximum-q Heuristic 1: Procedure: I MPROVE ((p, c), A): 2: Eremerge ← {(u, v) ∈ E \ A | u ∈ Hc , v ∈ Hp } 3: A ← A \ {(p, c)} 4: if Eremerge ̸= ∅ then 5: Pick arbitrary e′ ∈ Eremerge ; A ← A ∪ {e′ } 6: else 7: A ← M ERGE U PWARDS(p, A) 8: A ← M ERGE D OWNWARDS(c, A) 9: end if 10: return A

M AX QSFL(Mempool (V, E, f, s), optional valid ordering σ): 12: (·, ·, A) ← L INEARIZE((V, E, f, s), σ) 13: while true do 14: Esplit ← {(p, c) ∈ A | Hp ≻ Hc } 15: if Esplit = ∅ then 16: break 17: end if 18: e∗ ← arg maxe=(p,c)∈Esplit q(Hp , Hc ), with ties broken arbitrarily 19: A ← I MPROVE(e∗ , A) 20: end while 21: (T1 , . . . , Tm ) ← active trees of (V, A), sorted by descending fee rate, ties broken arbitrarily 22: σout ← a valid ordering induced by (T1 , . . . , Tm ) 23: Return: (T1 , . . . , Tm ), σout , A 11: Procedure:

Returning to the LP interpretation, a split corresponds to making a slack variable basic. The simplex method only permits such a pivot if the derivative of the objective with respect to the slack variable is positive, which, in our case, translates to requiring the parent-side chunk A to have a higher fee rate than the child-side chunk B. A natural strategy is to select the split with the largest such derivative. This corresponds to maximizing q(A, B). The complete algorithm using this rule is presented in Algorithm 7.9 The refined SFL algorithm with the maximum-q heuristic may revisit the same active forest state and therefore does not guarantee termination. Fig. 6 shows a cluster with 15 transactions and 30 dependencies that permits a cycle of 24 split-and-merge operations that ultimately returns to the original state. The black edges form the initial active tree: T1→T0, T6→T0, T12→T0, T2→T1, T3→T1, T7→T4, T7→T5, T12→T5, T14→T5, T10→T7, T2→T8, T2→T9, T13→T11, and T2→T13. 9 Although preliminary tests suggested the maximum-q heuristic performs well in practice, it was not adopted as the split-selection rule in the Bitcoin Core implementation.

24

T4: -1935/514

T1: 686/736

T13: -277/177

T2: 1760/1019

T8: 1405/436

T3: 1073/456

T0: -1962/877

T9: 672/595

T7: -55/449

T5: -1952/962

T14: -1085/693

T11: -1278/1003

T6: 1682/503

T12: -1066/402

T10: 1808/532

Fig. 6: An example of a transaction DAG that can repeat the same sequence of split and merge steps when following a specific trajectory. A transaction with fee f and size s is denoted as f /s.

From this configuration, a sequence of 24 steps can be performed that results in a return to the same state. Each step deactivates one edge (dependency) and activates another, sometimes a grey edge from the original graph. The steps are: -T12→T0 +T13→T4, -T7→T4 +T13→T5, -T2→T1 +T3→T8, -T2→T8 +T3→T9, -T2→T9 +T6→T5, -T6→T0 +T3→T7, -T13→T5 +T14→T11, -T14→T5 +T12→T11, -T12→T5 +T1→T4, -T13→T4 +T3→T13, -T3→T7 +T10→T8, -T3→T8 +T10→T9, -T3→T9 +T6→T11, -T6→T5 +T7→T11, -T3→T13 +T14→T0, -T14→T11 +T12→T0, -T12→T11 +T7→T4, -T1→T4 +T7→T0, -T7→T11 +T2→T9, -T10→T9 +T2→T8, -T10→T8 +T6→T0, -T6→T11 +T2→T1, -T7→T0 +T14→T5, -T14→T0 +T12→T5. This demonstrates that Algorithm 7, without additional safeguards, does not guarantee termination. While such cyclic states appear rare in practice, their existence motivates modifying the algorithm to guarantee termination. A PPENDIX E L INEARIZATION VIA M INIMUM C UTS In 1982, Picard and Queyranne [11] introduced an algorithm for finding a maximum-ratio closure in a graph. In our terminology, it consists of starting with an initial solution consisting of all transactions, and then repeatedly improving it by removing transactions from it, in such a way that the solution remains a closure, and the fee rate increases. With n transactions, this will find the maximum fee rate closure in at most n − 1 steps. We can use this approach to compute a complete optimal linearization, by finding all consecutive maximum-ratio closures, of which there may be n. Together, this approach can find an optimal linearization using O(n2 ) improvement steps. Each improvement step in the paper’s algorithm takes an existing closure as input, and tries to find in it a subset with higher fee rate that is also a closure. Specifically, if λ is the fee rate of the existing closure, it defines ci = fi − λsi for every transaction i in it, i.e. its fee above the closure’s average fee P rate. It then finds the closure S which maximizes i∈S ci . If

a subset closure exists with higher fee rate than λ, the solution will be one of them. If not, the solution will be the empty set or the entire input closure. To achieve this, improvement steps work by finding a minimum cut of a flow network with n + 2 vertices: one for each transaction, plus two special vertices s (the source) and t (the sink). The network is given the following edges: For every dependency between two transactions, an edge with infinite capacity from the child to the parent. • For every transaction i, an edge with capacity ci from the source to the transaction if ci > 0, or an edge with capacity −ci from the transaction to the sink if ci < 0. •

The minimum cut of this network will be a partition of the nodes into a source side U (containing s) and a sink side V (containing t), for which the sum of capacities of edges from U to V is minimal. The transaction nodes on the source side are our maximum fee rate closure. It must clearly be a closure, because if it is not, P the cut value would be infinite. It must further maximize i∈U ci , because if a subset of transactions with positive total ci could be moved to U , or a subset with negative total ci could be moved to the V , while leaving U a closure, it would decrease the cut value by that amount. Many algorithms exist for solving this minimum-cut problem, and any of them can be used here. A very practical choice is the push-relabel algorithm [9] with√maximum-label heuristic [10], which has complexity O(V 2 E), for V vertices and E edges. √ Instantiated for our problem this gives complexity O(n4 m), for n transactions and m dependencies, to find the optimal linearization. In 1989, Gallo, Grigordiadis, and Tarjan [2] introduced algorithms for finding minimum cuts in parametrized flow networks, allowing the computation of multiple minimum cuts with the same complexity as a single one, as long as all networks are the same, except some subgraphs may be contracted into the source and/or sink, and the capacities may vary monotonically in a single parameter. This is exactly the case in our setting, where earlier chunks are contracted into the source, and the parameter λ is the fee rate of the best known next closure so far. This is achieved by reusing the push-relabel data structure across multiple instances of the minimum-cut problem, in such a way that the complexity for up to n such instances is the same as that for a single instance. This reduces

25

√ the complexity for a full linearization to O(n3 m). The all-breakpoints algorithm in the same paper is a further improvement over this. Instead of computing the maximum fee rate closures one by one in order, it uses a divide-andconquer approach, where every computed minimum cut splits the graph in two, and both sides are kept and then divided further with more cuts. It runs every minimum cut twice, in parallel, one forward and one in reverse, and stops both when the first one finishes. A clever scheme then reuses the final state for one of the two resulting subgraphs, in such a way that the complexity of the overall algorithm is the same as √ that of a single minimum cut, O(n2 m). As the number of dependencies is bounded by n2 /4, this means O(n3 ) when expressed just in n. This is referred to in our benchmarks as the bidirectional variant. A simpler variant, where a random direction is chosen √ for every minimum cut, has worst-case complexity O(n3 n),√but has better constant factors, and we believe it is also O(n2 n) when averaged over random seeds. Note that the paper gives a somewhat better complexity O(nm log(n2 /m)) for a minimum cut, by relying on a dynamic trees-based algorithm for minimum cuts instead of the max-label heuristic. In practice that algorithm is complicated and has bad constant factors, so it is rarely used. However, an instantiation with max-label is very practical, and an obvious choice for comparison with SFL, as it has great worst-case complexity.