CS Paper Radar

Tight Characterizations of AMM Mechanism Design under Weak Efficiency

Chengkai Zhang, Lirong Xia, Elaine Shi, Mengqian Zhang, Qishen Han, Yuhao Li

cs.GT ·submitted 2026-10-27 04:49 UTC · v1
theory

Abstract

Miner extractable value (MEV) poses a persistent challenge for blockchain ecosystems. It arises from the fact that a block builder can exploit its unilateral control over transaction inclusion and ordering to extract profit, potentially at users' expense. Recent work has explored consensus-aided mechanism design to mitigate MEV. This approach combines generic consensus-layer guarantees with application-layer mechanisms that use these guarantees to address application-specific MEV problems. Prior work exemplifies this approach for automated market makers (AMMs). When the consensus layer offers fair sequencing, which orders transactions according to their arrival times, their proposed mechanism achieves incentive compatibility (IC) and weak local efficiency (wLE). Informally, IC rules out profitable strategic deviations by users and builders. Meanwhile, wLE ensures that after execution, any order willing to trade at the initial price cannot benefit from further trade with the pool at the ending marginal price. In this work, we resolve the main open question left by prior works: whether IC and wLE can be achieved under plain consensus (e.g., current Ethereum) without fair sequencing. We prove that no deterministic, anonymous batch AMM can achieve both properties. The impossibility holds even when the consensus layer guarantees censorship resilience and block space is unlimited, establishing the first separation between censorship resilience and fair sequencing in the context of decentralized mechanism design. Our impossibility proof combines three strategic capabilities: creating Sybil identities, over-reporting budgets, and misreporting values. We further show the tightness of our impossibility result: removing any one from the strategy space restores feasibility under censorship resilience. Specifically, we construct a mechanism achieving IC and wLE for each restricted setting.

Comment
Abstract shortened to comply with arXiv's character limit

Closest papers

Nearest neighbours by meaning across the whole index.

Otter: A Provably MEV-Resilient Automated Market Maker via Surplus Redistribution

cs.GT ·2026-09-03 ·Elaine Shi, Mengqian Zhang, Hao Chung, Yuhao Li
similarity 0.71
Abstract · Abstract shortened to comply with arXiv's character limit

Miner extractable value (MEV) in automated market makers allows block builders to profit from transaction ordering and injected trades, imposing costs on users and contributing to builder centralization. We introduce Otter (Optimal Truthful Trading with Excess Redistribution), a two-asset batch AMM that achieves provable MEV resilience when the consensus layer provides censorship resilience and block space is uncongested. Otter makes truthful behavior a dominant strategy for both users and builders. Consequently, a builder cannot profit from strategic deviations, including reordering bids or injecting sybil bids, even when the builder is itself a trader with intrinsic value. Moreover, we show that Otter maximizes social welfare, in a strong sense, within a natural class of mechanisms satisfying the desired game-theoretic properties. To achieve these guarantees, we introduce a new paradigm called surplus redistribution, which provably prevents residual surplus from being captured as MEV by redirecting it to the broader community. Specifically, the pool's output tokens need not be distributed entirely among users in the current batch. Instead, residual surplus may be transferred to a smart contract governed by the decentralized community. The accumulated surplus can be used to benefit community members --- for example, by subsidizing transaction fees, rewarding liquidity providers, or returning assets to the pool. Our approach relies on the underlying consensus layer to provide censorship resilience. We motivate its necessity through an impossibility result showing that the desired game-theoretic guarantees become unattainable when the builder is additionally allowed to censor transactions. Thus, our results also provide a mathematically formal demonstration of how consensus-level security guarantees can fundamentally expand what is achievable at the application layer.

0.47

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

cs.DC cs.CRcs.GT ·2026-11-06 ·William Diamond, Fatima Elsheimy, Dahlia Malkhi, Geoff Ramseyer, Srivatsan Sridhar
similarity 0.69
Abstract

Decentralized exchanges typically give traders no execution guarantee until a block is finalized. In the meantime, external prices move, traders strategically delay submission, and block producers can influence inclusion and ordering. We introduce FirstSwap, a DEX built on a constant-function market maker pricing curve that gives traders an early pre-approval before consensus, guaranteeing inclusion and execution within their submitted price limit, with final ordering determined by limit prices rather than by a block producer. We demonstrate the benefits of trade pre-approvals in an economic model combining auction theory with CEX-DEX arbitrage. When the CEX price changes gradually, FirstSwap rewards earlier traders with better prices, discouraging strategic delay and yielding higher social welfare and gains to AMM liquidity providers than a batch auction. When the CEX price jumps abruptly, FirstSwap yields higher welfare and smaller AMM losses than fair ordering. The central challenge is delivering fast trade pre-approvals without consensus. We introduce a decentralized, scaled admissibility protocol under which each validator reserves only a fraction of the available liquidity at every price. A trader obtains approval in a single round of messages with a quorum of validators. Somewhat surprisingly, despite Byzantine validators who may approve trades arbitrarily, we show that all quorum-certified trades are jointly admissible and execute within their limits. Our protocol extends naturally to a setting where buy and sell orders can be pre-approved against each other before a block is finalized.

0.19

Uniform-Price Mechanism Design for Automated Market Makers

cs.GT ·2026-10-16 ·Zhike Peng
published similarity 0.64
Abstract · 22 pages. Full version of a paper accepted at IJTCS-FAW 2026

Automated market makers (AMMs) are central to decentralized exchanges, but their reserve curves make mechanism design different from classical double auctions. We study a batch double auction with buyers, sellers, and a liquidity-nondecreasing AMM: post-trade reserves must have weakly larger product than the initial reserves. Each user has two-dimensional private information: a unit value and a demand or supply quantity. User trades clear at one uniform price subject to AMM feasibility. The objective is user-side trading volume, benchmarked against the optimal feasible individually rational (IR) uniform-price allocation. We give a randomized uniform-price mechanism based on binary quantity buckets. It randomly chooses one of three clearing modes: peer-to-peer matching, AMM sales to buyers, and seller sales to the AMM. Every deterministic realization of the mechanism is ex-post feasible and satisfies IR and weak quantity incentive compatibility: conditional on any quantity report, truthful unit-value reporting is dominant whenever it gives a non-negative utility, no unit-value deviation gives a positive utility if the truthful one doesn't, and users cannot benefit by under-reporting the quantity together with their truthful unit value. Let $V^\ast$ be the optimal feasible IR uniform-price volume without incentive constraints, and let $γ=\bar q/\underline q$, where $\bar q$ and $\underline q$ are the quantity-domain bounds. For $γ\ge1$, the mechanism achieves an expected trading volume of $ Ω(1/(1+\logγ)^2)V^\ast - O(\bar q). $ We also show that full incentive compatibility over the two-dimensional type space forces a worst-case approximation ratio of $O(1/γ)$ at every prescribed initial reserve ratio, even when both AMM reserves are scaled by an arbitrarily large common factor and the optimal volume $V^\ast$ is arbitrarily large relative to $\bar q$.

0.36

Breaking Cycles for Scalable Fair Ordering in Blockchain Systems

cs.DC ·2026-09-01 ·Jinchun He, Wangjie Qiu, Yizhong Liu, Shengda Zhuo, Kwok-Yan Lam
similarity 0.63
Abstract

In blockchain systems, transaction order directly determines financial outcomes: unfair ordering enables front-running and sandwich attacks that have extracted over \$686M from Ethereum users. Current fair-ordering protocols aggregate pairwise receive-order evidence from replicas. Under contention or adversarial manipulation, however, Condorcet cycles force them into global strongly connected component (SCC) condensation, causing delays, coarse batches, and scaling failures. We present FlashOrder, a deterministic fair-ordering engine that localizes cyclic ambiguity before it propagates across the batch. FlashOrder embeds pairwise preferences into one-dimensional canonical positions, clusters nearby transactions with a partition hypergraph, and performs hierarchical inter- and intra-cluster serialization, replacing batch-wide SCC condensation with localized sorting and aggregation. Evaluated against Themis (CCS '23) and Rashnu (VLDB '24) on a libhotstuff-based prototype, FlashOrder achieves up to 10.5$\times$ higher throughput than Themis and 4.8$\times$ higher than Rashnu, with the latency gap widening as network scales. In controlled adversarial simulation, it reduces maximum rank displacement by 88.7\%, and under Condorcet attacks it sustains 12.0$\times$ and 9.7$\times$ higher throughput than Themis and Rashnu on average. These results show that localizing cyclic ambiguity yields stronger fairness at substantially higher throughput.

0.18

Mitigating Front-Running Attacks through Fair and Resilient Transaction Dissemination

cs.DC ·2026-09-21 ·Wassim Yahyaoui, Joachim Bruneau-Queyreix, Jérémie Decouchant, Marcus Völp
publishedhighly cited similarity 0.63
Abstract

In modern blockchains, efficient, fair, and faulttolerant information dissemination is critical for performance and security. Several stages of the transaction lifecycle are affected, from the creation and dissemination of transactions to the dissemination of blocks in the consensus layer. Mempool protocols, such as L{Ø}, already address some of modern blockchains' security threats. However, others remain unless fairness is embedded most fundamentally in the dissemination layer used by these protocols to share transactions and blocks and to reconcile mempools. This paper introduces HERMES, a novel dissemination protocol for mempools that leverages robust minimal structures to optimize data propagation, balance load, and ensure fairness despite faults and Byzantine actors. Specifically, we address front-running attacks by randomizing the choice of an overlay structure while forcing nodes to prove adherence to the mempools' dissemination policies and the random choice made. Experimental results show significant performance improvements compared to traditional broadcast protocols for both permissioned and permissionless blockchains.

0.57

Slow and Steady: Preventing MEV with Verifiable Delays

cs.CR ·2026-08-13 ·Zeta Avarikioti, Dimitris Karakostas, Karl Kreder, Shreekara Shastry
similarity 0.62
Abstract · A revised version is accepted for publication at the 10th International Workshop on Cryptocurrencies and Blockchain Technology (CBT 2026)

Our work presents a defense mechanism against Maximal Extractable Value (MEV) opportunities in distributed ledgers. The mechanism relies on the idea of enforcing a verifiable delay when generating transactions, such that a block creator cannot react to the appearance of a MEV opportunity without breaking liveness. We present positive results both in the Byzantine setting and in a game theoretic model of rational participants. We additionally present negative bounds that outline the limitations of this line of defense. Finally, we explore real-world implementation details of verifiable delays and show that, based on historical MEV data, our mechanism could realistically help prevent most existing MEV threats.

0.13

RANDAO Manipulation in the Presence of MEV

cs.GT ·2026-10-01 ·Kaya Alpturer, Nicholas Hope, S. Matthew Weinberg
published similarity 0.61
Abstract · 23 pages, 7 figures, full version of the AFT 2026 paper

Ethereum's randomness beacon (RANDAO) is well-known to be manipulable, and prior work [AW24] computes the precise fraction of blocks a strategic proposer can propose. The fraction of blocks proposed, however, is only a proxy for participants' rewards. We propose a generalized reward model capturing many canonical forms of rewards: consensus reward rollover, multi-block MEV, CEX-DEX arbitrage, oracle manipulation, and others. We provide a methodology that computes an ε-optimal strategy for any reward scheme in our model (and in particular, any combination of the above rewards). Finally, we apply our methodology to several canonical examples, and establish the sensitivity of RANDAO manipulation to the underlying rewards. We find that if rewards partially roll over, or scale super-linearly with consecutive blocks, the incentive to manipulate RANDAO is amplified. Lastly, we investigate tail-slot slashing, which can be modeled as a reward function, and show that honest equilibria can be recovered.

0.46

Bandwidth Fee Mechanisms for Certified Transaction Dissemination

cs.GT ·2026-09-30 ·Eleftheria Fassman, Mahimna Kelkar, Benjamin Marsh, Ke Wu
similarity 0.60
Abstract

We study bandwidth fee mechanisms (BFMs) for pricing threshold-certified transaction dissemination before consensus. Analogous to transaction fee mechanisms for computation, BFMs price blockchain communication, which is especially relevant when dissemination is separated from consensus and execution. We model BFMs as two-sided procurement auctions between users submitting transactions and validators receiving and forwarding them. Any validator may serve as a transaction's source and forward it to a threshold of attesters. The model accounts for receipt from the user and subsequent transfers between validators, while abstracting away unrestricted multi-hop gossip and network topology. We establish limits on myopic incentive compatibility: no nontrivial transcript-based BFM prevents profitable collusion between two validators, and no nontrivial BFM simultaneously satisfies incentive compatibility for individual users, individual validators, and coalitions of one validator and one user. On the feasibility side, we give a greedy-route posted-price mechanism that is incentive compatible for every individual user and validator. We also study bandwidth pricing across blocks. Assuming honest validator execution, we propose an EIP-1559-style price-update rule whose fluid approximation has a unique fixed point that is locally stable for sufficiently small step sizes. In large markets, prices starting near this point remain nearby with high probability over any fixed time horizon.

0.06