Introduction
This paper introduces FirstSwap, a decentralized exchange operated by a network of validators that finalizes blocks of trades epoch by epoch. FirstSwap 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
Figure 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.
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 requests 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.
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 ) p(x) p ( x ) increases as more assets are purchased, where x x x is the quantity already bought.
The pre-approval mechanism operates epoch by epoch. During an epoch, trade requests in the form t x = ( a m t , l i m i t ) \mathrm{tx}=(\mathrm{amt},\mathrm{limit}) tx = ( amt , limit ) arrive and are admitted to FirstSwap promptly upon arrival. A trader’s limit price l i m i t \mathrm{limit} 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 T T of trades of the form ( a m t , l i m i t ) (\mathrm{amt},\mathrm{limit}) ( amt , limit ) is admissible if for every limit ℓ \ell ℓ in T T T , the sum total x x x of amounts in trades whose limit is ≤ ℓ \le\ell ≤ ℓ satisfies p ( x ) ≤ ℓ p(x)\le\ell 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 t x \mathrm{tx} tx may be pre-approved if adding the trade request to the set A A A of previously pre-approved trades preserves admissibility; that is, if A ∪ { t x } A\cup\{\mathrm{tx}\} 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 p(x)=x p ( x ) = x , so the price per unit equals the number of units already consumed. The set A = { 3 , 1 , 3 , 5 } A=\{3,1,3,5\} A = { 3 , 1 , 3 , 5 } (writing only limits for each trade) is admissible, because for every limit ℓ \ell ℓ , the number of trade requests in A A A with limit at most ℓ \ell ℓ is ≤ ℓ \le\ell ≤ ℓ ; indeed, an execution in sorted order 1 , 3 , 3 , 5 1,3,3,5 1 , 3 , 3 , 5 satisfies all price limits.
Now consider an incoming trade request t x = 4 \mathrm{tx}=4 tx = 4 . The set A ∪ { t x } = { 3 , 1 , 3 , 5 , 4 } A\cup\{\mathrm{tx}\}=\{3,1,3,5,4\} A ∪ { tx } = { 3 , 1 , 3 , 5 , 4 } remains admissible, so the new trade request can be pre-approved, and the execution order is 1 , 3 , 3 , 4 , 5 1,3,3,4,5 1 , 3 , 3 , 4 , 5 . A different incoming trade request may be t x ′ = 2 \mathrm{tx}'=2 tx ′ = 2 . The set A ∪ { t x ′ } = { 3 , 1 , 3 , 5 , 2 } A\cup\{\mathrm{tx}'\}=\{3,1,3,5,2\} A ∪ { tx ′ } = { 3 , 1 , 3 , 5 , 2 } is not admissible: for ℓ = 3 \ell=3 ℓ = 3 , there are 4 trade requests whose limits are at most 3, hence p ( { t x ∈ A ∪ { 2 } ∣ t x ≤ 3 } ) = 4 > 3 p(\{\mathrm{tx}\in A\cup\{2\}\mid\mathrm{tx}\le3\})=4>3 p ({ tx ∈ A ∪ { 2 } ∣ tx ≤ 3 }) = 4 > 3 . Indeed, no sequenced execution of T ∪ { t x ′ } T\cup\{\mathrm{tx}'\} T ∪ { tx ′ } may satisfy all price limits. Thus, t x ′ \mathrm{tx}' 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 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 § 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 q 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 pre-approves only a certain fraction of the allowed capacity at each price. For n n n validators, f f f dishonest validators, and quorum size q = n − f q=n-f q = n − f , the pre-approval fraction is η : = q − f n − f \eta:= \frac{q-f}{n-f} η := n − f q − f . For the conventional BFT quorum sizes, n = 3 f + 1 n=3f+1 n = 3 f + 1 , q = 2 f + 1 q=2f+1 q = 2 f + 1 and η = f + 1 2 f + 1 ≈ 1 2 \eta=\frac{f+1}{2f+1}\approx\frac{1}{2} η = 2 f + 1 f + 1 ≈ 2 1 ; choosing larger quorum systems, e.g., q = ⌈ 4 n + 1 5 ⌉ q=\left\lceil\frac{4n+1}{5}\right\rceil q = ⌈ 5 4 n + 1 ⌉ can yield η ≈ 4 5 \eta\approx\frac{4}{5} η ≈ 5 4 . Importantly, modified admissibility is checked locally by each validator 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 n-f n − f mini-blocks and orders them into a final block, guaranteeing inclusion of every trade with a pre-approval certificate.
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. § 3 presents one Byzantine fault-tolerant protocol under partial synchrony.
A trade is a tuple t x = ( a m t , l i m i t ) \mathrm{tx}=(\mathrm{amt},\mathrm{limit}) tx = ( amt , limit ) , where a m t ∈ R + \mathrm{amt}\in\mathbb{R}_{+} amt ∈ R + is the amount of assets the trader wants to buy, and l i m i t ∈ R + \mathrm{limit}\in\mathbb{R}_{+} 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 p p such that if x x 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 ) p(x) 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 .
Definition 1 (Admissibility of trades). Let S = { t x i = ( a m t i , l i m i t i ) } i = 1 m S=\{\mathrm{tx}_i=(\mathrm{amt}_i,\mathrm{limit}_i)\}_{i=1}^{m} S = { tx i = ( amt i , limit i ) } i = 1 m be a set of trades. S S S is admissible if for all i i i , p ( ∑ j : l i m i t j ≤ l i m i t i a m t j ) ≤ l i m i t i p\left(\sum_{j:\mathrm{limit}_j\le\mathrm{limit}_i}\mathrm{amt}_j\right)\le\mathrm{limit}_i p ( ∑ j : limit j ≤ limit i amt j ) ≤ limit i .
Let S = { t x i = ( a m t i , l i m i t i ) } i = 1 m S=\{\mathrm{tx}_i=(\mathrm{amt}_i,\mathrm{limit}_i)\}_{i=1}^{m} S = { tx i = ( amt i , limit i ) } i = 1 m be the set of approved trades in the epoch. The validator executes each trade t x i \mathrm{tx}_i tx i at the price p ( ∑ j : l i m i t j ≤ l i m i t i a m t j ) p\left(\sum_{j:\mathrm{limit}_j\le\mathrm{limit}_i}\mathrm{amt}_j\right) p ( ∑ j : limit j ≤ limit i amt j ) . 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.
Lemma 1. Let S = { t x i = ( a m t i , l i m i t i ) } i = 1 m S=\{\mathrm{tx}_i=(\mathrm{amt}_i,\mathrm{limit}_i)\}_{i=1}^{m} S = { tx i = ( amt i , limit i ) } i = 1 m be a set of trades. There exists an ordering ( t x i = ( a m t i , l i m i t i ) ) i = 1 m (\mathrm{tx}_i=(\mathrm{amt}_i,\mathrm{limit}_i))_{i=1}^{m} ( tx i = ( amt i , limit i ) ) i = 1 m on S S S such that for all i i i , p ( ∑ j ≤ i a m t j ) ≤ l i m i t i p\left(\sum_{j\le i}\mathrm{amt}_j\right)\le\mathrm{limit}_i p ( ∑ j ≤ i amt j ) ≤ limit i if and only if S S S is admissible.
Economic Model
The model has a continuum of infinitesimal traders and time is measured continuously. At time t t t , trader i i i has value θ i , t = p e x , t + ε i \theta_{i,t}=p_{\mathrm{ex},t}+\varepsilon_i θ i , t = p ex , t + ε i for holding the asset provided by the AMM, where p e x , t p_{\mathrm{ex},t} p ex , t is a publicly observed “CEX price” and ε i ∼ F ε \varepsilon_i \sim F_{\varepsilon} ε i ∼ F ε is drawn i.i.d. across traders and is fixed over time. The distribution F ε F_{\varepsilon} F ε has unit mass and is normalized to mean 0, so that p e x , t p_{\mathrm{ex},t} p ex , t reflects the valuation of the average trader. We write ε ( r ) = F ε − 1 ( 1 − r ) \varepsilon(r) = F_{\varepsilon}^{-1}(1-r) ε ( r ) = F ε − 1 ( 1 − r ) for the value of ε \varepsilon ε with a fraction r r r of the population with a higher valuation for r ∈ ( 0 , 1 ) r \in(0,1) 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: p e x , t = p e x , 0 + σ e x W t , T b l k ∼ Exp ( λ b l k ) , \text{Diffusion model:}\qquad p_{\mathrm{ex},t} = p_{\mathrm{ex},0} + \sigma_{\mathrm{ex}} W_t,\qquad T_{\mathrm{blk}} \sim\operatorname{Exp}(\lambda_{\mathrm{blk}}), Diffusion model: p ex , t = p ex , 0 + σ ex W t , T blk ∼ Exp ( λ blk ) ,
where W t W_t W t is Brownian motion and the exponentially distributed random time T b l k T_{\mathrm{blk}} T blk at which the epoch ends and transactions execute is independent of W t W_t W t . 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 Δ p e x \Delta p_{\mathrm{ex}} Δ p ex and p e x , t = p e x , 0 + Δ p e x , ∀ t > 0 p_{\mathrm{ex},t} = p_{\mathrm{ex},0} + \Delta p_{\mathrm{ex}}, \ \forall t > 0 p ex , t = p ex , 0 + Δ p ex , ∀ t > 0 . Economic incentives for traders differ markedly in these settings. With gradual information, traders will strategically wait to observe the evolution of p e x , t p_{\mathrm{ex},t} p ex , 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 ) p(x) p ( x ) , where x x 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, T b l k T_{\mathrm{blk}} T blk , is
Social welfare: x 0 p e x , T b l k + ∫ q i ( ε i ) ε i d F ε ( ε i ) , (1) \text{Social welfare:}\qquad x_0p_{\mathrm{ex},T_{\mathrm{blk}}} + \int q_i(\varepsilon_i)\varepsilon_i \,dF_{\varepsilon}(\varepsilon_i), \tag*{(1)} Social welfare: x 0 p ex , T blk + ∫ q i ( ε i ) ε i d F ε ( ε i ) , (1)
where x 0 x_0 x 0 is total asset supply and q i ( ε i ) q_i(\varepsilon_i) q i ( ε i ) is the final quantity allocated to a trader with private value ε i \varepsilon_i ε i . For fixed x 0 x_0 x 0 , the common-value component x 0 p e x , T b l k x_0p_{\mathrm{ex},T_{\mathrm{blk}}} x 0 p ex , T blk 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 \varepsilon_i ε i . Hence, increasing the covariance between active-trader holdings and ε i \varepsilon_i ε i increases overall social welfare.
Our second metric is AMM gains relative to passively holding the asset:
AMM gains: ( x 0 − x L P ) ( p ˉ − p e x , T b l k ) , (2) \text{AMM gains:}\qquad(x_0-x_{\mathrm{LP}})(\bar{p}-p_{\mathrm{ex},T_{\mathrm{blk}}}), \tag*{(2)} AMM gains: ( x 0 − x LP ) ( p ˉ − p ex , T blk ) , (2)
where x L P x_{\mathrm{LP}} x LP is the inventory remaining with passive liquidity providers and p ˉ \bar{p} 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 p e x , T b l k p_{\mathrm{ex},T_{\mathrm{blk}}} p ex , T blk is high. This results in “loss-versus-rebalancing” or LVR, where the passive AMM liquidity experiences losses after large price movements. An ideal protocol therefore induces traders with high private valuations ε i \varepsilon_i ε i to buy without inducing a large negative correlation between the volume x 0 − x L P x_0-x_{\mathrm{LP}} x 0 − x LP executed and price movements p ˉ − p e x , T b l k \bar{p}-p_{\mathrm{ex},T_{\mathrm{blk}}} p ˉ − p ex , T blk .
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 τ \tau τ be the stopping time at which the trade occurs and let p b i d , τ p_{\mathrm{bid},\tau} p bid , τ denote the limit price submitted at that time. If a mass x τ x_\tau x τ of traders has already been approved to trade, the marginal AMM price for our trader is p ( x τ ) p(x_\tau) p ( x τ ) . Thus a trader with private value ε \varepsilon ε has expected utility
sup τ , p b i d , τ E [ 1 { τ < T b l k } 1 { p b i d , τ ≥ p ( x τ ) } ( p e x , τ + ε − p ( x τ ) ) ] . (3) \underset{\tau,p_{\mathrm{bid},\tau}}{\sup}\ \mathbb{E}\left[1\{\tau<T_{\mathrm{blk}}\}1\{p_{\mathrm{bid},\tau}\ge p(x_\tau)\}\left(p_{\mathrm{ex},\tau}+\varepsilon-p(x_\tau)\right)\right]. \tag*{(3)} τ , p bid , τ sup E [ 1 { τ < T blk } 1 { p bid , τ ≥ p ( x τ )} ( p ex , τ + ε − p ( x τ ) ) ] . (3)
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 p b i d , τ ≥ p ( x τ ) p_{\mathrm{bid},\tau}\ge p(x_\tau) p bid , τ ≥ p ( x τ ) . Since the execution price is p ( x τ ) p(x_\tau) 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, p b i d , τ = p ( x τ ) p_{\mathrm{bid},\tau}=p(x_\tau) p bid , τ = p ( x τ ) . Thus, the economically substantive decision is when to trade. We look for a monotone equilibrium in which a trader with valuation ε ( r ) \varepsilon(r) ε ( r ) chooses a time to trade that is strictly increasing in r r r . Given the AMM pricing function p ( . ) p(.) p ( . ) , a price p ( r ) p(r) p ( r ) is available to a trade that fills after a mass r r r of trades has previously occurred, so p b i d , τ = p ( r ) p_{\mathrm{bid},\tau}=p(r) p bid , τ = 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 r r chooses to submit when the CEX price p e x , t p_{\mathrm{ex},t} p ex , t first reaches some threshold p e x ∗ ( r ) p_{\mathrm{ex}}^*(r) p ex ∗ ( r ) regardless of other history.
Let γ d i f f ≡ 2 λ b l k σ e x \gamma_{\mathrm{diff}}\equiv\frac{\sqrt{2\lambda_{\mathrm{blk}}}}{\sigma_{\mathrm{ex}}} γ diff ≡ σ ex 2 λ blk . The probability that Brownian motion reaches p e x ∗ ( r ) p_{\mathrm{ex}}^*(r) p ex ∗ ( r ) before the epoch ends is e − γ d i f f [ p e x ∗ ( r ) − p e x , 0 ] e^{-\gamma_{\mathrm{diff}}[p_{\mathrm{ex}}^*(r)-p_{\mathrm{ex},0}]} e − γ diff [ p ex ∗ ( r ) − p ex , 0 ] (the Brownian first-passage probability formula). Hence the expected utility of a trader whose valuation ε ( r ) \varepsilon(r) ε ( r ) of the asset is less than that of a fraction r r r of the population (i.e. Pr { ε i > ε ( r ) } = r \Pr\{\varepsilon_i>\varepsilon(r)\}=r Pr { ε i > ε ( r )} = r ) is
U ( r ) = e − γ d i f f [ p e x ∗ ( r ) − p e x , 0 ] [ p e x ∗ ( r ) + ε ( r ) − p ( r ) ] . (4) U(r)=e^{-\gamma_{\mathrm{diff}}[p_{\mathrm{ex}}^*(r)-p_{\mathrm{ex},0}]}\left[p_{\mathrm{ex}}^*(r)+\varepsilon(r)-p(r)\right]. \tag*{(4)} U ( r ) = e − γ diff [ p ex ∗ ( r ) − p ex , 0 ] [ p ex ∗ ( r ) + ε ( r ) − p ( r ) ] . (4)
A particularly simple equilibrium obtains when κ ≡ − p ′ ( r ) ε ′ ( r ) > 0 \kappa\equiv-\frac{p'(r)}{\varepsilon'(r)}>0 κ ≡ − ε ′ ( r ) p ′ ( r ) > 0 is constant. In this case, we show in Appendix A that the optimal threshold is
p e x ∗ ( r ) = p ( r ) − ε ( r ) + 1 γ d i f f ( 1 + κ ) . (5) p_{\mathrm{ex}}^*(r)=p(r)-\varepsilon(r)+\frac{1}{\gamma_{\mathrm{diff}}(1+\kappa)}. \tag*{(5)} p ex ∗ ( r ) = p ( r ) − ε ( r ) + γ diff ( 1 + κ ) 1 . (5)
Traders optimally wait until their contemporaneous valuation exceeds the AMM price by a constant 1 γ d i f f ( 1 + κ ) \frac{1}{\gamma_{\mathrm{diff}}(1+\kappa)} γ diff ( 1 + κ ) 1 . For our diffusion analysis, we assume that no trader has a value of ε ( r ) \varepsilon(r) ε ( r ) so high that p ( r ) − ε ( r ) p(r)-\varepsilon(r) p ( r ) − ε ( r ) is below the starting CEX price p e x , 0 p_{\mathrm{ex},0} p ex , 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 r r trades when some value of p e x , t p_{\mathrm{ex},t} p ex , t exceeds p e x ∗ ( r ) p_{\mathrm{ex}}^*(r) p ex ∗ ( r ) before the epoch ends. This has probability (using the Brownian first-passage probability)
Pr F S d i f f ( r ) = exp ( − 1 1 + κ ) exp { − γ d i f f [ p ( r ) − ε ( r ) − p e x , 0 ] } . (6) \Pr^{\mathrm{diff}}_{\mathrm{FS}}(r)=\exp\left(-\frac{1}{1+\kappa}\right)\exp\left\{-\gamma^{\mathrm{diff}}\left[p(r)-\varepsilon(r)-p_{\mathrm{ex},0}\right]\right\}. \tag*{(6)} FS Pr diff ( r ) = exp ( − 1 + κ 1 ) exp { − γ diff [ p ( r ) − ε ( r ) − p ex , 0 ] } . (6)
We show in Appendix A that expected welfare W F S d i f f W^{\mathrm{diff}}_{\mathrm{FS}} W FS diff and AMM gains R F S d i f f R^{\mathrm{diff}}_{\mathrm{FS}} R FS diff are respectively given by
W F S d i f f = ∫ 0 1 ε ( r ) Pr F S d i f f ( r ) d r , (7) W^{\mathrm{diff}}_{\mathrm{FS}}=\int_0^1 \varepsilon(r)\Pr^{\mathrm{diff}}_{\mathrm{FS}}(r)\,dr, \tag*{(7)} W FS diff = ∫ 0 1 ε ( r ) FS Pr diff ( r ) d r , (7)
R F S d i f f = ∫ 0 1 [ ε ( r ) − 1 γ d i f f ( 1 + κ ) ] Pr F S d i f f ( r ) d r . (8) R^{\mathrm{diff}}_{\mathrm{FS}}=\int_0^1\left[\varepsilon(r)-\frac{1}{\gamma^{\mathrm{diff}}(1+\kappa)}\right]\Pr^{\mathrm{diff}}_{\mathrm{FS}}(r)\,dr. \tag*{(8)} R FS diff = ∫ 0 1 [ ε ( r ) − γ diff ( 1 + κ ) 1 ] FS Pr diff ( r ) d r . (8)
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 p e x , T b l k p_{\mathrm{ex},T_{\mathrm{blk}}} p ex , T blk , but (since every trader is infinitely small) they will choose a limit price equal to their true honest values. Rank r r r trades if p e x , T b l k ≥ p ( r ) − ε ( r ) p_{\mathrm{ex},T_{\mathrm{blk}}}\ge p(r)-\varepsilon(r) p ex , T blk ≥ p ( r ) − ε ( r ) . Since p e x , T b l k − p e x , 0 p_{\mathrm{ex},T_{\mathrm{blk}}}-p_{\mathrm{ex},0} p ex , T blk − p ex , 0 is a Brownian motion at an exponential stopping time, it follows a Laplace distribution, so the probability of this trade is
Pr b a t c h d i f f ( r ) = 1 2 exp { − γ d i f f [ p ( r ) − ε ( r ) − p e x , 0 ] } . (9) \Pr^{\mathrm{diff}}_{\mathrm{batch}}(r)=\frac{1}{2}\exp\left\{-\gamma^{\mathrm{diff}}\left[p(r)-\varepsilon(r)-p_{\mathrm{ex},0}\right]\right\}. \tag*{(9)} batch Pr diff ( r ) = 2 1 exp { − γ diff [ p ( r ) − ε ( r ) − p ex , 0 ] } . (9)
If r b a t c h r_{\mathrm{batch}} r batch is the rank of the trader choosing a limit price equal to the batch auction’s clearing price, the uniform batch price is p b a t c h d i f f = p ( r b a t c h ) = p e x , T b l k + ε ( r b a t c h ) p^{\mathrm{diff}}_{\mathrm{batch}}=p(r_{\mathrm{batch}})=p_{\mathrm{ex},T_{\mathrm{blk}}}+\varepsilon(r_{\mathrm{batch}}) p batch diff = p ( r batch ) = p ex , T blk + ε ( r batch ) . Because p ′ ( r ) = − κ ε ′ ( r ) p'(r)=-\kappa\varepsilon'(r) p ′ ( r ) = − κ ε ′ ( r ) , p ( r ) + κ ε ( r ) p(r)+\kappa\varepsilon(r) p ( r ) + κ ε ( r ) is constant. Conditional on rank r r r executing, the terminal public price exceeds p ( r ) − ε ( r ) p(r)-\varepsilon(r) p ( r ) − ε ( r ) by an exponentially distributed amount with mean 1 γ d i f f \frac{1}{\gamma^{\mathrm{diff}}} γ diff 1 , so E [ p b a t c h d i f f − p e x , T b l k ∣ r executes ] = ε ( r ) − 1 γ d i f f ( 1 + κ ) \mathbb{E}[p^{\mathrm{diff}}_{\mathrm{batch}}-p_{\mathrm{ex},T_{\mathrm{blk}}}\mid r\text{ executes}]=\varepsilon(r)-\frac{1}{\gamma^{\mathrm{diff}}(1+\kappa)} E [ p batch diff − p ex , T blk ∣ r executes ] = ε ( r ) − γ diff ( 1 + κ ) 1 . Utilitarian welfare W b a t c h d i f f W^{\mathrm{diff}}_{\mathrm{batch}} W batch diff and A M M AMM A M M gains R b a t c h d i f f R^{\mathrm{diff}}_{\mathrm{batch}} R batch diff are given by
W F S d i f f = 2 e − 1 / ( 1 + κ ) W b a t c h d i f f and R F S d i f f = 2 e − 1 / ( 1 + κ ) R b a t c h d i f f . (10) W^{\mathrm{diff}}_{\mathrm{FS}}=2e^{-1/(1+\kappa)}W^{\mathrm{diff}}_{\mathrm{batch}}
\qquad\text{and}\qquad
R^{\mathrm{diff}}_{\mathrm{FS}}=2e^{-1/(1+\kappa)}R^{\mathrm{diff}}_{\mathrm{batch}}. \tag*{(10)} W FS diff = 2 e − 1/ ( 1 + κ ) W batch diff and R FS diff = 2 e − 1/ ( 1 + κ ) R batch diff . (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 1 + κ < log 2 ⟺ κ > 1 log 2 − 1 ≈ 0.4427. (11) \frac{1}{1+\kappa}<\log2
\qquad\Longleftrightarrow\qquad
\kappa>\frac{1}{\log2}-1\approx0.4427. \tag*{(11)} 1 + κ 1 < log 2 ⟺ κ > log 2 1 − 1 ≈ 0.4427. (11)
A large value of κ \kappa κ is the natural assumption in financial markets, since the common-value variation p e x , t p_{\mathrm{ex},t} p ex , t in an asset’s value should be much larger than variation in agents’ private valuations ε \varepsilon ε . 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 p e x , t p_{\mathrm{ex},t} p ex , t experiences a single large jump instead of gradually changing over time, taking on a single value
p e x , j u m p ≡ p e x , 0 + Δ p e x . p_{\mathrm{ex,jump}}\equiv p_{\mathrm{ex},0}+\Delta p_{\mathrm{ex}}. p ex , jump ≡ p ex , 0 + Δ p ex .
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 p b i d , F S j u m p ( r ) p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r) p bid , FS jump ( r ) denote the equilibrium bid of a trader with private valuation ε ( r ) \varepsilon(r) ε ( r ) and Pr f i l l ( p b i d , F S j u m p ( r ) ) \Pr_{\mathrm{fill}}(p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r)) Pr fill ( p bid , FS jump ( r )) the probability at equilibrium that the trade is approved. The optimal bid p b i d , F S j u m p ( r ) p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r) p bid , FS jump ( r ) of type r r r maximizes over the choice of p b i d p_{\mathrm{bid}} p bid
[ p e x , j u m p + ε ( r ) − p b i d ] Pr f i l l ( p b i d ) . (12) \left[p_{\mathrm{ex,jump}}+\varepsilon(r)-p_{\mathrm{bid}}\right]\Pr_{\mathrm{fill}}(p_{\mathrm{bid}}). \tag*{(12)} [ p ex , jump + ε ( r ) − p bid ] fill Pr ( p bid ) . (12)
In a “regular” equilibrium where limit prices are strictly decreasing in the rank r r r and Pr f i l l ( p b i d ) \Pr_{\mathrm{fill}}(p_{\mathrm{bid}}) Pr fill ( p bid ) is smooth, the limit for any trader choosing Pr f i l l ( p b i d ) ∈ ( 0 , 1 ) \Pr_{\mathrm{fill}}(p_{\mathrm{bid}})\in(0,1) Pr fill ( p bid ) ∈ ( 0 , 1 ) satisfies a first-order condition
p b i d , F S j u m p ( r ) = p e x , j u m p + ε ( r ) − Pr f i l l ( p b i d , F S j u m p ( r ) ) Pr f i l l ′ ( p b i d , F S j u m p ( r ) ) . (13) p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r)=p_{\mathrm{ex,jump}}+\varepsilon(r)-\frac{\Pr_{\mathrm{fill}}(p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r))}{\Pr_{\mathrm{fill}}'(p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r))}. \tag*{(13)} p bid , FS jump ( r ) = p ex , jump + ε ( r ) − Pr fill ′ ( p bid , FS jump ( r )) Pr fill ( p bid , FS jump ( 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 p b i d , b a t c h j u m p ( r ) = p e x , j u m p + ε ( r ) p_{\mathrm{bid,batch}}^{\mathrm{jump}}(r)=p_{\mathrm{ex,jump}}+\varepsilon(r) p bid , batch jump ( r ) = p ex , 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 I F O , F S , batch auction } m\in\{FIFO,FS,\text{batch auction}\} m ∈ { F I F O , F S , batch auction } . After a realized jump Δ p e x \Delta p_{\mathrm{ex}} Δ p ex , welfare and gains have the following simple expressions, where we denote ε v i r t ( r ) = ε ( r ) + r ε ′ ( r ) \varepsilon_{\mathrm{virt}}(r)=\varepsilon(r)+r\varepsilon'(r) ε 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
W m j u m p = ∫ 0 1 ε ( r ) Pr m j u m p ( r ) d r ; R m j u m p = ∫ 0 1 ε v i r t ( r ) Pr m j u m p ( r ) d r . (14) W_m^{\mathrm{jump}}=\int_{0}^{1}\varepsilon(r)\Pr_m^{\mathrm{jump}}(r)\,dr;\qquad R_m^{\mathrm{jump}}=\int_{0}^{1}\varepsilon_{\mathrm{virt}}(r)\Pr_m^{\mathrm{jump}}(r)\,dr. \tag*{(14)} W m jump = ∫ 0 1 ε ( r ) m Pr jump ( r ) d r ; R m jump = ∫ 0 1 ε virt ( r ) m Pr jump ( r ) d r . (14)
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 holds, there is a cutoff r ∗ r^{*} r ∗ where one mechanism has a higher probability of trade execution for r > r ∗ r > r^{*} r > r ∗ and the other for r < r ∗ r < r^{*} r < r ∗ .
Lemma 3 (Single-crossing welfare and revenue decompositions). Consider two mechanisms m , n ∈ { F S , F I F O , b a t c h } m,n \in\{\mathrm{FS},\mathrm{FIFO},\mathrm{batch}\} m , n ∈ { FS , FIFO , batch } , with a difference in trade probabilities d m n ( r ) = Pr m j u m p ( r ) − Pr n j u m p ( r ) d_{mn}(r) = \Pr_{\mathrm{m}}^{\mathrm{jump}}(r)-\Pr_{\mathrm{n}}^{\mathrm{jump}}(r) d mn ( r ) = Pr m jump ( r ) − Pr n jump ( r ) and volumes Δ V o l m n j u m p = ∫ 0 1 ( Pr m j u m p ( r ) − Pr n j u m p ( r ) ) d r \Delta V\!ol_{mn}^{\mathrm{jump}} = \int_{0}^{1}(\Pr_{\mathrm{m}}^{\mathrm{jump}}(r)-\Pr_{\mathrm{n}}^{\mathrm{jump}}(r))\,dr Δ V o l mn jump = ∫ 0 1 ( Pr m jump ( r ) − Pr n jump ( r )) d r . If the two mechanisms satisfy the single-crossing condition with crossing point r ∗ r^{*} r ∗ , welfare and AMM gains satisfy
W m j u m p − W n j u m p = ∫ 0 1 [ ε ( r ) − ε ( r ∗ ) ] d m n ( r ) d r ⏟ selection effect + ε ( r ∗ ) Δ V o l m n j u m p ⏟ volume effect , (15) W_{\mathrm{m}}^{\mathrm{jump}}-W_{\mathrm{n}}^{\mathrm{jump}}=\underbrace{\int_{0}^{1}[\varepsilon(r)-\varepsilon(r^{*})]d_{mn}(r)\,dr}_{\text{selection effect}}+\underbrace{\varepsilon(r^{*})\Delta V\!ol_{mn}^{\mathrm{jump}}}_{\text{volume effect}}, \tag*{(15)} W m jump − W n jump = selection effect ∫ 0 1 [ ε ( r ) − ε ( r ∗ )] d mn ( r ) d r + volume effect ε ( r ∗ ) Δ V o l mn jump , (15) R m j u m p − R n j u m p = ∫ 0 1 [ ε v i r t ( r ) − ε v i r t ( r ∗ ) ] d m n ( r ) d r ⏟ selection effect + ε v i r t ( r ∗ ) Δ V o l m n j u m p ⏟ volume effect . R_{\mathrm{m}}^{\mathrm{jump}}-R_{\mathrm{n}}^{\mathrm{jump}}=\underbrace{\int_{0}^{1}[\varepsilon_{\mathrm{virt}}(r)-\varepsilon_{\mathrm{virt}}(r^{*})]d_{mn}(r)\,dr}_{\text{selection effect}}+\underbrace{\varepsilon_{\mathrm{virt}}(r^{*})\Delta V\!ol_{mn}^{\mathrm{jump}}}_{\text{volume effect}}. R m jump − R n jump = selection effect ∫ 0 1 [ ε virt ( r ) − ε virt ( r ∗ )] d mn ( r ) d r + volume effect ε virt ( r ∗ ) Δ V o l mn jump . 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 ε F_{\varepsilon} F ε has a smooth nondecreasing hazard rate f ε ( e ) / ( 1 − F ε ( e ) ) f_{\varepsilon}(e)/(1-F_{\varepsilon}(e)) f ε ( e ) / ( 1 − F ε ( e )) ; and 2. p p p is C 3 C^{3} C 3 with p ′ p' p ′ , p ′ ′ > 0 p'' > 0 p ′′ > 0 , and 1 ≤ C ( x ) : = p ′ ( x ) p ′ ′ ′ ( x ) p ′ ′ ( x ) 2 ≤ 2 1 \le C(x) := \frac{p'(x)p'''(x)}{p''(x)^{2}} \le2 1 ≤ C ( x ) := p ′′ ( x ) 2 p ′ ( x ) 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 ε \varepsilon ε 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). (i) Let Δ p m i d = p e x , j u m p − p ( 1 / 2 ) \Delta p_{\mathrm{mid}} = p_{\mathrm{ex,jump}}-p(1/2) Δ p mid = p ex , jump − p ( 1/2 ) . For any Δ p m i d \Delta p_{\mathrm{mid}} Δ p mid , V o l F I F O j u m p ≥ max { V o l b a t c h j u m p , V o l F S j u m p } V\!ol_{\mathrm{FIFO}}^{\mathrm{jump}} \ge\max\{V\!ol_{\mathrm{batch}}^{\mathrm{jump}},V\!ol_{\mathrm{FS}}^{\mathrm{jump}}\} V o l FIFO jump ≥ max { V o l batch jump , V o l FS jump } . Batch’s single crossing with either mechanism is at ε ∗ = ε ( V o l b a t c h j u m p ) = p ( V o l b a t c h j u m p ) − p e x , j u m p \varepsilon^{*}=\varepsilon(V\!ol_{\mathrm{batch}}^{\mathrm{jump}})=p(V\!ol_{\mathrm{batch}}^{\mathrm{jump}})-p_{\mathrm{ex,jump}} ε ∗ = ε ( V o l batch jump ) = p ( V o l batch jump ) − p ex , jump . Batch has higher welfare and AMM gains than FIFO for Δ p m i d ≥ 0 \Delta p_{\mathrm{mid}}\ge0 Δ p mid ≥ 0 .
(ii) Small jumps. Under additional regularity conditions in Appendix D, if 0 ≤ Δ p m i d < 1 2 f ε ( 0 ) + p ′ ( 1 / 2 ) / 4 p ( 1 / 2 ) − p ( 1 / 4 ) 24 p ′ ( 1 / 2 ) 0\le\Delta p_{\mathrm{mid}}<\frac{1}{2f_{\varepsilon}(0)+p'(1/2)/4}\sqrt{\frac{p(1/2)-p(1/4)}{24p'(1/2)}} 0 ≤ Δ p mid < 2 f ε ( 0 ) + p ′ ( 1/2 ) /4 1 24 p ′ ( 1/2 ) p ( 1/2 ) − p ( 1/4 ) , and p ( 1 / 2 ) − p ( 1 / 4 ) ≥ 2 F ε − 1 ( 3 / 4 ) p(1/2)-p(1/4)\ge2F_{\varepsilon}^{-1}(3/4) p ( 1/2 ) − p ( 1/4 ) ≥ 2 F ε − 1 ( 3/4 ) then batch has higher welfare and AMM gains than FirstSwap.
(iii) Large jumps. If p e x , j u m p ≥ p ( 1 ) + 1 2 p ′ ( 1 ) p_{\mathrm{ex,jump}}\ge p(1)+\frac{1}{2}p'(1) p ex , jump ≥ p ( 1 ) + 2 1 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 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 ) p(0) 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 § 12 .
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.
The FirstSwap Decentralized Protocol
In this section, we describe the decentralized FirstSwap protocol, a distributed implementation of the abstract FirstSwap design presented in § 2 over a network of n n n validators. Due to space limitations, a glossary, algorithms in pseudocode and several (easy) proofs are deferred to Appendix § 13 .
The fault model. We assume at most f ≤ ⌊ ( n − 1 ) / 3 ⌋ f \le\lfloor(n-1)/3 \rfloor f ≤ ⌊( n − 1 ) /3 ⌋ validators are Byzantine; typically f = ⌊ ( n − 1 ) / 3 ⌋ f = \lfloor(n-1)/3 \rfloor 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 Δ n e t > 0 \Delta_{\mathrm{net}} > 0 Δ net > 0 such that after GST any message sent at time t t t is received by max ( t , G S T ) + Δ n e t \max(t, \mathrm{GST}) + \Delta_{\mathrm{net}} 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 η \eta η of the available capacity at each price level. For n n n validators, up to f f f dishonest, and quorum size q : = n − f q := n-f q := n − f , define the approval fraction
η : = q − f n − f . \eta:= \frac{q-f}{n-f}. η := n − f q − f .
For conventional BFT parameters (n = 3 f + 1 n = 3f+1 n = 3 f + 1 , q = 2 f + 1 q = 2f+1 q = 2 f + 1 ), η = f + 1 2 f + 1 ≈ 1 2 \eta= \frac{f+1}{2f+1} \approx\frac{1}{2} η = 2 f + 1 f + 1 ≈ 2 1 ; larger quorums (e.g. q = ⌈ 4 n + 1 5 ⌉ q = \lceil\frac{4n+1}{5} \rceil q = ⌈ 5 4 n + 1 ⌉ ) yield η ≈ 4 5 \eta\approx\frac{4}{5} η ≈ 5 4 . Recall that a set S S S of trade requests is admissible if they can all be satisfied simultaneously within their price limits (Definition 1). A scaled η \eta η -admissible criterion is defined as follows:
Definition 2 (η \eta η -admissible). The set S = { ( a m t i , l i m i t i ) } S = \{(\mathrm{amt}_i, \mathrm{limit}_i)\} S = {( amt i , limit i )} is η \eta η -admissible if the scaled set { ( a m t i / η , l i m i t i ) } \{(\mathrm{amt}_i/\eta,\mathrm{limit}_i)\} {( amt i / η , limit i )} is admissible.
Since η < 1 \eta< 1 η < 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 t x = ( a m t , l i m i t ) \mathrm{tx} = (\mathrm{amt},\mathrm{limit}) tx = ( amt , limit ) to each validator and collect signed responses. A pre-approval σ v ( t x ) \sigma_v(\mathrm{tx}) σ v ( tx ) from validator v v v is a signed message ⟨ A P P R O V E , t x ⟩ \langle\mathrm{APPROVE},\mathrm{tx}\rangle ⟨ APPROVE , tx ⟩ . A collection of pre-approvals for tx from q q q distinct validators constitutes an approval certificate π ( t x ) \pi(\mathrm{tx}) π ( tx ) , where q q q is a Byzantine quorum threshold chosen so that any two quorums intersect in at least one honest validator (e.g. q = n − f q = n-f q = n − f in standard BFT settings). A trader that obtains π ( t x ) \pi(\mathrm{tx}) π ( tx ) may forward it to validators. Each validator v v v maintains a local set A v A_v A v of trade requests it has pre-approved and a set Π v \Pi_v Π 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 v v pre-approves tx if and only if A v ∪ { t x } A_v \cup\{\mathrm{tx}\} A v ∪ { tx } is η \eta η -admissible (Definition 2). If so, v v v returns σ v ( t x ) \sigma_v(\mathrm{tx}) σ v ( tx ) and updates A v : = A v ∪ { ( t x , σ v ( t x ) ) } A_v := A_v \cup\{(\mathrm{tx}, \sigma_v(\mathrm{tx}))\} A v := A v ∪ {( 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 v v forms and signs a mini-block B v = ( A v , Π v ) B_v = (A_v, \Pi_v) B v = ( A v , Π v ) . An honest validator includes in A v A_v A v all pre-approvals it signed before the finalization cutoff. It also includes in Π v \Pi_v Π 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) { t x : t x ∈ A v } \{\mathrm{tx}: \mathrm{tx} \in A_v\} { tx : tx ∈ A v } is η \eta η -admissible and each pre-approval is correctly signed by v v v , and (ii) every π ( t x ) ∈ Π v \pi(\mathrm{tx}) \in\Pi_v π ( 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 \mathcal{B} B satisfies the predicate Valid below:
Definition 4 (Valid). Valid(B \mathcal{B} B ) holds if (i) B \mathcal{B} B contains well-formed mini-blocks from at least M B ≥ n − f M_{\mathcal{B}} \ge n-f M B ≥ n − f distinct validators, and (ii) for every π ( t x ) \pi(\mathrm{tx}) π ( tx ) appearing in B \mathcal{B} B and every validator v v v whose mini-block B v = ( A v , ∗ ) B_v = (A_v, *) B v = ( A v , ∗ ) is in B \mathcal{B} B , if v v v 's signature appears in π ( t x ) \pi(\mathrm{tx}) π ( tx ) then the same signed pre-approval for tx must appear in A v A_v A v .
External validity provides three assurances: each A v A_v A v must satisfy η \eta η -admissibility to be counted; a trade request pre-approved by n − f n-f n − f honest validators appears in at least M B − f M_B-f M B − f included mini-blocks; and a validator that attempts to hide a signed pre-approval it issued may be excluded from B B 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 B B , an ordered set of trades is induced deterministically:
Pre-approved inclusion. Every trade request tx with signatures from at least η M B \eta M_B η M B distinct validators in B B B is included.
AC inclusion. Every trade request tx for which a valid π ( t x ) \pi(\mathrm{tx}) π ( tx ) appears in B B 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 f f -Agreement. If at most f f f validators are Byzantine, all honest validators output the same final block at each epoch. (Proof deferred to Appendix § 13 .)
f f f -Price validity. Suppose at most f f f validators are Byzantine. Let T T T be the ordered set of trades in the final block. Then T T T is admissible (Definition 1).
( f , η ) (f,\eta) ( f , η ) -Pre-approval liveness. Let S a n y S_{\mathrm{any}} S any be the set of trade requests sent to any honest validator during the epoch, and S a l l ⊆ S a n y S_{\mathrm{all}} \subseteq S_{\mathrm{any}} S all ⊆ S any the set sent to all honest validators. If S a n y S_{\mathrm{any}} S any is η \eta η -admissible, then under synchrony every trade request in S a l l S_{\mathrm{all}} S all obtains an approval certificate.
f f f -Pre-approval inclusion. If either (i) a trade request tx has pre-approvals from q q q honest validators, or (ii) an π ( t x ) \pi(\mathrm{tx}) π ( tx ) is received by f + 1 f+1 f + 1 honest validators, then tx must be included in the final block.
Accountable inclusion. There exists a function J J 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 v v and evidence w w w with v ∈ J ( w ) v \in J(w) v ∈ J ( w ) . Moreover, for all honest validators v v v and all w w w , v ∉ J ( w ) v \notin J(w) v ∈ / J ( w ) . (Proof deferred to Appendix § 13 .)
Validity. Let V ∗ V^* V ∗ be the set of creators of the mini-blocks in the decided proposal B B B , and let M B : = ∣ V ∗ ∣ M_B := |V^*| M B := ∣ V ∗ ∣ . External validity gives M B ≥ n − f M_B \ge n-f M B ≥ n − f and ensures that every B v = ( A v , Π v ) B_v=(A_v,\Pi_v) B v = ( A v , Π v ) for v ∈ V ∗ v \in V^* v ∈ V ∗ is well-formed. Let S S S be the set of trade requests included by the two inclusion rules of the protocol. We use the notation limit ( t x ) \operatorname{limit}(\mathrm{tx}) limit ( tx ) and amt ( t x ) \operatorname{amt}(\mathrm{tx}) amt ( tx ) to denote the limit and amount of a trade request tx.
Lemma 5 (Representation of included requests). Every trade request in S S S appears in A v A_v A v for at least η M B \eta M_B η M B validators v ∈ V ∗ v \in V^* v ∈ V ∗ .
Proof. If a request is included by the pre-approved inclusion rule, the claim follows from its threshold η M B \eta M_B η M B . Otherwise, its approval certificate has q q q signers, at least q + M B − n q+M_B-n q + M B − n of whom belong to V ∗ V^* V ∗ . Dividing this lower bound by the number of selected validators gives
q + M B − n M B = 1 − n − q M B ≥ 1 − n − q n − f = q − f n − f ≥ η . \frac{q+M_B-n}{M_B}=1-\frac{n-q}{M_B}\ge1-\frac{n-q}{n-f}=\frac{q-f}{n-f}\ge\eta. M B q + M B − n = 1 − M B n − q ≥ 1 − n − f n − q = n − f q − f ≥ η .
The first inequality uses n − q ≥ 0 n-q\ge0 n − q ≥ 0 and M B ≥ n − f M_B\ge n-f M B ≥ n − f ; the last uses the assumed bound on η \eta η . Thus at least η M B \eta M_B η M B selected validators signed the request. The external-validity cross-check requires its signed approval to appear in A v A_v A v for every such signer. □
Lemma 6 (Admissibility of included requests). The set S S S is admissible.
Proof. Fix a limit ℓ \ell ℓ occurring in S S S and write X ( ℓ ) = ∑ t x ∈ S : limit ( t x ) ≤ ℓ amt ( t x ) X(\ell)=\sum_{\substack{\mathrm{tx}\in S:\operatorname{limit}(\mathrm{tx})\le\ell}}\operatorname{amt}(\mathrm{tx}) X ( ℓ ) = ∑ tx ∈ S : limit ( tx ) ≤ ℓ amt ( tx ) . For each v ∈ V ∗ v\in V^* v ∈ V ∗ , similarly write X v ( ℓ ) = ∑ t x ∈ A v : limit ( t x ) ≤ ℓ amt ( t x ) X_v(\ell)=\sum_{\substack{\mathrm{tx}\in A_v:\operatorname{limit}(\mathrm{tx})\le\ell}}\operatorname{amt}(\mathrm{tx}) X v ( ℓ ) = ∑ tx ∈ A v : limit ( tx ) ≤ ℓ amt ( tx ) . By Lemma 5, each request counted in X ( ℓ ) X(\ell) X ( ℓ ) appears in at least η M B \eta M_B η M B selected approved sets. Counting its amount in each gives
η M B X ( ℓ ) ≤ ∑ v ∈ V ∗ X v ( ℓ ) . (16) \eta M_B X(\ell)\le\sum_{v\in V^*}X_v(\ell). \tag*{(16)} η M B X ( ℓ ) ≤ v ∈ V ∗ ∑ X v ( ℓ ) . (16)
For every v v v with X v ( ℓ ) > 0 X_v(\ell)>0 X v ( ℓ ) > 0 , let ℓ v \ell_v ℓ v be its largest limit at most ℓ \ell ℓ among the requests counted by X v ( ℓ ) X_v(\ell) X v ( ℓ ) . Since A v A_v A v is η \eta η -admissible, p ( X v ( ℓ ) / η ) ≤ ℓ v ≤ ℓ p(X_v(\ell)/\eta)\le\ell_v\le\ell p ( X v ( ℓ ) / η ) ≤ ℓ v ≤ ℓ . Let Y = max v ∈ V ∗ X v ( ℓ ) / η Y=\max_{v\in V^*}X_v(\ell)/\eta Y = max v ∈ V ∗ X v ( ℓ ) / η , treating an empty prefix as zero. Then p ( Y ) ≤ ℓ p(Y)\le\ell p ( Y ) ≤ ℓ . Dividing (16) by η M B > 0 \eta M_B>0 η M B > 0 gives
X ( ℓ ) ≤ 1 η M B ∑ v ∈ V ∗ X v ( ℓ ) ≤ 1 η M B ∑ v ∈ V ∗ η Y = Y . (17) X(\ell)\le\frac{1}{\eta M_B}\sum_{v\in V^*}X_v(\ell)\le\frac{1}{\eta M_B}\sum_{v\in V^*}\eta Y=Y. \tag*{(17)} X ( ℓ ) ≤ η M B 1 v ∈ V ∗ ∑ X v ( ℓ ) ≤ η M B 1 v ∈ V ∗ ∑ η Y = Y . (17)
Monotonicity of p p p gives p ( X ( ℓ ) ) ≤ p ( Y ) ≤ ℓ p(X(\ell))\le p(Y)\le\ell p ( X ( ℓ )) ≤ p ( Y ) ≤ ℓ . This holds for every limit in S S S , which is exactly admissibility. □
Corollary 1. The protocol satisfies f f 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 , η ) (f,\eta) ( f , η ) -pre-approval liveness.
Proof. Assume S a n y S_{\mathrm{any}} S any is η \eta η -admissible. Immediately before an honest validator v v v processes t x ∈ S a n y \mathrm{tx}\in S_{\mathrm{any}} tx ∈ S any , the set A v ∪ { t x } A_v\cup\{\mathrm{tx}\} A v ∪ { tx } is a subset of S a n y S_{\mathrm{any}} S any . Removing requests only decreases every prefix amount, so this subset remains η \eta η -admissible. Validator v v v therefore signs an approval for t x \mathrm{tx} tx . Every request in S a l l S_{\mathrm{all}} S all is approved by every honest validator. There are at least n − f = q n-f=q n − f = q honest validators, and synchrony delivers their responses during the epoch. Thus the trader obtains an AC. □
Theorem 3. The protocol satisfies f f f -pre-approval inclusion.
Proof. n ≥ 4 f + 1 n \ge4f + 1 n ≥ 4 f + 1 , q = n − f q = n - f q = n − f , and η = q − 2 f n − f \eta= \frac{q-2f}{n-f} η = n − f q − 2 f , First suppose t x \mathrm{tx} tx has approvals from q q q honest validators. Exactly n − M B n - M_B n − M B validators lie outside V ∗ V^* V ∗ , so at least q + M B − n ≥ η M B q + M_B - n \ge\eta M_B q + M B − n ≥ η M B of these honest approvers belong to V ∗ V^* V ∗ , by the bound in the proof of Lemma 5. Their complete approved sets contain their signed approvals for t x \mathrm{tx} tx , meeting the pre-approved inclusion threshold. Now suppose an AC for t x \mathrm{tx} tx is received before the cutoff by f + 1 f + 1 f + 1 honest validators. Since n − M B ≤ f n - M_B \le f n − M B ≤ f , at least one of these validators belongs to V ∗ V^* V ∗ . The honest mini-block construction places the AC in that validator’s Π v \Pi_v Π v , so the AC inclusion rule includes t x \mathrm{tx} tx . □
Corollary 2. For any n n n , f f f , q q q , η \eta η such that n ≥ 3 f + 1 n \ge3f + 1 n ≥ 3 f + 1 , q = n − f q = n - f q = n − f and η ≤ q − f n − f \eta\le\frac{q-f}{n-f} η ≤ n − f q − f , the FirstSwap protocol with parameters n n n , f f f , q q q , η \eta η satisfies f f f -agreement, f f f -price validity, ( f , η ) (f,\eta) ( f , η ) -pre-approval liveness, f f f -pre-approval inclusion, and accountable inclusion.
Stronger inclusion guarantees for pre-approved trades. By parameterizing the protocol with n = 4 f + 1 n = 4f + 1 n = 4 f + 1 , q = n − f q = n - f q = n − f , and η = q − 2 f n − f = f + 1 3 f + 1 ≈ 1 3 \eta= \frac{q-2f}{n-f} = \frac{f+1}{3f+1} \approx\frac{1}{3} η = n − f q − 2 f = 3 f + 1 f + 1 ≈ 3 1 , we can strengthen pre-approval inclusion: if a trade request t x \mathrm{tx} tx is pre-approved by q q q validators (not necessarily all honest), then t x \mathrm{tx} tx is guaranteed to be included in the final block. Moreover, with these parameters, accountable inclusion is also strengthened: at least f + 1 f + 1 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.
Maximal Fill Volume
The pre-approval liveness guarantee of the FirstSwap protocol in Section 3 requires the set of trade requests S a n y S_{\mathrm{any}} S any sent to any honest validator to be η \eta η -admissible. For example, let p ( x ) = x p(x) = x p ( x ) = x and suppose two traders submit requests t x 1 = ( a m t 1 = 1 , l i m i t 1 = 5 ) \mathrm{tx}_1 = (\mathrm{amt}_1 = 1, \mathrm{limit}_1 = 5) tx 1 = ( amt 1 = 1 , limit 1 = 5 ) and t x 2 = ( a m t 2 = 2 , l i m i t 2 = 5 ) \mathrm{tx}_2 = (\mathrm{amt}_2 = 2, \mathrm{limit}_2 = 5) tx 2 = ( amt 2 = 2 , limit 2 = 5 ) to all honest validators. For η = 1 / 2 \eta= 1/2 η = 1/2 , the set S a n y = { t x 1 , t x 2 } S_{\mathrm{any}} = \{\mathrm{tx}_1,\mathrm{tx}_2\} S any = { tx 1 , tx 2 } is not η \eta η -admissible, so the liveness guarantee does not apply. No trade is guaranteed to be included. Yet each request is individually η \eta η -admissible, as is the full amount of t x 1 \mathrm{tx}_1 tx 1 combined with half the amount of t x 2 \mathrm{tx}_2 tx 2 , 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 S a n y S_{\mathrm{any}} S any non-η \eta η -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 blockchain-based 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 t x = ( t x , f i l l ) \mathrm{tx} = (\mathrm{tx}, \mathrm{fill}) tx = ( tx , fill ) , where t x = \mathrm{tx} = tx = ( a m t , l i m i t ) (\mathrm{amt}, \mathrm{limit}) ( amt , limit ) is the original trade request and f i l l ∈ [ 0 , a m t ] \mathrm{fill} \in[0,\mathrm{amt}] fill ∈ [ 0 , amt ] is the amount filled. The trader specifies the maximum amount a m t \mathrm{amt} amt he is willing to buy, and the protocol determines the actual amount bought f i l l \mathrm{fill} fill . Validators continue to use the η \eta η -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 liveness). 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 f i l l \mathrm{fill} fill rather than their requested amounts a m t \mathrm{amt} amt . η \eta η -admissibility continues to use the full amounts.
Definition 5 (Admissible trades). Let T = { ( t x i = ( a m t i , l i m i t i ) , f i l l i ) } i = 1 m T = \{(\mathrm{tx}_i = (\mathrm{amt}_i, \mathrm{limit}_i), \mathrm{fill}_i)\}_{i=1}^{m} T = {( tx i = ( amt i , limit i ) , fill i ) } i = 1 m . The set T T T is admissible if 0 ≤ f i l l i ≤ a m t i 0 \le\mathrm{fill}_i \le\mathrm{amt}_i 0 ≤ fill i ≤ amt i for every i i i and, for every i i i with f i l l i > 0 \mathrm{fill}_i > 0 fill i > 0 , p ( ∑ j : l i m i t j ≤ l i m i t i f i l l j ) ≤ l i m i t i p\left(\sum_{j:\mathrm{limit}_j \le\mathrm{limit}_i} \mathrm{fill}_j\right) \le\mathrm{limit}_i p ( ∑ j : limit j ≤ limit i fill j ) ≤ limit i .
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 v v also records every valid request it receives before the finalization cutoff in a set R v R_v R v , and includes this set in its signed mini-block B v = ( A v , Π v , R v ) B_v = (A_v, \Pi_v, R_v) B v = ( A v , Π v , R v ) . Well-formedness checks the validity and trader authorization of these additional requests. Recording does not reserve capacity: the η \eta η -admissibility check still applies only to A v A_v A v .
Let B B B be the collection of mini-blocks decided by consensus, V ∗ V^* V ∗ their distinct creators, and M B = ∣ V ∗ ∣ ≥ n − f M_B = |V^*| \ge n-f M B = ∣ V ∗ ∣ ≥ n − f . Let U U U contain every distinct request appearing in B B B , including recorded but unapproved requests. Write G G G for the requests selected by either of the first two inclusion rules below. As in the main protocol, use q = n − f q = n-f q = n − f and η = ( n − 2 f ) / ( n − f ) \eta= (n-2f)/(n-f) η = ( n − 2 f ) / ( n − f ) . The final ordered block is constructed as follows.
Pre-approved inclusion. Every trade request t x = ( a m t , l i m i t ) \mathrm{tx} = (\mathrm{amt},\mathrm{limit}) tx = ( amt , limit ) with signatures from at least M B − f M_B-f M B − f distinct validators in B B B is included with f i l l = a m t \mathrm{fill} = \mathrm{amt} fill = amt .
AC inclusion. Every trade request t x = ( a m t , l i m i t ) \mathrm{tx} = (\mathrm{amt},\mathrm{limit}) tx = ( amt , limit ) for which a valid π ( t x ) \pi(\mathrm{tx}) π ( tx ) appears in B B B is included with f i l l = a m t \mathrm{fill} = \mathrm{amt} fill = amt , unless already covered above.
Residual inclusion. Then consider every remaining trade request in U U 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 U U , including prefixes ending at requests that currently have zero fill. Equivalently, assign the largest x ∈ [ 0 , a m t i ] x \in[0,\mathrm{amt}_i] x ∈ [ 0 , amt i ] for which replacing f i l l i = 0 \mathrm{fill}_i = 0 fill i = 0 by x x 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.
Feasible fills and capacity. For a set of requests U U U , write
F ( U ) = { f i l l ∈ ∏ i = 1 ∣ U ∣ [ 0 , a m t i ] : { ( t x i , f i l l i ) } t x i ∈ U is admissible } . (18) \mathcal{F}(U)=\left\{\mathrm{fill}\in\prod_{i=1}^{|U|}[0,\mathrm{amt}_i]:\{(\mathrm{tx}_i,\mathrm{fill}_i)\}_{\mathrm{tx}_i\in U}\text{ is admissible}\right\}. \tag*{(18)} F ( U ) = ⎩ ⎨ ⎧ fill ∈ i = 1 ∏ ∣ U ∣ [ 0 , amt i ] : {( tx i , fill i ) } tx i ∈ U is admissible ⎭ ⎬ ⎫ . (18)
Define
R ( U ) = max f i l l ∈ F ( U ) ∑ i f i l l i , R ( ∅ ) = 0. R(U)=\max_{\mathrm{fill}\in\mathcal{F}(U)}\sum_i\mathrm{fill}_i,\qquad R(\varnothing)=0. R ( U ) = fill ∈ F ( U ) max i ∑ fill i , R ( ∅ ) = 0.
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 η \eta η -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 G G is admissible when f i l l = a m t \mathrm{fill}=\mathrm{amt} 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 f f validators are Byzantine during an epoch. Let S S S be the set of valid trade requests sent to all honest validators in time to arrive before the finalization cutoff. Let T T T denote the trades in the final block of the epoch. The protocol satisfies f -Maximal volume filled if
∑ ( t x i , f i l l i ) ∈ T f i l l i ≥ R ( S ) . (19) \sum_{(\mathrm{tx}_i,\mathrm{fill}_i)\in T}\mathrm{fill}_i\ge R(S). \tag*{(19)} ( tx i , fill i ) ∈ T ∑ fill i ≥ R ( S ) . (19)
Lemma 7 (Maximal fills maximize volume). Starting from the full fills of G G G , the protocol’s residual rule produces a feasible fill of U U U with total volume R ( U ) R(U) R ( U ) .
Proof. By Lemma 6, the initial full fills of G G 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.
Suppose, for a contradiction, that another admissible fill vector f i l l ^ \widehat{\mathrm{fill}} fill has larger total volume. Write D = ∑ j ( f i l l ^ j − f i l l j ) > 0 D = \sum_j (\widehat{\mathrm{fill}}_j-\mathrm{fill}_j)>0 D = ∑ j ( fill j − fill j ) > 0 , and choose a request t x i \mathrm{tx}_i tx i with largest l i m i t \mathrm{limit} limit among those for which f i l l ^ i > f i l l i \widehat{\mathrm{fill}}_i>\mathrm{fill}_i fill i > fill i . For every ℓ ≥ l i m i t i \ell\ge\mathrm{limit}_i ℓ ≥ limit i , requests with limit above ℓ \ell ℓ have f i l l ^ j ≤ f i l l j \widehat{\mathrm{fill}}_j \le\mathrm{fill}_j fill j ≤ fill j , so
∑ j : l i m i t j ≤ ℓ ( f i l l ^ j − f i l l j ) = D − ∑ j : l i m i t j > ℓ ( f i l l ^ j − f i l l j ) ≥ D . (20) \sum_{j:\mathrm{limit}_j\le\ell}(\widehat{\mathrm{fill}}_j-\mathrm{fill}_j)=D-\sum_{j:\mathrm{limit}_j>\ell}(\widehat{\mathrm{fill}}_j-\mathrm{fill}_j)\ge D. \tag*{(20)} j : limit j ≤ ℓ ∑ ( fill j − fill j ) = D − j : limit j > ℓ ∑ ( fill j − fill j ) ≥ D . (20)
Increase f i l l i \mathrm{fill}_i fill i by ε = min { D , f i l l ^ i − f i l l i } > 0 \varepsilon=\min\{D,\widehat{\mathrm{fill}}_i-\mathrm{fill}_i\}>0 ε = min { D , fill i − fill i } > 0 . The increased fill is at most f i l l ^ i ≤ a m t i \widehat{\mathrm{fill}}_i\le\mathrm{amt}_i fill i ≤ amt i . Prefixes below l i m i t i \mathrm{limit}_i limit i are unchanged, and (20) shows that every prefix at or above l i m i t i \mathrm{limit}_i limit i has total fill at most the corresponding prefix of f i l l ^ \widehat{\mathrm{fill}} fill . For each such limit ℓ \ell ℓ , the alternative prefix contains a positive fill because f i l l ^ i > 0 \widehat{\mathrm{fill}}_i>0 fill i > 0 . Let ℓ ′ \ell' ℓ ′ be the largest limit of any positive-filled request in that prefix. Admissibility of f i l l ^ \widehat{\mathrm{fill}} fill gives
p ( ∑ j : l i m i t j ≤ ℓ f i l l ^ j ) = p ( ∑ j : l i m i t j ≤ ℓ ′ f i l l ^ j ) ≤ ℓ ′ ≤ ℓ . p\left(\sum_{j:\mathrm{limit}_j\le\ell}\widehat{\mathrm{fill}}_j\right)=p\left(\sum_{j:\mathrm{limit}_j\le\ell'}\widehat{\mathrm{fill}}_j\right)\le\ell'\le\ell. p j : limit j ≤ ℓ ∑ fill j = p j : limit j ≤ ℓ ′ ∑ fill j ≤ ℓ ′ ≤ ℓ .
By monotonicity of p p p , the increased fill vector therefore remains admissible, including at l i m i t i \mathrm{limit}_i limit i . This contradicts the impossibility of increasing any final fill. No admissible vector has larger total volume, so the protocol attains R ( U ) R(U) R ( U ) . □ \square □
Theorem 4 (f -Maximal volume filled). Under the synchrony and epoch-duration assumptions of Section 3, the extended protocol satisfies f-Maximal volume filled as defined in Definition 6.
Proof. Let S S S be the set in the property definition. Every honest validator records each t x ∈ S \mathrm{tx}\in S tx ∈ S and includes it in its mini-block. Since V ∗ V^* V ∗ contains at least M B − f ≥ n − 2 f > 0 M_B-f\ge n-2f>0 M B − f ≥ n − 2 f > 0 honest validators, every request in S S S appears in U U U . Thus S ⊆ U S\subseteq U S ⊆ U .
Any admissible fill of S S S extends to an admissible fill of U U U by assigning zero to U ∖ S U\setminus S 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 ) R(U)\ge R(S) R ( U ) ≥ R ( S ) .
By Lemma 7, the protocol fills total volume R ( U ) R(U) R ( U ) . Discarding zero-filled requests changes no volume, so its final block T T T satisfies
∑ ( t x i , f i l l i ) ∈ T f i l l i = R ( U ) ≥ R ( S ) . \sum_{(\mathrm{tx}_i,\mathrm{fill}_i)\in T}\mathrm{fill}_i=R(U)\ge R(S). ( tx i , fill i ) ∈ T ∑ fill i = R ( U ) ≥ R ( S ) .
□ \square □
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 it is able to pre-approve a request. We add side ∈ { b u y , s e l l } \in\{\mathrm{buy},\mathrm{sell}\} ∈ { buy , sell } to the existing trade request format: t x = ( s i d e , a m t , l i m i t ) \mathrm{tx} = (\mathrm{side}, \mathrm{amt}, \mathrm{limit}) tx = ( side , amt , limit ) . A naive way to handle both buys and sells would be to run two independent instances of the protocol from § 3 , one for buys and one for sells. However, this approach 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 G G of pre-approved trade requests that must be executed fully and a set U ⊇ G U \supseteq G U ⊇ G of trade requests that can optionally be executed to fill enough liquidity to support the trades in G G G . We show a pre-approval rule and block finalization protocol (similar to those in § 3 ) that ensures bilateral admissibility when G G G is the set of pre-approved trade requests and U U 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 G G (and optionally some others in U U U ) can be executed while satisfying all limit prices.
We extend our AMM curve p ( x ) p(x) p ( x ) to allow for either positive or negative net purchases x x x and write P ( x ) = ∫ 0 x p ( u ) d u P(x) = \int_{0}^{x} p(u)\,\mathrm{d}u P ( x ) = ∫ 0 x p ( u ) d u . Let c ( ℓ ) c(\ell) c ( ℓ ) be the inverse of p ( x ) p(x) p ( x ) , with c ( p ( 0 ) ) = 0 c(p(0)) = 0 c ( p ( 0 )) = 0 and both c ( ⋅ ) , p ( ⋅ ) c(\cdot), p(\cdot) c ( ⋅ ) , p ( ⋅ ) continuous. Write [ z ] + = max { z , 0 } [z]_{+} = \max\{z, 0\} [ z ] + = max { z , 0 } . At limit ℓ \ell ℓ , the AMM offers supply [ c ( ℓ ) ] + [c(\ell)]_{+} [ c ( ℓ ) ] + and demand [ − c ( ℓ ) ] + [-c(\ell)]_{+} [ − c ( ℓ ) ] + .
Definition 7 (Bilateral admissibility). Let G ⊆ U G \subseteq U G ⊆ U be a collection of trade requests. G G G is said to be bilaterally admissible in U U U if for every ℓ \ell ℓ ,
∑ t x i ∈ G b u y s l i m i t i ≤ ℓ a m t i ≤ [ c ( ℓ ) ] + + ∑ t x j ∈ U s e l l s l i m i t j ≤ ℓ a m t j , (21) \sum_{\substack{\mathrm{tx}_i \in G\ \mathrm{buys}\\ \mathrm{limit}_i \le\ell}} \mathrm{amt}_i \le[c(\ell)]_{+} + \sum_{\substack{\mathrm{tx}_j \in U\ \mathrm{sells}\\ \mathrm{limit}_j \le\ell}} \mathrm{amt}_j, \tag*{(21)} tx i ∈ G buys limit i ≤ ℓ ∑ amt i ≤ [ c ( ℓ ) ] + + tx j ∈ U sells limit j ≤ ℓ ∑ amt j , (21) ∑ t x i ∈ G s e l l s l i m i t i ≥ ℓ a m t i ≤ [ − c ( ℓ ) ] + + ∑ t x j ∈ U b u y s l i m i t j ≥ ℓ a m t j . (22) \sum_{\substack{\mathrm{tx}_i \in G\ \mathrm{sells}\\ \mathrm{limit}_i \ge\ell}} \mathrm{amt}_i \le[-c(\ell)]_{+} + \sum_{\substack{\mathrm{tx}_j \in U\ \mathrm{buys}\\ \mathrm{limit}_j \ge\ell}} \mathrm{amt}_j. \tag*{(22)} tx i ∈ G sells limit i ≥ ℓ ∑ amt i ≤ [ − c ( ℓ ) ] + + tx j ∈ U buys limit j ≥ ℓ ∑ amt j . (22)
In our extended protocol, similar to § 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 § 4 , trades included in the final block will have a parameter f i l l i ∈ [ 0 , a m t i ] \mathrm{fill}_i \in[0,\mathrm{amt}_i] fill i ∈ [ 0 , amt i ] denoting partial filling of trade requests. In addition, each trade will also be assigned p r i c e i \mathrm{price}_i price i denoting the execution price of the trade. When we considered only buys, we had implicitly considered p r i c e i \mathrm{price}_i price i to be the price determined by the AMM curve after trades has been ordered by their limit prices. Our goal is to ensure that p r i c e i ≤ l i m i t i price_i \le limit_i p r i c e i ≤ l imi t i for all executed buys and p r i c e i ≥ l i m i t i price_i \ge limit_i p r i c e i ≥ l imi t i for all executed sells.
Modified Pre-Approval Protocol. Alongside the original pre-approval and certificate sets, validator v v v records trade requests R v R_v R v 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 v v , given the set of trade requests it has seen, define
S ^ v ( ℓ ) = ∑ t x i ∈ R v s e l l s l i m i t i ≤ ℓ a m t i , B ^ v ( ℓ ) = ∑ t x i ∈ R v b u y s l i m i t i ≥ ℓ a m t i . \widehat{S}_v(\ell)=\sum_{\substack{tx_i\in R_v\ \mathrm{sells}\\ limit_i\le\ell}} amt_i,\qquad\widehat{B}_v(\ell)=\sum_{\substack{tx_i\in R_v\ \mathrm{buys}\\ limit_i\ge\ell}} amt_i. S v ( ℓ ) = t x i ∈ R v sells l imi t i ≤ ℓ ∑ am t i , B v ( ℓ ) = t x i ∈ R v buys l imi t i ≥ ℓ ∑ am t i .
Our validator’s new rule for adding a trade request to its pre-approved set A v A_v A v is that it will pre-approve if doing so does not violate
∑ t x i ∈ A v b u y s l i m i t i ≤ ℓ a m t i ≤ η ( [ c ( ℓ ) ] + + S ^ v ( ℓ ) ) for every ℓ (23) \sum_{\substack{tx_i\in A_v\ \mathrm{buys}\\ limit_i\le\ell}} amt_i\le\eta\left([c(\ell)]_+ + \widehat{S}_v(\ell)\right)\quad\text{for every }\ell \tag*{(23)} t x i ∈ A v buys l imi t i ≤ ℓ ∑ am t i ≤ η ( [ c ( ℓ ) ] + + S v ( ℓ ) ) for every ℓ (23)
∑ t x i ∈ A v s e l l s l i m i t i ≥ ℓ a m t i ≤ η ( [ − c ( ℓ ) ] + + B ^ v ( ℓ ) ) for every ℓ . (24) \sum_{\substack{tx_i\in A_v\ \mathrm{sells}\\ limit_i\ge\ell}} amt_i\le\eta\left([-c(\ell)]_+ + \widehat{B}_v(\ell)\right)\quad\text{for every }\ell. \tag*{(24)} t x i ∈ A v sells l imi t i ≥ ℓ ∑ am t i ≤ η ( [ − c ( ℓ ) ] + + B v ( ℓ ) ) for every ℓ . (24)
Note that this is the analogue of η \eta η -admissibility (Definition 2) for bilateral admissibility (Definition 7).
Modified Finalization Protocol. In our modified finalization protocol, each mini-block B v = ( A v , Π v , R v ) B_v=(A_v,\Pi_v,R_v) B v = ( A v , Π v , R v ) additionally contains the recorded requests R v R_v R v . Well-formedness verifies these requests and replaces the original η \eta η -admissibility by checking Equations (23) and (24) . The quorum requirement and approval-certificate cross-check for block validity are as before. The inclusion and execution ordering steps are described below. First, if U U U is the set of all trade requests appearing in the block (including recorded and approved), note that all pre-approved transactions G ⊆ U G\subseteq U G ⊆ U satisfy joint bilateral feasibility.
Lemma 8 (Admissibility of pre-approved requests). Under (23)–(24) with η = ( q − f ) / q \eta=(q-f)/q η = ( q − f ) / q , the set G G G of trade requests with at least M B − f M_B-f M B − f approvals among selected mini-blocks is bilaterally admissible.
Proof. For each limit ℓ \ell ℓ , let X ( ℓ ) X(\ell) X ( ℓ ) be the total quantity of buys in G G G with limits at most ℓ \ell ℓ , and let X v ( ℓ ) X_v(\ell) X v ( ℓ ) be the corresponding quantity in A v A_v A v . Let S U ( ℓ ) S_U(\ell) S U ( ℓ ) be the total quantity of sells in U U U with limits at most ℓ \ell ℓ . Every trade request recorded as seen in a selected mini-block belongs to U U U , so S ^ v ( ℓ ) ≤ S U ( ℓ ) \widehat{S}_v(\ell)\le S_U(\ell) S v ( ℓ ) ≤ S U ( ℓ ) for every v ∈ V ∗ v\in V^* v ∈ V ∗ . Counting approvals and summing the local buy budgets gives
X ( ℓ ) ≤ 1 M B − f ∑ v ∈ V ∗ X v ( ℓ ) ≤ η M B M B − f ( [ c ( ℓ ) ] + + S U ( ℓ ) ) ≤ [ c ( ℓ ) ] + + S U ( ℓ ) . X(\ell)\le\frac{1}{M_B-f}\sum_{v\in V^*}X_v(\ell)\le\frac{\eta M_B}{M_B-f}\left([c(\ell)]_+ + S_U(\ell)\right)\le[c(\ell)]_+ + S_U(\ell). X ( ℓ ) ≤ M B − f 1 v ∈ V ∗ ∑ X v ( ℓ ) ≤ M B − f η M B ( [ c ( ℓ ) ] + + S U ( ℓ ) ) ≤ [ c ( ℓ ) ] + + S U ( ℓ ) .
This demonstrates Equation (21) for buys and an analogous argument demonstrates Equation (22) for sells. □ \square □
Next, we show how to compute the amounts filled for each trade request f i l l i \mathrm{fill}_i fill i , given a block with trades U U U and pre-approved trades G ⊆ U G \subseteq U G ⊆ U that are bilaterally admissible. Lemma 9 shows that all trades in G G 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 U 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 G 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 G G . We then compute a price ℓ ∗ \ell^* ℓ ∗ where executing all buys in U ∖ G U \setminus G U ∖ G with limit prices below ℓ ∗ \ell^* ℓ ∗ and all sells above ℓ ∗ \ell^* ℓ ∗ (with potential partial fills at ℓ ∗ \ell^* ℓ ∗ ) allows all trades in G G G to execute. This results in a total set U ∗ U^* U ∗ of trades that actually execute. If U ∗ U^* U ∗ has more buys than sells so that the AMM is a net seller, sells in U ∗ U^* 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 ∗ U^* 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 U U and set of pre-approved transactions G ⊆ U G \subseteq U G ⊆ U , with G G G bilaterally admissible in U U U .
Output: Fill vector f i l l = ( f i l l i ) t i ∈ U \mathrm{fill} = (\mathrm{fill}_i)_{t_i \in U} fill = ( fill i ) t i ∈ U
Pre-approval inclusion. Set f i l l i = a m t i \mathrm{fill}_i = \mathrm{amt}_i fill i = amt i for every request in G G G and initialize all other fills to zero. Define the guaranteed net demand
g = ∑ t i ∈ G b u y s a m t i − ∑ t i ∈ G s e l l s a m t i g = \sum_{t_i \in G\ \mathrm{buys}} \mathrm{amt}_i - \sum_{t_i \in G\ \mathrm{sells}} \mathrm{amt}_i g = t i ∈ G buys ∑ amt i − t i ∈ G sells ∑ amt i
and the right-continuous augmented liquidity curve
c ~ ( ℓ ) = c ( ℓ ) + ∑ t i ∈ U ∖ G s e l l s l i m i t i ≤ ℓ a m t i − ∑ t i ∈ U ∖ G b u y s l i m i t i > ℓ a m t i . (25) \widetilde{c}(\ell) = c(\ell) + \sum_{\substack{t_i \in U \setminus G\ \mathrm{sells}\\ \mathrm{limit}_i \le\ell}} \mathrm{amt}_i - \sum_{\substack{t_i \in U \setminus G\ \mathrm{buys}\\ \mathrm{limit}_i > \ell}} \mathrm{amt}_i . \tag*{(25)} c ( ℓ ) = c ( ℓ ) + t i ∈ U ∖ G sells limit i ≤ ℓ ∑ amt i − t i ∈ U ∖ G buys limit i > ℓ ∑ amt i . (25)
Limit-matched-inclusion. Choose the cutoff ℓ ∗ = inf { ℓ : c ~ ( ℓ ) ≥ g } \ell^* = \inf\{\ell: \widetilde{c}(\ell) \ge g\} ℓ ∗ = inf { ℓ : c ( ℓ ) ≥ g } . Among requests in U ∖ G U \setminus G U ∖ G , fully fill buys with l i m i t i > ℓ ∗ \mathrm{limit}_i > \ell^* limit i > ℓ ∗ and sells with l i m i t i < ℓ ∗ \mathrm{limit}_i < \ell^* limit i < ℓ ∗ . Leave buys with limit i < ℓ ∗ \operatorname{limit}_i < \ell^* limit i < ℓ ∗ and sells with limit i > ℓ ∗ \operatorname{limit}_i > \ell^* limit i > ℓ ∗ unfilled. Define the remaining imbalance
Δ ℓ ∗ = g − c ~ ( ℓ ∗ ) + ∑ t x i ∈ U ∖ G s e l l s limit i = ℓ ∗ amt i . \Delta_{\ell^*} = g - \widetilde{c}(\ell^*) + \sum_{\substack{\mathrm{tx}_i \in U \setminus G\ \mathrm{sells}\\ \operatorname{limit}_i=\ell^*}} \operatorname{amt}_i. Δ ℓ ∗ = g − c ( ℓ ∗ ) + tx i ∈ U ∖ G sells limit i = ℓ ∗ ∑ amt i .
If Δ ℓ ∗ > 0 \Delta_{\ell^*} > 0 Δ ℓ ∗ > 0 , fill this quantity of sells with limit ℓ ∗ \ell^* ℓ ∗ ; if Δ ℓ ∗ < 0 \Delta_{\ell^*} < 0 Δ ℓ ∗ < 0 , fill − Δ ℓ ∗ -\Delta_{\ell^*} − Δ ℓ ∗ of buys with limit ℓ ∗ \ell^* ℓ ∗ . Process these requests in a fixed order by identifier, assigning each at most amt i \operatorname{amt}_i amt i until the required quantity is reached. Leave all other requests at the cutoff unfilled. Output fill = ( fill i ) t x i ∈ U \operatorname{fill} = (\operatorname{fill}_i)_{\mathrm{tx}_i \in U} fill = ( fill i ) tx i ∈ U .
Lemma 9 (Limit-satisfying prices for bilateral admissibility). If G ⊆ U G \subseteq U G ⊆ U is bilaterally admissible and fill \operatorname{fill} fill is as computed above, then there exists price such that:
all pre-approved trades are completely filled: for all t x i ∈ G \mathrm{tx}_i \in G tx i ∈ G , fill i = amt i \operatorname{fill}_i = \operatorname{amt}_i fill i = amt i ;
all limits are respected: for all t x i ∈ U \mathrm{tx}_i \in U tx i ∈ U such that fill i > 0 \operatorname{fill}_i > 0 fill i > 0 , side i = b u y ⇒ price i ≤ limit i \operatorname{side}_i = \mathrm{buy} \mathrel{\Rightarrow} \operatorname{price}_i \le\operatorname{limit}_i side i = buy ⇒ price i ≤ limit i and side i = s e l l ⇒ price i ≥ limit i \operatorname{side}_i = \mathrm{sell} \mathrel{\Rightarrow} \operatorname{price}_i \ge\operatorname{limit}_i side i = sell ⇒ price i ≥ limit i ;
the AMM’s revenue is exactly P ( x ) P(x) P ( x ) where x : = ∑ t x i ∈ U b u y s fill i − ∑ t x i ∈ U s e l l s fill i x := \sum_{\mathrm{tx}_i \in U\ \mathrm{buys}} \operatorname{fill}_i - \sum_{\mathrm{tx}_i \in U\ \mathrm{sells}} \operatorname{fill}_i x := ∑ tx i ∈ U buys fill i − ∑ tx i ∈ U sells fill i is the net purchase quantity;
prices are monotonic: for all t x i , t x j ∈ U \mathrm{tx}_i,\mathrm{tx}_j \in U tx i , tx j ∈ U such that fill i > 0 \operatorname{fill}_i > 0 fill i > 0 and side i = side j \operatorname{side}_i = \operatorname{side}_j side i = side j , limit i ≤ limit j ⇒ price i ≤ price j \operatorname{limit}_i \le\operatorname{limit}_j \mathrel{\Rightarrow} \operatorname{price}_i \le\operatorname{price}_j limit i ≤ limit j ⇒ price i ≤ price j .
Proof. We first justify that the cutoff ℓ ∗ \ell^* ℓ ∗ exists and is finite. For this argument, let a = min ( { p ( 0 ) } ∪ { limit i : t x i ∈ U } ) a = \min(\{p(0)\} \cup\{\operatorname{limit}_i : \mathrm{tx}_i \in U\}) a = min ({ p ( 0 )} ∪ { limit i : tx i ∈ U }) and b = max ( { p ( 0 ) } ∪ { limit i : t x i ∈ U } ) b = \max(\{p(0)\} \cup\{\operatorname{limit}_i : \mathrm{tx}_i \in U\}) b = max ({ p ( 0 )} ∪ { limit i : tx i ∈ U }) . Since c ( a ) ≤ 0 c(a) \le0 c ( a ) ≤ 0 and every request has limit at least a a a , Equation (22) at a a a gives
c ~ ( a − ) = c ( a ) − ∑ t x i ∈ U ∖ G b u y s amt i ≤ g . \widetilde{c}(a^-) = c(a) - \sum_{\substack{\mathrm{tx}_i \in U \setminus G\\ \mathrm{buys}}} \operatorname{amt}_i \le g. c ( a − ) = c ( a ) − tx i ∈ U ∖ G buys ∑ amt i ≤ g .
Similarly, c ( b ) ≥ 0 c(b) \ge0 c ( b ) ≥ 0 and every request has limit at most b b b , so Equation (21) at b b b gives
g ≤ c ( b ) + ∑ t x i ∈ U ∖ G s e l l s amt i = c ~ ( b ) . g \le c(b) + \sum_{\substack{\mathrm{tx}_i \in U \setminus G\\ \mathrm{sells}}} \operatorname{amt}_i = \widetilde{c}(b). g ≤ c ( b ) + tx i ∈ U ∖ G sells ∑ amt i = c ( b ) .
For every ℓ < a \ell< a ℓ < a , strict monotonicity of c = p − 1 c = p^{-1} c = p − 1 gives
c ~ ( ℓ ) = c ( ℓ ) − ∑ t x i ∈ U ∖ G b u y s amt i < c ~ ( a − ) ≤ g . \widetilde{c}(\ell) = c(\ell) - \sum_{\substack{\mathrm{tx}_i \in U \setminus G\\ \mathrm{buys}}} \operatorname{amt}_i < \widetilde{c}(a^-) \le g. c ( ℓ ) = c ( ℓ ) − tx i ∈ U ∖ G buys ∑ amt i < c ( a − ) ≤ g .
Thus the set defining the cutoff is nonempty and has no element below a a a , so its infimum lies in [ a , b ] [a,b] [ a , b ] . Second, we show that there are enough trades with limit exactly ℓ ∗ \ell^* ℓ ∗ to fill the quantity ± Δ ℓ ∗ \pm\Delta_{\ell^*} ± Δ ℓ ∗ . The curve c ~ \widetilde{c} c is nondecreasing and right-continuous, with only upward jumps. Consequently,
c ~ ( ℓ ∗ − ) ≤ g ≤ c ~ ( ℓ ∗ ) . \widetilde{c}(\ell^*-) \le g \le\widetilde{c}(\ell^*). c ( ℓ ∗ − ) ≤ g ≤ c ( ℓ ∗ ) .
Here the left-hand value includes buys at the cutoff and excludes sells at the cutoff. Consequently,
− ∑ t x i ∈ U ∖ G b u y s l i m i t i = ℓ ∗ a m t i ≤ Δ ℓ ∗ ≤ ∑ t x i ∈ U ∖ G s e l l s l i m i t i = ℓ ∗ a m t i . -\sum_{\substack{tx_i\in U\setminus G\ \mathrm{buys}\\ \mathrm{limit}_i=\ell^*}} \mathrm{amt}_i \le\Delta_{\ell^*} \le\sum_{\substack{tx_i\in U\setminus G\ \mathrm{sells}\\ \mathrm{limit}_i=\ell^*}} \mathrm{amt}_i. − t x i ∈ U ∖ G buys limit i = ℓ ∗ ∑ amt i ≤ Δ ℓ ∗ ≤ t x i ∈ U ∖ G sells limit i = ℓ ∗ ∑ amt i .
There is therefore enough volume at the cutoff to fill ± Δ ℓ ∗ \pm\Delta_{\ell^*} ± Δ ℓ ∗ while respecting every request’s quantity bound.
Price construction. Let U ∗ U^* U ∗ be the set of executed requests. Their net asset purchase is
x = ∑ t x i ∈ U ∗ b u y s f i l l i − ∑ t x i ∈ U ∗ s e l l s f i l l i = c ( ℓ ∗ ) . x=\sum_{tx_i\in U^*\ \mathrm{buys}}\mathrm{fill}_i-\sum_{tx_i\in U^*\ \mathrm{sells}}\mathrm{fill}_i=c(\ell^*). x = t x i ∈ U ∗ buys ∑ fill i − t x i ∈ U ∗ sells ∑ fill i = c ( ℓ ∗ ) .
Define the AMM’s executed volume with marginal price at most ℓ \ell ℓ by
F A M M ( ℓ ) = ∣ ∫ 0 x 1 { p ( v ) ≤ ℓ } d v ∣ . F_{\mathrm{AMM}}(\ell)=\left|\int_0^x \mathbf{1}_{\{p(v)\le\ell\}}\,dv\right|. F AMM ( ℓ ) = ∫ 0 x 1 { p ( v ) ≤ ℓ } d v .
We now define two distribution functions that represent the set of buy and sell limit prices that will execute as actual trades, including the liquidity supplied by the AMM.
F U ∗ , b u y ( ℓ ) = ∑ t x i ∈ U ∗ b u y s l i m i t i ≤ ℓ f i l l i + 1 { x < 0 } F A M M ( ℓ ) , (26) F_{U^*,\mathrm{buy}}(\ell)=\sum_{\substack{tx_i\in U^*\ \mathrm{buys}\\ \mathrm{limit}_i\le\ell}}\mathrm{fill}_i+\mathbf{1}_{\{x<0\}}F_{\mathrm{AMM}}(\ell), \tag*{(26)} F U ∗ , buy ( ℓ ) = t x i ∈ U ∗ buys limit i ≤ ℓ ∑ fill i + 1 { x < 0 } F AMM ( ℓ ) , (26)
F U ∗ , s e l l ( ℓ ) = ∑ t x i ∈ U ∗ s e l l s l i m i t i ≤ ℓ f i l l i + 1 { x > 0 } F A M M ( ℓ ) , (27) F_{U^*,\mathrm{sell}}(\ell)=\sum_{\substack{tx_i\in U^*\ \mathrm{sells}\\ \mathrm{limit}_i\le\ell}}\mathrm{fill}_i+\mathbf{1}_{\{x>0\}}F_{\mathrm{AMM}}(\ell), \tag*{(27)} F U ∗ , sell ( ℓ ) = t x i ∈ U ∗ sells limit i ≤ ℓ ∑ fill i + 1 { x > 0 } F AMM ( ℓ ) , (27)
The total buy and sell quantities are equal, i.e., F U ∗ , b u y ( ∞ ) = F U ∗ , s e l l ( ∞ ) = M F_{U^*,\mathrm{buy}}(\infty)=F_{U^*,\mathrm{sell}}(\infty)=M F U ∗ , buy ( ∞ ) = F U ∗ , sell ( ∞ ) = M , and all liquidity F A M M ( ℓ ) F_{\mathrm{AMM}}(\ell) F AMM ( ℓ ) is only added on one side to meet the quantity imbalance in U ∗ U^* U ∗ between buys and sells.
Define the inverse functions F U ∗ , b u y − 1 ( u ) F^{-1}_{U^*,\mathrm{buy}}(u) F U ∗ , buy − 1 ( u ) with F U ∗ , s e l l − 1 ( u ) F^{-1}_{U^*,\mathrm{sell}}(u) F U ∗ , sell − 1 ( u ) where F − 1 ( u ) = inf { ℓ : F ( ℓ ) ≥ u } F^{-1}(u)=\inf\{\ell:F(\ell)\ge u\} F − 1 ( u ) = inf { ℓ : F ( ℓ ) ≥ u } .
If x ≥ 0 x\ge0 x ≥ 0 , assign p r i c e i = l i m i t i \mathrm{price}_i=\mathrm{limit}_i price i = limit i for each sell in U ∗ U^* U ∗ . Sort all buys in U ∗ U^* U ∗ by limit prices, treating buys with a tied limit price as a single larger buy. For the i i i -th buy, let I i : = [ ∑ j = 1 i − 1 f i l l j , ∑ j = 1 i f i l l j ] I_i:=\left[\sum_{j=1}^{i-1}\mathrm{fill}_j,\sum_{j=1}^{i}\mathrm{fill}_j\right] I i := [ ∑ j = 1 i − 1 fill j , ∑ j = 1 i fill j ] be the interval it occupies in the sorted order. Set the i i i -th buy’s price as
p r i c e i = 1 f i l l i ∫ I i F U ∗ , s e l l − 1 ( u ) d u . \mathrm{price}_i=\frac{1}{\mathrm{fill}_i}\int_{I_i}F^{-1}_{U^*,\mathrm{sell}}(u)\,du. price i = fill i 1 ∫ I i F U ∗ , sell − 1 ( u ) d u .
If x < 0 x<0 x < 0 , assign p r i c e i = l i m i t i \mathrm{price}_i=\mathrm{limit}_i price i = limit i for each buy in U ∗ U^* U ∗ . Sort all sells in U ∗ U^* U ∗ by limit prices, also merging tied limit prices into a single sell. For the i i i -th sell, let I i : = [ ∑ j = 1 i − 1 f i l l j , ∑ j = 1 i f i l l j ] I_i:=\left[\sum_{j=1}^{i-1}\mathrm{fill}_j,\sum_{j=1}^{i}\mathrm{fill}_j\right] I i := [ ∑ j = 1 i − 1 fill j , ∑ j = 1 i fill j ] be the interval it occupies in the sorted order. Set the i i i -th sell’s price as
p r i c e i = 1 f i l l i ∫ I i F U ∗ , b u y − 1 ( u ) d u . \mathrm{price}_i=\frac{1}{\mathrm{fill}_i}\int_{I_i}F^{-1}_{U^*,\mathrm{buy}}(u)\,du. price i = fill i 1 ∫ I i F U ∗ , buy − 1 ( u ) d u .
A buyer pays f i l l i p r i c e i \mathrm{fill}_i\mathrm{price}_i fill i price i and a seller receives f i l l i p r i c e i \mathrm{fill}_i\mathrm{price}_i fill i price i .
Limit validity. If we can show that F U ∗ , s e l l − 1 ( u ) ≤ F U ∗ , b u y − 1 ( u ) F^{-1}_{U^*,\mathrm{sell}}(u) \le F^{-1}_{U^*,\mathrm{buy}}(u) F U ∗ , sell − 1 ( u ) ≤ F U ∗ , buy − 1 ( u ) , then executing at the above price satisfies limits. This is because the i i i -th buy’s price is exactly l i m i t i \mathrm{limit}_i limit i when x < 0 x<0 x < 0 and when x ≥ 0 x\geq0 x ≥ 0 ,
p r i c e i = 1 f i l l i ∫ I i F U ∗ , s e l l − 1 ( u ) d u ≤ 1 f i l l i ∫ I i F U ∗ , b u y − 1 ( u ) d u = l i m i t i , \mathrm{price}_i=\frac{1}{\mathrm{fill}_i}\int_{I_i}F^{-1}_{U^*,\mathrm{sell}}(u)\,\mathrm{d}u\leq\frac{1}{\mathrm{fill}_i}\int_{I_i}F^{-1}_{U^*,\mathrm{buy}}(u)\,\mathrm{d}u=\mathrm{limit}_i, price i = fill i 1 ∫ I i F U ∗ , sell − 1 ( u ) d u ≤ fill i 1 ∫ I i F U ∗ , buy − 1 ( u ) d u = limit i ,
Similarly, when x < 0 x<0 x < 0 , for the i i i -th sell,
l i m i t i = 1 f i l l i ∫ I i F U ∗ , s e l l − 1 ( u ) d u ≤ 1 f i l l i ∫ I i F U ∗ , b u y − 1 ( u ) d u = p r i c e i . \mathrm{limit}_i=\frac{1}{\mathrm{fill}_i}\int_{I_i}F^{-1}_{U^*,\mathrm{sell}}(u)\,\mathrm{d}u\leq\frac{1}{\mathrm{fill}_i}\int_{I_i}F^{-1}_{U^*,\mathrm{buy}}(u)\,\mathrm{d}u=\mathrm{price}_i. limit i = fill i 1 ∫ I i F U ∗ , sell − 1 ( u ) d u ≤ fill i 1 ∫ I i F U ∗ , buy − 1 ( u ) d u = price i .
We prove the equivalent statement that F U ∗ , b u y ( ℓ ) ≤ F U ∗ , s e l l ( ℓ ) F_{U^*,\mathrm{buy}}(\ell)\leq F_{U^*,\mathrm{sell}}(\ell) F U ∗ , buy ( ℓ ) ≤ F U ∗ , sell ( ℓ ) pointwise. For ℓ < ℓ ∗ \ell<\ell^* ℓ < ℓ ∗ , executed buys with limits at most ℓ \ell ℓ are exactly the corresponding buys in G G G , and all available sells with limits at most ℓ \ell ℓ in U U U fill completely. Since c ( ℓ ) ≤ x = c ( ℓ ∗ ) c(\ell)\leq x=c(\ell^*) c ( ℓ ) ≤ x = c ( ℓ ∗ ) , the definition of F A M M F_{\mathrm{AMM}} F AMM gives
1 { x < 0 } F A M M ( ℓ ) = 0 , 1 { x > 0 } F A M M ( ℓ ) = [ c ( ℓ ) ] + . \mathbf{1}_{\{x<0\}}F_{\mathrm{AMM}}(\ell)=0,\qquad\mathbf{1}_{\{x>0\}}F_{\mathrm{AMM}}(\ell)=[c(\ell)]_+. 1 { x < 0 } F AMM ( ℓ ) = 0 , 1 { x > 0 } F AMM ( ℓ ) = [ c ( ℓ ) ] + .
Thus inequality (21) gives F U ∗ , b u y ( ℓ ) ≤ F U ∗ , s e l l ( ℓ ) F_{U^*,\mathrm{buy}}(\ell)\leq F_{U^*,\mathrm{sell}}(\ell) F U ∗ , buy ( ℓ ) ≤ F U ∗ , sell ( ℓ ) . For ℓ ≥ ℓ ∗ \ell\geq\ell^* ℓ ≥ ℓ ∗ , we instead have c ( ℓ ) ≥ x c(\ell)\geq x c ( ℓ ) ≥ x , so
1 { x > 0 } ( ∣ x ∣ − F A M M ( ℓ ) ) = 0 , \mathbf{1}_{\{x>0\}}\left(|x|-F_{\mathrm{AMM}}(\ell)\right)=0, 1 { x > 0 } ( ∣ x ∣ − F AMM ( ℓ ) ) = 0 ,
1 { x < 0 } ( ∣ x ∣ − F A M M ( ℓ ) ) = [ − c ( ℓ ) ] + . \mathbf{1}_{\{x<0\}}\left(|x|-F_{\mathrm{AMM}}(\ell)\right)=[-c(\ell)]_+. 1 { x < 0 } ( ∣ x ∣ − F AMM ( ℓ ) ) = [ − c ( ℓ ) ] + .
Equal total mass and the cutoff rule for filling trades on each side of ℓ ∗ \ell^* ℓ ∗ therefore give
F U ∗ , b u y ( ℓ ) − F U ∗ , s e l l ( ℓ ) = ∑ t x j ∈ G s e l l s l i m i t j > ℓ a m t j − ∑ t x i ∈ U b u y s l i m i t i > ℓ a m t i − 1 { x < 0 } ( ∣ x ∣ − F A M M ( ℓ ) ) ≤ 0 , \begin{aligned}
F_{U^*,\mathrm{buy}}(\ell)-F_{U^*,\mathrm{sell}}(\ell)
={}&\sum_{\substack{t x_j\in G\ \mathrm{sells}\\ \mathrm{limit}_j>\ell}}\mathrm{amt}_j-\sum_{\substack{t x_i\in U\ \mathrm{buys}\\ \mathrm{limit}_i>\ell}}\mathrm{amt}_i\\
&-\mathbf{1}_{\{x<0\}}\left(|x|-F_{\mathrm{AMM}}(\ell)\right)\leq0,
\end{aligned} F U ∗ , buy ( ℓ ) − F U ∗ , sell ( ℓ ) = t x j ∈ G sells limit j > ℓ ∑ amt j − t x i ∈ U buys limit i > ℓ ∑ amt i − 1 { x < 0 } ( ∣ x ∣ − F AMM ( ℓ ) ) ≤ 0 ,
where the inequality follows from (22) applied just above ℓ \ell ℓ . Thus F U ∗ , b u y ≤ F U ∗ , s e l l F_{U^*,\mathrm{buy}}\leq F_{U^*,\mathrm{sell}} F U ∗ , buy ≤ F U ∗ , sell everywhere.
AMM payment and price monotonicity. If x ≥ 0 x\geq0 x ≥ 0 , total buyer payments are
∫ 0 M F U ∗ , s e l l − 1 ( u ) d u = ∑ t x i ∈ U ∗ s e l l s f i l l i l i m i t i + P ( x ) , \int_0^M F^{-1}_{U^*,\mathrm{sell}}(u)\,\mathrm{d}u=\sum_{\substack{t x_i\in U^*\ \mathrm{sells}}}\mathrm{fill}_i\mathrm{limit}_i+P(x), ∫ 0 M F U ∗ , sell − 1 ( u ) d u = t x i ∈ U ∗ sells ∑ fill i limit i + P ( x ) ,
since the sell distribution includes the AMM’s supply at marginal prices p ( v ) p(v) p ( v ) for v ∈ [ 0 , x ] v\in[0,x] v ∈ [ 0 , x ] . After paying trader sellers at their limits, the AMM retains P ( x ) P(x) P ( x ) . If x < 0 x<0 x < 0 , total seller receipts are
∫ 0 M F U ∗ , b u y − 1 ( u ) d u = ∑ t x i ∈ U ∗ b u y s f i l l i l i m i t i − P ( x ) , \int_0^M F^{-1}_{U^*,\mathrm{buy}}(u)\,\mathrm{d}u=\sum_{\substack{t x_i\in U^*\ \mathrm{buys}}}\mathrm{fill}_i\mathrm{limit}_i-P(x), ∫ 0 M F U ∗ , buy − 1 ( u ) d u = t x i ∈ U ∗ buys ∑ fill i limit i − P ( x ) ,
since the AMM’s buy orders have total value ∫ x 0 p ( v ) d v = − P ( x ) \int_x^0p(v)\,\mathrm{d}v=-P(x) ∫ x 0 p ( v ) d v = − P ( x ) . Subtracting these receipts from trader buyers’ payments again gives a net AMM receipt of P ( x ) P(x) P ( x ) . Finally, both F U ∗ , b u y − 1 F^{-1}_{U^*,\mathrm{buy}} F U ∗ , buy − 1 and F U ∗ , s e l l − 1 F^{-1}_{U^*,\mathrm{sell}} F U ∗ , sell − 1 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 I i I_i I i . 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 η \eta η -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 = ( R A , R C ) R=(R_A,R_C) R = ( R A , R C ) be the post-trade reserves in the AMM and Λ > 0 \Lambda>0 Λ > 0 the outstanding LP shares before processing these requests. All conversions use this same snapshot:
A withdrawal burns its locked w w w shares and receives ( w / Λ ) R (w/\Lambda)R ( w /Λ ) R .
A deposit with locked asset caps ( d A , d C ) (d_A,d_C) ( d A , d C ) mints
m = Λ min { d A / R A , d C / R C } . m=\Lambda\min\{d_A/R_A,\ d_C/R_C\}. m = Λ min { d A / R A , d C / R C } .
contributes ( m / Λ ) R (m/\Lambda)R ( 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.
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 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.
Table 1. Glossary of main notation used in Section 2.
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 ) \varepsilon(r) ε ( r ) chooses a cutoff p e x ∗ ( s ) p_{\mathrm{ex}}^*(s) p ex ∗ ( s ) , at which a mass s s s has traded and the AMM price is p ( s ) p(s) p ( s ) , to maximize
e − γ d i f f [ p e x ∗ ( s ) − p e x , 0 ] [ p e x ∗ ( s ) + ε ( r ) − p ( s ) ] . (28) e^{-\gamma_{\mathrm{diff}}[p_{\mathrm{ex}}^*(s)-p_{\mathrm{ex},0}]}\left[p_{\mathrm{ex}}^*(s)+\varepsilon(r)-p(s)\right]. \tag*{(28)} e − γ diff [ p ex ∗ ( s ) − p ex , 0 ] [ p ex ∗ ( s ) + ε ( r ) − p ( s ) ] . (28)
Differentiating with respect to s s s and evaluating at s = r s=r s = r gives
γ d i f f [ p e x ∗ ( r ) + ε ( r ) − p ( r ) ] = 1 − p ′ ( r ) p e x ∗ ( r ) . (29) \gamma_{\mathrm{diff}}\left[p_{\mathrm{ex}}^*(r)+\varepsilon(r)-p(r)\right]=1-\frac{p'(r)}{p_{\mathrm{ex}}^*(r)}. \tag*{(29)} γ diff [ p ex ∗ ( r ) + ε ( r ) − p ( r ) ] = 1 − p ex ∗ ( r ) p ′ ( r ) . (29)
Constant markup. For p e x ∗ ( r ) = p ( r ) − ε ( r ) + c p_{\mathrm{ex}}^{*}(r)=p(r)-\varepsilon(r)+c p ex ∗ ( r ) = p ( r ) − ε ( r ) + c and p ′ ( r ) = − κ ε ′ ( r ) p^{\prime}(r)=-\kappa\varepsilon^{\prime}(r) p ′ ( r ) = − κ ε ′ ( r ) , we have p e x ∗ ′ ( r ) = − ( 1 + κ ) ε ′ ( r ) p_{\mathrm{ex}}^{*\prime}(r)=-(1+\kappa)\varepsilon^{\prime}(r) p ex ∗ ′ ( r ) = − ( 1 + κ ) ε ′ ( r ) . The FOC becomes
γ d i f f c = 1 − κ 1 + κ ⟹ c = 1 γ d i f f ( 1 + κ ) , (30) \gamma_{\mathrm{diff}}c=1-\frac{\kappa}{1+\kappa}\quad\Longrightarrow\quad c=\frac{1}{\gamma_{\mathrm{diff}}(1+\kappa)}, \tag*{(30)} γ diff c = 1 − 1 + κ κ ⟹ c = γ diff ( 1 + κ ) 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
W F S d i f f = ∫ 0 1 ε ( r ) Pr F S d i f f ( r ) d r . (31) \mathcal{W}_{\mathrm{FS}}^{\mathrm{diff}}=\int_{0}^{1}\varepsilon(r)\Pr_{\mathrm{FS}}^{\mathrm{diff}}(r)\,dr. \tag*{(31)} W FS diff = ∫ 0 1 ε ( r ) FS Pr diff ( r ) d r . (31)
For AMM gains from trade, let τ r \tau_r τ r be the first time p e x , t p_{\mathrm{ex},t} p ex , t reaches p e x ∗ ( r ) p_{\mathrm{ex}}^{*}(r) p ex ∗ ( r ) . Conditional on τ r < T b l k \tau_r<T_{\mathrm{blk}} τ r < T blk , exponential memorylessness and the strong Markov property imply
E [ p e x , T b l k ∣ τ r < T b l k ] = p e x ∗ ( r ) . (32) \mathbb{E}[p_{\mathrm{ex},T_{\mathrm{blk}}}\mid\tau_r<T_{\mathrm{blk}}]=p_{\mathrm{ex}}^{*}(r). \tag*{(32)} E [ p ex , T blk ∣ τ r < T blk ] = p ex ∗ ( r ) . (32)
Thus the expected AMM markout on a filled type-r r r trade is p ( r ) − p e x ∗ ( r ) p(r)-p_{\mathrm{ex}}^{*}(r) p ( r ) − p ex ∗ ( r ) , giving
R F S d i f f = ∫ 0 1 [ p ( r ) − p e x ∗ ( r ) ] Pr F S d i f f ( r ) d r . (33) \mathcal{R}_{\mathrm{FS}}^{\mathrm{diff}}=\int_{0}^{1}[p(r)-p_{\mathrm{ex}}^{*}(r)]\Pr_{\mathrm{FS}}^{\mathrm{diff}}(r)\,dr. \tag*{(33)} R FS diff = ∫ 0 1 [ p ( r ) − p ex ∗ ( r )] FS Pr diff ( r ) d r . (33)
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 ∈ { F S , F I F O , b a t c h } \mathbf{m}\in\{\mathrm{FS},\mathrm{FIFO},\mathrm{batch}\} m ∈ { FS , FIFO , batch } . Write e e e for private value, a ( e ) : = Pr m j u m p ( 1 − F ε ( e ) ) a(e):=\Pr_{\mathbf{m}}^{\mathrm{jump}}(1-F_{\varepsilon}(e)) a ( e ) := Pr m jump ( 1 − F ε ( e )) for its interim allocation probability, and t ( e ) t(e) t ( e ) for expected payment. The expected utility of a trader given its type e e e is
u ( e ) = ( p e x , j u m p + e ) a ( e ) − t ( e ) . u(e)=(p_{\mathrm{ex,jump}}+e)a(e)-t(e). u ( e ) = ( p ex , 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 ′ ) a(e^{\prime}),t(e^{\prime}) a ( e ′ ) , t ( e ′ ) , we have the first-order condition u ′ ( e ) = a ( e ) u^{\prime}(e)=a(e) u ′ ( e ) = a ( e ) . So long as the distribution F ε F_{\varepsilon} F ε has support on types who do not want to trade, u ( e ) → 0 u(e)\to0 u ( e ) → 0 as e → − ∞ e\to-\infty e → − ∞ , and hence
t ( e ) − p e x , j u m p a ( e ) = e a ( e ) − ∫ − ∞ e a ( s ) d s . t(e)-p_{\mathrm{ex,jump}}a(e)=ea(e)-\int_{-\infty}^{e}a(s)\,ds. t ( e ) − p ex , jump a ( e ) = e a ( e ) − ∫ − ∞ e a ( s ) d s .
Integrating over F ε F_{\varepsilon} F ε and applying Fubini gives
R m j u m p = ∫ [ e − 1 − F ε ( e ) f ε ( e ) ] a ( e ) d F ε ( e ) . \mathcal{R}_{\mathbf{m}}^{\mathrm{jump}}=\int\left[e-\frac{1-F_{\varepsilon}(e)}{f_{\varepsilon}(e)}\right]a(e)\,dF_{\varepsilon}(e). R m jump = ∫ [ e − f ε ( e ) 1 − F ε ( e ) ] a ( e ) d F ε ( e ) .
Since r = 1 − F ε ( e ) r=1-F_{\varepsilon}(e) r = 1 − F ε ( e ) and ε ′ ( r ) = − 1 / f ε ( ε ( r ) ) \varepsilon^{\prime}(r)=-1/f_{\varepsilon}(\varepsilon(r)) ε ′ ( r ) = − 1/ f ε ( ε ( r )) , this is the stated rank formula. The welfare formula follows directly because, conditional on p e x , j u m p p_{\mathrm{ex,jump}} p ex , jump , allocating the asset to type e e e contributes the mechanism-dependent surplus e e e . ⊓⊔
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 z z , define
w ( z ) = 1 p ′ ( p − 1 ( z ) ) , α ( z ) = − w ′ ( z ) w ( z ) = p ′ ′ ( p − 1 ( z ) ) p ′ ( p − 1 ( z ) ) 2 , H ( z ) = 1 α ( z ) . w(z) = \frac{1}{p'(p^{-1}(z))}, \qquad\alpha(z) = -\frac{w'(z)}{w(z)} = \frac{p''(p^{-1}(z))}{p'(p^{-1}(z))^2}, \qquad\mathcal{H}(z) = \frac{1}{\alpha(z)}. w ( z ) = p ′ ( p − 1 ( z )) 1 , α ( z ) = − w ( z ) w ′ ( z ) = p ′ ( p − 1 ( z ) ) 2 p ′′ ( p − 1 ( z )) , H ( z ) = α ( z ) 1 .
The AMM assumption gives
H ′ ( z ) = 2 − C ( p − 1 ( z ) ) ∈ [ 0 , 1 ] , H is concave . (34) \mathcal{H}'(z) = 2 - C(p^{-1}(z)) \in[0,1], \qquad\mathcal{H}\text{ is concave}. \tag*{(34)} H ′ ( z ) = 2 − C ( p − 1 ( z )) ∈ [ 0 , 1 ] , H is concave . (34)
On the common interior allocation range, write θ = p e x , j u m p + e \theta= p_{\mathrm{ex,jump}} + e θ = p ex , jump + e , p b i d ( e ) = p b i d , F S j u m p ( r ( e ) ) p_{\mathrm{bid}}(e) = p_{\mathrm{bid,FS}}^{\mathrm{jump}}(r(e)) p bid ( e ) = p bid , FS jump ( r ( e )) , and δ = θ − p b i d ( e ) > 0 \delta= \theta- p_{\mathrm{bid}}(e) > 0 δ = θ − p bid ( e ) > 0 . Here p b i d p_{\mathrm{bid}} p bid abbreviates p b i d ( e ) p_{\mathrm{bid}}(e) p bid ( e ) , and p b i d ′ ( e ) p'_{\mathrm{bid}}(e) p bid ′ ( e ) denotes differentiation with respect to private value, not rank. The queue formulas and the differentiated first-price FOC give
d d e Pr F I F O j u m p ( r ( e ) ) = w ( θ ) F ‾ ε ( e ) , d d e Pr F S j u m p ( r ( e ) ) = p b i d ′ ( e ) w ( p b i d ) F ‾ ε ( e ) , \frac{d}{de}\Pr_{\mathrm{FIFO}}^{\mathrm{jump}}(r(e)) = \frac{w(\theta)}{\overline{F}_{\varepsilon}(e)}, \qquad\frac{d}{de}\Pr_{\mathrm{FS}}^{\mathrm{jump}}(r(e)) = \frac{p'_{\mathrm{bid}}(e)w(p_{\mathrm{bid}})}{\overline{F}_{\varepsilon}(e)}, d e d FIFO Pr jump ( r ( e )) = F ε ( e ) w ( θ ) , d e d FS Pr jump ( r ( e )) = F ε ( e ) p bid ′ ( e ) w ( p bid ) ,
p b i d ′ ( e ) = 1 + δ h ε ( e ) 2 + δ α ( p b i d ) . (35) p'_{\mathrm{bid}}(e) = \frac{1+\delta h_{\varepsilon}(e)}{2+\delta\alpha(p_{\mathrm{bid}})}. \tag*{(35)} p bid ′ ( e ) = 2 + δ α ( p bid ) 1 + δ h ε ( e ) . (35)
Thus, defining the allocation difference and its slope ratio by
Δ ( e ) = Pr F S j u m p ( r ( e ) ) − Pr F I F O j u m p ( r ( e ) ) , \Delta(e) = \Pr_{\mathrm{FS}}^{\mathrm{jump}}(r(e)) - \Pr_{\mathrm{FIFO}}^{\mathrm{jump}}(r(e)), Δ ( e ) = FS Pr jump ( r ( e )) − FIFO Pr jump ( r ( e )) ,
D ( e ) = d d e Pr F S j u m p ( r ( e ) ) d d e Pr F I F O j u m p ( r ( e ) ) = w ( p b i d ) w ( θ ) 1 + δ h ε ( e ) 2 + δ α ( p b i d ) , \mathcal{D}(e) = \frac{\frac{d}{de}\Pr_{\mathrm{FS}}^{\mathrm{jump}}(r(e))}{\frac{d}{de}\Pr_{\mathrm{FIFO}}^{\mathrm{jump}}(r(e))} = \frac{w(p_{\mathrm{bid}})}{w(\theta)}\frac{1+\delta h_{\varepsilon}(e)}{2+\delta\alpha(p_{\mathrm{bid}})}, D ( e ) = d e d Pr FIFO jump ( r ( e )) d e d Pr FS jump ( r ( e )) = w ( θ ) w ( p bid ) 2 + δ α ( p bid ) 1 + δ h ε ( e ) ,
we have Δ ′ ( e ) = w ( θ ) [ D ( e ) − 1 ] / F ‾ ε ( e ) \Delta'(e) = w(\theta)[\mathcal{D}(e)-1]/\overline{F}_{\varepsilon}(e) Δ ′ ( e ) = w ( θ ) [ D ( e ) − 1 ] / F ε ( e ) . All derivatives of Δ \Delta Δ and D \mathcal{D} D below are with respect to e e e .
We show that D ′ > 0 \mathcal{D}' > 0 D ′ > 0 whenever D = 1 \mathcal{D}=1 D = 1 . At such a point, set
a = δ α ( p b i d ) > 0 , k = p b i d ′ ( e ) = w ( θ ) w ( p b i d ) , N = 1 + δ h ε ( e ) = k ( 2 + a ) , β = H ′ ( p b i d ) ∈ [ 0 , 1 ] . a = \delta\alpha(p_{\mathrm{bid}})>0, \qquad k = p'_{\mathrm{bid}}(e) = \frac{w(\theta)}{w(p_{\mathrm{bid}})}, \qquad N = 1+\delta h_{\varepsilon}(e) = k(2+a), \qquad\beta= \mathcal{H}'(p_{\mathrm{bid}})\in[0,1]. a = δ α ( p bid ) > 0 , k = p bid ′ ( e ) = w ( p bid ) w ( θ ) , N = 1 + δ h ε ( e ) = k ( 2 + a ) , β = H ′ ( p bid ) ∈ [ 0 , 1 ] .
Since N ≥ 1 N\geq1 N ≥ 1 and H ′ ≤ 1 \mathcal{H}'\leq1 H ′ ≤ 1 ,
1 2 + a ≤ k = exp { − ∫ p b i d θ α ( z ) d z } ≤ 1 1 + a . (36) \frac{1}{2+a}\leq k=\exp\left\{-\int_{p_{\mathrm{bid}}}^{\theta}\alpha(z)\,dz\right\}\leq\frac{1}{1+a}. \tag*{(36)} 2 + a 1 ≤ k = exp { − ∫ p bid θ α ( z ) d z } ≤ 1 + a 1 . (36)
Differentiating D \mathcal{D} D at this point yields
δ N D ′ D = ( 1 − k ) ( 2 k − 1 ) + δ 2 h ε ′ ( e ) − δ 2 α ′ ( p b i d ) k 2 + δ N [ α ( θ ) − α ( p b i d ) k ] . (37) \delta N\frac{\mathcal{D}'}{\mathcal{D}} = (1-k)(2k-1)+\delta^2h'_{\varepsilon}(e)-\delta^2\alpha'(p_{\mathrm{bid}})k^2+\delta N[\alpha(\theta)-\alpha(p_{\mathrm{bid}})k]. \tag*{(37)} δ N D D ′ = ( 1 − k ) ( 2 k − 1 ) + δ 2 h ε ′ ( e ) − δ 2 α ′ ( p bid ) k 2 + δ N [ α ( θ ) − α ( p bid ) k ] . (37)
Here derivatives of α \alpha α are with respect to price. Increasing hazard gives h ε ′ ≥ 0 h_{\varepsilon}' \ge0 h ε ′ ≥ 0 , while concavity of H \mathcal{H} H gives α ( θ ) ≥ α ( p b i d ) / ( 1 + β a ) \alpha(\theta) \ge\alpha(p_{\mathrm{bid}})/(1+\beta a) α ( θ ) ≥ α ( p bid ) / ( 1 + β a ) and − δ 2 α ′ ( p b i d ) = β a 2 -\delta^{2}\alpha'(p_{\mathrm{bid}})=\beta a^{2} − δ 2 α ′ ( p bid ) = β a 2 . Therefore
δ N D ′ D ≥ ( 1 − k ) ( 2 k − 1 ) + β a 2 k 2 + a k ( 2 + a ) [ 1 1 + β a − k ] . \delta N\frac{D'}{D}\ge(1-k)(2k-1)+\beta a^{2}k^{2}+ak(2+a)\left[\frac{1}{1+\beta a}-k\right]. δ N D D ′ ≥ ( 1 − k ) ( 2 k − 1 ) + β a 2 k 2 + ak ( 2 + a ) [ 1 + β a 1 − k ] .
The right side decreases in β \beta β : its derivative is a 2 k [ k − ( 2 + a ) / ( 1 + β a ) 2 ] < 0 a^{2}k\left[k-(2+a)/(1+\beta a)^{2}\right]<0 a 2 k [ k − ( 2 + a ) / ( 1 + β a ) 2 ] < 0 by (36). Setting β = 1 \beta=1 β = 1 hence gives
δ N D ′ D ≥ L a ( k ) : = − 1 + [ 3 + a ( 2 + a ) 1 + a ] k − 2 ( 1 + a ) k 2 . \delta N\frac{D'}{D}\ge L_{a}(k):=-1+\left[3+\frac{a(2+a)}{1+a}\right]k-2(1+a)k^{2}. δ N D D ′ ≥ L a ( k ) := − 1 + [ 3 + 1 + a a ( 2 + a ) ] k − 2 ( 1 + a ) k 2 .
This quadratic is concave, and at the endpoints of the permitted interval,
L a ( 1 2 + a ) = a ( 2 + a ) 2 ( 1 + a ) > 0 , L a ( 1 1 + a ) = a ( 1 + a ) 2 > 0. L_{a}\left(\frac{1}{2+a}\right)=\frac{a}{(2+a)^{2}(1+a)}>0,\qquad L_{a}\left(\frac{1}{1+a}\right)=\frac{a}{(1+a)^{2}}>0. L a ( 2 + a 1 ) = ( 2 + a ) 2 ( 1 + a ) a > 0 , L a ( 1 + a 1 ) = ( 1 + a ) 2 a > 0.
Thus D ′ > 0 D'>0 D ′ > 0 whenever D = 1 D=1 D = 1 , so the slope ratio can cross one only upward.
Small- and large-jump comparisons
This appendix proves Lemma 4(ii) and (iii) of § 2 . We first prove part (ii), without linking the AMM curve to the private-value quantiles. At Δ p m i d = 0 \Delta p_{\mathrm{mid}}=0 Δ p mid = 0 , batch fills exactly the positive-private-value traders. For small positive Δ p m i d \Delta p_{\mathrm{mid}} Δ p mid , 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 f_{\varepsilon}>0 f ε > 0 is C 1 C^{1} C 1 on R \mathbb{R} R , symmetric about zero, and log-concave, and p ∈ C 2 p\in C^{2} p ∈ C 2 satisfies p ′ > 0 p'>0 p ′ > 0 and p ′ ′ ≥ 0 p''\ge0 p ′′ ≥ 0 on an inventory domain containing [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] , with p ( 0 ) p(0) 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 Δ p m i d = p e x , j u m p − p ( 1 / 2 ) \Delta p_{\mathrm{mid}}=p_{\mathrm{ex,jump}}-p(1/2) Δ p mid = p ex , jump − p ( 1/2 ) , s p = p ′ ( 1 / 2 ) s_{p}=p'(1/2) s p = p ′ ( 1/2 ) , Δ p = p ( 1 / 2 ) − p ( 1 / 4 ) \Delta p=p(1/2)-p(1/4) Δ p = p ( 1/2 ) − p ( 1/4 ) , and s ε = 1 / ( 2 f ε ( 0 ) ) s_{\varepsilon}=1/(2f_{\varepsilon}(0)) s ε = 1/ ( 2 f ε ( 0 )) . If Δ p ≥ 2 F ε − 1 ( 3 / 4 ) \Delta p\ge2F_{\varepsilon}^{-1}(3/4) Δ p ≥ 2 F ε − 1 ( 3/4 ) and 0 ≤ Δ p m i d < ( s ε + s p / 4 ) Δ p / ( 24 s p ) 0\le\Delta p_{\mathrm{mid}}<(s_{\varepsilon}+s_{p}/4)\sqrt{\Delta p/(24s_{p})} 0 ≤ Δ p mid < ( s ε + s p /4 ) Δ p / ( 24 s p ) , then batch has strictly higher welfare and AMM gains: W b a t c h j u m p > W F S j u m p W_{\mathrm{batch}}^{\mathrm{jump}}>W_{\mathrm{FS}}^{\mathrm{jump}} W batch jump > W FS jump and R b a t c h j u m p > R F S j u m p R_{\mathrm{batch}}^{\mathrm{jump}}>R_{\mathrm{FS}}^{\mathrm{jump}} R batch jump > R FS jump .
Proof. Put a = F ε − 1 ( 3 / 4 ) a=F_{\varepsilon}^{-1}(3/4) a = F ε − 1 ( 3/4 ) and let W ∗ = ∫ 0 ∞ e f ε ( e ) d e W^{*}=\int_{0}^{\infty}ef_{\varepsilon}(e)\,de W ∗ = ∫ 0 ∞ e f ε ( e ) d e , the welfare from filling exactly the positive-private-value traders. Symmetric log-concavity implies f ε ( e ) ≤ f ε ( 0 ) f_{\varepsilon}(e)\le f_{\varepsilon}(0) f ε ( e ) ≤ f ε ( 0 ) and a nondecreasing hazard rate h ε = f ε / ( 1 − F ε ) h_{\varepsilon}=f_{\varepsilon}/(1-F_{\varepsilon}) h ε = f ε / ( 1 − F ε ) . In particular,
a ≥ 1 4 f ε ( 0 ) = s ε 2 , f ε ( a ) = 1 4 h ε ( a ) ≥ 1 4 h ε ( 0 ) = f ε ( 0 ) 2 . a\ge\frac{1}{4f_{\varepsilon}(0)}=\frac{s_{\varepsilon}}{2},\qquad f_{\varepsilon}(a)=\frac{1}{4}h_{\varepsilon}(a)\ge\frac{1}{4}h_{\varepsilon}(0)=\frac{f_{\varepsilon}(0)}{2}. a ≥ 4 f ε ( 0 ) 1 = 2 s ε , f ε ( a ) = 4 1 h ε ( a ) ≥ 4 1 h ε ( 0 ) = 2 f ε ( 0 ) .
Since Δ p ≥ 2 a ≥ s ε \Delta p\ge2a\ge s_{\varepsilon} Δ p ≥ 2 a ≥ s ε and Δ p ≤ s p / 4 \Delta p\le s_{p}/4 Δ p ≤ s p /4 , we have s ε ≤ s p / 4 s_{\varepsilon}\le s_{p}/4 s ε ≤ s p /4 . The assumed upper bound on Δ p m i d \Delta p_{\mathrm{mid}} Δ p mid is therefore at most ( s p / 2 ) 1 / 96 < s p / 4 (s_{p}/2)\sqrt{1/96}<s_{p}/4 ( s p /2 ) 1/96 < s p /4 . We will prove the bound
W b a t c h j u m p − W F S j u m p ≥ s ε [ Δ p 96 s p − 1 4 ( Δ p m i d s ε + s p / 4 ) 2 ] > 0. (38) W_{\mathrm{batch}}^{\mathrm{jump}}-W_{\mathrm{FS}}^{\mathrm{jump}}\ge s_{\varepsilon}\left[\frac{\Delta p}{96s_{p}}-\frac{1}{4}\left(\frac{\Delta p_{\mathrm{mid}}}{s_{\varepsilon}+s_{p}/4}\right)^{2}\right]>0. \tag*{(38)} W batch jump − W FS jump ≥ s ε [ 96 s p Δ p − 4 1 ( s ε + s p /4 Δ p mid ) 2 ] > 0. (38)
Batch’s loss is quadratic. Write − z -z − z for batch’s marginal private value. Since Δ p m i d ≥ 0 \Delta p_{\mathrm{mid}} \ge0 Δ p mid ≥ 0 , we have z ≥ 0 z \ge0 z ≥ 0 , and symmetry and batch clearing give
x b a t c h j u m p = F ε ( z ) , Δ p m i d = z + p ( F ε ( z ) ) − p ( 1 / 2 ) ≥ z + s p [ F ε ( z ) − 1 / 2 ] . x_{\mathrm{batch}}^{\mathrm{jump}} = F_{\varepsilon}(z), \qquad\Delta p_{\mathrm{mid}} = z + p(F_{\varepsilon}(z)) - p(1/2) \ge z + s_p[F_{\varepsilon}(z) - 1/2]. x batch jump = F ε ( z ) , Δ p mid = z + p ( F ε ( z )) − p ( 1/2 ) ≥ z + s p [ F ε ( z ) − 1/2 ] .
For Δ p m i d ≤ s p / 4 \Delta p_{\mathrm{mid}} \le s_p/4 Δ p mid ≤ s p /4 , this implies F ε ( z ) ≤ 3 / 4 F_{\varepsilon}(z) \le3/4 F ε ( z ) ≤ 3/4 and hence z ≤ a z \le a z ≤ a . The density is nonincreasing on [ 0 , a ] [0,a] [ 0 , a ] , so F ε ( z ) − 1 / 2 ≥ z f ε ( a ) ≥ z f ε ( 0 ) / 2 F_{\varepsilon}(z) - 1/2 \ge zf_{\varepsilon}(a) \ge zf_{\varepsilon}(0)/2 F ε ( z ) − 1/2 ≥ z f ε ( a ) ≥ z f ε ( 0 ) /2 . Therefore
z ≤ Δ p m i d 1 + s p f ε ( 0 ) / 2 , z \le\frac{\Delta p_{\mathrm{mid}}}{1+s_pf_{\varepsilon}(0)/2}, z ≤ 1 + s p f ε ( 0 ) /2 Δ p mid ,
and
W ∗ − W b a t c h j u m p = ∫ 0 z e f ε ( e ) d e ≤ f ε ( 0 ) z 2 2 ≤ s ε 4 ( Δ p m i d s ε + s p / 4 ) 2 . (39) W^* - W_{\mathrm{batch}}^{\mathrm{jump}} = \int_0^z ef_{\varepsilon}(e)\,de \le\frac{f_{\varepsilon}(0)z^2}{2} \le\frac{s_{\varepsilon}}{4}\left(\frac{\Delta p_{\mathrm{mid}}}{s_{\varepsilon}+s_p/4}\right)^2. \tag*{(39)} W ∗ − W batch jump = ∫ 0 z e f ε ( e ) d e ≤ 2 f ε ( 0 ) z 2 ≤ 4 s ε ( s ε + s p /4 Δ p mid ) 2 . (39)
FirstSwap has a uniform selection loss. A bid of p ( 1 / 4 ) p(1/4) p ( 1/4 ) fills with probability at least 1 / 4 1/4 1/4 : the eligible population has mass at most one, so cumulative sales satisfy x ′ ( t ) ≤ 1 x'(t) \le1 x ′ ( t ) ≤ 1 and x ( t ) ≤ t x(t) \le t x ( t ) ≤ t , and an order arriving before queue time 1 / 4 1/4 1/4 finds the quote at or below p ( 1 / 4 ) p(1/4) p ( 1/4 ) . For every private value e ∈ [ − a , 0 ] e \in[-a,0] e ∈ [ − a , 0 ] this deviation gives
U F S j u m p ( e ) ≥ Δ p m i d + e + Δ p 4 ≥ Δ p − a 4 ≥ Δ p 8 > 0. (40) U_{\mathrm{FS}}^{\mathrm{jump}}(e) \ge\frac{\Delta p_{\mathrm{mid}}+e+\Delta p}{4} \ge\frac{\Delta p-a}{4} \ge\frac{\Delta p}{8} > 0. \tag*{(40)} U FS jump ( e ) ≥ 4 Δ p mid + e + Δ p ≥ 4 Δ p − a ≥ 8 Δ p > 0. (40)
Let p b i d ( e ) p_{\mathrm{bid}}(e) p bid ( e ) denote the equilibrium bid of type e e e and δ ( e ) : = p e x , j u m p + e − p b i d ( e ) \delta(e) := p_{\mathrm{ex,jump}}+e-p_{\mathrm{bid}}(e) δ ( e ) := p ex , jump + e − p bid ( e ) its surplus per fill, so that U F S j u m p ( e ) = Pr F S j u m p ( 1 − F ε ( e ) ) δ ( e ) U_{\mathrm{FS}}^{\mathrm{jump}}(e) = \Pr_{\mathrm{FS}}^{\mathrm{jump}}(1-F_{\varepsilon}(e))\delta(e) U FS jump ( e ) = Pr FS jump ( 1 − F ε ( e )) δ ( e ) . Since U F S j u m p ( e ) > 0 U_{\mathrm{FS}}^{\mathrm{jump}}(e) > 0 U FS jump ( e ) > 0 , the equilibrium bid fills with positive probability, which requires p b i d ( e ) ≥ p ( 0 ) p_{\mathrm{bid}}(e) \ge p(0) p bid ( e ) ≥ p ( 0 ) because the AMM quote never falls below p ( 0 ) p(0) p ( 0 ) . Hence
δ ( e ) ≤ p e x , j u m p + e − p ( 0 ) ≤ Δ p m i d + [ p ( 1 / 2 ) − p ( 0 ) ] ≤ s p 4 + s p 2 = 3 s p 4 , \delta(e) \le p_{\mathrm{ex,jump}}+e-p(0) \le\Delta p_{\mathrm{mid}}+[p(1/2)-p(0)] \le\frac{s_p}{4}+\frac{s_p}{2}=\frac{3s_p}{4}, δ ( e ) ≤ p ex , jump + e − p ( 0 ) ≤ Δ p mid + [ p ( 1/2 ) − p ( 0 )] ≤ 4 s p + 2 s p = 4 3 s p ,
using e ≤ 0 e \le0 e ≤ 0 , the maintained restriction Δ p m i d ≤ s p / 4 \Delta p_{\mathrm{mid}} \le s_p/4 Δ p mid ≤ s p /4 , and convexity (p ′ ≤ s p p' \le s_p p ′ ≤ s p on [ 0 , 1 / 2 ] [0,1/2] [ 0 , 1/2 ] ). Therefore
Pr F S j u m p ( 1 − F ε ( e ) ) = U F S j u m p ( e ) δ ( e ) ≥ Δ p / 8 3 s p / 4 = Δ p 6 s p , − a ≤ e ≤ 0. \Pr_{\mathrm{FS}}^{\mathrm{jump}}(1-F_{\varepsilon}(e))=\frac{U_{\mathrm{FS}}^{\mathrm{jump}}(e)}{\delta(e)} \ge\frac{\Delta p/8}{3s_p/4}=\frac{\Delta p}{6s_p}, \qquad-a \le e \le0. FS Pr jump ( 1 − F ε ( e )) = δ ( e ) U FS jump ( e ) ≥ 3 s p /4 Δ p /8 = 6 s p Δ p , − a ≤ e ≤ 0.
The argument uses only that type e e 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 ) f_{\varepsilon} \le f_{\varepsilon}(0) f ε ≤ f ε ( 0 ) ,
∫ − a 0 ( − e ) f ε ( e ) d e = ∫ 0 a [ 1 4 − ( F ε ( u ) − 1 / 2 ) ] d u ≥ ∫ 0 s ε / 2 [ 1 4 − f ε ( 0 ) u ] d u = s ε 16 . \int_{-a}^{0}(-e)f_{\varepsilon}(e)\,de = \int_{0}^{a}\left[\frac{1}{4}-(F_{\varepsilon}(u)-1/2)\right]du \ge\int_{0}^{s_{\varepsilon}/2}\left[\frac{1}{4}-f_{\varepsilon}(0)u\right]du = \frac{s_{\varepsilon}}{16}. ∫ − a 0 ( − e ) f ε ( e ) d e = ∫ 0 a [ 4 1 − ( F ε ( u ) − 1/2 ) ] d u ≥ ∫ 0 s ε /2 [ 4 1 − f ε ( 0 ) u ] d u = 16 s ε .
Consequently,
W ∗ − W F S j u m p = ∫ 0 ∞ e [ 1 − Pr F S j u m p ( 1 − F ε ( e ) ) ] f ε ( e ) d e + ∫ − ∞ 0 ( − e ) Pr F S j u m p ( 1 − F ε ( e ) ) f ε ( e ) d e ≥ Δ p 6 s p ⋅ s ε 16 = s ε Δ p 96 s p . W^*-W_{\mathrm{FS}}^{\mathrm{jump}} = \int_{0}^{\infty}e[1-\Pr_{\mathrm{FS}}^{\mathrm{jump}}(1-F_{\varepsilon}(e))]f_{\varepsilon}(e)\,de+\int_{-\infty}^{0}(-e)\Pr_{\mathrm{FS}}^{\mathrm{jump}}(1-F_{\varepsilon}(e))f_{\varepsilon}(e)\,de \ge\frac{\Delta p}{6s_p}\cdot\frac{s_{\varepsilon}}{16}=\frac{s_{\varepsilon}\Delta p}{96s_p}. W ∗ − W FS jump = ∫ 0 ∞ e [ 1 − FS Pr jump ( 1 − F ε ( e ))] f ε ( e ) d e + ∫ − ∞ 0 ( − e ) FS Pr jump ( 1 − F ε ( e )) f ε ( e ) d e ≥ 6 s p Δ p ⋅ 16 s ε = 96 s p s ε Δ p .
Subtracting (39) proves (38) .
AMM gains are also higher. Let U m j u m p = W m j u m p − R m j u m p U_m^{\mathrm{jump}} = W_m^{\mathrm{jump}} - R_m^{\mathrm{jump}} U m jump = W m jump − R m jump denote aggregate trader utility. If x F S j u m p ≤ x b a t c h j u m p x_{\mathrm{FS}}^{\mathrm{jump}} \le x_{\mathrm{batch}}^{\mathrm{jump}} x FS jump ≤ x batch jump , the batch price p b a t c h j u m p = p ( x b a t c h j u m p ) p_{\mathrm{batch}}^{\mathrm{jump}} = p(x_{\mathrm{batch}}^{\mathrm{jump}}) p batch jump = p ( x batch jump ) is at least FirstSwap’s terminal quote. An infinitesimal trader can therefore obtain its batch payoff under FirstSwap by bidding p b a t c h j u m p p_{\mathrm{batch}}^{\mathrm{jump}} p batch jump , which guarantees execution, if its value is at least p b a t c h j u m p p_{\mathrm{batch}}^{\mathrm{jump}} p batch jump , and by abstaining otherwise. Optimality implies U F S j u m p ≥ U b a t c h j u m p U_{\mathrm{FS}}^{\mathrm{jump}} \ge U_{\mathrm{batch}}^{\mathrm{jump}} U FS jump ≥ U batch jump .
If x F S j u m p ≥ x b a t c h j u m p x_{\mathrm{FS}}^{\mathrm{jump}} \ge x_{\mathrm{batch}}^{\mathrm{jump}} x FS jump ≥ x batch jump , Lemma 2 gives U m j u m p = ∫ 0 1 ω ( r ) Pr m j u m p ( r ) d r U_m^{\mathrm{jump}} = \int_0^1 \omega(r)\Pr_m^{\mathrm{jump}}(r)\,\mathrm{d}r U m jump = ∫ 0 1 ω ( r ) Pr m jump ( r ) d r , where ω ( r ) = − r ε ′ ( r ) = 1 / h ε ( ε ( r ) ) \omega(r) = -r\varepsilon'(r) = 1/h_\varepsilon(\varepsilon(r)) ω ( r ) = − r ε ′ ( r ) = 1/ h ε ( ε ( r )) is positive and nondecreasing because the hazard rate h ε h_\varepsilon h ε is nondecreasing. At a fixed volume this integral is minimized by allocating to the smallest ranks. Hence
U F S j u m p ≥ ∫ 0 x F S j u m p ω ( r ) d r ≥ ∫ 0 x b a t c h j u m p ω ( r ) d r = U b a t c h j u m p . U_{\mathrm{FS}}^{\mathrm{jump}} \ge\int_0^{x_{\mathrm{FS}}^{\mathrm{jump}}} \omega(r)\,\mathrm{d}r \ge\int_0^{x_{\mathrm{batch}}^{\mathrm{jump}}} \omega(r)\,\mathrm{d}r = U_{\mathrm{batch}}^{\mathrm{jump}}. U FS jump ≥ ∫ 0 x FS jump ω ( r ) d r ≥ ∫ 0 x batch jump ω ( r ) d r = U batch jump .
In either case,
R b a t c h j u m p − R F S j u m p = W b a t c h j u m p − W F S j u m p + U F S j u m p − U b a t c h j u m p ≥ W b a t c h j u m p − W F S j u m p > 0. R_{\mathrm{batch}}^{\mathrm{jump}} - R_{\mathrm{FS}}^{\mathrm{jump}} = W_{\mathrm{batch}}^{\mathrm{jump}} - W_{\mathrm{FS}}^{\mathrm{jump}} + U_{\mathrm{FS}}^{\mathrm{jump}} - U_{\mathrm{batch}}^{\mathrm{jump}} \ge W_{\mathrm{batch}}^{\mathrm{jump}} - W_{\mathrm{FS}}^{\mathrm{jump}} > 0. R batch jump − R FS jump = W batch jump − W FS jump + U FS jump − U batch jump ≥ W batch jump − W FS jump > 0.
The condition Δ p ≥ 2 a \Delta_p \ge2a Δ p ≥ 2 a 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 Δ p m i d \Delta p_{\mathrm{mid}} Δ p mid . 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 ) p(0) p ( 0 ) and that no type can gain by switching to the bid p ( 1 / 4 ) p(1/4) p ( 1/4 ) ; the AMM-gain comparison uses optimal bidding and the envelope identity of Lemma 2.
Proof (Proof of Lemma 4(iii) ). Write F ‾ ε = 1 − F ε \overline{F}_\varepsilon= 1 - F_\varepsilon F ε = 1 − F ε and let c F S j u m p c_{\mathrm{FS}}^{\mathrm{jump}} c FS jump be FirstSwap’s terminal eligibility cutoff. The limiting queue FOC gives
c F S j u m p = p ( x F S j u m p ) − p e x , j u m p + p ′ ( x F S j u m p ) F ‾ ε ( c F S j u m p ) . c_{\mathrm{FS}}^{\mathrm{jump}} = p(x_{\mathrm{FS}}^{\mathrm{jump}}) - p_{\mathrm{ex,jump}} + p'(x_{\mathrm{FS}}^{\mathrm{jump}})\overline{F}_\varepsilon(c_{\mathrm{FS}}^{\mathrm{jump}}). c FS jump = p ( x FS jump ) − p ex , jump + p ′ ( x FS jump ) F ε ( c FS jump ) .
If c F S j u m p > 0 c_{\mathrm{FS}}^{\mathrm{jump}} > 0 c FS jump > 0 , symmetry gives F ‾ ε ( c F S j u m p ) < 1 / 2 \overline{F}_\varepsilon(c_{\mathrm{FS}}^{\mathrm{jump}}) < 1/2 F ε ( c FS jump ) < 1/2 . Since x F S j u m p ≤ 1 x_{\mathrm{FS}}^{\mathrm{jump}} \le1 x FS jump ≤ 1 , convexity and the jump condition imply
c F S j u m p ≤ p ( 1 ) − p e x , j u m p + 1 2 p ′ ( 1 ) ≤ 0 , c_{\mathrm{FS}}^{\mathrm{jump}} \le p(1) - p_{\mathrm{ex,jump}} + \frac{1}{2}p'(1) \le0, c FS jump ≤ p ( 1 ) − p ex , jump + 2 1 p ′ ( 1 ) ≤ 0 ,
a contradiction. Thus FirstSwap fills every nonnegative-private-value trader with certainty. FIFO does too, because its terminal quote is p ( x F I F O j u m p ) ≤ p ( 1 ) < p e x , j u m p p(x_{\mathrm{FIFO}}^{\mathrm{jump}}) \le p(1) < p_{\mathrm{ex,jump}} p ( x FIFO jump ) ≤ p ( 1 ) < p ex , jump . The single crossing can therefore be chosen with e ⋆ ≤ 0 e^\star\le0 e ⋆ ≤ 0 .
FirstSwap bids do not exceed values, so its eligible mass at any common inventory is at most FIFO’s, giving x F S j u m p ≤ x F I F O j u m p x^{\mathrm{jump}}_{\mathrm{FS}} \le x^{\mathrm{jump}}_{\mathrm{FIFO}} x FS jump ≤ x FIFO jump by queue comparison. Both terms in the welfare decomposition of Lemma 3 are consequently nonnegative. For AMM gains, Lemma 2 replaces private value e e e by the virtual value e − F ‾ ε ( e ) / f ε ( e ) e - \overline{F}_{\varepsilon}(e)/f_{\varepsilon}(e) e − F ε ( e ) / f ε ( e ) . The increasing hazard rate makes this function strictly increasing, and its value at e ⋆ ≤ 0 e^{\star} \le0 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.
Validator-count equivalence after a simultaneous jump
Fair ordering: anonymity, neutrality, and a uniform queue
Fix a simultaneous cohort of m m m labeled orders. Conditional on all submitted bids, quantities, and private values, suppose the n n n validators’ receipt rankings are independent uniform permutations:
π 1 , … , π n ∼ i i d Unif ( S m ) . \pi_1,\ldots,\pi_n \mathrel{\overset{\mathrm{iid}}{\sim}} \operatorname{Unif}(\mathcal{S}_m). π 1 , … , π n ∼ iid Unif ( S m ) .
Independent continuous, identically distributed receipt delays satisfy this assumption. We consider an aggregation rule A n \mathcal{A}_n A n that returns a complete ordering and satisfies the following axioms.
Transaction neutrality. For every relabeling ρ ∈ S m \rho\in\mathcal{S}_m ρ ∈ S m ,
A n ( ρ π 1 , … , ρ π n ) = d ρ A n ( π 1 , … , π n ) . \mathcal{A}_n(\rho\pi_1,\ldots,\rho\pi_n) \mathrel{\overset{d}{=}} \rho\mathcal{A}_n(\pi_1,\ldots,\pi_n). A n ( ρ π 1 , … , ρ π n ) = d ρ A n ( π 1 , … , π n ) .
Here ρ π \rho\pi ρ π relabels the entries of the ordered list π \pi π .
Validator anonymity. Permuting the n n n input rankings does not change the output distribution.
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 n \ge1 n ≥ 1 and every conditional bid and value profile,
Pr { A n ( π 1 , … , π n ) = σ } = 1 m ! , σ ∈ S m . \Pr\{\mathcal{A}_n(\pi_1,\ldots,\pi_n)=\sigma\} = \frac{1}{m!}, \qquad\sigma\in\mathcal{S}_m. Pr { A n ( π 1 , … , π n ) = σ } = m ! 1 , σ ∈ S 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 ρ \rho ρ . Transaction neutrality therefore implies that the output law is also unchanged by ρ \rho ρ . For any two full rankings σ \sigma σ and σ ′ \sigma' σ ′ , there is a relabeling ρ \rho ρ with ρ σ = σ ′ \rho\sigma=\sigma' ρ σ = σ ′ . 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.
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 ) = p e x , j u m p + ε ( r ) , D : = 1 − F ε ( p ( 0 ) − p e x , j u m p ) ∈ ( 0 , 1 ) . \theta(r)=p_{\mathrm{ex,jump}}+\varepsilon(r),\qquad D:=1-F_{\varepsilon}\bigl(p(0)-p_{\mathrm{ex,jump}}\bigr)\in(0,1). θ ( r ) = p ex , jump + ε ( r ) , D := 1 − F ε ( p ( 0 ) − p ex , jump ) ∈ ( 0 , 1 ) .
Proof. Entry, execution prices, and the incentive equation. Every execution price is at least p ( 0 ) p(0) p ( 0 ) , so values below p ( 0 ) p(0) p ( 0 ) cannot profit from entry. Conversely, any value above p ( 0 ) p(0) p ( 0 ) can bid strictly between p ( 0 ) p(0) 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 ) p(0) p ( 0 ) . Participation is precisely r < D r<D r < D , up to the indifferent boundary type.
Because bids strictly decrease with r r r , lower-value active types execute first. Hence
X n ( r ) = ∫ r D a n ( t ) d t , p n ( r ) = p ( X n ( r ) ) . X_n(r)=\int_r^D a_n(t)\,\mathrm{d}t,\qquad p_n(r)=p\bigl(X_n(r)\bigr). X n ( r ) = ∫ r D a n ( t ) d t , p n ( r ) = p ( X n ( r ) ) .
A trader of true rank r r r who submits rank t t t ’s bid receives utility
a n ( t ) [ θ ( r ) − p ( X n ( t ) ) ] . a_n(t)\left[\theta(r)-p\bigl(X_n(t)\bigr)\right]. a n ( t ) [ θ ( r ) − p ( X n ( t ) ) ] .
The first-order condition at t = r t=r t = r , together with X n ′ = − a n X_n'=-a_n X n ′ = − a n , 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) \begin{aligned}
X'(r)&=-a(r),\\
a'(r)&=-\frac{a(r)^2p'\bigl(X(r)\bigr)}{\theta(r)-p\bigl(X(r)\bigr)},\qquad a(0+)=1,\qquad X(D-)=0. \tag*{(41)}
\end{aligned} X ′ ( r ) a ′ ( r ) = − a ( r ) , = − θ ( r ) − p ( X ( r ) ) a ( r ) 2 p ′ ( X ( r ) ) , a ( 0 + ) = 1 , X ( D − ) = 0. (41)
The boundary X ( D − ) = 0 X(D-)=0 X ( D − ) = 0 follows from the definition of execution depth. A bid covering p ( 2 D ) p(2D) p ( 2 D ) receives every signature and can be added to any feasible allocation, so it guarantees execution at a price at most p ( D ) p(D) p ( D ) . Comparing this deviation with an equilibrium payoff at most a n ( r ) [ θ ( r ) − p ( 0 ) ] a_n(r)[\theta(r)-p(0)] a n ( r ) [ θ ( r ) − p ( 0 )] , and using θ ( r ) → ∞ \theta(r)\to\infty θ ( r ) → ∞ as r ↓ 0 r\downarrow0 r ↓ 0 , proves a n ( 0 + ) = 1 a_n(0+)=1 a n ( 0 + ) = 1 . We show that there is at most one solution to this system of differential equations with these boundary conditions.
Table 2. Glossary of main notation used in § 3 .
To prove uniqueness, set Z = − a Z=-a Z = − a . The system for ( X , Z ) (X,Z) ( X , Z ) is a so-called cooperative system with ∂ X ′ ∂ Z \frac{\partial X'}{\partial Z} ∂ Z ∂ X ′ and ∂ Z ′ ∂ X \frac{\partial Z'}{\partial X} ∂ X ∂ Z ′ both positive:
X ′ = Z , Z ′ = Z 2 p ′ ( X ) θ − p ( X ) , ∂ ∂ X p ′ ( X ) θ − p ( X ) = p ′ ′ ( X ) [ θ − p ( X ) ] + p ′ ( X ) 2 [ θ − p ( X ) ] 2 > 0. X'=Z,\qquad Z'=\frac{Z^2p'(X)}{\theta-p(X)},\qquad\frac{\partial}{\partial X}\frac{p'(X)}{\theta-p(X)}=\frac{p''(X)[\theta-p(X)]+p'(X)^2}{[\theta-p(X)]^2}>0. X ′ = Z , Z ′ = θ − p ( X ) Z 2 p ′ ( X ) , ∂ X ∂ θ − p ( X ) p ′ ( X ) = [ θ − p ( X ) ] 2 p ′′ ( X ) [ θ − p ( X )] + p ′ ( X ) 2 > 0.
By the comparison theorem for cooperative systems, a larger initial condition X ( 0 + ) X(0+) X ( 0 + ) and the same Z ( 0 ) = − 1 Z(0)=-1 Z ( 0 ) = − 1 give larger X X X and weakly larger Z Z Z pointwise. The difference between the two X X X paths is nondecreasing, so stays at least their strictly positive initial difference. They cannot both end at X ( D − ) = 0 X(D-)=0 X ( D − ) = 0 . There is therefore at most one solution satisfying a ( 0 + ) = 1 a(0+)=1 a ( 0 + ) = 1 and $X(D-)=0.
Thus every regular separating equilibrium, whenever it exists, has
a n ( r ) = a ( r ) , X n ( r ) = X ( r ) , p n ( r ) = p ( X ( r ) ) , 0 < r < D , (42) a_n(r)=a(r),\qquad X_n(r)=X(r),\qquad p_n(r)=p(X(r)),\qquad0<r<D, \tag*{(42)} a n ( r ) = a ( r ) , X n ( r ) = X ( r ) , p n ( r ) = p ( X ( r )) , 0 < r < D , (42)
where p n ( r ) p_n(r) p n ( r ) is the expected price conditional on filling. ⊓⊔
Supplemental Protocol Information: Glossary, Algorithms and Proofs
This appendix gives pseudocode for the decentralized protocol of § 3 and overflow security proofs. Algorithm 1 is run by traders, Algorithm 2 by validators during the pre-approval stage, and Algorithm 3 by validators at the end of the epoch. All parameters, the pricing function, and the notions of admissibility and η \eta η -admissibility are as defined in the main text. The pseudocode describes a single epoch e e 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.
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 f f -Agreement). The protocol satisfies f f f -Agreement (defined in § 3 ).
Proof. By MVBA agreement, all honest validators decide the same output B \mathcal{B} B . They apply the same inclusion and execution rules, including the deterministic tie-breaking rule, and therefore output the same final block. □ \square □
Proof of Accountable Inclusion.
Theorem 8 (Accountable inclusion). The protocol satisfies accountable inclusion.
Proof. Let the evidence w w w consist of an AC for tx, the decided output B \mathcal{B} B , V ∗ V^* V ∗ the creators of its mini-blocks, and M B ← ∣ V ∗ ∣ M_B \leftarrow|V^*| M B ← ∣ V ∗ ∣ . Define J ( w ) J(w) J ( w ) to contain every validator v v v such that v ∈ V ∗ v \in V^* v ∈ V ∗ , the AC contains v v v ’s approval of tx, and A v A_v A v omits that signed approval.
Suppose tx obtains an AC but is absent from the final block. The AC cannot appear in any selected Π v \Pi_v Π v , because that would include tx directly. Moreover, fewer than η M B \eta M_B η M B selected approved sets contain tx, because otherwise the pre-approved inclusion rule would include it. The AC signer set and V ∗ V^* V ∗ intersect in at least q + M B − n ≥ η M B q + M_B - n \ge\eta M_B q + M B − n ≥ η M B validators, by the bound in the proof of Lemma 5. Thus at least one signer in this intersection omitted its approval, so J ( w ) J(w) J ( w ) is nonempty. An honest validator retains every approval it issues in A v A_v A v . Therefore no valid evidence causes J J J to identify an honest validator. □ \square □
Algorithm 2 Validator-side processing at validator v v v in epoch e e e
Upon receiving trade request t x = ( a m t , l i m i t ) \mathrm{tx}=(\mathrm{amt},\mathrm{limit}) tx = ( amt , limit ) :
if v v v has previously responded to t x \mathrm{tx} tx then
return previously signed response
end if
if the pre-approval stage of epoch e e e has ended then
Ignore t x \mathrm{tx} tx
end if
{Check η \eta η -admissibility of A v ∪ { t x } A_v \cup\{\mathrm{tx}\} A v ∪ { tx } ; only limits ≥ l i m i t \ge\mathrm{limit} ≥ limit are affected}
for all ℓ ∈ { l i m i t } ∪ { l i m i t i : t x i ∈ A v , l i m i t i > l i m i t } \ell\in\{\mathrm{limit}\} \cup\{\mathrm{limit}_i : \mathrm{tx}_i \in A_v,\ \mathrm{limit}_i > \mathrm{limit}\} ℓ ∈ { limit } ∪ { limit i : tx i ∈ A v , limit i > limit } do
if ℓ < p ( ( ∑ t x j ∈ A v : l i m i t j ≤ ℓ a m t j / η ) + a m t / η ) \ell< p\left(\left(\sum_{\mathrm{tx}_j\in A_v:\ \mathrm{limit}_j\le\ell}\mathrm{amt}_j/\eta\right)+\mathrm{amt}/\eta\right) ℓ < p ( ( ∑ tx j ∈ A v : limit j ≤ ℓ amt j / η ) + amt / η ) then
return signed ⟨ R E J E C T , t x , e ⟩ \langle\mathrm{REJECT},\mathrm{tx},e\rangle ⟨ REJECT , tx , e ⟩ {stored and replayed}
end if
end for
σ v ( t x ) ← \sigma_v(\mathrm{tx}) \leftarrow σ v ( tx ) ← signed ⟨ A P P R O V E , t x , e ⟩ \langle\mathrm{APPROVE},\mathrm{tx},e\rangle ⟨ APPROVE , tx , e ⟩
A v ← A v ∪ { ( t x , σ v ( t x ) ) } A_v \leftarrow A_v \cup\{(\mathrm{tx},\sigma_v(\mathrm{tx}))\} A v ← A v ∪ {( tx , σ v ( tx ))}
return σ v ( t x ) \sigma_v(\mathrm{tx}) σ v ( tx )
Upon receiving π ( t x ) \pi(\mathrm{tx}) π ( tx ) before the end of the pre-approval stage :
if π ( t x ) \pi(\mathrm{tx}) π ( tx ) holds valid epoch-e e e approvals of t x \mathrm{tx} tx from q q q distinct validators then
Π v ← Π v ∪ { π ( t x ) } \Pi_v \leftarrow\Pi_v \cup\{\pi(\mathrm{tx})\} Π v ← Π v ∪ { π ( tx )}
end if
Strengthened Inclusion Guarantees
Lemma 10 ( f f f -Certified inclusion). Let n ≥ 4 f + 1 n \ge4f + 1 n ≥ 4 f + 1 , q = n − f q = n - f q = n − f , and η = ( q − 2 f ) / ( n − f ) \eta= (q - 2f)/(n - f) η = ( q − 2 f ) / ( n − f ) . The protocol satisfies the following strengthened pre-approval inclusion property: if at most f f f validators are Byzantine and a trade request t x \mathrm{tx} tx obtains valid pre-approvals for an epoch from q q q distinct validators, not necessarily all honest, then t x \mathrm{tx} tx is included in that epoch’s final block.
Proof. At least q − f q-f q − f approvers are honest. Since only n − M B n-M_B n − M B validators lie outside V ∗ V^* V ∗ , at least q − f − ( n − M B ) = M B − 2 f q-f-(n-M_B)=M_B-2f q − f − ( n − M B ) = M B − 2 f honest approvers have selected mini-blocks, each containing its approval of t x \mathrm{tx} tx . Moreover,
M B − 2 f − η M B = 2 f ( M B − ( n − f ) ) n − f ≥ 0. M_B-2f-\eta M_B=\frac{2f(M_B-(n-f))}{n-f}\ge0. M B − 2 f − η M B = n − f 2 f ( M B − ( n − f )) ≥ 0.
Thus t x \mathrm{tx} tx appears in at least η M B \eta M_B η M B selected approved sets and is included by the pre-approved inclusion rule. □ \square □
Lemma 11 (Strengthened accountable inclusion). Let n ≥ 4 f + 1 n \ge4f + 1 n ≥ 4 f + 1 , q = n − f q = n-f q = n − f , and η = ( q − 2 f ) / ( n − f ) \eta=(q-2f)/(n-f) η = ( q − 2 f ) / ( n − f ) . There exists a publicly verifiable function J J J such that, if a trade request t x \mathrm{tx} tx obtains an approval certificate but is omitted from a valid final block for that epoch, there is evidence w w w with ∣ J ( w ) ∣ ≥ f + 1 |J(w)| \ge f+1 ∣ J ( w ) ∣ ≥ f + 1 (and hence at least f f f ). Moreover, v ∉ J ( w ) v \notin J(w) v ∈ / J ( w ) for every honest validator v v v and every w w w .
Algorithm 3 End-of-epoch block consensus at validator v v v
External validity predicate (Definition 4). Valid ( B ) = 1 \operatorname{Valid}(B) = 1 Valid ( B ) = 1 if and only if: (i) B B B contains well-formed mini-blocks from at least n − f n-f n − f distinct validators, where B u = ( A u , Π u ) B_u = (A_u, \Pi_u) B u = ( A u , Π u ) is well-formed if A u A_u A u is η \eta η -admissible with every approval correctly signed by u u u for epoch e e e , and every π ( t x ) ∈ Π u \pi(\mathrm{tx}) \in\Pi_u π ( tx ) ∈ Π u is correctly formed; and (ii) for every π ( t x ) \pi(\mathrm{tx}) π ( tx ) in B B B and every B u B_u B u in B B B , if u u u ’s signature appears in π ( t x ) \pi(\mathrm{tx}) π ( tx ) , then the same signed approval of tx appears in A u A_u A u .
Protocol.
At the end of the epoch, form the mini-block B v ← ( A v , Π v ) B_v \leftarrow(A_v, \Pi_v) B v ← ( A v , Π v ) and sign it
Invoke MVBA with input B v B_v B v and external-validity predicate Valid \operatorname{Valid} Valid
Let B \mathcal{B} B be the decision by MVBA, V ∗ V^* V ∗ the creators of its mini-blocks, and M B ← ∣ V ∗ ∣ M_B \leftarrow|V^*| M B ← ∣ V ∗ ∣
Pre-approved inclusion: include every tx with approval signatures from at least η M B \eta M_B η M B distinct validators in V ∗ V^* V ∗
AC inclusion: include every tx for which a valid π ( t x ) \pi(\mathrm{tx}) π ( tx ) appears in B \mathcal{B} B , unless already included
Execution ordering: order all included trade requests in non-decreasing order of limit, breaking ties deterministically by trade request identifier
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 w w . Let J ( w ) J(w) J ( w ) contain each selected certificate signer whose mini-block omits its signed approval, and set J ( w ) = ∅ J(w) = \varnothing J ( w ) = ∅ for invalid evidence. At least q + M B − n = M B − f q + M_B - n = M_B - f q + M B − n = M B − f certificate signers are selected. If tx is omitted, fewer than η M B \eta M_B η M B selected approved sets contain it. Therefore
∣ J ( w ) ∣ > M B − f − η M B = 2 f M B n − f − f ≥ f . |J(w)| > M_B - f - \eta M_B = \frac{2fM_B}{n-f} - f \ge f. ∣ J ( w ) ∣ > M B − f − η M B = n − f 2 f M B − f ≥ f .
Since ∣ J ( w ) ∣ |J(w)| ∣ J ( w ) ∣ is an integer, at least f + 1 f + 1 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. ⊔