FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design William Diamond1 , Fatima Elsheimy2 , Dahlia Malkhi3 , Geoff Ramseyer4 , and Srivatsan Sridhar5⋆ 1

arXiv:2611.10254v1 [cs.DC] 6 Nov 2026

University of Wisconsin–Madison 2 Yale University 3 University of California, Santa Barbara 4 Stellar 5 University of California, Berkeley

November 10, 2026

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 quorumcertified 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.

1

Introduction

This paper introduces FirstSwap, a decentralized exchange operated by a network of validators that finalizes blocks of trades epoch by epoch. FirstSwap ⋆

We thank Malcolm Granville for insights in the early stages of this project.

2

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Welfare and AMM gains

incentivizes early submission of trade requests by granting pre-approval certificates promptly upon arrival, without waiting for end-of-epoch consensus. Preapprovals are processed through a single direct interaction between each trader and a quorum of validators, yielding a fast, consensus-free procedure. We develop an economic model to analyze FirstSwap’s pre-approval mechanism as a market design. Early pre-approvals yield higher social welfare and gains to AMM liquidity providers than the end-of-block confirmation typical of blockchains. FirstSwap naturally mitigates two prevalent forms of strategic exploitation. First, MEV is curtailed because trade execution depends only on block contents and not on their ordering, and because pre-approvals must come from a quorum of validators and not at the discretion of a single block builder. Second, CEX–DEX arbitrage exploiting a passive AMM is reduced because traders must race for early pre-approval instead of waiting for arbitrage opportunities. FirstSwap consists of two key ingredients, each of potential interest on its own: First, we propose a pre-approval mechanism which constitutes a new form of auction, where both arrival order and price matter. Traders post trade requests with limit prices; each trade request is either pre-approved or rejected based on a price-contingent capacity without being assigned a final position in the block. At epoch end, a final block is produced with an intra-execution ordering, guaranteed to include all pre-approved trade requests settling within their price limits. We develop an economic model to analyze this mechanism and demonstrate that early pre-approvals yield higher social and AMM profitability compared to other proposed AMM mechanisms. Figure 1 illustrates our findings. Small jump

Gradual diffusion

r

r

r r

r Batch FIFO

Large jump

r

FS

Batch FIFO

r FS

Batch FIFO

FS

Fig. 1. Qualitative comparison of exchange mechanisms (Batch = batch auction, FIFO = first-in-first-out, FS = FirstSwap). Both overall welfare and AMM gains from trade follow the same trends, under the conditions of Equation (11) and Lemma 4. Higher positions indicate higher outcomes within each scenario; vertical distances are not to scale. The ranges indicate that the comparison of FS with FIFO (small jump) or Batch (large jump) is ambiguous without further assumptions.

Second, we propose a fast, consensus-free implementation for a network of validators to collectively operate the pre-approval system. Each pre-approval is obtained through a single direct exchange between the trader and a quorum of validators, with each validator deciding whether to pre-approve a trade request based solely on local information, requiring no coordination among validators. Somewhat surprisingly, the protocol guarantees that at the end of a block epoch, all pre-approvals obtained in this manner can settle within their price limits. Furthermore, Byzantine validators cannot prevent pre-approved trade requests from settling, and if they attempt to hide pre-approved trade requests, not only

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

3

do they fail but their action is punishable. A straightforward extension of our protocol allows for simultaneous buy and sell orders to be handled simultaneously, where validators can pre-approve additional buys when they have seen sell trade reqests that could execute against them and conversely. AMM liquidity providers can also deposit and withdraw funds at the end of the block after orders are executed without impacting our analysis. 1.1

Overview

The Exchange Design. Assume for now that the protocol is run by a single validator. FirstSwap allocates trades against a pool of fungible assets for sale. The exchange employs a continuous pricing mechanism identical to that of constant-function market makers (CFMMs). The price per unit p(x) increases as more assets are purchased, where x is the quantity already bought. The pre-approval mechanism operates epoch by epoch. During an epoch, trade requests in the form tx = (amt, limit) arrive and are admitted to FirstSwap promptly upon arrival. A trader’s limit price limit constrains the total quantity that may be consumed before and including their trade. For each trade request, the pre-approval system determines whether it can be satisfied based on the trades pre-approved so far. If so, unlike existing blockchain-based platforms, the system returns a pre-approval certificate immediately. Pre-approved trades are then gathered into a finalized block for execution. FirstSwap guarantees that all pre-approved trade requests can be executed within their price limits, and the final ordering of trades within the finalized block is computed deterministically. A key notion in the pre-approval mechanism is admissibility: A set T of trades of the form (amt, limit) is admissible if for every limit ℓ in T , the sum total x of amounts in trades whose limit is ≤ ℓ satisfies p(x) ≤ ℓ. Note that if a set is admissible, then executing trades in ascending order of limits allows all trade requests to settle within the requested price limits. An incoming trade request tx may be pre-approved if adding the trade request to the set A of previously pre-approved trades preserves admissibility; that is, if A ∪ {tx} is admissible. For illustration, consider the special case where all trade requests are for a single unit and the price function is simply p(x) = x, so the price per unit equals the number of units already consumed. The set A = {3, 1, 3, 5} (writing only limits for each trade) is admissible, because for every limit = ℓ, the number of trade requests in A with limit at most ℓ is ≤ ℓ; indeed, an execution in sorted order 1, 3, 3, 5 satisfies all price limits. Now consider an incoming trade request tx = 4. The set A∪{tx} = {3, 1, 3, 5, 4} remains admissible, so the new trade request can be pre-approved, and the new execution order is 1, 3, 3, 4, 5. A different incoming trade request may be tx′ = 2. The set A ∪ {tx′ } = {3, 1, 3, 5, 2} is not admissible: for ℓ = 3, there are
4 trade requests whose limits are at most 3, hence p {tx ∈ A ∪ {2} | tx ≤ 3} = 4 > 3. Indeed, no sequenced execution of T ∪ {tx′ } may satisfy all price limits. Thus, tx′ should be denied pre-approval. Economic Incentives and Market Efficiency in FirstSwap. A trade in FirstSwap has a greater chance of executing when it is sent earlier and when

4

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

it offers a higher limit price, since trades are processed in the order received and more high-limit-price trades can be approved. Traders rationally offer prices strictly below their asset valuations, to ensure a positive gain from an executed trade, but high-valuation traders offer higher prices and also submit trades earlier. FirstSwap uses both trade time and limit price to ensure that assets go to traders who value them the most. The sorting method in FirstSwap lives between the extremes of two other MEV-resistant AMM mechanisms. A first-in-first-out fair ordering protocol as in [11] sets a trade’s execution price purely based on arrival time, while a batch auction as in [8, 9] approves trades only based on limit price and ignores arrival time entirely. FirstSwap, unlike the other two mechanisms, incentivizes traders to bid strictly less than their valuations. This lack of honest bidding in FirstSwap actually increases economic efficiency in a model with the realistic possibility of CEX-DEX arbitrage by reducing the volume of arbitrage trades. We illustrate the economic value of FirstSwap relative to other market designs in an economic model that combines auction theory with dynamic CEX-DEX arbitrage trading. Our model is the first, to our knowledge, that allows us to compare the social welfare of different AMM trading mechanisms where both the limit price and time of a trade are chosen strategically. This makes our model ideal for examining market design responses to the CEX-DEX arbitrage problem. By rewarding traders for trading fast instead of waiting for a better trading opportunity, FirstSwap yields higher utilitarian welfare and gains to AMM liquidity providers than an end-of-epoch batch auction. This is in contrast to [8], which argues in favor of batch auctions in a setting where there is no motive for traders to wait. While a fair ordering protocol based on [22, 11] provides similar improvements over a batch auction, FirstSwap provides higher welfare and gains to AMM liquidity providers than fair ordering after a large, sudden jump in the CEX price. Fast, Consensus-free Pre-approvals. Granting pre-approvals one by one requires solving the consensus problem repeatedly among the network of validators. FirstSwap avoids solving consensus for each trade request to speed up the pre-approval step. We develop in Section 3 a pre-approval protocol consisting of a single exchange between the trader and a quorum of validators that requires no coordination among validators. In a nutshell, consensus-free pre-approval works as follows. The trader sends a trade request to the network of validators. Each validator considers only the trade requests it has pre-approved locally and returns a signed response. A trade request that has pre-approvals from a quorum of q distinct validators is pre-approval-certified. In order to guarantee that all pre-approval-certified trade requests form an admissible set without relying on consensus, each validator preapproves only a certain fraction of the allowed capacity at each price. For n validators, f dishonest validators, and quorum size q = n−f , the pre-approval fracq−f . For the conventional BFT quorum sizes, n = 3f +1, q = 2f +1 tion is η := n−f f +1 1 4n+1 and η = 2f +1 ≈ 2 ; choosing larger quorum systems, e.g., q = ⌈ 5 ⌉ can yield 4 η ≈ 5 . Importantly, modified admissibility is checked locally by each validator

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

5

without any coordination among validators. Nevertheless, we show that all trade requests which are pre-approved individually by validators in this manner can be settled within their price limits. At the end of each epoch, validators run a single BFT consensus instance, each contributing a mini-block of its own pre-approved trades. The consensus output is formed from at least n−f mini-blocks and orders them into a final block, guaranteeing inclusion of every trade with a pre-approval certificate.

2

Fast Pre-Approvals as a Market Design Tool

To analyze the economic properties, we first describe the exchange mechanism, as if run by a single validator, and assume messages are delivered in the order they are sent. Theorem 1 shows that the same economic allocations would also occur in a range of distributed implementations. Section 3 presents one Byzantine fault-tolerant protocol under partial synchrony. A trade is a tuple tx = (amt, limit), where amt ∈ R+ is the amount of assets the trader wants to buy, and limit ∈ R+ is the maximum price per unit. As in a constant-function market maker (CFMM) [21], we consider a monotonically increasing price function p such that if x units of assets have already been bought from the exchange, the price per unit paid for buying the next infinitesimal quantity is p(x). The exchange operates in periods of time called epochs. In each epoch, traders send their trades to the exchange. The exchange approves the trade if adding this trade to the set of all trades approved so far keeps the set admissible. m

Definition 1 (Admissibility of trades). Let S = {txi = (amti , limiti )}i=1 be P a set of trades. S is admissible if for all i, p j:limitj ≤limiti amtj ≤ limiti . m

Let S = {txi = (amti , limiti )}i=1 be the set of approved P trades in theepoch. The validator executes each trade txi at the price p j:limitj ≤limiti amtj . This is equivalent to ordering the approved trades by their limit price, then executing them at the price determined by the pricing curve. Admissibility ensures that all trades can be charged prices consistent with the pricing function while satisfying their limit prices. Ordering by limit prices is without loss of generality due to Lemma 1. Thus, while we could choose any such ordering, ordering by limit prices naturally favors trades with higher valuations. m

Lemma 1. Let S = {txi = (amti , limiti )}i=1 be a set of trades. P There exists an m ordering (txi = (amti , limiti ))i=1 on S such that for all i, p j≤i amtj ≤ limiti if and only if S is admissible. 2.1

Economic Model

The model has a continuum of infinitesimal traders and time is measured continuously. At time t, trader i has value θi,t = pex,t +εi for holding the asset provided

6

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

by the AMM, where pex,t is a publicly observed “CEX price” and εi ∼ Fε is drawn i.i.d. across traders and is fixed over time. The distribution Fε has unit mass and is normalized to mean 0, so that pex,t reflects the valuation of the average trader. We write ε(r) = Fε−1 (1 − r) for the value of ε with a fraction r of the population with a higher valuation for r ∈ (0, 1). We make the simple choice that only the CEX price evolves over time, since only arbitrage trades are time-sensitive enough to meaningfully vary in value within a single epoch. We analyze the FirstSwap protocol first when the CEX price evolves gradually as a diffusion, Diffusion model:

pex,t = pex,0 + σex Wt ,

Tblk ∼ Exp(λblk ),

where Wt is Brownian motion and the exponentially distributed random time Tblk at which the epoch ends and transactions execute is independent of Wt . This Brownian-price/Poisson-epoch timing follows the approach of [27, 28] to tractably study loss-versus-rebalancing against an AMM. We adapt their approach in a model with rational traders with differing values who can strategically wait to trade. We also examine the case when the CEX price experiences a single large jump ∆pex and pex,t = pex,0 + ∆pex , ∀ t > 0. Economic incentives for traders differ markedly in these settings. With gradual information, traders will strategically wait to observe the evolution of pex,t before trading, while they will race each other for good price execution [8] after a jump. Each active trader may buy once. Passive LPs commit ex ante to providing AMM liquidity at a price p(x), where x is cumulative inventory sold. Measures of Economic Value We compare our trading mechanisms using two criteria: social welfare and AMM gains from trade. In the continuum model, social welfare at the end of the epoch, Tblk , is Z Social welfare: x0 pex,Tblk + qi (εi )εi dFε (εi ), (1) where x0 is total asset supply and qi (εi ) is the final quantity allocated to a trader with private value εi . For fixed x0 , the common-value component x0 pex,Tblk is identical across allocations. Thus welfare differences come from allocating more of the asset to traders with higher private values. We treat active traders and passive AMM liquidity providers as ex ante drawn from the same population; because passive liquidity must be treated identically by the mechanism, its allocation is uncorrelated with εi . Hence, increasing the covariance between activetrader holdings and εi increases overall social welfare. Our second metric is AMM gains relative to passively holding the asset: AMM gains:

(x0 − xLP ) (p̄ − pex,Tblk ) ,

(2)

where xLP is the inventory remaining with passive liquidity providers and p̄ is the average execution price received by the AMM across trades executed. Because AMM liquidity is passive, strategic traders can leave the AMM with less inventory precisely when pex,Tblk is high. This results in “loss-versus-rebalancing”

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

7

or LVR, where the passive AMM liquidity experiences losses after large price movements. An ideal protocol therefore induces traders with high private valuations εi to buy without inducing a large negative correlation between the volume x0 − xLP executed and price movements p̄ − pex,Tblk . The trader’s problem with gradual price evolution A trader chooses both when to submit a trade and the limit price attached to that trade. Let τ be the stopping time at which the trade occurs and let pbid,τ denote the limit price submitted at that time. If a mass xτ of traders has already been approved to trade, the marginal AMM price for our trader is p(xτ ). Thus a trader with private value ε has expected utility Utility:

sup E [1{τ < Tblk }1{pbid,τ ≥ p(xτ )} (pex,τ + ε − p(xτ ))] .

(3)

τ,pbid,τ

We assume in our gradual diffusion model that messages arrive at validators in exactly the same order as they are sent, so the bid will fill precisely if pbid,τ ≥ p(xτ ). Since the execution price is p(xτ ) and does not depend on the trader’s bid, whenever the trader wishes to trade it is without loss to submit the smallest limit price that executes, pbid,τ = p(xτ ). Thus, the economically substantive decision is when to trade. We look for a monotone equilibrium in which a trader with valuation ε(r) chooses a time to trade that is strictly increasing in r. Given the AMM pricing function p(.), a price p(r) is available to a trade that fills after a mass r of trades has previously occurred, so pbid,τ = p(r) in a monotone equilibrium. We show in Appendix A that each trader optimally follows a simple “memoryless” trading strategy: a trader of type r chooses to submit when the CEX price pex,t first reaches some threshold p∗ex (r) regardless of other history. √ ∗ blk Let γdiff ≡ 2λ σex . The probability that Brownian motion reaches pex (r) be∗ fore the epoch ends is e−γdiff [pex (r)−pex,0 ] (the Brownian first-passage probability formula). Hence the expected utility of a trader whose valuation ε(r) of the asset is less than that of a fraction r of the population (i.e. Pr{εi > ε(r)} = r) is ∗

U (r) = e−γdiff [pex (r)−pex,0 ] [p∗ex (r) + ε(r) − p(r)] .

(4)

′

(r) A particularly simple equilibrium obtains when κ ≡ − pε′ (r) > 0 is constant. In this case, we show in Appendix A that the optimal threshold is

p∗ex (r) = p(r) − ε(r) +

1 . γdiff (1 + κ)

(5)

Traders optimally wait until their contemporaneous valuation exceeds the AMM 1 . For our diffusion analysis, we assume that no price by a constant γdiff (1+κ) trader has a value of ε(r) so high that p(r) − ε(r) is below the starting CEX price pex,0 , which prevents an initial discrete spike in trading volume. Welfare and AMM gains under FirstSwap and a batch auction. Given the rational bidding strategy in Equation (5), type r trades when some value of pex,t exceeds p∗ex (r) before the epoch ends. This has probability (using

8

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

the Brownian first-passage probability)   1 exp{−γdiff [p(r) − ε(r) − pex,0 ]}. Prdiff (r) = exp − FS 1+κ

(6)

diff We show in Appendix A that expected welfare WFS and AMM gains Rdiff FS are respectively given by Z 1 diff ε(r) Prdiff (7) WFS = FS (r) dr, 0  Z 1 1 Rdiff = ε(r) − Prdiff (8) FS FS (r) dr. γ (1 + κ) diff 0

We compare these metrics to what would happen in a pure batch auction that executes at the end of the epoch. Here, all bidders will strategically wait until the epoch end and bid based on the final value of pex,Tblk , but (since every trader is infinitely small) they will choose a limit price equal to their true honest values. Rank r trades if pex,Tblk ≥ p(r) − ε(r). Since pex,Tblk − pex,0 is a Brownian motion at an exponential stopping time, it follows a Laplace distribution, so the probability of this trade is Prdiff batch (r) =

1 exp{−γdiff [p(r) − ε(r) − pex,0 ]}. 2

(9)

If rbatch is the rank of the trader choosing a limit price equal to the batch auction’s clearing price, the uniform batch price is pdiff batch = p(rbatch ) = pex,Tblk + ε(rbatch ). Because p′ (r) = −κε′ (r), p(r) + κε(r) is constant. Conditional on rank r executing, the terminal public price exceeds p(r) − ε(r) by an exponentially 1 distributed amount with mean γdiff , so E[pdiff batch − pex,Tblk | r executes] = ε(r) − 1 diff . Utilitarian welfare W and AM M gains Rdiff batch batch are given by γdiff (1+κ) diff diff WFS = 2e−1/(1+κ) Wbatch

−1/(1+κ) diff Rdiff Rbatch . FS = 2e

and

(10)

So long as the mean gains from trade are nonnegative for the AMM, FirstSwap dominates a batch auction for both welfare and AMM gains iff 1 < log 2 1+κ

⇐⇒

κ>

1 − 1 ≈ 0.4427. log 2

(11)

A large value of κ is the natural assumption in financial markets, since the common-value variation pex,t in an asset’s value should be much larger than variation in agents’ private valuations ε. We note that a FIFO/fair ordering protocol would yield exactly the same allocation as FS under gradual price diffusion, because the FS equilibrium is in fact providing price execution that is strictly better for earlier trades and no trades are rejected in equilibrium. Optimal Trading Strategies with a Jump. Next, we analyze our protocol when the price pex,t experiences a single large jump instead of gradually changing over time, taking on a single value pex,jump ≡ pex,0 + ∆pex .

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

9

In this setting, many traders will submit their orders at once, and we model the arrival times of these orders as uniformly random. We examine two competitor mechanisms to FirstSwap: the batch auction we examined previously and the incentive-compatible protocol of Chan, Wu, and Shi [11] that relies on fair ordering of transactions that we will call FIFO. In our model, each trader chooses its limit price not knowing the speed with which the trade will be received by validators. A rational trader maximizes its expected utility across possible realizations where the trade arrives early or late. Let pjump bid,FS (r) denote the equilibrium bid of a trader with private valuation ε(r) and Prfill (pjump bid,FS (r)) the probability at equilibrium that the trade is approved. The optimal bid pjump bid,FS (r) of type r maximizes over the choice of pbid [pex,jump + ε(r) − pbid ] Prfill (pbid ).

(12)

In a “regular” equilibrium where limit prices are strictly decreasing in the rank r and Prfill (pbid ) is smooth, the limit for any trader choosing Prfill (pbid ) ∈ (0, 1) satisfies a first-order condition pjump bid,FS (r) = pex,jump + ε(r) −

Prfill (pjump bid,FS (r)) Pr′fill (pjump bid,FS (r))

.

(13)

In the FirstSwap equilibrium, every trader’s limit price is strictly less than its true valuation of the asset. Increasing your limit raises the odds of the trade being executed, but a trader with a higher limit pays more if the trade executes. In a batch auction or FIFO, a small trader’s limit price has no impact on the price at which it can trade and is only used to determine if the trader would accept the price it is offered. Because traders should accept a trade precisely when they pay less than their true valuation, traders rationally choose a limit price equal to their true valuation in both mechanisms. Choosing a limit price equal to the trader’s true valuation pjump bid,batch (r) = pex,jump + ε(r) is a dominant strategy for both of these mechanisms. Welfare and Revenue Next, we compare welfare and AMM gains from trade across our three mechanisms: m ∈ {F IF O, F S, batch auction}. After a realized jump ∆pex , welfare and gains have the following simple expressions, where we denote εvirt (r) = ε(r) + rε′ (r) following Myerson’s [29] similar concept of a virtual value used to study revenue in auctions. Lemma 2 (Allocation representation after a jump). When all traders are rational, welfare and AMM gains from trade are respectively given by Z 1 Z 1 jump jump Wm = ε(r) Prjump (r) dr; R = εvirt (r) Prjump (r) dr. (14) m m m 0

0

The proof is in Appendix B. We use this lemma to compare welfare and revenue across our three mechanisms. Under conditions we state in Lemma 3, the equilibria induced by these mechanisms can be ordered with a “single crossing condition.” When this condition

10

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

holds, there is a cutoff r∗ where one mechanism has a higher probability of trade execution for r > r∗ and the other for r < r∗ . Lemma 3 (Single-crossing welfare and revenue decompositions). Consider two mechanisms m, n ∈ {FS, FIFO, batch}, with a difference in trade probaR1 jump bilities dmn (r) = Prjump (r)−Prjump (r) and volumes ∆V olmn = 0 (Prjump (r)− m n m Prjump (r)) dr. If the two mechanisms satisfy the single-crossing condition with n crossing point r∗ , welfare and AMM gains satisfy Z 1 jump jump Wm , (15) − Wnjump = [ε(r) − ε(r∗ )]dmn (r) dr + ε(r∗ )∆V olmn | {z } 0 | {z } volume effect selection effect

Rjump − Rjump = m n

Z 1

jump [(εvirt (r) − εvirt (r∗ )]dmn (r) dr + εvirt (r∗ )∆V olmn . | {z } 0 | {z } volume effect selection effect

The batch equilibrium always has the single crossing property relative to FIFO or FirstSwap. Sufficient conditions for FirstSwap to have the single-crossing property relative to FIFO are: 1. Fε has a smooth nondecreasing hazard rate ′ ′′′ (x) fε (e)/(1 − Fε (e)); and 2. p is C 3 with p′ , p′′ > 0, and 1 ≤ C(x) := p (x)p ≤2 p′′ (x)2 is a nondecreasing function. In the above decomposition, the “selection effect” term always yields higher welfare and AMM gains for a batch auction than for FirstSwap or FIFO, since a batch auction perfectly allocates the asset to agents with the highest ε values. Because the FirstSwap equilibrium features limit prices strictly below agents’ true valuations, it increases the probability that a given price will result in an executed trade. Under the conditions in the lemma, this results in a positive selection effect for FirstSwap relative to FIFO, since high-valuation agents will rationally choose limit prices at which they pay to increase their chances of trading. Lemma 4 (Jump size, volume, and welfare rankings). jump jump jump (i) Let ∆pmid = pex,jump −p(1/2). For any ∆pmid , V olFIFO ≥ max{V olbatch , V olFS }. jump jump ∗ Batch’s single crossing with either mechanism is at ε = ε(V olbatch ) = p(V olbatch )− pex,jump . Batch has higher welfare and AMM gains than FIFO for ∆pmid ≥ 0. (ii) Small jumps. Under additional regularity conditions in Appendix D, if 0 ≤ p ∆pmid < ( 2fε1(0) +p′ (1/2)/4) [p(1/2) − p(1/4)]/(24p′ (1/2)), and p(1/2)−p(1/4) ≥ 2Fε−1 (3/4) then batch has higher welfare and AMM gains than FirstSwap. (iii) Large jumps. If pex,jump ≥ p(1) + 12 p′ (1), then FirstSwap has higher welfare and AMM gains than FIFO. The proofs are in Appendices C and D. Equivalent allocations with many validators. Our economic analysis has assumed that orders submitted at the same time are received by a single validator in random order. We show in the appendix that the equilibrium of any of our protocols is equivalent in terms of the probability of trade, welfare

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

11

and AMM gains to one with many validators if every validator’s view is used in selecting which transactions to execute at the end of the epoch. For FS, our equivalence result applies to any version of our protocol satisfying three conditions: (i) accepted orders execute in ascending bid order at marginal AMM prices, without exceeding their submitted limits; (ii) against the equilibrium bids of other traders, bids arbitrarily close to p(0) from above have positive execution probability; and (iii) some finite bid guarantees execution. For FS, this result is akin to the revenue equivalence theorem of Myerson [29] for standard auctions, showing that within a certain family of mechanisms implementation details do not impact the economic allocation of resources. The proof is in Appendix E. Theorem 1 (Validator-count equivalence). For each of the mechanisms batch, FIFO, and FirstSwap, any regular monotone equilibrium in a protocol with multiple validators yields the same allocation, welfare, and AMM revenue as in the one-validator case. For batch and FIFO, the bidding strategies are also identical, but the optimal bidding strategies for FirstSwap can vary with the number of validators despite yielding the same allocation.

3

The FirstSwap Decentralized Protocol

In this section, we describe the decentralized FirstSwap protocol, a distributed implementation of the abstract FirstSwap design presented in Section 2 over a network of n validators. Due to space limitations, a glossary, algorithms in pseudocode and several (easy) proofs are deferred to Appendix F. The fault model. We assume at most f ≤ ⌊(n−1)/3⌋ validators are Byzantine; typically f = ⌊(n − 1)/3⌋, though other thresholds may be used. The numbers of all traders and Byzantine traders are unknown. Honest parties follow the protocol while Byzantine parties may deviate arbitrarily. We assume unforgeable digital signatures and work in the standard partially synchronous model [16]: there exists an unknown Global Stabilization Time (GST) and a known bound ∆net > 0 such that after GST any message sent at time t is received by max(t, GST) + ∆net . Safety holds at all times; liveness is guaranteed only after GST. Protocol structure. The protocol operates in fixed-duration periods called epochs; unless noted otherwise, we focus on a single epoch. Within each epoch the protocol proceeds in two stages: a consensus-free pre-approval stage, followed by a finalization stage that runs a single BFT consensus instance. For liveness, we assume the epoch is long enough for traders to submit trade requests and receive validator responses, followed by a period sufficient for one consensus instance. Scaled admissibility. The key technical challenge is ensuring that all independently pre-approved requests are jointly admissible, without any coordination among validators. To this end, each validator pre-approves only a scaled fraction η of the available capacity at each price level. For n validators, up to f dishonest, and quorum size q := n−f , define the approval fraction η :=

q−f . n−f

12

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

f +1 1 For conventional BFT parameters (n = 3f +1, q = 2f +1), η = 2f +1 ≈ 2 ; 4 larger quorums (e.g. q = ⌈ 4n+1 5 ⌉) yield η ≈ 5 . Recall that a set S of trade requests is admissible if they can all be satisfied simultaneously within their price limits (Definition 1). A scaled η-admissible criterion is defined as follows:

Definition 2 (η-admissible). The set S = {(amti , limiti )} is η-admissible if the scaled set {(amti /η, limiti )} is admissible. Since η < 1, this is a strictly stronger requirement than admissibility, and the slack it introduces is precisely what allows each validator to enforce admissibility locally and independently, without coordinating with other validators, while still guaranteeing that all trades with approval certificates are jointly admissible. Pre-Approval Protocol. During the pre-approval stage, traders submit trade requests tx = (amt, limit) to each validator and collect signed responses. A pre-approval σv (tx) from validator v is a signed message ⟨APPROVE, tx⟩. A collection of pre-approvals for tx from q distinct validators constitutes an approval certificate π(tx), where q is a Byzantine quorum threshold chosen so that any two quorums intersect in at least one honest validator (e.g. q = n−f in standard BFT settings). A trader that obtains π(tx) may forward it to validators. Each validator v maintains a local set Av of trade requests it has pre-approved and a set Πv of approval certificates it has seen. Both sets are empty at the start of an epoch. A validator stores its first response to each tx and replays it on retransmission. Validator v pre-approves tx if and only if Av ∪ {tx} is η-admissible (Definition 2). If so, v returns σv (tx) and updates Av := Av ∪ {(tx, σv (tx))}. Scaled admissibility is checked locally by each validator without any coordination between validators. All trade requests holding approval certificates, each admitted individually by validators in the above decentralized manner, can be satisfied within their price limits, without relying on consensus. Finalization Protocol. Throughout the epoch, traders and validators forward signed pre-approvals and approval certificates they observe to all validators. At the end of the epoch, each validator v forms and signs a mini-block Bv = (Av , Πv ). An honest validator includes in Av all pre-approvals it signed before the finalization cutoff. It also includes in Πv every valid certificate received before this cutoff. Anyone can verify the validator did not surpass its scaled pre-approval capacity. More formally: Definition 3 (Well-formed mini-block). A mini-block is well-formed if: (i) {tx : tx ∈ Av } is η-admissible and each pre-approval is correctly signed by v, and (ii) every π(tx) ∈ Πv is correctly formed. Each validator submits its signed mini-block as input to a single MVBA consensus instance. The MVBA protocol must satisfy an external validity condition such that a decided value B satisfies the predicate Valid below: Definition 4 (Valid). Valid(B) holds if (i) B contains well-formed mini-blocks from at least MB ≥ n−f distinct validators, and (ii) for every π(tx) appearing in B and every validator v whose mini-block Bv = (Av , ∗) is in B, if v’s signature appears in π(tx) then the same signed pre-approval for tx must appear in Av .

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

13

External validity provides three assurances: each Av must satisfy η-admissibility to be counted; a trade request pre-approved by n−f honest validators appears in at least MB −f included mini-blocks; and a validator that attempts to hide a signed pre-approval it issued may be excluded from B via the cross-check. In addition to external validity, the MVBA must uphold standard consensus properties: agreement (no two honest validators decide different values), and termination (every honest validator eventually decides after GST, provided all honest validators submit a valid input). Beyond these properties, the MVBA protocol is treated as a black box. Once the MVBA decides B, an ordered set of trades is induced deterministically: Pre-approved inclusion. Every trade request tx with signatures from at least ηMB distinct validators in B is included. AC inclusion. Every trade request tx for which a valid π(tx) appears in B is included, unless already covered above. Execution ordering. All included trade requests are ordered in non-decreasing order of limit, with ties broken deterministically by trade request identifier. Every included trade is guaranteed to be satisfiable within its price limit. Security Analysis. FirstSwap guarantees the following desired properties: f -Agreement. If at most f validators are Byzantine, all honest validators output the same final block at each epoch. (Proof deferred to Appendix F.) f -Price validity. Suppose at most f validators are Byzantine. Let T be the ordered set of trades in the final block. Then T is admissible (Definition 1). (f, η)-Pre-approval liveness. Let Sany be the set of trade requests sent to any honest validator during the epoch, and Sall ⊆ Sany the set sent to all honest validators. If Sany is η-admissible, then under synchrony every trade request in Sall obtains an approval certificate. f -Pre-approval inclusion. If either (i) a trade request tx has pre-approvals from q honest validators, or (ii) an π(tx) is received by f +1 honest validators, then tx must be included in the final block. Accountable inclusion. There exists a function J such that if tx obtains an approval certificate and is not included in the epoch’s final block, then there exists at least one validator v and evidence w with v ∈ J(w). Moreover, for all honest validators v and all w, v ∈ / J(w). (Proof deferred to Appendix F.) Validity. Let V ∗ be the set of creators of the mini-blocks in the decided proposal B, and let MB := |V ∗ |. External validity gives MB ≥ n − f and ensures that every Bv = (Av , Πv ) for v ∈ V ∗ is well-formed. Let S be the set of trade requests included by the two inclusion rules of the protocol. We use the notation limit(tx) and amt(tx) to denote the limit and amount of a trade request tx. Lemma 5 (Representation of included requests). Every trade request in S appears in Av for at least ηMB validators v ∈ V ∗ .

14

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Proof. If a request is included by the pre-approved inclusion rule, the claim follows from its threshold ηMB . Otherwise, its approval certificate has q signers, at least q + MB − n of whom belong to V ∗ . Dividing this lower bound by the number of selected validators gives n−q n−q q−f q + MB − n =1− ≥1− = ≥ η. MB MB n−f n−f The first inequality uses n − q ≥ 0 and MB ≥ n − f ; the last uses the assumed bound on η. Thus at least ηMB selected validators signed the request. The external-validity cross-check requires its signed approval to appear in Av for every such signer. ⊔ ⊓ Lemma 6 (Admissibility of included requests). The set S is admissible. P Proof. Fix a limit ℓ occurring in S and write X(ℓ) = tx∈S:limit(tx)≤ℓ amt(tx). P For each v ∈ V ∗ , similarly write Xv (ℓ) = tx∈Av :limit(tx)≤ℓ amt(tx). By Lemma 5, each request counted in X(ℓ) appears in at least ηMB selected approved sets. Counting its amount in each gives X ηMB X(ℓ) ≤ Xv (ℓ). (16) v∈V ∗

For every v with Xv (ℓ) > 0, let ℓv be its largest limit at most ℓ among the requests counted by Xv (ℓ). Since Av is η-admissible, p(Xv (ℓ)/η) ≤ ℓv ≤ ℓ. Let Y = maxv∈V ∗ Xv (ℓ)/η, treating an empty prefix as zero. Then p(Y ) ≤ ℓ. Dividing Equation (16) by ηMB > 0 gives X(ℓ) ≤

1 X 1 X Xv (ℓ) ≤ ηY = Y. ηMB ηMB ∗ ∗ v∈V

(17)

v∈V

Monotonicity of p gives p(X(ℓ)) ≤ p(Y ) ≤ ℓ. This holds for every limit in S, which is exactly admissibility. ⊓ ⊔ Corollary 1. The protocol satisfies f -Price validity. Liveness. The following proofs use the synchrony and epoch-duration assumptions from above. In particular, messages sent during the reservation period arrive before its cutoff, and MVBA termination produces a final block. Theorem 2. The protocol satisfies (f, η)-pre-approval liveness. Proof. Assume Sany is η-admissible. Immediately before an honest validator v processes tx ∈ Sany , the set Av ∪ {tx} is a subset of Sany . Removing requests only decreases every prefix amount, so this subset remains η-admissible. Validator v therefore signs an approval for tx. Every request in Sall is approved by every honest validator. There are at least n − f = q honest validators, and synchrony delivers their responses during the epoch. Thus the trader obtains an AC. ⊔ ⊓

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

15

Theorem 3. The protocol satisfies f -pre-approval inclusion. Proof. n ≥ 4f + 1, q = n − f , and η = q−2f n−f , First suppose tx has approvals from q honest validators. Exactly n − MB validators lie outside V ∗ , so at least q + MB − n ≥ ηMB of these honest approvers belong to V ∗ , by the bound in the proof of Lemma 5. Their complete approved sets contain their signed approvals for tx, meeting the pre-approved inclusion threshold. Now suppose an AC for tx is received before the cutoff by f + 1 honest validators. Since n − MB ≤ f , at least one of these validators belongs to V ∗ . The honest mini-block construction places the AC in that validator’s Πv , so the AC inclusion rule includes tx. ⊔ ⊓ q−f , Corollary 2. For any n, f, q, η such that n ≥ 3f + 1, q = n − f and η ≤ n−f the FirstSwap protocol with parameters n, f, q, η satisfies f -agreement, f -price validity, (f, η)-pre-approval liveness, f -pre-approval inclusion, and accountable inclusion.

Stronger inclusion guarantees for pre-approved trades. By parameterizf +1 1 ing the protocol with n = 4f + 1, q = n − f , and η = q−2f n−f = 3f +1 ≈ 3 , we can strengthen pre-approval inclusion: if a trade request tx is pre-approved by q validators (not necessarily all honest), then tx is guaranteed to be included in the final block. Moreover, with these parameters, accountable inclusion is also strengthened: at least f + 1 validators (not just one) is caught with evidence if a pre-approved trade is not included in the final block. The proofs of these strengthened properties are in Appendix F. All other security properties are preserved because these parameters satisfy the conditions of Corollary 2.

4

Maximal Fill Volume

The pre-approval liveness guarantee of the FirstSwap protocol in Section 3 requires the set of trade requests Sany sent to any honest validator to be ηadmissible. For example, let p(x) = x and suppose two traders submit requests tx1 = (amt1 = 1, limit1 = 5) and tx2 = (amt2 = 2, limit2 = 5) to all honest validators. For η = 1/2, the set Sany = {tx1 , tx2 } is not η-admissible, so the liveness guarantee does not apply. No trade is guaranteed to be included. Yet each request is individually η-admissible, as is the full amount of tx1 combined with half the amount of tx2 , suggesting that the protocol leaves some liveness unexploited. Moreover, a malicious trader can spam the system by submitting a large request to just one honest validator. This makes Sany non-η-admissible, leaving the pre-approval liveness property unable to guarantee inclusion of either the honest requests or the spammer’s request. In contrast, a standard blockchainbased DEX would include either the honest requests or the spammer’s request in a block: if the spammer displaced the honest requests, it would at least pay fees for its own. If no trade requests are pre-approved, no trade requests are guaranteed to be included in the block. We propose a simple extension that addresses these limitations by allowing partial fills in the final block. A trade is denoted by tx = (tx, fill), where tx =

16

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

(amt, limit) is the original trade request and fill ∈ [0, amt] is the amount filled. The trader specifies the maximum amount amt he is willing to buy, and the protocol determines the actual amount bought fill. Validators continue to use the η-admissibility condition to pre-approve trade requests, so pre-approval liveness remains as it is. The final block fully fills all pre-approved requests (preserving pre-approval inclusion) and partially fills residual requests while maintaining admissibility (improving livness). The residual fill algorithm solves a fractional knapsack problem variant, maximizing total filled volume. With partial fills, a set of trades is considered admissible based on their filled amounts fill rather than their requested amounts amt. η-admissibility continues to use the full amounts. Definition 5 (Admissible trades). Let T = {(txi = (amti , limiti ), filli )}m i=1 . The set T is admissible if 0 ≤ filli ≤ amti for every i and, for every i with P filli > 0, p j:limitj ≤limiti fillj ≤ limiti . We keep the pre-approval rule and the consensus validity conditions of Section 3. To make rejected requests available for residual inclusion, each honest validator v also records every valid request it receives before the finalization cutoff in a set Rv , and includes this set in its signed mini-block Bv = (Av , Πv , Rv ). Well-formedness checks the validity and trader authorization of these additional requests. Recording does not reserve capacity: the η-admissibility check still applies only to Av . Let B be the collection of mini-blocks decided by consensus, V ∗ their distinct creators, and MB = |V ∗ | ≥ n−f . Let U contain every distinct request appearing in B, including recorded but unapproved requests. Write G for the requests selected by either of the first two inclusion rules below. As in the main protocol, use q = n − f and η = (n − 2f )/(n − f ). The final ordered block is constructed as follows. Pre-approved inclusion. Every trade request tx = (amt, limit) with signatures from at least MB −f distinct validators in B is included with fill = amt. AC inclusion. Every trade request tx = (amt, limit) for which a valid π(tx) appears in B is included with fill = amt, unless already covered above. Residual inclusion. Then consider every remaining trade request in U in a fixed deterministic order, and assign it the maximum fill amount, up to its requested amount, that preserves admissibility. Initially set the fills of all other requests to zero. At each step keep all other fills fixed, and check admissibility against every prefix in U , including prefixes ending at requests that currently have zero fill. Equivalently, assign the largest x ∈ [0, amti ] for which replacing filli = 0 by x keeps the complete fill vector admissible. Execution ordering. Discard requests with zero fill and order all remaining requests in non-decreasing order of limit, breaking ties deterministically by request identifier.

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

Feasible fills and capacity. For a set of requests U , write   |U |   Y F(U ) = fill ∈ [0, amti ] : {(txi , filli )}txi ∈U is admissible .  

17

(18)

i=1

Define R(U ) =

max

X

fill∈F (U )

filli ,

R(∅) = 0.

i

Security analysis. The strengthened liveness property achieved by this modified protocol is stated in Definition 6 and proved in Theorem 4. It guarantees that the total filled volume of the final block is at least as large as the maximum feasible fill of all valid trade requests sent to all honest validators before the finalization cutoff. This holds even if the set of requests sent to honest validators is not η-admissible. In particular, even if a malicious trader spams some honest validators, either the honest trade requests or an equivalent volume of the spammer’s trade requests will be filled in the final block. This restores a liveness guarantee similar to that of a standard blockchain-based DEX, in which the spammer would pay fees for the spammer’s trade requests. Price validity is preserved by construction: By Lemma 6, G is admissible when fill = amt for every request. Assigning zero fills to the remaining requests changes no filled amount and preserves admissibility. Each residual step preserves admissibility by construction and leaves pre-approved fills unchanged. Hence the complete final fill vector is admissible. All other security properties of the original protocol remain unchanged. Definition 6 (f -Maximal volume filled). Suppose that the network is synchronous and at most f validators are Byzantine during an epoch. Let S be the set of valid trade requests sent to all honest validators in time to arrive before the finalization cutoff. Let T denote the trades in the final block of the epoch. The protocol satisfies f -Maximal volume filled if X filli ≥ R(S). (19) (txi ,filli )∈T

Lemma 7 (Maximal fills maximize volume). Starting from the full fills of G, the protocol’s residual rule produces a feasible fill of U with total volume R(U ). Proof. By Lemma 6, the initial full fills of G are admissible; zero fills for the remaining requests and each subsequent residual step preserve admissibility. Moreover, no final fill can be increased while the other fills are fixed. Pre-approved requests are already full. For a residual request, any increase that were admissible at the end would also have been admissible when it was processed: all other fills were then no larger, and decreasing fills preserves admissibility. Such an increase would contradict the greedy rule.

18

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

c has larger Suppose, for a contradiction, that another admissible fill vector fill P c total volume. Write D = j (fillj −fillj ) > 0, and choose a request txi with largest ci > filli . For every ℓ ≥ limiti , requests with limit limit among those for which fill cj ≤ fillj , so above ℓ have fill X

cj − fillj ) = D − (fill

j:limitj ≤ℓ

X

cj − fillj ) ≥ D. (fill

(20)

j:limitj >ℓ

ci − filli } > 0. The increased fill is at most fill ci ≤ Increase filli by ε = min{D, fill amti . Prefixes below limiti are unchanged, and (20) shows that every prefix at c or above limiti has total fill at most the corresponding prefix of fill. For each such limit ℓ, the alternative prefix contains a positive fill because ci > 0. Let ℓ′ be the largest limit of any positive-filled request in that prefix. fill c gives Admissibility of fill     X X cj  = p  cj  ≤ ℓ′ ≤ ℓ. p fill fill j:limitj ≤ℓ

j:limitj ≤ℓ′

By monotonicity of p, the increased fill vector therefore remains admissible, including at limiti . This contradicts the impossibility of increasing any final fill. No admissible vector has larger total volume, so the protocol attains R(U ). ⊔ ⊓ Theorem 4 (f -Maximal volume filled). Under the synchrony and epochduration assumptions of Section 3, the extended protocol satisfies f -Maximal volume filled as defined in Definition 6. Proof. Let S be the set in the property definition. Every honest validator records each tx ∈ S and includes it in its mini-block. Since V ∗ contains at least MB −f ≥ n − 2f > 0 honest validators, every request in S appears in U . Thus S ⊆ U . Any admissible fill of S extends to an admissible fill of U by assigning zero to U \ S. The added requests require no execution, and the filled amount in the prefix of every positive-filled request is unchanged. Hence its inequality in Definition 5 remains satisfied. It follows that R(U ) ≥ R(S). By Lemma 7, the protocol fills total volume R(U ). Discarding zero-filled requests changes no volume, so its final block T satisfies X filli = R(U ) ≥ R(S). (txi ,filli )∈T

⊔ ⊓

5

Combining Buys and Sells

We extend our main protocol to allow for simultaneous buys and sells. Each Validator receives trade requests with both buys and sells and must decide when

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

19

it is able to pre-approve a request. We add side ∈ {buy, sell} to the existing trade request format: tx = (side, amt, limit). A naive way to handle both buys and sells would be to run two independent instances of the the protocol from Section 3, one for buys and one for sells. However, this approach approves would forego the opportunity of approving more buys when there are matching sells and conversely. The challenge lies in determining when a validator can safely pre-approve additional buys based on the sell requests it has seen (and vice versa) without violating any limit prices. Towards this, we first propose an extended definition of admissibility for the bilateral setting with both buys and sells (Definition 7). Unlike the unilateral setting (Definition 1), bilateral admissibility involves two sets of trade requests: a set G of pre-approved trade requests that must be executed fully and a set U ⊇ G of trade requests that can optionally be executed to fill enough liquidity to support the trades in G. We show a pre-approval rule and block finalization protocol (similar to those in Section 3) that ensures bilateral admissibility when G is the set of pre-approved trade requests and U is the set of all other trade requests reported in any finalized block that may or may not execute. Finally, we show in lemma 9 that when the set of trades in a block is bilaterally admissible, all pre-approved trades in G (and optionally some others in U ) can be executed while satisfying all limit prices. We extend our AMM curve Rp(x) to allow for either positive or negative net x purchases x and write P (x) = 0 p(u) du. Let c(ℓ) be the inverse of p(x), with c(p(0)) = 0 and both c(.), p(.) continuous. Write [z]+ = max{z, 0}. At limit ℓ, the AMM offers supply [c(ℓ)]+ and demand [−c(ℓ)]+ . Definition 7 (Bilateral admissibility). Let G ⊆ U be a collection of trade requests. G is said to be bilaterally admissible in U if for every ℓ, X txi ∈G buys limiti ≤ℓ

X txi ∈G sells limiti ≥ℓ

X

amti ≤ [c(ℓ)]+ +

amtj ,

(21)

txj ∈U sells limitj ≤ℓ

amti ≤ [−c(ℓ)]+ +

X

amtj .

(22)

txj ∈U buys limitj ≥ℓ

In our extended protocol, similar to Section 4, validators keep track of not only trade requests they pre-approved but also all trade requests that they have seen. An honest validator pre-approves only trade requests where it has sufficient capacity. As new trade requests are received that may increase capacity, it promotes old seen trade requests to pre-approved in the order received. When forming a mini-block, validators report separate lists of seen and pre-approved trade requests that can be used to build a final block. Similar to Section 4, trades included in the final block will have a parameter filli ∈ [0, amti ] denoting partial filling of trade requests. In addition, each trade will also be assigned pricei denoting the execution price of the trade. When we considered only buys, we had implcitly considered pricei to be the price determined by the AMM curve

20

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

after trades has been ordered by their limit prices. Our goal is to ensure that pricei ≤ limiti for all executed buys and pricei ≥ limiti for all executed sells. Modified Pre-Approval Protocol. Alongside the original pre-approval and certificate sets, validator v records trade requests Rv that it has seen. Before the finalization cutoff, it records and relays every valid trade request, including trade requests that fail the approval test. For each validator v, given the set of trade requests it has seen, define X

Sbv (ℓ) =

txi ∈Rv sells limiti ≤ℓ

amti ,

bv (ℓ) = B

X

amti .

txi ∈Rv buys limiti ≥ℓ

Our validator’s new rule for adding a trade request to its pre-approved set Av is that it will pre-approve if doing so does not violate X
amti ≤ η [c(ℓ)]+ + Sbv (ℓ) for every ℓ (23) txi ∈Av buys limiti ≤ℓ

X

bv (ℓ) for every ℓ. amti ≤ η [−c(ℓ)]+ + B

(24)

txi ∈Av sells limiti ≥ℓ

Note that this is the analogue of η-admissibility (Definition 2) for bilateral admissibility (Definition 7). Modified Finalization Protocol. In our modified finalization protocol, each mini-block Bv = (Av , Πv , Rv ) additionally contains the recorded requests Rv . Well-formedness verifies these requests and replaces the original η-admissibility by checking Equations (23) and (24). The quorum requirement and approvalcertificate cross-check for block validity are as before. The inclusion and execution ordering steps are described below. First, if U is the set of all trade requests appearing in the block (including recorded and approved), note that all pre-approved transactions G ⊆ U satisfy joint bilateral feasibility. Lemma 8 (Admissibility of pre-approved requests). Under (23)–(24) with η = (q − f )/q, the set G of trade requests with at least MB − f approvals among selected mini-blocks is bilaterally admissible. Proof. For each limit ℓ, let X(ℓ) be the total quantity of buys in G with limits at most ℓ, and let Xv (ℓ) be the corresponding quantity in Av . Let SU (ℓ) be the total quantity of sells in U with limits at most ℓ. Every trade request recorded as seen in a selected mini-block belongs to U , so Sbv (ℓ) ≤ SU (ℓ) for every v ∈ V ∗ . Counting approvals and summing the local buy budgets gives X(ℓ) ≤

X
ηMB 1 Xv (ℓ) ≤ [c(ℓ)]+ + SU (ℓ) ≤ [c(ℓ)]+ + SU (ℓ). MB − f MB − f ∗ v∈V

This demonstrates Equation (21) for buys and an analogous argument demonstrates Equation (22) for sells. ⊔ ⊓

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

21

Next, we show how to compute the amounts filled for each trade request filli , given a block with trades U and pre-approved trades G ⊆ U that are bilaterally admissible. Lemma 9 shows that all trades in G are completely filled, every filled trade can be assigned a price that satisfies its limit, and the AMM receives the correct revenue. This is because the bilateral admissibility ensures that the trades in U supply enough demand or supply to augment the AMM’s own demand and supply to meet the supply or demand of the pre-approved trades in G. It also preserves monotonicity: a trade with a higher limit price will not be executed at a lower price than a trade with a lower limit price (monotonicity was implicit in Section 3 by ordering trades by limit prices). Our protocol works in two steps. First, we compute the quantity of buys minus the quantity of sells in the set of pre-approved trades G. We then compute a price ℓ∗ where executing all buys in U \ G with limit prices below ℓ∗ and all sells above ℓ∗ (with potential partial fills at ℓ∗ ) allows all trades in G to execute. This results in a total set U ∗ of trades that actually execute. If U ∗ has more buys than sells so that the AMM is a net seller, sells in U ∗ are effectively added to the AMM’s liquidity supply. Buys are executed in order of limit price, where each buy is greedily given the best possible price provided by the remaining sell liquidity as in our main protocol. Sells execute at their limit price. If U ∗ had more sells, we reverse this procedure so buys fill at their limit price and sells are given price improvement. This pricing preserves the property in our main protocol that a trade’s execution price is an increasing function of its limit price. Because requesting an attractive limit price lowers a trade request’s chance of approval, this allows traders with a particularly high desire to trade to choose an unattractive limit price to increase their odds of acceptance. In our economic analysis, this allowed for a “selection effect” where traders who benefit the most from trading have the highest chance of their trades executing. Input: Set of seen trade requests U and set of pre-approved transactions G ⊆ U , with G bilaterally admissible in U . Output: Fill vector fill = (filli )txi ∈U Pre-approval inclusion. Set filli = amti for every request in G and initialize all other fills to zero. Define the guaranteed net demand X

g=

amti −

txi ∈G buys

X

amti

txi ∈G sells

and the right-continuous augmented liquidity curve e c(ℓ) = c(ℓ) +

X txi ∈U \G sells limiti ≤ℓ

amti −

X

amti .

(25)

txi ∈U \G buys limiti >ℓ

Limit-matched-inclusion. Choose the cutoff ℓ∗ = inf{ℓ : e c(ℓ) ≥ g}. Among requests in U \ G, fully fill buys with limiti > ℓ∗ and sells with limiti < ℓ∗ .

22

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Leave buys with limiti < ℓ∗ and sells with limiti > ℓ∗ unfilled. Define the remaining imbalance X ∆ℓ∗ = g − e c(ℓ∗ ) + amti . txi ∈U \G sells limiti =ℓ∗

If ∆ℓ∗ > 0, fill this quantity of sells with limit ℓ∗ ; if ∆ℓ∗ < 0, fill −∆ℓ∗ of buys with limit ℓ∗ . Process these requests in a fixed order by identifier, assigning each at most amti until the required quantity is reached. Leave all other requests at the cutoff unfilled. Output fill = (filli )txi ∈U . Lemma 9 (Limit-satisfying prices for bilateral admissibility). If G ⊆ U is bilaterally admissible and fill is as computed above, then there exists price such that: 1. all pre-approved trades are completely filled: for all txi ∈ G, filli = amti ; 2. all limits are respected: for all txi ∈ U such that filli > 0, sidei = buy =⇒ pricei ≤ limiti and sidei = sell =⇒ pricei ≥ limit Pi ; P 3. the AMM’s revenue is exactly P (x) where x := txi ∈U buys filli − txi ∈U sells filli is the net purchase quantity; 4. prices are monotonic: for all txi , txj ∈ U such that filli > 0 and sidei = sidej , limiti ≤ limitj =⇒ pricei ≤ pricej . Proof. We first justify that the cutoff ℓ∗ exists and is finite. For this argument, let a = min({p(0)} ∪ {limiti : txi ∈ U }) and b = max({p(0)} ∪ {limiti : txi ∈ U }). Since c(a) ≤ 0 and every request has limit at least a, Equation (22) at a gives X e c(a− ) = c(a) − amti ≤ g. txi ∈U \G buys

Similarly, c(b) ≥ 0 and every request has limit at most b, so Equation (21) at b gives X g ≤ c(b) + amti = e c(b). txi ∈U \G sells

For every ℓ < a, strict monotonicity of c = p−1 gives X e c(ℓ) = c(ℓ) − amti < e c(a− ) ≤ g. txi ∈U \G buys

Thus the set defining the cutoff is nonempty and has no element below a, so its infimum lies in [a, b]. Second, we show that there are enough trades with limit exactly ℓ∗ to fill the quantity ±∆ℓ∗ . The curve e c is nondecreasing and right-continuous, with only upward jumps. Consequently, e c(ℓ∗ −) ≤ g ≤ e c(ℓ∗ ).

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

23

Here the left-hand value includes buys at the cutoff and excludes sells at the cutoff. Consequently, X X − amti ≤ ∆ℓ∗ ≤ amti . txi ∈U \G buys limiti =ℓ∗

txi ∈U \G sells limiti =ℓ∗

There is therefore enough volume at the cutoff to fill ±∆ℓ∗ while respecting every request’s quantity bound. Price construction. Let U ∗ be the set of executed requests. Their net asset purchase is X X filli = c(ℓ∗ ). filli − x= txi ∈U ∗ sells

txi ∈U ∗ buys

Define the AMM’s executed volume with marginal price at most ℓ by Z x 1{p(v)≤ℓ} dv . FAMM (ℓ) = 0

We now define two distribution functions that represent the set of buy and sell limit prices that that will execute as actual trades, including the liquidity supplied by the AMM. X FU ∗ ,buy (ℓ) = filli + 1{x<0} FAMM (ℓ), (26) txi ∈U ∗ buys limiti ≤ℓ

FU ∗ ,sell (ℓ) =

X

filli + 1{x>0} FAMM (ℓ),

(27)

txi ∈U ∗ sells limiti ≤ℓ

The total buy and sell quantities are equal, i.e., FU ∗ ,buy (∞) = FU ∗ ,sell (∞) = M , and all liquidity FAMM (ℓ) is only added on one side to meet the quantity imbalance in U ∗ between buys and sells. −1 −1 Define the inverse functions FU−1 (u) = ∗ ,buy (u) with FU ∗ ,sell (u) where F inf{ℓ : F (ℓ) ≥ u}. If x ≥ 0, assign pricei = limiti for each sell in U ∗ . Sort all buys in U ∗ by limit prices, treating a tied limit price as a single larger buy. For the Pbuys with i Pi i−1 i-th buy, let Ii := j=1 fillj , j=1 fillj be the interval it occupies in the sorted order. Set the i-th buy’s price as Z 1 F −1 (u) du. pricei = ∗ filli Ii U ,sell If x < 0, assign pricei = limiti for each buy in U ∗ . Sort all sells in U ∗ by limit prices, tied P also merging i limit prices into a single sell. For the i-th sell, let Pi i−1 Ii := fill , fill j j be the interval it occupies in the sorted order. Set j=1 j=1 the i-th sell’s price as Z 1 pricei = F −1 (u) du. ∗ filli Ii U ,buy

24

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

A buyer pays filli pricei and a seller receives filli pricei . −1 Limit validity. If we can show that FU−1 ∗ ,sell (u) ≤ FU ∗ ,buy (u), then executing at the above price satisfies limits. This is because the i-th buy’s price is exactly limiti when x < 0 and when x ≥ 0, Z Z 1 1 FU−1 (u) du ≤ F −1 (u) du = limiti , pricei = ∗ ,sell ∗ filli Ii filli Ii U ,buy Similarly, when x < 0, for the i-th sell, Z Z 1 1 −1 limiti = F ∗ (u) du ≤ F −1 (u) du = pricei . ∗ filli Ii U ,sell filli Ii U ,buy We prove the equivalent statement that FU ∗ ,buy (ℓ) ≤ FU ∗ ,sell (ℓ) pointwise. For ℓ < ℓ∗ , executed buys with limits at most ℓ are exactly the corresponding buys in G, and all available sells with limits at most ℓ in U fill completely. Since c(ℓ) ≤ x = c(ℓ∗ ), the definition of FAMM gives 1{x<0} FAMM (ℓ) = 0,

1{x>0} FAMM (ℓ) = [c(ℓ)]+ .

Thus inequality (21) gives FU ∗ ,buy (ℓ) ≤ FU ∗ ,sell (ℓ). For ℓ ≥ ℓ∗ , we instead have c(ℓ) ≥ x, so
1{x>0} |x| − FAMM (ℓ) = 0,
1{x<0} |x| − FAMM (ℓ) = [−c(ℓ)]+ . Equal total mass and the cutoff rule for filling trades on each side of ℓ∗ therefore give X X FU ∗ ,buy (ℓ) − FU ∗ ,sell (ℓ) = amtj − amti txj ∈G sells limitj >ℓ

txi ∈U buys limiti >ℓ

− 1{x<0} |x| − FAMM (ℓ) ≤ 0, where the inequality follows from (22) applied just above ℓ. Thus FU ∗ ,buy ≤ FU ∗ ,sell everywhere. AMM payment and price monotonicity. If x ≥ 0, total buyer payments are Z M X FU−1 filli limiti + P (x), ∗ ,sell (u) du = 0

txi ∈U ∗ sells

since the sell distribution includes the AMM’s supply at marginal prices p(v) for v ∈ [0, x]. After paying trader sellers at their limits, the AMM retains P (x). If x < 0, total seller receipts are Z M X FU−1 filli limiti − P (x), ∗ ,buy (u) du = 0

txi ∈U ∗ buys

R0 since the AMM’s buy orders have total value x p(v) dv = −P (x). Subtracting these receipts from trader buyers’ payments again gives a net AMM receipt

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

25

−1 of P (x). Finally, both FU−1 ∗ ,buy and FU ∗ ,sell are nondecreasing. Requests on one side execute at their limits; on the other side, execution prices are averages of the corresponding inverse function over consecutive intervals Ii . An earlier interval’s average cannot exceed a later interval’s average, so execution prices are nondecreasing on each side in the prescribed order of limits and identifiers. ⊔ ⊓

Security properties. Price validity and pre-approval inclusion are implied by Lemma 9. Pre-approval liveness holds with η-admissibility replaced by Equations (23) and (24). Agreement and accountable inclusion remain unchanged. LP deposits and withdrawals at block end. A standard extension to our protocol would allow passive LPs to deposit and withdraw liquidity in the AMM. We impose that all deposits and withdrawals are handled at the end of a block, after regular trade requests have been executed. Validators pre-approve all valid LP deposit and withdrawal requests, and such a pre-approval in even a single selected mini-block ensures execution of a valid request. After all trades settle, process every distinct valid LP request. Let R = (RA , RC ) be the post-trade reserves in the AMM and Λ > 0 the outstanding LP shares before processing these requests. All conversions use this same snapshot: – A withdrawal burns its locked w shares and receives (w/Λ)R. – A deposit with locked asset caps (dA , dC ) mints m = Λ min{dA /RA , dC /RC }, contributes (m/Λ)R, and receives its unused escrow back. Any deposit that does not have sufficient inventory in both assets does not execute, and any withdrawal without enough shares does not execute.

6

Related Work

AMM arbitrage and loss-versus-rebalancing. Constant-function market makers (CFMMs) enable decentralized asset exchange through deterministic pricing curves [21, 1, 2]. Because AMM prices change only when trades occur, movements in external market prices create arbitrage opportunities against stale AMM prices, resulting in loss-versus-rebalancing (LVR) [28]. Prior work studies the effects of fees and arbitrage on these losses and on liquidity provision [27, 10], while recent empirical work highlights the role of large price movements in CEX– DEX arbitrage [25]. FirstSwap keeps the underlying CFMM pricing rule but changes when traders receive an execution commitment. Traders can obtain a pre-approval while the block is still being formed rather than waiting until its end. Our economic analysis studies how this earlier commitment reduces the incentive to wait for a large CEX–DEX price discrepancy before trading. MEV mitigation and transaction ordering. A growing literature studies how execution and ordering rules can reduce maximal extractable value (MEV), including front-running, sandwich attacks, and arbitrage [14, 33]. One approach

26

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

is to reduce the importance of ordering. Batch execution [9] executes trades together at a uniform end-of-batch price, while SPEEDEX [31] and Groundhog [32] avoid imposing an intra-block order through commutative state updates; these systems still rely on consensus to determine end-of-batch outcomes. A complementary line seeks fairer sequencing: order fairness [22] and enforceable sequencing rules [17]. For AMMs specifically, CLVR [26] reduces intra-block price movements, while Chan, Wu, and Shi [11] design an incentive-compatible mechanism requiring fair ordering. Diamandis and Angeris [15] show, however, that fair ordering need not yield economically efficient allocations. Moreover, Condorcet cycles limit fair ordering. Practical systems such as MEV Blocker [12] and SUAVE [18] instead use order-flow auctions and alternative block-building mechanisms to reduce or redistribute ordering-based MEV. FirstSwap deterministically executes pre-approved trades, without the complex task of fairly ordering transactions by arrival time. Consensus-free fast paths and pre-confirmations. Several systems bypass full consensus for latency-sensitive operations. Prior work shows that payments and single-owner transactions can be confirmed by validator quorums without consensus [19, 3, 24, 4, 6, 34], while hybrid protocols optimistically avoid consensus and fall back to it upon conflicts [20, 13]. Recent work shows that some shared-object operations can also avoid consensus. Stingray [35] uses local approvals against scaled capacity bounds, CryptoConcurrency [37] avoids consensus when concurrent transfers are jointly feasible, and Zef [5] explores consensus-free decentralized assets and swaps. FirstSwap applies similar ideas to AMMs, where trades compete for liquidity and independently approved trades may not all be feasible. We use limit prices together with a scaled admissibility rule to pre-approve trades while maintaining admissibility. Recent work on pre-confirmations [7] makes commitments before block confirmation for censorship resistance. FirstSwap obtains similar guarantees directly from a quorum of validators and provides a different economic rationale for their usefulness.

Acknowledgments SS was supported in part by the AFOSR Award FA9550-24-1-0156, and research grants from the Bakar Fund, Peder Sather Funds, the Stellar Development Foundation, Supra Inc., Category Labs, Input Output Global, and Byzantine Research Inc.

References 1. Adams, H.: Uniswap whitepaper (2018), https://hackmd.io/@HaydenAdams/ HJ9jLsfTz, whitepaper 2. Angeris, G., Chitra, T.: Improved price oracles: Constant function market makers. In: Proceedings of the 2nd ACM Conference on Advances in Financial Technologies (AFT). pp. 80–91. ACM (2020). https://doi.org/10.1145/3419614.3423251

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

27

3. Auvolat, A., Frey, D., Raynal, M., Taïani, F.: Money transfer made simple: a specification, a generic algorithm, and its proof. Bull. EATCS 132 (2020) 4. Baudet, M., Danezis, G., Sonnino, A.: FastPay: High-performance byzantine fault tolerant settlement. In: Proceedings of the 2nd ACM Conference on Advances in Financial Technologies (AFT). pp. 163–177. ACM (2020). https://doi.org/10. 1145/3419614.3423249 5. Baudet, M., Sonnino, A., Król, M.: Low-latency, scalable, DeFi with Zef. arXiv preprint arXiv:2201.05073 (2022). https://doi.org/10.48550/arXiv.2201.05073 6. Blackshear, S., Chursin, A., Danezis, G., Kichidis, A., Kokoris-Kogias, L., Li, X., Logan, M., Menon, A., Nowacki, T., Sonnino, A., Williams, B., Zhang, L.: Sui lutris: A blockchain combining broadcast and consensus. In: Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security. pp. 2606–2620. ACM (2024). https://doi.org/10.1145/3658644.3670286 7. Botha, Q., Kyriacou, D., McMenamin, C., Oshitani, L., Stouka, A.P.: SoK: Preconfirmations. In: 2026 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). pp. 1–19. IEEE (2026). https://doi.org/10.1109/ICBC67748. 2026.11575526 8. Budish, E., Cramton, P., Shim, J.: The high-frequency trading arms race: Frequent batch auctions as a market design response. The Quarterly Journal of Economics 130(4), 1547–1621 (2015). https://doi.org/10.1093/qje/qjv027 9. Canidio, A., Fritsch, R.: Batching trades on automated market makers. In: 5th Conference on Advances in Financial Technologies (AFT 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 282, pp. 24:1–24:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023). https://doi.org/10.4230/LIPIcs.AFT. 2023.24 10. Capponi, A., Jia, R.: Liquidity provision on blockchain-based decentralized exchanges. The Review of Financial Studies 38(10), 3040–3085 (2025). https: //doi.org/10.1093/rfs/hhaf046 11. Chan, T.H.H., Wu, K., Shi, E.: Mechanism design for automated market makers. In: 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), vol. 354, pp. 7:1–7:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025). https://doi.org/10.4230/ LIPIcs.AFT.2025.7 12. CoW Protocol, Beaver Build, Agnostic Relay: MEV blocker: Order-flow auction for user protection. Technical specification (2023), https://mevblocker.io 13. Cowling, J.A., Myers, D.S., Liskov, B., Rodrigues, R., Shrira, L.: HQ replication: A hybrid quorum protocol for byzantine fault tolerance. In: OSDI. pp. 177–190. USENIX Association (2006) 14. Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., Juels, A.: Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In: 2020 IEEE Symposium on Security and Privacy (SP). pp. 910–927. IEEE (2020). https://doi.org/10.1109/ SP40000.2020.00040 15. Diamandis, T., Angeris, G.: A note on the welfare gap in fair ordering (2023), https://arxiv.org/abs/2303.15239 16. Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. Journal of the ACM (JACM) 35(2), 288–323 (1988) 17. Ferreira, M.V.X., Parkes, D.C.: Credible decentralized exchange design via verifiable sequencing rules. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC). pp. 723–736. ACM (2023). https://doi.org/10.

28

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

1145/3564246.3585233 18. Flashbots: SUAVE: Single unifying auction for value expression. Blog post and technical specification (2023), https://writings.flashbots.net/ the-future-of-mev-is-suave 19. Guerraoui, R., Kuznetsov, P., Monti, M., Pavlovic, M., Seredinschi, D.: The consensus number of a cryptocurrency. In: PODC. pp. 307–316. ACM (2019) 20. Hendricks, J., Sinnamohideen, S., Ganger, G.R., Reiter, M.K.: Zzyzx: Scalable fault tolerance through byzantine locking. In: Proceedings of the 2010 IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2010, Chicago, IL, USA, June 28 - July 1 2010. pp. 363–372. IEEE Computer Society (2010). https://doi.org/10.1109/DSN.2010.5544297, https://doi.org/10. 1109/DSN.2010.5544297 21. Hertzog, E., Benartzi, G., Benartzi, G.: Bancor protocol: Continuous liquidity and asynchronous price discovery for tokens through their smart contracts (Apr 2017), https://resources.bancor.network/pages/BancorProtocolWhitepaper. pdf, whitepaper, Draft Version 0.77 22. Kelkar, M., Zhang, F., Goldfeder, S., Juels, A.: Order-fairness for byzantine consensus. In: Advances in Cryptology – CRYPTO 2020. Lecture Notes in Computer Science, vol. 12172, pp. 451–480. Springer (2020). https://doi.org/10.1007/ 978-3-030-56877-1_16, https://doi.org/10.1007/978-3-030-56877-1_16 23. Kemeny, J.G.: Mathematics without numbers. Daedalus 88(4), 577–591 (1959), https://www.jstor.org/stable/20026529 24. Kuznetsov, P., Pignolet, Y., Ponomarev, P., Tonkikh, A.: Permissionless and asynchronous asset transfer. Distributed Comput. 36(3), 349–371 (2023) 25. Ladóczki, B., Rásonyi, M., Tapolcai, J.: Where does MEV really come from? revisiting CEX–DEX arbitrage on ethereum (2026), https://arxiv.org/abs/2604. 15973 26. McLaughlin, R., Chemaya, N., Liu, D., Malkhi, D.: CLVR ordering of transactions on AMMs (2024), https://arxiv.org/abs/2408.02634 27. Milionis, J., Moallemi, C.C., Roughgarden, T.: Automated market making and arbitrage profits in the presence of fees. In: Financial Cryptography and Data Security. pp. 159–171. Springer (2024). https://doi.org/10.1007/ 978-3-031-78676-1_9, https://arxiv.org/abs/2305.14604 28. Milionis, J., Moallemi, C.C., Roughgarden, T., Zhang, A.L.: Automated market making and loss-versus-rebalancing (2022), https://arxiv.org/abs/2208.06046 29. Myerson, R.B.: Optimal auction design. Mathematics of Operations Research 6(1), 58–73 (1981). https://doi.org/10.1287/moor.6.1.58 30. Ramseyer, G., Goel, A.: Fair ordering in replicated systems via streaming social choice. In: Mavronicolas, M., Qi, Q., Schoenebeck, G. (eds.) Web and Internet Economics (WINE 2024). Lecture Notes in Computer Science, vol. 15534, pp. 438– 456. Springer (2026). https://doi.org/10.1007/978-3-032-08560-3_25, https: //doi.org/10.1007/978-3-032-08560-3_25 31. Ramseyer, G., Goel, A., Mazières, D.: Speedex: A scalable, parallelizable, and economically efficient decentralized exchange. In: 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). pp. 849–875 (2023) 32. Ramseyer, G., Mazières, D.: Groundhog: Linearly-scalable smart contracting via commutative transaction semantics (2024) 33. Roughgarden, T.: Transaction fee mechanism design. In: Proceedings of the 22nd ACM Conference on Economics and Computation (EC). p. 792. ACM (2021). https://doi.org/10.1145/3465456.3467591

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

29

Table 1. Glossary of main notation used in Section 2. Symbol / Term Definition The FirstSwap exchange tx = (amt, limit) A trade request; amt: amount of assets the trader wishes to buy; limit: max. price per unit the trader is willing to pay. p(x), P (x), x0 Price per unit after x units R have been bought from the pool; with cumulative payment P (x) = 0x p(u) du, x0 and initial pool capacity x0 . S, admissible Set Pof trade requests S = {(amti , limiti )}, admissible if ∀ txi ∈ S: p( j:limit ≤limit amtj ) ≤ limiti . j

Economic model m ∈ {FS, FIFO, batch} pex,t , pex,0 εi , Fε θi,t , r, ε(r) qi (εi ), xLP τ, pbid,τ Prfill (pbid ), Prm (r) V olm , Wm , Rm

i

Trading mechanism: FirstSwap, fair ordering, or batch auction. CEX price at time t, and its initial value. Trader i’s fixed private asset valuation, with a mean-zero distribution having CDF Fε . Total valuation θi,t = pex,t + εi . Rank r is the fraction of highervaluation traders; ε(r) = Fε−1 (1 − r). Quantity allocated to trader i, inventory remaining in the pool. Submission time, submitted limit price. Execution probability of a submitted order and of a trader of rank r under mechanism R m. Total volume: 01 Prm (r) dr, social welfare and AMM gains from trade for mechanism m.

34. Spiegelman, A., Sonnino, A., Malkhi, D., Keidar, I.: Linera: A Byzantine-fault tolerant protocol for low-latency total order (2023), https://arxiv.org/abs/2308. 09534 35. Sridhar, S., Sonnino, A., Kokoris-Kogias, L.: Stingray: Fast concurrent transactions without consensus (2025), https://arxiv.org/abs/2501.06531 36. Tideman, T.N.: Independence of clones as a criterion for voting rules. Social Choice and Welfare 4(3), 185–206 (1987). https://doi.org/10.1007/BF00433944, https: //doi.org/10.1007/BF00433944 37. Tonkikh, A., Ponomarev, P., Kuznetsov, P., Pignolet, Y.A.: CryptoConcurrency: (almost) consensusless asset transfer with shared accounts. In: Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security. pp. 1556–1570. ACM (2023). https://doi.org/10.1145/3576915.3616587

A

Brownian FirstSwap equilibrium and outcome formulas

This appendix proves the threshold formula (5) and derives the execution probability (6), welfare (7), and AMM gains (8) stated in Section 2. 1. First-order condition. A trader with private value ε(r) chooses a cutoff p∗ex (s), at which a mass s has traded and the AMM price is p(s), to maximize ∗

e−γdiff [pex (s)−pex,0 ] [p∗ex (s) + ε(r) − p(s)].

(28)

Differentiating with respect to s and evaluating at s = r gives γdiff [p∗ex (r) + ε(r) − p(r)] = 1 −

p′ (r) . p∗′ ex (r)

(29)

30

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

2. Constant markup. For p∗ex (r) = p(r) − ε(r) + c and p′ (r) = −κε′ (r), we have ′ p∗′ ex (r) = −(1 + κ)ε (r). The FOC becomes γdiff c = 1 −

κ 1+κ

=⇒

c=

1 , γdiff (1 + κ)

(30)

which gives (5). Because the derivative of the trader’s objective function in Equation (28) only crosses zero once, this choice of trading time is globally optimal. Because total asset supply is fixed and passive liquidity is allocated independently of private values, the mechanism-dependent component of expected welfare is Z 1

ε(r) Prdiff FS (r) dr.

diff WFS =

(31)

0

For AMM gains from trade, let τr be the first time pex,t reaches p∗ex (r). Conditional on τr < Tblk , exponential memorylessness and the strong Markov property imply E[pex,Tblk | τr < Tblk ] = p∗ex (r). (32) Thus the expected AMM markout on a filled type-r trade is p(r) − p∗ex (r), giving Z 1 diff (33) RFS = [p(r) − p∗ex (r)] Prdiff FS (r) dr. 0

B

Allocation representation after a jump

This appendix proves the allocation representation in Lemma 2 of Section 2. Proof (Proof of Lemma 2). Fix a mechanism m ∈ {FS, FIFO, batch}. Write e for private value, a(e) := Prjump (1 − Fε (e)) for its interim allocation probability, m and t(e) for expected payment. The expected utility of a trader given its type e is u(e) = (pex,jump + e)a(e) − t(e). Because each trader could "mimic" the choices of any other trader and obtain their expected payment and fill probabilities a(e′ ), t(e′ ), we have the first-order condition u′ (e) = a(e). So long as the distribution Fε has support on types who do not want to trade, u(e) → 0 as e → −∞, and hence Z e t(e) − pex,jump a(e) = ea(e) − a(s) ds. −∞

Integrating over Fε and applying Fubini gives  Z  1 − Fε (e) jump Rm = e− a(e) dFε (e). fε (e) Since r = 1 − Fε (e) and ε′ (r) = −1/fε (ε(r)), this is the stated rank formula. The welfare formula follows directly because, conditional on pex,jump , allocating the asset to type e contributes the mechanism-dependent surplus e. ⊔ ⊓

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

C

31

Single crossing and jump-volume comparisons

This appendix proves the decompositions and the FirstSwap–FIFO single-crossing conditions of Lemma 3. The lemma statement appears in Section 2. Proof of sufficient condition for single crossing in Lemma 3 Proof. We compare the slopes of the two fill probabilities. If their ratio crosses one only upward, the allocation difference first decreases and then may increase, giving the desired single crossing. For prices z, define w(z) =

1 p′ (p−1 (z))

w′ (z) p′′ (p−1 (z)) , = ′ −1 w(z) p (p (z))2

α(z) = −

,

H(z) =

1 . α(z)

The AMM assumption gives H′ (z) = 2 − C(p−1 (z)) ∈ [0, 1],

H is concave.

(34)

On the common interior allocation range, write θ = pex,jump + e, pbid (e) = ′ pjump bid,FS (r(e)), and δ = θ − pbid (e) > 0. Here pbid abbreviates pbid (e), and pbid (e) denotes differentiation with respect to private value, not rank. The queue formulas and the differentiated first-price FOC give p′bid (e)w(pbid ) d Prjump , FS (r(e)) = de F ε (e)

w(θ) d Prjump (r(e)) = , de FIFO F ε (e) 1 + δhε (e) . p′bid (e) = 2 + δα(pbid )

(35)

Thus, defining the allocation difference and its slope ratio by jump ∆(e) = Prjump FS (r(e)) − PrFIFO (r(e)), d

D(e) = de d

Prjump FS (r(e))

jump de PrFIFO (r(e))

=

w(pbid ) 1 + δhε (e) . w(θ) 2 + δα(pbid )

we have ∆′ (e) = w(θ)[D(e) − 1]/F ε (e). All derivatives of ∆ and D below are with respect to e. We show that D′ > 0 whenever D = 1. At such a point, set a = δα(pbid ) > 0,

k = p′bid (e) =

w(θ) , w(pbid )

β = H′ (pbid ) ∈ [0, 1].

N = 1+δhε (e) = k(2+a),

Since N ≥ 1 and H′ ≤ 1, ( Z ) θ 1 1 ≤ k = exp − α(z) dz ≤ . 2+a 1 + a pbid

(36)

Differentiating D at this point yields δN

D′ = (1 − k)(2k − 1) + δ 2 h′ε (e) − δ 2 α′ (pbid )k 2 + δN [α(θ) − α(pbid )k]. (37) D

32

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Here derivatives of α are with respect to price. Increasing hazard gives h′ε ≥ 0, while concavity of H gives α(θ) ≥ α(pbid )/(1 + βa) and −δ 2 α′ (pbid ) = βa2 . Therefore   1 D′ ≥ (1 − k)(2k − 1) + βa2 k 2 + ak(2 + a) −k . δN D 1 + βa The right side decreases in β: its derivative is a2 k[k − (2 + a)/(1 + βa)2 ] < 0 by (36). Setting β = 1 hence gives   D′ a(2 + a) δN ≥ La (k) := −1 + 3 + k − 2(1 + a)k 2 . D 1+a This quadratic is concave, and at the endpoints of the permitted interval,     a 1 a 1 > 0, La > 0. = = La 2 2+a (2 + a) (1 + a) 1+a (1 + a)2 Thus D′ > 0 whenever D = 1, so the slope ratio can cross one only upward. ⊔ ⊓

D

Small- and large-jump comparisons

This appendix proves Lemma 4(ii) and (iii) of Section 2. We first prove part (ii), without linking the AMM curve to the private-value quantiles. At ∆pmid = 0, batch fills exactly the positive-private-value traders. For small positive ∆pmid , its welfare loss is quadratic, while FirstSwap continues to execute a positive fraction of central negative types. Theorem 5 (Batch dominance near efficient clearing). Suppose fε > 0 is C 1 on R, symmetric about zero, and log-concave, and p ∈ C 2 satisfies p′ > 0 and p′′ ≥ 0 on an inventory domain containing [0, 1/2], with p(0) finite. Fix any equilibrium of the first-price jump game, and assume both mechanisms have finite terminal prices and inventories inside this domain. Set ∆pmid = pex,jump − p(1/2), sp = p′ (1/2), ∆p = p(1/2) − p(1/4), and sε = 1/(2fε (0)). p If ∆p ≥ 2Fε−1 (3/4) and 0 ≤ ∆pmid < (sε + sp /4) ∆p /(24sp ), then batch has jump jump jump strictly higher welfare and AMM gains: Wbatch > WFS and Rjump batch > RFS . R ∞ Proof. Put a = Fε−1 (3/4) and let W ∗ = 0 efε (e) de, the welfare from filling exactly the positive-private-value traders. Symmetric log-concavity implies fε (e) ≤ fε (0) and a nondecreasing hazard rate hε = fε /(1 − Fε ). In particular, a≥

1 sε = , 4fε (0) 2

fε (a) = 41 hε (a) ≥ 14 hε (0) =

fε (0) . 2

Since ∆p ≥ 2a ≥ sε and ∆p ≤ sp /4, we have p sε ≤ sp /4. The assumed upper bound on ∆pmid is therefore at most (sp /2) 1/96 < sp /4. We will prove the bound "  2 # ∆p 1 ∆pmid jump jump Wbatch − WFS ≥ sε − > 0. (38) 96sp 4 sε + sp /4

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

33

Batch’s loss is quadratic. Write −z for batch’s marginal private value. Since ∆pmid ≥ 0, we have z ≥ 0, and symmetry and batch clearing give xjump batch = Fε (z),

∆pmid = z + p(Fε (z)) − p(1/2) ≥ z + sp [Fε (z) − 1/2].

For ∆pmid ≤ sp /4, this implies Fε (z) ≤ 3/4 and hence z ≤ a. The density is nonincreasing on [0, a], so Fε (z) − 1/2 ≥ zfε (a) ≥ zfε (0)/2. Therefore z≤ and W

∗

jump − Wbatch =

∆pmid , 1 + sp fε (0)/2

Z z

fε (0)z 2 sε efε (e) de ≤ ≤ 2 4 0



∆pmid sε + sp /4

2 .

(39)

FirstSwap has a uniform selection loss. A bid of p(1/4) fills with probability at least 1/4: the eligible population has mass at most one, so cumulative sales satisfy x′ (t) ≤ 1 and x(t) ≤ t, and an order arriving before queue time 1/4 finds the quote at or below p(1/4). For every private value e ∈ [−a, 0] this deviation gives ∆pmid + e + ∆p ∆p − a ∆p jump UFS (e) ≥ ≥ ≥ > 0. (40) 4 4 8 Let pbid (e) denote the equilibrium bid of type e and δ(e) := pex,jump + e − pbid (e) jump jump its surplus per fill, so that UFS (e) = Prjump FS (1−Fε (e)) δ(e). Since UFS (e) > 0, the equilibrium bid fills with positive probability, which requires pbid (e) ≥ p(0) because the AMM quote never falls below p(0). Hence   sp sp 3sp δ(e) ≤ pex,jump + e − p(0) ≤ ∆pmid + p(1/2) − p(0) ≤ + = , 4 2 4 using e ≤ 0, the maintained restriction ∆pmid ≤ sp /4, and convexity (p′ ≤ sp on [0, 1/2]). Therefore Prjump FS (1 − Fε (e)) =

jump UFS (e) ∆p /8 ∆p ≥ = , δ(e) 3sp /4 6sp

−a ≤ e ≤ 0.

The argument uses only that type e’s equilibrium payoff weakly exceeds the payoff from the deviation; no monotonicity or differentiability of the equilibrium is needed. The central negative types have a uniformly positive private-value loss. By symmetry and fε ≤ fε (0),   Z sε /2  Z 0 Z a 1 sε 1 − (Fε (u) − 1/2) du ≥ − fε (0)u du = . (−e)fε (e) de = 4 4 16 0 −a 0 Consequently, jump W ∗ −WFS =

Z ∞ 0

Z 0 ∆p sε sε ∆p e[1−Prjump (1−F (e))]f (e) de+ (−e) Prjump · = . ε ε FS FS (1−Fε (e))fε (e) de ≥ 6sp 16 96 sp −∞

34

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Subtracting (39) proves (38). jump AMM gains are also higher. Let Umjump = Wm − Rjump denote aggregate m jump jump jump trader utility. If xFS ≤ xbatch , the batch price pbatch = p(xjump batch ) is at least FirstSwap’s terminal quote. An infinitesimal trader can therefore obtain its batch payoff under FirstSwap by bidding pjump batch , which guarantees execution, if its jump value is at least pjump , and by abstaining otherwise. Optimality implies UFS ≥ batch jump Ubatch . R1 jump If xjump ≥ xjump = 0 ω(r) Prjump (r) dr, where ω(r) = m FS batch , Lemma 2 gives Um −rε′ (r) = 1/hε (ε(r)) is positive and nondecreasing because the hazard rate hε is nondecreasing. At a fixed volume this integral is minimized by allocating to the smallest ranks. Hence jump ≥ UFS

Z xjump FS

Z xjump batch ω(r) dr ≥

0

0

jump ω(r) dr = Ubatch .

In either case, jump jump jump jump jump jump jump Rjump = Wbatch − WFS + UFS − Ubatch ≥ Wbatch − WFS > 0. batch − RFS

⊔ ⊓ The condition ∆p ≥ 2a says that the AMM’s price rise from inventory 1/4 to 1/2 exceeds the interquartile range of private values. It guarantees that central negative types can profitably bid for early liquidity. The jump bound keeps batch’s marginal private value close to zero, limiting its welfare loss to a quadratic in ∆pmid . The result applies to general convex AMMs, including constant-product curves with sufficient liquidity, and uses no bound on the AMM slope near inventory exhaustion. It also places no restriction on the FirstSwap equilibrium beyond existence: the welfare proof uses only that a filled order pays at least p(0) and that no type can gain by switching to the bid p(1/4); the AMM-gain comparison uses optimal bidding and the envelope identity of Lemma 2. be FirstSwap’s Proof (Proof of Lemma 4(iii)). Write F ε = 1 − Fε and let cjump FS terminal eligibility cutoff. The limiting queue FOC gives jump ′ jump cjump = p(xjump FS FS ) − pex,jump + p (xFS )F ε (cFS ). jump If cjump > 0, symmetry gives F ε (cjump ≤ 1, convexity and FS FS ) < 1/2. Since xFS the jump condition imply

1 cjump ≤ p(1) − pex,jump + p′ (1) ≤ 0, FS 2 a contradiction. Thus FirstSwap fills every nonnegative-private-value trader with certainty. FIFO does too, because its terminal quote is p(xjump FIFO ) ≤ p(1) < pex,jump . The single crossing can therefore be chosen with e⋆ ≤ 0.

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

35

FirstSwap bids do not exceed values, so its eligible mass at any common inventory is at most FIFO’s, giving xjump ≤ xjump FS FIFO by queue comparison. Both terms in the welfare decomposition of Lemma 3 are consequently nonnegative. For AMM gains, Lemma 2 replaces private value e by the virtual value e − F ε (e)/fε (e). The increasing hazard rate makes this function strictly increasing, and its value at e⋆ ≤ 0 is negative. The same centered selection–volume decomposition therefore gives nonnegative terms for AMM gains. Both rankings are strict if allocations differ on a set of positive measure. ⊔ ⊓

E

Validator-count equivalence after a simultaneous jump

E.1

Fair ordering: anonymity, neutrality, and a uniform queue

Fix a simultaneous cohort of m labeled orders. Conditional on all submitted bids, quantities, and private values, suppose the n validators’ receipt rankings are independent uniform permutations: iid

π1 , . . . , πn ∼ Unif(Sm ). Independent continuous, identically distributed receipt delays satisfy this assumption. We consider an aggregation rule An that returns a complete ordering and satisfies the following axioms. 1. Transaction neutrality. For every relabeling ρ ∈ Sm , d

An (ρπ1 , . . . , ρπn ) = ρ An (π1 , . . . , πn ). Here ρπ relabels the entries of the ordered list π. 2. Validator anonymity. Permuting the n input rankings does not change the output distribution. 3. Bid blindness and neutral resolution. The aggregator uses only the receipt rankings and fresh independent randomness. Bids, values, quantities, and privileged transaction labels cannot affect priority; any ties or partial orders are resolved into a complete order in a transaction-neutral way. Theorem 6 (Ideal fair ordering is equivalent to one random queue). Under these assumptions, for every n ≥ 1 and every conditional bid and value profile, 1 , σ ∈ Sm . Pr{An (π1 , . . . , πn ) = σ} = m! Consequently, applying the same serial AMM execution and payment rule to the aggregated queue gives exactly the same joint allocation and payment law as one validator with a uniform receipt queue. Proof. Condition on a fixed bid and value profile. The joint receipt-ranking law is unchanged by a common relabeling ρ. Transaction neutrality therefore implies that the output law is also unchanged by ρ. For any two full rankings σ and

36

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

σ ′ , there is a relabeling ρ with ρσ = σ ′ . Thus every ranking has the same probability. Their probabilities sum to one, proving the displayed formula. Bid blindness ensures that this argument remains valid after conditioning on the traders’ chosen bids. ⊔ ⊓ The stated axioms are satisfied, for example, by the Kemeny [23] and Ranked Pairs methods [36, 30] of aggregating preference orderings. E.2

FirstSwap with bid-ordered AMM execution

We now specify conditions under which any monotone equilibrium of the FS protocol yields the same allocation as in the version with a single centralized validator. Let θ(r) = pex,jump + ε(r),

D := 1 − Fε (p(0) − pex,jump ) ∈ (0, 1).

Proof. Entry, execution prices, and the incentive equation. Every execution price is at least p(0), so values below p(0) cannot profit from entry. Conversely, any value above p(0) can bid strictly between p(0) and its value. Arriving sufficiently early at all validators and receiving a sufficiently early tie-break among the highest signature scores has positive probability and gives a feasible fill at a price no larger than this bid. Thus a regular equilibrium cannot exclude an interval of values above p(0). Participation is precisely r < D, up to the indifferent boundary type. Because bids strictly decrease with r, lower-value active types execute first. Hence Z D

Xn (r) =

an (t) dt,

pn (r) = p(Xn (r)).

r

A trader of true rank r who submits rank t’s bid receives utility an (t) [θ(r) − p(Xn (t))]. The first-order condition at t = r, together with Xn′ = −an , gives the following system, suppressing the validator subscript: X ′ (r) = −a(r), a′ (r) = −

a(r)2 p′ (X(r)) , θ(r) − p(X(r))

a(0+) = 1,

X(D−) = 0.

(41)

The boundary X(D−) = 0 follows from the definition of execution depth. A bid covering p(2D) receives every signature and can be added to any feasible allocation, so it guarantees execution at a price at most p(D). Comparing this deviation with an equilibrium payoff at most an (r)[θ(r)−p(0)], and using θ(r) → ∞ as r ↓ 0, proves an (0+) = 1. We show that there is at most one solution to this system of differential equations with these boundary conditions.

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

37

Table 2. Glossary of main notation used in Section 3. Symbol / Term Definition Scaled Admissibility n; f ; q Number of validators; Byzantine threshold; quorum size η Pre-approval fraction; η := (q − f )/(n − f ). Each validator pre-approves at most an η-fraction of available capacity at each price level. η-admissible admissible when every txi ∈ S has amti scaled by a factor 1/η. Pre-approvals and certificates σv (tx) Pre-approval of tx by validator v: a signed message ⟨APPROVE, tx⟩. π(tx) Approval certificate for tx with pre-approvals from q distinct validators. Av Local set of trade requests pre-approved by validator v in the current epoch; η-admissible by construction. Πv Local set of approval certificates learned by validator v in the current epoch. Protocol structure epoch A fixed-duration period comprising a pre-approval phase followed by a consensus round to decide a final block. Bv Mini-block formed by validator v at epoch end: Bv = (Av , Πv ). B Final block output by MVBA: a set of at least n−f well-formed mini-blocks. Valid External validity predicate for MVBA; holds when B contains well-formed mini-blocks from MB ≥ n−f validators with consistent cross-signatures. J(w) Accountability function; returns the set of validators implicated by evidence w; never implicates an honest validator.

To prove uniqueness, set Z = −a. The system for (X, Z) is a so-called coop′ ∂Z ′ erative system with ∂X ∂Z and ∂X both positive: X ′ = Z,

Z′ =

Z 2 p′ (X) , θ − p(X)

∂ p′ (X) p′′ (X)[θ − p(X)] + p′ (X)2 = > 0. ∂X θ − p(X) [θ − p(X)]2

By the comparison theorem for cooperative systems, a larger initial condition X(0+) and the same Z(0) = −1 give larger X and weakly larger Z pointwise. The difference between the two X paths is nondecreasing, so stays at least their strictly positive initial difference. They cannot both end at X(D−) = 0. There is therefore at most one solution satisfying a(0+) = 1 and X(D−) = 0. Thus every regular separating equilibrium, whenever it exists, has an (r) = a(r),

Xn (r) = X(r),

pn (r) = p(X(r)),

0 < r < D,

where pn (r) is the expected price conditional on filling.

F

(42) ⊔ ⊓

Supplemental Protocol Information: Glossary, Algorithms and Proofs

This appendix gives pseudocode for the decentralized protocol of Section 3 and overflow security proofs. Algorithm 1 is run by traders, Algorithm 2 by validators during the preapproval stage, and Algorithm 3 by validators at the end of the epoch. All parameters, the pricing function, and the notions of admissibility and η-admissibility are as defined in the main text. The pseudocode describes a single epoch e. All local state is reset at the start of each epoch, and approvals are signed together with the epoch number, so an approval cannot be reused in a later epoch.

38

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Algorithm 1 Trader-side pre-approval protocol for trade request tx in epoch e Require: Trade request tx = (amt, limit) 1: Send tx to all validators 2: Responses ← ∅ 3: while the pre-approval stage of epoch e has not ended do 4: Wait for a signed validator response, retransmitting tx to validators that have not responded 5: if the response is a valid signature on ⟨APPROVE, tx, e⟩ from a validator not yet in Responses then 6: Add the response to Responses 7: if |Responses| = q then 8: Form π(tx) from Responses and send it to all validators 9: return π(tx) 10: end if 11: end if 12: end while 13: return ⊥

Proof of Agreement Theorem 7 (f -Agreement). The protocol satisfies f -Agreement (defined in Section 3). Proof. By MVBA agreement, all honest validators decide the same output B. They apply the same inclusion and execution rules, including the deterministic tie-breaking rule, and therefore output the same final block. ⊔ ⊓

Proof of Accountable Inclusion. Theorem 8 (Accountable inclusion). The protocol satisfies accountable inclusion. Proof. Let the evidence w consist of an AC for tx, the decided output B, V ∗ the creators of its mini-blocks, and MB ← |V ∗ |. Define J(w) to contain every validator v such that v ∈ V ∗ , the AC contains v’s approval of tx, and Av omits that signed approval. Suppose tx obtains an AC but is absent from the final block. The AC cannot appear in any selected Πv , because that would include tx directly. Moreover, fewer than ηMB selected approved sets contain tx, because otherwise the preapproved inclusion rule would include it. The AC signer set and V ∗ intersect in at least q + MB − n ≥ ηMB validators, by the bound in the proof of Lemma 5. Thus at least one signer in this intersection omitted its approval, so J(w) is nonempty. An honest validator retains every approval it issues in Av . Therefore no valid evidence causes J to identify an honest validator. ⊔ ⊓

FirstSwap: Pre-Consensus Trade Approvals for Decentralized Market Design

39

Algorithm 2 Validator-side processing at validator v in epoch e Upon receiving trade request tx = (amt, limit): 1: if v has previously responded to tx then 2: return previously signed response 3: end if 4: if the pre-approval stage of epoch e has ended then 5: Ignore tx 6: end if {Check η-admissibility of Av ∪ {tx}; only limits ≥ limit are affected} 7: for all ℓ ∈ {limit} ∪ {limiti : txi ∈ Av , limiti > limit} do P 8: if ℓ < p(( txj ∈Av : limitj ≤ℓ amtj /η) + amt/η) then 9: return signed ⟨REJECT, tx, e⟩ {stored and replayed} 10: end if 11: end for 12: σv (tx) ← signed ⟨APPROVE, tx, e⟩ 13: Av ← Av ∪ {(tx, σv (tx))} 14: return σv (tx) Upon receiving π(tx) before the end of the pre-approval stage: 15: if π(tx) holds valid epoch-e approvals of tx from q distinct validators then 16: Πv ← Πv ∪ {π(tx)} 17: end if

Strengthened Inclusion Guarantees Lemma 10 (f -Certified inclusion). Let n ≥ 4f + 1, q = n − f , and η = (q − 2f )/(n − f ). The protocol satisfies the following strengthened pre-approval inclusion property: if at most f validators are Byzantine and a trade request tx obtains valid pre-approvals for an epoch from q distinct validators, not necessarily all honest, then tx is included in that epoch’s final block. Proof. At least q − f approvers are honest. Since only n − MB validators lie outside V ∗ , at least q − f − (n − MB ) = MB − 2f honest approvers have selected mini-blocks, each containing its approval of tx. Moreover,
2f MB − (n − f ) MB − 2f − ηMB = ≥ 0. n−f Thus tx appears in at least ηMB selected approved sets and is included by the pre-approved inclusion rule. ⊔ ⊓ Lemma 11 (Strengthened accountable inclusion). Let n ≥ 4f + 1, q = n − f , and η = (q − 2f )/(n − f ). There exists a publicly verifiable function J such that, if a trade request tx obtains an approval certificate but is omitted from a valid final block for that epoch, there is evidence w with |J(w)| ≥ f + 1 (and hence at least f ). Moreover, v ∈ / J(w) for every honest validator v and every w.

40

W. Diamond, F. Elsheimy, D. Malkhi, G. Ramseyer, S. Sridhar

Algorithm 3 End-of-epoch block consensus at validator v 1: External validity predicate (Definition 4). Valid(B) = 1 if and only if: 2: (i) B contains well-formed mini-blocks from at least n−f distinct validators, where Bu = (Au , Πu ) is well-formed if Au is η-admissible with every approval correctly signed by u for epoch e, and every π(tx) ∈ Πu is correctly formed; and 3: (ii) for every π(tx) in B and every Bu in B, if u’s signature appears in π(tx), then the same signed approval of tx appears in Au . 4: Protocol. 5: At the end of the epoch, form the mini-block Bv ← (Av , Πv ) and sign it 6: Invoke MVBA with input Bv and external-validity predicate Valid 7: Let B be the decision by MVBA, V ∗ the creators of its mini-blocks, and MB ← |V ∗ | 8: Pre-approved inclusion: include every tx with approval signatures from at least ηMB distinct validators in V ∗ 9: AC inclusion: include every tx for which a valid π(tx) appears in B, unless already included 10: Execution ordering: order all included trade requests in non-decreasing order of limit, breaking ties deterministically by trade request identifier 11: Output the resulting ordered block for execution {optionally supplemented with non-pre-approved trades as in Section 4}

Proof. Use the certificate and authenticated decided mini-blocks as evidence w. Let J(w) contain each selected certificate signer whose mini-block omits its signed approval, and set J(w) = ∅ for invalid evidence. At least q + MB − n = MB − f certificate signers are selected. If tx is omitted, fewer than ηMB selected approved sets contain it. Therefore |J(w)| > MB − f − ηMB =

2f MB − f ≥ f. n−f

Since |J(w)| is an integer, at least f + 1 validators are identified. An honest validator includes every approval it issued for the epoch in its mini-block, so valid evidence never identifies an honest validator. ⊔ ⊓

Related documents

• QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets#1605226
• EmbodiedIntentBench: Benchmarking Intent-Driven Runtime Adaptation for Mobile Robotic Missions#1605227
• Reproducible LoRA Inference Through Deterministic Split-K Reduction#1605228
• Continual Instruction Tuning for LLM-ased Management of Continuum Resources#1605229
• PACE: Keeping the Right Tokens in the KV Cache Is Not Enough for Long-Horizon LLM Agents#1605231