Safe Quotes for Retroactive Liquidity Pools Peter Bro Miltersen∗ July 30, 2026
arXiv:2607.28522v1 [cs.DC] 30 Jul 2026
Abstract Automated market makers exchange assets through liquidity pools whose quoted prices depend on their reserves, with constant product pools being the most common. When such pools reside on different blockchains or shards, a sequence of swaps cannot in general be executed atomically. Aanes et al. introduced lock-swaps and retroactive constant product liquidity pools to provide price guarantees for such a setting. A retroactive pool implicitly maintains a virtual pool for each possible execute/cancel resolution of its active locks. In the presence of active locks, serving a new swap request requires computing a safe quote; a quote with an output that does not exceed the minimum possible output, taken over all virtual pools. The quote being safe is a hard constraint ensuring the integrity of the pool. A soft constraint is to make the quote as close to the minimum possible output as possible. Aanes et al. gave a simple and efficient algorithm for computing the exact minimum when unresolved provides and reclaims of liquidity do not coexist, showed by an explicit example that the algorithm fails in general, and left the computational complexity of the general case open. In this paper, we show that unless P is equal to NP, there is no polynomial time algorithm that computes in the general case a safe quote with any fixed multiplicative approximation ratio (e.g., 50%) relative to the exact minimum. This seems like a severe obstacle for deployment of the lock-swap functionality. However, we also present two simple and practical algorithms for computing safe quotes that have input-dependent approximation ratios that are likely to be satisfactory in practice, thus circumventing that obstacle.
Keywords: DeFi, Automated Market Makers, Constant Product Liquidity Pools, Sharded Blockchains, Cross-chain DeFi.
1
Introduction
Constant-product automated market makers allow traders to exchange two assets without a conventional order book. Such a market maker is particularly easy to use when all swaps in a transaction are executed atomically: an arbitrageur can submit a cycle of swaps and arrange that either the entire cycle is executed or none of it is. This protection is generally unavailable when the pools involved lie on different blockchains or on different shards of a sharded blockchain. While a trader waits for one swap to settle, another trade may change the price offered by a later pool, and a planned arbitrage cycle may end in a loss. ∗
Peter Bro Miltersen is an independent researcher. He dedicates this paper to the memory of Kurt Nielsen who first suggested the lock-swap mechanism and worked hard to get it deployed. Kurt sadly passed away much too early in July 2026.
1
Aanes, Gravgaard, Miltersen, Nielsen, and Pourpouneh [AGM+ 25] introduced lock-swaps to recover the relevant price guarantee without freezing the pool. A lock-swap gives its holder an option: acquire a quote for a swap, execute the swap later, or cancel it. A trader can first acquire one such lock for each leg of a cross-chain transaction and then execute all the locked swaps if the complete chain of transactions is satisfactory. Other traders may continue to swap in the meantime, and liquidity providers may continue to provide and reclaim liquidity; the locks fix the quoted prices, not the pool itself. Aanes et al. implement the lock-swap functionality by a construction called a retroactive pool. An active lock must remain executable whichever of the already-active locks are later executed or canceled, so the retroactive pool conceptually maintains one virtual pool for each execute/cancel resolution of the active locks; with k active locks there are 2k virtual pools. The default quote for a new lock-swap is then the minimum, over all virtual pools, of the exact swap output. The computational challenge is to find this minimum without explicitly enumerating the 2k virtual pools, incurring exponential time complexity. For an important restricted case, Aanes et al. overcome that challenge completely. Their Theorem 4 states that if the current state contains no unresolved provide operations, or no unresolved reclaim operations, then the minimizing resolution is fixed and simple: for an A-to-B lock-swap request, execute every active A-to-B lock and cancel every active B-to-A lock. Only one virtual pool per swap direction is then needed, a quote takes time linear in the stored state, and if reclaims are disallowed while locks are active, two running sums give constant-time quotes. The paper also shows, by an explicit counterexample, that the simple rule fails as soon as unresolved provides and reclaims coexist. Aanes et al. accordingly posed an open problem: can the general minimum be computed in polynomial time, is it NP-hard, and if it is hard, do useful approximation algorithms exist? The present paper resolves the open problem in a negative and a positive direction. We establish NP-hardness of computing not only the exact minimum quote among the virtual pools, but also safe quotes with any constant multiplicative approximation ratio (say, 50%) relative to that minimum. Here, a quote is safe if it is less than or equal to the exact minimum. Being safe is the hard constraint needed to ensure the integrity of the pool: a conservative quote may be less attractive to a trader, but a too optimistic quote can leave the reference pool unable to honor the quote of another active lock or even bring about a violation of the constant product invariant of the pool. The NP-hardness of computing such quotes with any constantfactor approximation guarantees seems a serious obstacle for the deployment of retroactive pools. Fortunately, we are able to give two algorithms that are computationally efficient in theory as well as in practice, with non-constant approximation ratios that are functions of a directly observable load parameter. When the assets of the stored event list are light relative to the base pool (as is likely to be the case in practice), both algorithms lead to quotes that are provably close to optimal. We therefore find it likely that these algorithms could be used for enabling a practical deployment of retroactive liquidity pools. We recall the model and fix notation before stating and proving our results. The presentation below is sufficient for the proofs in this paper; we refer to Aanes et al. for the description of the full abstract data type that the retroactive pool implements, its correctness properties, and discussions of the cross-chain protocol using it.
2
1.1
Constant-product pools and liquidity operations
A pool holds positive amounts a and b of two assets, called A and B. We call (a, b) its asset amount pair, or its allocation. In the fee-free, or exact, model, a trader who sends x > 0 units of A receives y > 0 units of B determined by (a + x)(b − y) = ab. Thus
bx . (1) a+x The product ab is unchanged by an exact swap. Swaps with fees can only increase it, but the open problem studied here assumes exact swaps in order to make the quote calculation unambiguous. Liquidity providers own shares of the pool represented by liquidity tokens. A liquidity token portion is a real-valued amount of such tokens. We write z > 0 for the total amount of liquidity tokens minted and not yet burned. The initialization operation y=
t ← init(a, b) creates the asset amount pair (a, b), sets z = 1, and returns a token portion t of amount 1. There are two operations for changing the supplied liquidity. A provide operation t ← provide(p, q),
p, q ≥ 0,
p + q > 0,
adds p units of A and q units of B. The amounts need not be proportional to the current pool holdings. Starting from (a, b, z), the operation produces r (a + p)(b + q) ′ ′ ′ a = a + p, b = b + q, z =z , (2) ab and returns a new liquidity token portion of amount z ′ − z. This token rule is the nonproportional-provide rule of [AGM+ 25]; it agrees with the usual proportional rule when p/a = q/b and can in general in the absense of fees and locks be simulated by first doing a swap making the provider’s assets proportional and then a provide by the proportional rule. A reclaim operation returns a previously issued token portion to the pool. If the portion has amount r < z, it is burned and the provider receives the same fraction r/z of each asset. Equivalently, r r (a, b, z) 7−→ 1 − a, 1 − b, z − r . (3) z z The condition r < z leaves both asset amounts positive. In operational terms, provide deposits assets and creates a claim on the pool, while reclaim burns such a claim and withdraws the corresponding share of the assets.
1.2
Locks and virtual pools
A lock is a signed asset delta (α, β) with one positive and one negative coordinate. An A-to-B lock has α > 0 and β < 0: executing it sends α units of A to the pool and removes −β units
3
of B. Canceling it leaves the pool unchanged. A lock is active, or unresolved, from the time it is granted until its holder executes or cancels it. We write L ← lockSwapAtoB(x)
or
L ← lockSwapBtoA(y)
for a request for an A-to-B or B-to-A lock, respectively. The holder later resolves L by performing execute(L) or cancel(L). The central difficulty is that later operations must be valid whichever of the active locks are eventually executed. A retroactive pool therefore maintains one virtual pool for each execute/cancel assignment to the active locks. If there are k active locks, there are 2k assignments. Each virtual pool is the state obtained by replaying the common history with the selected lock resolutions. When a new A-to-B lock with input x is requested, the retroactive pool evaluates the exact output in Equation (1) for every virtual pool and grants the smallest of these outputs. The lock is consequently executable under every later resolution of the earlier locks. A trace is a chronological record of retroactive-pool operations and their returned values. It is valid if every operation and return value obeys the preceding rules: in particular, each lock receives the minimum output over the current virtual pools, no token portion is reclaimed twice, and every reclaim is valid in every current virtual pool. The full histories need not be stored. The baseline implementation of [AGM+ 25] uses a compressed representation consisting of a base state (a0 , b0 , z0 ) and a chronological event list beginning with the earliest active lock. The entries have four forms: 1. an active lock, represented by its signed delta (α, β); 2. a provide(p, q) whose token portion cannot yet be finalized; 3. a reclaim of a token portion of amount r whose asset withdrawal cannot yet be finalized; or 4. the aggregate signed delta (α, β) of adjacent locks that have already been resolved. A provide or reclaim is called unresolved while a lock that was active when the operation was requested remains unresolved. The assets supplied by a provide can be put to work immediately, but its token amount depends on the virtual pool in which (2) is evaluated. Similarly, Equation (3) gives different withdrawals for different virtual token supplies. The token portion minted by an unresolved provide is not returned to its provider until the preceding locks have been resolved and therefore cannot be named by a reclaim in the current event list. An unresolved reclaim, by contrast, immediately surrenders its named token portion: the portion cannot be named again, and every virtual replay subtracts its amount from z at the position of the request. Only the asset withdrawal and its incorporation into the compressed base state await resolution of the preceding locks. Every unresolved reclaim therefore burns a distinct portion already included in the base token supply z0 . Given an execute/cancel assignment, the corresponding virtual pool is computed by scanning the event list from (a0 , b0 , z0 ). An executed lock adds (α, β) and a canceled lock does nothing. A resolved-lock aggregate always adds its delta. A provide and a reclaim use the transitions in Equations (2) and (3), respectively. We call a compressed state reachable if it is produced by a valid sequence of retroactive-pool operations.
4
1.3
The quote problem
Fix a reachable state and an exact A-to-B lock-swap request with input x > 0. For a resolution τ of the active locks, let (aτ , bτ ) be the final asset amount pair obtained in the corresponding virtual pool. By (1), the output in this virtual pool is x
bτ . aτ + x
The worst exact quote is therefore µ = min τ
xbτ . aτ + x
(4)
Direct enumeration takes time exponential in the number of active locks. For deployment, an underestimate of (4) is more useful than an ordinary feasible solution to this minimization problem. We call ℓ ≥ 0 a safe quote if ℓ ≤ µ. Both µ and ℓ are amounts of asset B. In the real-valued replay model, a safe quote does not exceed the output of any current virtual pool. For ρ ≥ 1, a safe quote is a ρ-approximation if µ ≤ ℓ ≤ µ. ρ This is the reverse of the usual approximation direction for a minimization problem: a feasible lock resolution gives an upper bound on µ, whereas a safe quote must be a lower bound.
1.4
Results and organization
Section 2 closes the road to exact quotes. It proves that the exact quote problem is NPhard. A second construction quotes a later lock in a known minimizing resolution and then removes that resolution by canceling an earlier lock. This amplifies the reduction’s additive gap and rules out every polynomial time computation of safe quotes within any constant factor of the exact minimum quote unless P = NP. Section 3 gives algorithms for computing safe quotes. The first maintains upper bounds on the two reserves and a lower bound on the liquidity-token supply. The second is an inexpensive input-output balance quote. Both algorithms scan the event list once, use a fixed number of arithmetic registers, avoid square roots, and return safe quote values. The first is strictly positive on every reachable state. The NP-hardness result rules out a universal constant approximation ratio, but both bounds have explicit approximation guarantees as a function of cumulative relative load. Our measure for that, η, adds the total reclaim-token fraction to the larger of the two cumulative relative asset loads. It is dimensionless, is computed from the stored state in one pass, and directly expresses whether the operations performed after the earliest active lock-swap are light relative to the pool. For η < 1, the product and balance quotes have approximation factors at most ((1 + η)/(1 − η))3 and ((1 + η)/(1 − η))2 , respectively. At total relative load η = 0.001, the guarantees evaluate to at least 99.40% and 99.60% of the exact minimum quote, respectively. Section 4 gives concluding remarks.
5
2
Hardness of Exact and Approximate Quotes
We first show NP-hardness of the following exact minimization problem, which captures the problem of determining the best safe quote. We then amplify the gap of the reduction to obtain a non-approximability result. Exact Virtual Quote: Given a valid finite trace of retroactive-pool operations whose numerical data are rational, a positive rational x, and a rational θ, decide whether, at the end xb of the trace, some virtual pool has an allocation (a, b) for which a+x ≤ θ. The promise is that the input trace is valid. Theorem 1. Exact Virtual Quote is an NP-hard promise problem. The source problem is positive-integer Subset Sum: given positive integers w1 , . P . . , wn and a positive integer target T , decide whether P there is a set I ⊆ {1, . . . , n} such that i∈I wi = T [GJ79]. The cases outside 0 < T < i wi are decided immediately and can be mapped to fixed yes- and no-instances, so this restricted source problem remains NP-hard. P Lemma 1. Let w1 , . . . , wn and T be positive integers satisfying 0 < T < S := i wi , and set L = 16S,
K = L + T,
Q = 3L.
One can construct, in polynomial time, a valid trace that begins with t⋆ ← provide(4/5, 4K/5).
init(1/5, K/5),
After these operations the allocation is (1, K), the token supply is 5, and t⋆ has amount 4. For Pi =
X
wj ,
Bi = K − Pi ,
δi =
j<i
Kwi , Bi (Bi − wi )
the trace next requests one active A-to-B lock Xi with delta (δi , −wi ) for each i ∈ {1, . . . , n}. The trace ends with an unresolved provide(0, Q) and an unresolved reclaim(t⋆ ). For every subset I ⊆ {1, . . . , n}, there is a resolution that executes precisely the locks Xi with i ∈ I. If X W = wi , B = L + T − W, i∈I
then the resulting final allocation (a, b) has 0 < a < 2 and b = f (B) := B + 3L −
4p B(B + 3L). 5
(5)
Proof. Initialize a retroactive pool by init(1/5, K/5) and then perform the proportional addition provide(4/5, 4K/5). The second operation mints a liquidity token portion t⋆ of amount 4. The resulting asset amount pair is (1, K), and the number of minted and unburnt liquidity tokens is 5. 6
When Xi is requested, all preceding active locks are A-to-B, and there is no unresolved provide or reclaim. Theorem 4 of [AGM+ 25] states that, under this condition, the minimum output for a new A-to-B lock is attained by the resolution that executes every active A-to-B lock and cancels every active B-to-A lock. Hence, in the present construction, the minimum is attained by executing every lock Xj with j < i. By induction, the allocation under this resolution is K , Bi . Bi Request Xi ← lockSwapAtoB(δi ). The exact output under the minimizing resolution is Bi δi = wi . K/Bi + δi The lock returned by the operation therefore has asset delta (δi , −wi ). After requesting the locks X1 , . . . , Xn , perform provide(0, Q)
and
reclaim(t⋆ ).
The portion t⋆ was issued before the locks Xi , and its amount is 4 < 5 when the reclaim is requested. Both operations are valid. Since the locks Xi remain active, the provide and reclaim are unresolved at the end of the trace and are replayed in every virtual pool. Thus every subset I occurs by executing exactly the locks Xi with i ∈ I. Fix an execute/cancel assignment and let X W = wi . i executed
Immediately before the B-only provide, the virtual B amount is B = K − W = L + T − W. The corresponding A amount is positive and uniformly bounded. Indeed, the all-executed increments telescope, and every assignment satisfies a≤
K 17 ≤ < 2. K −S 15
The B-only provide multiplies the number of liquidity tokens by r B+Q . B Burning t⋆ then scales both asset amounts by s 4 B 1− . 5 B+Q Consequently the final B amount is f (B). All event parameters are rational and have polynomial bit length, so the construction runs in polynomial time. 7
Lemma 2. With S, L, and f as in Lemma 1, f is uniquely minimized at B = L. For every integer B ∈ [L − S, L + S] with B ̸= L, f (B) − f (L) >
1 . 100L
Proof. Differentiation gives f ′ (B) = 1 − and f ′′ (B) =
4 2B + 3L p 5 2 B(B + 3L)
(3L)2 4 > 0. 5 4(B(B + 3L))3/2
Since f ′ (L) = 0, strict convexity makes L the unique minimizer, with f (L) =
12L . 5
The relevant interval lies in (0, 2L], so B + 3L ≤ 5L and (B(B + 3L))3/2 < 32L3 . Hence f ′′ (B) >
9 160L
throughout the interval. Taylor’s theorem and |B − L| ≥ 1 now give f (B) − f (L) ≥
1 9 1 (B − L)2 > . 2 160L 100L
Proof of Theorem 1. Apply Lemma 1 to the given Subset Sum instance. Set ∆=
1 , 100L
x = 106 L2 ,
θ=
12L ∆ + . 5 2
If some subset sums to T , its lock assignment has B = L. By Lemmas 1 and 2, its final B amount is 12L/5, and its quote value is x(12L/5) 12L < < θ. a+x 5 Suppose that no subset sums to T . Every assignment then has B ̸= L, so Lemmas 1 and 2 give a final B amount of at least 12L/5 + ∆ and a final A amount less than 2. Its quote value is therefore at least x(12L/5 + ∆) . x+2 This quantity exceeds θ. It suffices to verify x∆ 12L ∆ >2 + . 2 5 2 The left side is 5000L, while the right side is below 5L for L ≥ 1. The quote instance is consequently a yes-instance exactly when the original Subset Sum instance is a yes-instance. Lemma 1 and the definitions of x and θ show that the reduction runs in polynomial time. 8
The traces constructed above and their compressed endpoints both have polynomial size. Hence the hardness result also holds when the input is a compressed state promised to be reachable, as in an implementation. The additive separation in the preceding reduction is only Θ(1/L) against a quote-value scale of Θ(L). We now show how a later exact lock can turn this small additive separation into an arbitrarily large multiplicative one. The construction uses a known minimizing resolution to determine that lock’s output and then cancels the earlier lock needed for that resolution. Theorem 2. Fix ρ > 1. If there is a polynomial-time algorithm that takes as input a valid trace whose numerical data are rational and a new exact lock-swap request to be made at the end of that trace, and always returns a ρ-approximate safe quote for that request, then P = NP. Proof. Use the Subset Sum notation and the initial operations stated in Lemma 1. Thus L = 16S, K = L + T , the current allocation is (1, K), the token supply is 5, and the token portion t⋆ of amount 4 is available. Put D = S − T. Before requesting any lock Xi , request a B-to-A lock with B input D. Its exact A output in the unique current pool is D c= , K +D so this calibration lock C has delta (−c, D). Next request the locks Xi with the inputs δi defined in Lemma 1. No provide or reclaim is unresolved at this point. For each new A-to-B quote, Theorem 4 of [AGM+ 25] identifies the minimizing resolution: cancel the active B-to-A calibration lock C and execute every A-to-B lock Xj with j < i. Thus the quote calculations are the same as in Lemma 1, and the returned deltas are again (δi , −wi ). Now perform reclaim(t⋆ ).
provide(0, 3L),
These are the valid unresolved operations from Lemma 1. Let χ ∈ {0, 1} record whether C executes, and let W be the total weight of the executed locks Xi . Immediately before the provide, the B reserve is B = K + χD − W. This is an integer in [L − S, L + S], since 0 ≤ W ≤ S and 0 < D < S. The final B reserve is consequently f (B), where f is defined in Lemma 1. If C and all locks Xi execute, then B = K + D − S = L. This known calibration resolution has final reserves 3 K 12L ac = −c , b∗ = f (L) = . 5 K −S 5 Both values are rational because the provide multiplier at B = L is 2 and the reclaim survival factor is 3/5. Any other resolution P with final B reserve b∗ must cancel C and execute the locks indexed by a set I for which i∈I wi = T . Its A reserve is ! X 3 aI = 1+ δi < ac . 5 i∈I
9
To see the strict inequality, observe that δi =
Kwi wi > Bi (Bi − wi ) K
and
c=
D D < . K +D K
The indices outside I have total weight D, and hence ! X X K δi − c > 0. −c− 1+ δi = K −S i∈I
i∈I /
Every resolution has final A reserve less than 2. Every resolution whose B reserve before the provide differs from L has final B reserve greater than b∗ + ∆, where ∆=
1 . 100L
Since ρ is fixed, hard-wire an integer g ≥ ρ into the reduction and set H = 2000gL2 . Request an A-to-B lock with input H. The exact output from allocation (a, b) is GH (a, b) =
bH . a+H
The calibration resolution uniquely minimizes GH . Among resolutions with b = b∗ , it has the largest A reserve, and GH (a, b∗ ) decreases with a. Every resolution whose B reserve before the provide differs from L gives GH (a, b) >
(b∗ + ∆)H > b∗ > GH (ac , b∗ ), H +2
where the middle inequality follows from H∆ = 20gL > 2b∗ = 24L/5. The new amplifier lock therefore has the known rational delta (H, −v),
v=
b∗ H . ac + H
Cancel the earlier calibration lock C while leaving the locks Xi and the amplifier active. The retroactive-pool operation removes the virtual pools in which C executes; it does not change the delta of the later lock. Since a lock Xi still precedes the provide and reclaim, these liquidity events remain unresolved. The resulting valid trace therefore ends in a state from which the resolution that determined v is absent. Request an A-to-B lock with input x = 1 in this state. Write ε = b∗ − v =
b∗ ac . ac + H
Every remaining resolution has B reserve at least b∗ . If the amplifier is canceled, its quote value is greater than b∗ /3 = 4L/5. If the amplifier executes, its quote value is less than 5L/H, since f (B) < B + 3L < 5L. The choice of H makes 5L/H < 4L/5, so every minimizing resolution executes it. 10
If some subset sums to T , that subset has B reserve b∗ before the amplifier and gives µ<
ε 2b∗ < 2 =: Y. H H
If no subset sums to T , every resolution has B reserve greater than b∗ + ∆ before the amplifier. Since its A reserve is less than 2, ∆ µ> =: N. H +3 The two rational bounds satisfy 25g N ∆H 2 ∆H = = > > g. Y 2b∗ (H + 3) 4b∗ 12 Run the assumed safe approximation and compare its rational output ℓ with Y . In a yesinstance, ℓ ≤ µ < Y . In a no-instance, ℓ ≥ µ/ρ > N/ρ > Y . The comparison decides Subset Sum. Every numerical value recorded in the constructed trace is rational with polynomial binary length. Square roots occur in non-calibration virtual replays, but they are neither recorded in the trace nor evaluated by the reduction. Lemma 2 supplies the required comparison: if B ̸= L, then f (B) > b∗ + ∆. Although H is numerically large, its binary representation has O(log g + log L) bits. Thus the reduction runs in polynomial time in the standard Turing machine model.
3
Efficiently Computable Safe Quotes
We now give the constructive results. The first quote follows from a product invariant and three scalar bounds. The second is an input-output balance quote that costs two additional accumulators. Write (α, β) for the asset delta of a lock or a resolved-lock aggregate, (p, q) for the nonnegative amounts in a provide, and r for the amount of a liquidity token portion burned by a reclaim. Let m be the event-list length. Each quote computation uses O(m) arithmetic operations and a fixed number of scalar registers.
3.1
A universal product-floor quote
For the reachable compressed state given as input, write (a0 , b0 , z0 ) for its base state: a0 and b0 are the base asset amounts, and z0 is the base amount of minted and unburnt liquidity tokens. For an allocation (a, b) with z minted and unburnt liquidity tokens, define z γ=√ , ab
γ0 = √
z0 . a0 b0
Lemma 3. At every prefix of every virtual replay of a reachable compressed state, γ ≤ γ0 . √ Proof. A provide (p, q) multiplies both z and ab by p (1 + p/a)(1 + q/b), 11
and a reclaim multiplies both by 1 − r/z. These operations preserve γ. Consider an A-to-B lock with delta (u, −v), where u, v > 0. When the lock is granted, its output satisfies, for every virtual allocation to which it may later be applied, v≤
bu . a+u
Indeed, the prefix of a later replay immediately before this lock is one of the virtual pools considered when the lock was granted. Equivalently, (a + u)(b − v) ≥ ab. √ Execution cannot decrease ab, while cancellation leaves it unchanged; neither operation changes z. The B-to-A case is symmetric. An aggregate of resolved locks represents a sequence of such executions. Induction over the event list proves the claim. The algorithm processes the given state’s entire stored event list in chronological order while maintaining reserve upper bounds A+ , B + and a token lower bound Z − . Initialize A+ = a0 ,
Z − = z0 .
B + = b0 ,
For a delta entry (α, β), set A+ ← A+ + max{0, α},
B + ← B + + max{0, β}.
For a provide (p, q), first compute ξ=
p q pq + + + + +, + A B A B
F− = 1 +
ξ . 2+ξ
and then set Z − ← Z −F −,
A+ ← A+ + p,
B + ← B + + q.
For a reclaim of amount r, set Z − ← Z − − r. Theorem 3. For every reachable compressed state and every exact A-to-B lock-swap request with input x > 0, let A+ , B + , Z − be the terminal register values produced by the algorithm above. Then x(Z − /z0 )2 a0 b0 ℓprod = (6) A+ (A+ + x) is a strictly positive safe quote. Proof. We first verify that a ≤ A+ and b ≤ B + after every prefix of every virtual-pool replay. The inequalities hold with equality at initialization. An active delta entry contributes either (0, 0) or (α, β), and a resolved aggregate contributes (α, β); in either case, the increase in each reserve is at most the positive part used in the update above. A provide adds exactly (p, q) to both the replayed reserves and their bounds. A reclaim multiplies both replayed reserves by a number in (0, 1) while leaving A+ and B + unchanged. Induction proves the two upper bounds. At a provide, its exact token multiplier is p F = (1 + p/a)(1 + q/b). 12
Since a ≤ A+ and b ≤ B + before the provide, F ≥
p
1+ξ ≥1+
ξ = F −. 2+ξ
The last inequality follows from p 1+ξ−1= √
ξ ξ ≥ . ξ+2 1+ξ+1
Thus z ≥ Z − at every step of the algorithm. Every intermediate value of Z − is positive. Each unresolved reclaim burns a distinct portion already included in z0 , so the amounts burned in any prefix sum to at most z0 . If the sum is less than z0 , positivity is immediate. If it equals z0 , the final reclaim in that prefix could not be valid without an earlier nonzero provide increasing the token supply in every virtual replay. For that provide, ξ > 0 and F − > 1, which leaves Z − > 0 after all z0 base tokens have been subtracted. For a final virtual pool, Lemma 3 gives 2 − 2 − 2 z Z Z ab = ≥ = a0 b0 . γ γ0 z0 Also a ≤ A+ . Since a(a + x) increases with a > 0, xab x(Z − /z0 )2 a0 b0 xb = ≥ . a+x a(a + x) A+ (A+ + x) This is (6).
3.2
An input-output balance quote
For an A-to-B lock-swap request, let D, P, and R denote the delta entries, provides, and reclaims. For e ∈ D, write (αe , βe ) for its asset delta; for e ∈ P, write (pe , qe ) for the assets deposited; and for e ∈ R, write re for the amount of the token portion burned. Define X X UA = max{0, αe } + pe , e∈D
DB =
X
e∈P
max{0, −βe },
e∈D
R=
X
(7) re .
e∈R
Here UA bounds additions to the input-asset balance, DB bounds withdrawals from the outputasset balance, and R is the total reclaimed token amount. The computation of ℓprod ends with A+ = a0 + UA , so only DB and R are new accumulators. For a real number y, write [y]+ = max{0, y}, and set x [(1 − R/z0 )b0 − DB ]+ ℓbal = . (8) a0 + UA + x The bracketed term is a lower bound on the final output-asset balance, while the denominator uses an upper bound on the final input-asset balance.
13
Lemma 4. For every reachable compressed state, if (a, b) is the final allocation of one of its virtual pools, then a ≤ a0 + UA , b ≥ (1 − R/z0 )b0 − DB . P Proof. List the reclaims chronologically as r1 , r2 , . . ., and put Rj = i≤j ri . Immediately before reclaim j, every replay has token supply zj ≥ z0 − Rj−1 , because provides only increase the token supply. Distinct unresolved portions are drawn from the base supply, so Rj ≤ z0 . Its reclaim scale therefore satisfies 1−
rj z0 − R j ≥ . zj z0 − Rj−1
The product of all reclaim scales is consequently at least 1 − R/z0 . Expand a final reserve into its base contribution and the additive contributions of delta entries and provides. Each contribution is multiplied by the reclaim scales that follow it. For the A reserve, omit negative contributions and all reclaim shrinkage, giving a ≤ a0 + UA . For the B reserve, omit positive contributions. Multiplication by a number in (0, 1] makes a negative contribution less negative, so replacing each such contribution by its unscaled value preserves a lower bound. The base coefficient is at least 1 − R/z0 , which proves the second inequality. Theorem 4. For every reachable compressed state and every exact A-to-B lock-swap request with input x > 0, the value ℓbal in Equation (8) is a safe quote. Proof. If the numerator in (8) is nonpositive, then ℓbal = 0 is safe. Otherwise Lemma 4 and the monotonicity of xb/(a + x) give, for every final virtual pool, xb x((1 − R/z0 )b0 − DB ) ≥ = ℓbal . a+x a0 + U A + x Hence ℓbal ≤ µ.
3.3
Approximation guarantees from cumulative load
Safety alone does not say how conservative a quote is. The following parameter gives both algorithms a useful performance guarantee. Define X X X X LA = |αe | + pe , LB = |βe | + qe , e∈D
e∈P
R η= + max z0
LA LB , a0 b0
e∈D
e∈P
(9)
.
This dimensionless statistic measures total unresolved activity relative to the compressed base pool. It is conservative because it counts both directions of every delta even though an active lock may be canceled. It is computed by three accumulators during the quote computation and is not a tuning parameter of either algorithm. For 0 ≤ η < 1, set (1 − η)a0 + x 1−η cη = , qη (x) = . (10) 1+η (1 + η)a0 + x 14
Theorem 5. For every reachable compressed state with η < 1 and every exact A-to-B lock-swap request with input x > 0, c2η qη (x)µ ≤ ℓprod ≤ µ, cη qη (x)µ ≤ ℓbal ≤ µ.
(11)
In particular, c3η µ ≤ ℓprod ≤ µ,
c2η µ ≤ ℓbal ≤ µ.
Proof. List the reclaims chronologically as r1 , r2 , . . ., and put Rj = before reclaim j, every exact replay has token supply
(12) P
i≤j ri .
Immediately
zj ≥ z0 − Rj−1 , because provides only increase the token supply. Here Rj ≤ R < z0 , since η < 1. Its reclaim scale therefore satisfies rj z0 − R j 1− ≥ . zj z0 − Rj−1 Multiplying these inequalities shows that the product of all reclaim scales is at least 1 − R/z0 . Expand either final asset amount into the contribution from its base amount and the additive contributions from delta entries and provides. Each contribution is multiplied by the reclaim scales that follow it. The base coefficient is at least 1 − R/z0 . A negative delta contributes no less than its unscaled value, while a positive contribution can be omitted from a lower bound. For an upper bound, reclaim scales and negative deltas can instead be omitted. Consequently, if (a, b) is any final virtual-pool allocation, then (1 − R/z0 )a0 − LA ≤ a ≤ a0 + LA , (1 − R/z0 )b0 − LB ≤ b ≤ b0 + LB . The definition of η gives the simpler bounds (1 − η)a0 ≤ a ≤ (1 + η)a0 ,
(1 − η)b0 ≤ b ≤ (1 + η)b0 .
(13)
In particular, every virtual-pool quote value is at most Uη =
x(1 + η)b0 , (1 − η)a0 + x
and hence
µ ≤ Uη .
(14)
In the computation of ℓprod , every provide multiplier is at least one. The final token lower bound and asset upper bound therefore obey Z − ≥ z0 − R ≥ (1 − η)z0 ,
A+ ≤ a0 + LA ≤ (1 + η)a0 .
Equation (6) now gives ℓprod ≥
x(1 − η)2 a0 b0 . (1 + η)a0 ((1 + η)a0 + x)
Dividing this lower bound by (14) yields ℓprod /µ ≥ c2η qη (x). Moreover, UA ≤ LA and DB ≤ LB . The numerator of ℓbal is positive when η < 1, and ℓbal ≥
x(1 − η)b0 , (1 + η)a0 + x
and division by (14) gives ℓbal /µ ≥ cη qη (x). Finally, qη (x) ≥ cη for x ≥ 0, proving Equation (12). 15
For every fixed load cap η̄ < 1, the two quotes are ordinary constant-factor approximations on the class η ≤ η̄. Their factors are at most
1 + η̄ 1 − η̄
3
and
1 + η̄ 1 − η̄
2 ,
respectively. Equivalently, ℓprod /µ ≥ 1 − 6η + O(η 2 ) and ℓbal /µ ≥ 1 − 4η + O(η 2 ) as η → 0. The following values are worst-case guarantees over every reachable event list and every resolution of the active locks: η c3η c2η 0.0001 0.9994 0.9996 0.001 0.9940 0.9960 0.005 0.9704 0.9801 0.010 0.9417 0.9607 0.020 0.8869 0.9231 0.050 0.7406 0.8185 The guarantees in Equation (11) are stronger when the requested input x is not negligible relative to a0 . Exchanging A and B gives the corresponding statement for a B-to-A lock-swap request. One may of course return max{ℓprod , ℓbal }. Both constituent quotes are safe, so their maximum is safe. It is strictly positive because ℓprod > 0 and is at least as accurate as either constituent quote.
3.4
Computation with exact rational and finite-precision arithmetic
The input-output balance quote has a particularly small implementation using integer arithmetic. Clearing the token denominator gives ℓbal =
x[ b0 (z0 − R) − z0 DB ]+ . z0 (a0 + UA + x)
(15)
Thus widened integer sums and products compute its numerator and denominator, and one downward-rounded integer division produces a safe lower bound on the exact-model quote. For rationally encoded inputs, the two algorithms are straight-line programs over rational field operations and maximum gates, with s = O(m + 1) gates. Let h be the largest bit length of a numerator or denominator in the input. A direct induction over the displayed running sums and the recurrence for Z − bounds the numerator and denominator bit lengths of every reduced intermediate value by some Λ = O((m + 1)2 (h + 1)); the final squaring in ℓprod and the final multiplication by x preserve this bound up to a constant factor. Exact rational evaluation is therefore polynomial-time in the standard Turing machine model. More relevant for deployment, for an integer d ≥ 0, an implementation using fixed-point arithmetic may instead enclose each input between adjacent points of 2−d Z, round every interval operation outward, and return the positive part of the final lower endpoint. Gatewise containment preserves safety. Every positive divisor and every positive exact-rational output of either algorithm is at least 2−Λ , while all intermediate magnitudes are at most 2Λ . A standard interval-error induction gives a universal constant C such that, for every integer κ ≥ 1,
16
choosing d ≥ C(sΛ + Λ + κ) and using checked integer arithmetic with polynomial total word width suffices to return, for ℓ ∈ {ℓprod , ℓbal }, a value ℓb satisfying (1 − 2−κ )ℓ ≤ ℓb ≤ ℓ ≤ µ. At this precision, the rounded quote incurs relative loss at most 2−κ . At lower precision, a divisor interval containing zero triggers the safe fallback value zero.
4
Concluding Remarks
The open problem of Aanes et al. [AGM+ 25] asked whether the exact worst-case quote of a retroactive pool can be computed efficiently in general. We have shown that, unless P = NP, neither the exact value nor any fixed-factor safe approximation can be computed in polynomial time. Fortunately, we have also shown that this hardness is not an obstacle to deployment: a retroactive pool does not need the exact minimum, only a safe quote, and safe quotes with an explicit, per-state accuracy certificate can be computed in practice with one linear scan and a constant number of registers. In the regime where the stored unresolved activity is light relative to the pool, which is the regime in which one would expect a healthy pool to operate, the certified accuracy is close to optimal. If the pool operates outside of that regime, the quotes are still safe, though they might not be very good. The safety arguments use only the inequality (a + u)(b − v) ≥ ab for executed locks, which fee-bearing execution preserves, so both algorithms remain safe in a pool that charges fees; we can expect the load-dependent guarantees to extend as well, suitably modified, but we do not pursue this here.
References [AGM+ 25] Jon Michael Aanes, Jesper Balman Gravgaard, Peter Bro Miltersen, Kurt Nielsen, and Mohsen Pourpouneh. Automated market makers for cross-chain DeFi and sharded blockchains. arXiv:2309.14290v3 [cs.DC], 2025. Version 3, last revised January 27, 2025. [GJ79]
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco, 1979.
17