Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of computing safe quotes for retroactive constant product liquidity pools in automated market makers, particularly when swaps cannot be executed atomically across different blockchains. The authors prove that unless P equals NP, no polynomial time algorithm can compute a safe quote with a fixed multiplicative approximation ratio in the general case, highlighting a significant barrier to the deployment of lock-swap functionality. To mitigate this, they introduce two practical algorithms that provide input-dependent approximation ratios, offering a feasible solution for real-world applications.
Computing safe quotes for retroactive liquidity pools is provably intractable in general, but practical algorithms exist that can deliver satisfactory results in real-world scenarios.
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.