Time Is Money: Incentivized Causal Transaction Ordering Hongyin Chen
Xu Zheng
Jichen Li
Ittay Eyal
arXiv:2607.11496v1 [cs.CR] 13 Jul 2026
Technion Miami Herbert Business School Tsinghua University Technion [email protected] [email protected] [email protected] [email protected]
Abstract—Front-running is a subtle and persistent problem for blockchains. A blockchain is a stateful virtual machine executing instructions called transactions. Users earn rewards by publishing functional transactions essential to the system. Attackers observe these transactions and publish their own ahead of the users’, seizing the reward and eroding users’ incentive to publish functional transactions. Preventing frontrunning means enforcing causality: If an attacker receives transaction txA and then publishes transaction txB , then txA must be ordered before txB . However, this causality is only observed by the attacker. Practical systems order transactions by bid amount, so transactions willing to pay more get executed first, but this only results in a bidding war eroding users’ rewards. Though numerous ordering approaches have been proposed, none achieves causality, leaving users vulnerable to front-running. We present PRECEDE, a mechanism-design approach that enforces transaction causality by removing the economic incentive to front-run. PRECEDE orders transactions by a powerweighted randomized lottery, whose winning probability grows super-linearly in the bid. The user’s strategy of publishing a transaction with a deterring bid forms an equilibrium where the attacker refrains from competing. Moreover, PRECEDE prevents the prominent sandwich attack, which relies on front-running. PRECEDE can be directly deployed in any censorship-resistant blockchain with a simple change to its transaction ordering mechanism.
1. Introduction Blockchains underpin the $3 trillion cryptocurrency market [1] and the $170 billion Decentralized Finance (DeFi) market [2]. A blockchain is a stateful virtual machine that executes an ordered sequence of instructions called transactions, each of which updates the machine’s state. Blockchain validators [3], [4], [5] extend this sequence by appending vectors of transactions called blocks. Users issue many functional transactions that benefit the system, such as arbitrage that aligns prices across markets [6], among others [7], [8]. They receive rewards from the system for these transactions. These rewards, however, are exposed to frontrunning [9]. When a user publishes a functional transaction, it is publicly visible before a validator places it on chain. An
attacker observes it and can bribe the validator to order her own transaction ahead of the user’s, seizing the reward [9], [10]. Front-running also serves as a building block for other order-manipulation attacks [11], [12], [13]. Practical chains often order transactions by bid [3], [5], [14], turning frontrunning into a race to the bottom: On Flashbots [15], for instance, arbitrage winners pay validators a median of over 90% of their reward [16]. Front-running is therefore harmful to blockchain functionality: With their rewards competed away, users have little incentive to issue functional transactions, and the markets that rely on them lose efficiency [6]. An extensive body of work (§2) addresses these attacks by limiting the validators’ ability to manipulate transaction order. One approach is to order transactions by their arrival times at an ordering committee [17], [18], [19], [20], but this fails to prevent front-running [21]: No such protocol ensures ordering an earlier transaction ahead of a later one [17], [19]. A second approach makes the order within each block random [22], [23]. However, an attacker can publish many copies so that one likely precedes the target [24], [25]; such spam burdens the system while still allowing frontrunning [24], [26], [27]. A third approach encrypts transaction content to hide it from attackers [28], [29], [30], [31], [32]. However, it still fails to prevent front-running [33]. Addressing front-running is fundamentally hard. It is a matter of causality [34]: If a participant creates and publishes her transaction after observing another’s [35], [36], [37], it should appear later on chain. But this causal relationship is private to the attacker who issues the later transaction. Moreover, in a decentralized system we cannot compel participants to follow the protocol, for instance to refrain from front-running or from misreporting transaction arrival times. Instead, each participant is free to take whichever action maximizes her own revenue [7], [38], [39], [40], [41], [42], [43]. Without making trust assumptions that nodes may violate for gain, the protocol can therefore rely only on a limited set of signals observable to the blockchain. Even the size of the front-running reward is unknown to the protocol and varies across orders of magnitude [16], so any defense must hold across the full range. Together, these constraints force the protocol to defend blindly: against any rational adversary, at any revenue scale, using only signals observable to the blockchain. In this work, we propose an ordering rule that prevents front-running under these constraints. We model (§3) front-
running as a competition between rational participants, a regular user and a set of attackers, all maximizing their own expected revenue. The state of the system gives rise to an opportunity. Any participant can publish a transaction to take advantage of this opportunity, and the first such transaction on chain earns a reward R. Each transaction carries a bid; the winning transaction pays its full bid, while every later transaction pays γb, where γ > 0 is the losingfee rate. The regular user discovers an opportunity first and publishes a transaction to earn the reward. An attacker observes it and reacts with a competing transaction. The two then keep publishing transactions or updating the bids of their existing transactions. An ordering protocol then orders these transactions, determining the winner and the revenues. Our primary goal is to enforce causal ordering of transactions. Most transactions are independent and therefore commute. We focus on conflicting ones, whose order affects outcomes; in our setting, these are the transactions that compete for the same opportunity. The protocol should also be profitable: The user earns a strictly positive expected revenue since she finds the opportunity first; otherwise the user would have little incentive to issue functional transactions like arbitrage. Since a participant could publish many copies of her transaction to increase her chance of winning, we require anti-spam: Each rational participant publishes at most one transaction. We present PRECEDE, Power-weighted Randomization for Enforcing Causal ordering through Entry DEterrence (§4). PRECEDE removes the incentive that drives front-running. The attack occurs only because it is profitable; PRECEDE applies mechanism design to make it unprofitable, deterring attacks. It thus enforces the causal order without trust assumptions. To achieve this, PRECEDE orders transactions by a randomized power-weighted lottery: It gives each transaction with bid b the weight w(b) = bk , where k > 1, and places it first with probability proportional to that weight. This rule generalizes two existing mechanisms. As k → ∞, all weight concentrates on the highest bid, degenerating to the bid-priority ordering of practical blockchains; at k = 0, all weights are equal, degenerating to uniform random ordering. Under this mechanism, the user has a deterrence strategy: By publishing one transaction with a sufficiently large bid, she ensures that every later entrant who observes her transaction earns a non-positive expected revenue. Intuitively, the super-linear weight squeezes counter-bids from both ends: A small bid has too little weight to win, while a large bid costs more than its expected reward. Front-running is therefore unprofitable. We give a closed-form expression for the smallest deterring bid for a newly discovered opportunity. Order randomization raises the same spam concern as uniform random ordering: A participant might publish many transactions to increase her chance of winning. We show that every rational participant publishes a single bid if and only if k ≥ ln 2/ ln(1 + γ), so PRECEDE satisfies antispam. We further show that, when k meets the same bound, the deterrence strategy is also profitable: The user earns
strictly positive expected revenue and remains incentivized to discover opportunities. Beyond the existence of this strategy, we also verify that rational players are incentivized to play it rather than use other strategies. We analyze this as a sequential game (§5), played between a user and an attacker. They act alternately, and the attacker moves last, reflecting her advantage in observing and reacting to others’ transactions (e.g., from lower network latency, or from controlling the set of placed transactions as the validator). We prove that, whenever k ≥ max{2, exp(1/γ)/γ}, it is a Subgame-Perfect Nash Equilibrium (SPNE) for the user to play the deterrence strategy in the first step and for neither player to act thereafter, achieving causal ordering regardless of the game’s length. This bound is loose: Our numerical experiments show that the anti-spam bound alone already suffices. We further study how to choose k so that PRECEDE meets both the anti-spam and equilibrium requirements while maximizing the user’s expected revenue (§6). A numerical simulation shows that the equilibrium bound is loose, so a much smaller k already suffices in practice. Although γ varies across opportunities, the designer can conservatively fix a single k that works for a range of γ values. For a fixed γ , the user’s revenue is maximized at k = 1 + 1/γ , where it equals γR/(1 + γ). Finally, we show that PRECEDE also defends against the sandwich attack [11], a prominent front-running-based attack (§7). In a sandwich attack, a user buys an asset on a decentralized exchange, where buying raises the asset’s price. The attacker front-runs to buy first, lets the user’s own transaction push the price higher, and then back-runs to sell at that higher price, profiting at the user’s expense. Under PRECEDE, defending against the sandwich attack is no harder than defending against front-running, and the user’s resulting cost of deterrence is strictly less than the loss she would suffer from a sandwich attack in practical blockchains. In all, our contributions are: (1) Modeling of frontrunning as competition under generic ordering protocols; (2) entry deterrence as a new ordering principle, distinct from time- and content-based ones; (3) PRECEDE, a powerweighted randomized lottery realizing this principle; (4) a closed-form expression for the smallest bid that deters all front-running; (5) an anti-spam reduction showing that single bids dominate multi-bid strategies; (6) game-theoretic proof that the deterrence strategy is a subgame-perfect equilibrium; (7) analysis of how to choose the parameter k and (8) extension to sandwich attacks. PRECEDE can be deployed directly in any censorshipresistant blockchain with only a small change to its transaction ordering mechanism.
2. Related Work Front-running is a central security concern for blockchain systems. Such attacks are widespread in practice as attackers front-run user transactions for profit [9], [10], [16], [27]. A large body of work studies front-running
attacks [9], [27], [44], [45], [46], [47], [48], [49], [50], [51], as well as other attacks they enable [13], such as sandwich attacks [10], [11], [12], [15], [52], [53], [54], [55], [56] and multi-victim generalizations [57], [58]. An extensive body of work designs transaction ordering protocols to defend against front-running [59], [60]. The dominant approach relies on a committee of nodes that orders transactions by their arrival order [17], [18], [61] or arrival timestamps [19], [20], aiming to prevent ordering manipulation. However, with an adversarial network and even a single corrupted committee node, no such protocol can respect the order in which nodes receive transactions [17], [19]. These local orders can conflict cyclically, leaving no global order that satisfies them all [62], [63]. The resulting arbitrary tie-breaks let an attacker order herself ahead, and thus do not prevent front-running. The field has therefore relaxed its goal to weaker notions: batch-order fairness, which groups transactions into batches without intra-batch order guarantees [17], [18], [64], [65], [66], [67], [68], [69], [70], [71], [72] (or with stricter intra-batch rules that still admit front-running [73], [74]); timed-order fairness, which only constrains transactions separated by more than a certain delay threshold [19], [20], [71], [75], [76], [77], [78], [79], [80] (or provides this guarantee only with high probability [81]); and bounded unfairness, which caps how far a transaction can be displaced behind another [82]. Yet none eliminates front-running: An attacker reacting quickly enough fits within the batch, time window, or position bound each relaxation permits. The Ambush attack empirically demonstrates this for a batch-order-fair system [21]. Another line of work hides transaction content until ordering is fixed. These designs differ in who opens the ciphertext: a decrypting committee [28], [32], [78], [83], [84], [85], [86], [87], [88], [89], [90], [91], [92], [93], a trusted execution environment (TEE [94]) [29], [95], [96], a timelocked puzzle or delay-based encryption [30], [97], [98], [99], a trusted relay [100], or the transaction creator [31], [101], [102]. However, such schemes still leave room for front-running: Publishing a transaction already exposes timing, propagation, and creator metadata, signals from which an attacker can speculatively race [33]. Moreover, parties able to open the ciphertext may be incentivized to abuse that capability and, even when confidentiality holds, distort DeFi market microstructure such as liquidations [103]. Within the committee-decryption subclass, the failure runs deeper still: Wadhwa et al. [104] prove a general impossibility with rational participants, where committee members can always deniably collude to leak contents. In contrast, we make transaction content public and reshape the ordering rule to disincentivize front-running. Some solutions hide transaction contents and offer weaker notions of order fairness at the same time [75], [78], [88], [89], [96]. But they are as vulnerable to frontrunning as the receive-order-fair protocols and contenthiding schemes they combine. Within a single block, it is possible to uniformly randomize the transaction order to remove the deterministic priority that reordering attacks exploit [22], [23]. However,
uniform randomization incentivizes spam, where adversaries publish many transactions to increase their probability of front-running [24], [26], [27] or sandwich attacks [105], as observed in deployed systems [25]. PRECEDE disincentivizes spamming. Several works address sandwich attacks specifically in Automated Market Makers [52], [53], [104], [106], [107], [108], [109], [110], [111] and address specific, predefined front-running attacks that do not change in response to their defense [21], [46], [112]. A complementary direction lets the applications themselves impose sequencing constraints, rather than fixing a global ordering rule [113]. We address the general front-running problem. Several adjacent lines of work study transaction ordering without directly preventing front-running. Some target other goals: incentivized inclusion of report transactions [7], bounded confirmation delay [114], reduced tail latency for long-waiting transactions [115], empirical quantification of order-fairness violations under adversarial reordering [116], [117], similar order positions for transactions with similar issue times and bids [118], [119], or coordination of transaction order with participants’ declared workflow intent in collaborative processes [120]. Another line detects unfair orderings post hoc rather than preventing them [121]. But such auditing mis-accuses honest miners with probability exceeding 25% within the sub-30-second window in which front-running operates [122]. Our mechanism enforces causal ordering, a classical notion from distributed systems [35], [36], [37]: A transaction issued in response to an observed one should not be ordered before it. However, classical solutions (like Lamport timestamps [34]) do not apply because malicious participants can misreport their timestamps to front-run, and the blockchain cannot verify them. We focus on the ordering of transactions for the same opportunity, which are linked by a data dependency so that their relative order affects their execution outcomes. Some ordering protocols [66], [67] and practical systems [14] also focus on such transactions, but require the blockchain to explicitly extract data dependencies between transactions. Extracting these dependencies is hard in general [123]. PRECEDE does not rely on transaction semantics. Another line of work, like ours, orders transactions by their bids. Validators in deployed blockchains usually order transactions by descending bid [3], [5], [14]. This introduces a bidding war: The user must outbid the attacker to win, paying away her reward [9], [16]. Flashbots [15] moves this competition off-chain, but the same bidding war still occurs [16]. We instead order at random. Another proposal lets users pay to improve their transactions’ positions through a trusted party [124]; we do not rely on this strong assumption. In the game theory literature, contest theory [125], [126] studies similar competitive settings: Players pay bids to compete for a prize, and the winner is drawn at random, with each bid’s winning probability proportional to a weight that increases with the bid. Our mechanism adopts the powerweight function from the Tullock contest [126]. Tullock contests, however, are full-pay: Every player pays her bid
in full whether she wins or loses. In practical blockchains, by contrast, a losing transaction is reverted and consumes different computational resources than the winner, paying a ratio of its bid. We adopt this partial-pay setting, to which prior results do not apply. Close to our work, sequential Tullock contests study players who bid in turn: Gao et al. [127] solve the two-player case for a general power-weight function and specifically observe entry deterrence, but only under all-pay costs and a single action per player, neither of which holds in transaction ordering. Hinnosaar [128] solves the multi-player case, but shares the same two assumptions and, in addition, applies only to a linear weight function. Our model instead goes beyond all-pay and lets a player act at multiple steps and publish multiple transactions (spam), both inherent to transaction ordering.
3. Model We consider a regular user and a set of attackers competing on a blockchain (§3.1) for a reward R (§3.2). Transaction publication induces a causality relation among transactions (§3.3). Our goal is to design a protocol that achieves Causal Ordering, Anti-Spam, and Profitability (§3.4).
3.1. Participants and Blockchain The system comprises rational participants P = {U }∪A: a user U and a set of attackers A. They all take actions to maximize their own revenue. Nodes called validators run a state machine replication protocol to maintain a blockchain. The blockchain is a stateful virtual machine that executes a totally ordered sequence of transactions. Each transaction is a log entry containing an instruction that updates the state. Participants create and publish these transactions. Formally, a transaction tx is a tuple (data, bid), where data includes the instruction and the creator, and bid is the fee that the creator is willing to pay for the transaction to be included on-chain. We denote the bid of a transaction tx by b(tx) > 0, abbreviated b when tx is clear from context. Once the transaction is on chain, the blockchain charges the creator the bid (or a ratio thereof). Validators maintain the blockchain by running an ordering protocol that extends the transaction sequence with new transactions; the virtual machine then executes the transactions in the order the protocol determines. We abstract away the blockchain implementation details and treat the ordering protocol as an idealized service that receives transactions from participants and processes them. Each execution of the ordering protocol consists of two phases: a collection phase and an ordering phase. In the collection phase, the protocol gathers the set of transactions it has received from participants, which we denote by TXall . In the ordering phase, the protocol runs an ordering function f on TXall . We assume an external random beacon pulse Q that is unpredictable before the ordering phase and becomes available when it begins; such beacons are well-established [129], [130] and are used in blockchain
mechanism design [7], [131]. Formally, f takes TXall and Q as input and outputs an ordered vector f (TXall , Q). The blockchain appends this output to its transaction sequence; the current execution then ends and the next begins.
3.2. Reward The state of the system allows any participant to earn an on-chain reward R by publishing a transaction. Only the creator of the first transaction for it in the blockchain’s transaction order earns R; every other transaction earns nothing. For simplicity, we ignore transactions that do not compete for R. The user knows of the reward at time 0 and can publish a transaction to receive it throughout the window [0, T ], the collection phase of a single execution of the ordering protocol. An attacker is initially unaware of the reward; only after the user publishes a transaction can the attacker observe it and publish her own to compete for the reward. We now describe the payment for transactions in TXall . We call the first transaction in f (TXall , Q) the winner and denote it by fwin (TXall , Q). For any transaction tx ∈ TXall , if it is the winner, i.e. tx = fwin (TXall , Q), its creator earns a reward R and pays the full bid b(tx); otherwise, the creator pays a ratio γ > 0 of the bid, the losing-fee rate γ , so the payment is γ b(tx). This rate reflects that, in practical blockchains, a non-winning transaction reverts along a different execution path and pays only for the resources it consumes [9], usually less than the winner’s payment but occasionally even slightly more (§A). The rate γ varies across competitions, but a participant knows it accurately in advance by locally pre-executing her transaction.
3.3. System Progress An execution unfolds over the window [0, T ]. To compete for the reward, a participant either publishes new transactions or increases the bids of those she has already published, and she may do so at any time. She cannot decrease the bid of an existing transaction [9]. A transaction a participant publishes becomes visible to the others only after some latency, as it propagates through the network, and this latency can be arbitrary. They observe it together with its bid. This is what lets an attacker react: The user may act at any time, whereas an attacker, initially unaware of the reward, publishes only after a user’s first transaction becomes visible to her. We assume that the ordering protocol is censorshipresistant: Every transaction published during [0, T ] enters TXall . This property is satisfied by a range of protocols that aggregate transactions across validators (e.g., [17], [18], [19], [20]). Such aggregation prevents any single node from omitting or deferring transactions [7]. Among all transactions in TXall , denote by TXU the user’s transactions and by TXA those of any attacker A ∈ A. Denote by P pub the publication strategy of a participant, which specifies how she publishes transactions and updates bids based on what she has observed at any time.
3.4. Goal Our goal is to design a protocol, an ordering function f together with a publication strategy P pub , i.e., a pair (f, P pub ), that eliminates front-running, captured by three properties: Causal Ordering, Anti-Spam, and Profitability. First, Causal Ordering requires that the protocol never makes any attacker’s transaction the winner: Since every attacker publishes only after observing the user’s transaction, the winner must be one of the user’s transactions. The difficulty is that the ordering function f cannot observe this causality: From TXall and Q alone it cannot tell which transaction was published in reaction to another, so it cannot single out the attacker’s transaction and must secure the guarantee blindly. Definition 1 (Causal Ordering). A protocol (f, P pub ) satisfies Causal Ordering if, for any random beacon pulse Q, it never orders any attacker’s transaction first, so no attacker front-runs the user successfully. Formally, let fwin (TXall , Q) be the winner of the ordering f (TXall , Q) and TXA the set of transactions an attacker A ∈ A publishes; we require [ ∀Q, fwin (TXall , Q) ∈ / TXA . A∈A
Second, because f orders transactions using the random beacon Q, such randomization might invite spam: A participant publishes many transactions to raise the chance that one of them is ordered first, reducing system efficiency. We therefore require that each participant publishes at most one transaction: Definition 2 (Anti-Spam). A protocol (f, P pub ) satisfies Anti-Spam if the user and every attacker publish at most one transaction, i.e., |TXU | ≤ 1 and for all A ∈ A, |TXA | ≤ 1. Finally, a user who follows the prescribed publication strategy P pub should profit; otherwise she stops exploring the system for opportunities (e.g., arbitrage), eroding system efficiency. Definition 3 (Profitability). A protocol (f, P pub ) satisfies Profitability if the user obtains a strictly positive expected revenue when she follows the protocol’s publication strategy P pub .
4. PRECEDE We present PRECEDE, Power-weighted Randomization for Enforcing Causal ordering through Entry DEterrence, to address front-running. We provide the design intuition (§4.1), the ordering protocol (§4.2), and the publication strategy by which a user deters entry, achieving Causal Ordering (§4.3). We then show that the protocol satisfies Anti-Spam (§4.4) and Profitability (§4.5).
4.1. Design Intuition PRECEDE orders transactions solely by the bid each carries, which is on-chain and verifiable, rather than by
timestamps or arrival times. Concretely, the protocol fixes an exponent k > 1 and assigns each transaction tx the weight w(b(tx)) = bk (tx), ordering it first with probability proportional to its weight. Our design principle is entry deterrence: The user publishes a bid high enough so that the attacker cannot profit by entry, i.e., by publishing a transaction to compete, so the attacker abstains. Whether the user can deter the attacker while still profiting hinges on the exponent k . As k grows to infinity, the highest bid wins with probability approaching one. The design then degenerates into the deterministic descendingbid ordering of deployed blockchains [3], [5], [14]. Under this rule the user can deter entry only by bidding the entire reward R: With any smaller bid, the attacker will bid slightly higher, win with certainty, and earn a positive revenue. Such deterrence leaves the user no profit, violating Profitability. A carefully chosen k softens this rule, letting the user deter entry more cheaply. Overbidding no longer guarantees a win, and a non-winning counter-bid pays the ratio γ of its bid. The attacker thus faces a dilemma: A small counterbid is cheap but, against the user’s large weight, wins with too low a probability to profit, while a large one wins with high probability but, since k > 1, must be so large that its cost exceeds the reward R. Neither option yields a positive expected revenue, so a bid strictly below R suffices to deter the attacker. At the other extreme, k = 0 makes every bid carry the same weight, so the ordering degenerates into uniform random selection. A participant’s winning probability then grows with the number of transactions she publishes, inviting spam [26], violating the Anti-Spam property. An exponent k > 1 makes merging, placing the whole bid on a single transaction, attractive on the winning rate: Because bk is superadditive, a single bid outweighs the same amount split across several transactions, so merging gives a higher winning probability than spamming. However, merging is not free. When the losing-fee rate γ is smaller than 1, as is common [9], a losing transaction pays only the fraction γ of its bid, while the winner pays in full. Concentrating the whole bid on a single transaction thus charges this full amount whenever it wins, raising the expected payment. As before, a carefully chosen k tips this balance: It should be large enough that the winning-probability gain from merging outweighs the extra payment, so each participant publishes a single transaction.
4.2. Ordering Protocol Recall that an ordering protocol runs in two phases: a collection phase, in which it gathers every transaction it receives into the set TXall , and an ordering phase, in which it applies an ordering function f to TXall and the random beacon Q to produce the order f (TXall , Q). PRECEDE’s ordering function f realizes a weighted ordering: It gives each transaction a weight and orders one transaction ahead of another with probability proportional to its weight. PRECEDE uses a power-weight function, where tx has weight w(b(tx)) = bk (tx), and k > 1 is the exponent
Algorithm 1 PRECEDE Ordering Function Input: Transaction set TXall , random beacon Q, exponent parameter k Ensure: Ordered sequence of transactions 1: for all tx ∈ TXall in parallel do 2: r(tx) ← H(tx ∥ Q) ▷ Random value in [0, 1] k 3: s(tx) ← r(tx)1/b (tx) ▷ set s(tx) = 0 if b(tx) = 0 4: end for 5: π ← sequence of transactions in TXall sorted by s(·) in descending order 6: return π parameter of the protocol. For two transactions tx1 and tx2 , we say tx1 ≺Q f tx2 if f orders tx1 before tx2 given Q. By the definition of a weighted ordering, Pr[tx1 ≺Q f tx2 ] =
w(b(tx1 )) . w(b(tx1 )) + w(b(tx2 ))
(1)
However, to serve as an ordering function, f should also satisfy three further properties. First, f must produce a total order, not just the pairwise outcomes above: Realizing the pairwise probabilities independently could create a cycle Q Q such as tx1 ≺Q f tx2 ≺f tx3 ≺f tx1 , which no ordering satisfies. Second, TXall holds more than the transactions competing for one reward; it also contains transactions competing for other rewards, and transactions that do not compete at all, and these must not affect the order among the transactions competing for the same reward. Third, f must be efficient to compute. We meet all three with a score-based method [132] that scores all transactions in parallel and then sorts once. Denote by H(·) a random oracle that maps any input to a value uniformly distributed in the range [0, 1] and by ∥ the concatenation operator. For each transaction tx ∈ TXall we draw a random value r(tx) = H(tx ∥ Q) and set its score s(tx) = r(tx)1/w(b(tx)) . The ordering function orders the transactions by descending score: tx1 ≺Q f tx2 if and only if s(tx1 ) > s(tx2 ). Algorithm 1 states f in full. This method realizes the pairwise probability (Equation 1) [132], and it meets the three properties. Sorting by score yields a single total order, and scoring in parallel before sorting once is efficient. Moreover, PRECEDE scores each transaction by s(tx), which depends only on the bid of transaction tx and the beacon Q, not on any other transaction. Hence the relative order among the transactions competing for one reward is independent of all other transactions, exactly as if they were ordered alone, so each competition can be analyzed in isolation. Restricting our model to the competition for a single reward is therefore without loss of generality.
4.3. Deterrence Strategy By definition (§3.2), the user is the participant who first identifies the reward, and hence the first to publish;
an attacker is any participant who later observes her bid and may enter to compete. We realize entry deterrence as a publication strategy: The user publishes a single bid large enough so no attacker can profit by competing. We compute the attacker’s revenue (§4.3.1), derive the bid that deters entry (§4.3.2), and provide the user’s strategy based on it (§4.3.3). 4.3.1. Revenue of the attacker. We consider the case in which an attacker, who has not yet published any transaction, has observed a nonempty set of transactions TX from the user, and now publishes a single transaction to compete for the reward. Denote the total weight of the set TX by: X W = bk (tx) > 0. tx∈TX
The attacker considers entering with a single transaction txA of bid b(txA ) > 0, hereafter simply b. Her transaction has weight bk , so PRECEDE places it first with probability q = bk /(bk + W ) (Equation 1). Under the payment rule, winning yields R − b (collect R, pay the full bid b) and losing yields −γb. Her expected revenue is therefore u(b; W ) = q (R − b) − (1 − q) γ b bk (R − b) − γ b W = bk + W k−1 b Rb − bk − γ W = . bk + W
(2)
4.3.2. The deterrence weight and bid. We now find the minimal weight W of observed transactions that deters the attacker from entry. The attacker earns revenue u(b; W ) from a bid b > 0 and 0 from abstaining, so entry is unprofitable exactly when u(b; W ) ≤ 0 for all b > 0. The following lemma gives the exact threshold of W at which this condition holds. Lemma 1 (Deterrence weight). Fix the exponent parameter k > 1 and the losing-fee rate γ > 0, and let W be the total weight of transactions the attacker observes. Then the attacker’s expected revenue with any single bid b > 0 satisfies u(b; W ) ≤ 0 if and only if W ≥
(k − 1)k−1 k R . γ kk
Intuitively, since the attacker’s revenue u(b; W ) is positive if and only if R bk−1 − bk − γ W > 0 (Equation 2), we then calculate the minimum W that makes this expression non-positive for all b > 0. The proof is in Appendix B. We name the threshold of the weight W that deters entry the deterrence weight, denoted: k,γ := Wdtr
(k − 1)k−1 k R . γ kk
By Lemma 1, a user who wants to deter all entry with k,γ a single bid must give that bid weight at least Wdtr . The
Algorithm 2 Deterrence Publication Strategy P pub for P Input: reward R, losing-fee rate γ , exponent parameter k , the set TX of transactions P has received P k 1: W ← ▷ total weight of transactions tx∈TX b (tx) 2: if TX = ∅ then ▷ P has not observed any transaction 3: publish a transaction with bid (k−1)k−1 1/k bk,γ dtr = R γ kk ▷ publish the deterrence bid k,γ 4: else if W ≥ Wdtr then ▷ entry is unprofitable 5: publish nothing 6: else ▷ the choice here is immaterial 7: publish nothing 8: end if
smallest such bid, which we call the deterrence bid bk,γ dtr , k,γ has weight exactly Wdtr : 1/k (k − 1)k−1 k,γ k,γ 1/k bdtr := Wdtr . (3) = R γ kk This bid achieves entry deterrence by making any attacker’s transaction unprofitable. Theorem 1 (Entry deterrence). Fix the exponent parameter k > 1 and the losing-fee rate γ > 0, and suppose the user publishes the deterrence bid bk,γ dtr . Then the attacker’s expected revenue with any single bid b > 0 is non-positive, k,γ i.e., u(b; Wdtr ) ≤ 0. This follows directly from Lemma 1: The deterrence bid k k,γ has weight bk,γ = W dtr dtr (Equation 3), so the attacker k,γ k,γ observes total weight W = Wdtr , at which u(b; Wdtr )≤0 for all b > 0.
4.3.3. Strategy. We give a single strategy that every participant P runs; what she observes, not her role, determines her action. The bound of Lemma 1 depends only on the weight P observes, not on who produced it, so one deterrence bid deters every later participant. Therefore, the strategy prescribes P ’s action in three cases. If she has not yet observed any transaction, meaning she is the first to publish a transaction to her knowledge, she publishes the deterrence bid bk,γ dtr . If instead she observes a set of transactions whose total weight already deters entry, that is k,γ W ≥ Wdtr , she publishes nothing. In the remaining case, P publishes nothing; the user, being the first to publish, never reaches this case, so the choice is immaterial and may be replaced by any other action. Algorithm 2 states this strategy P pub , which P runs once, at the first time t ∈ [0, T ] she learns of the reward R. At every other time in the window she does nothing, leaving any bid she has published unchanged.
4.4. Anti-Spam Requirements We show that PRECEDE satisfies Anti-Spam. We consider any number of participants and replace one participant’s transactions by a single bid of the same weight (§4.4.1). We analyze the resulting revenues (§4.4.2), show that the replacement leaves every other participant’s revenue unchanged (§4.4.3), and show that the replaced participant is not worse off if k is no less than a threshold that depends on γ (§4.4.4). 4.4.1. Setup. Anti-Spam is a per-participant property: Whether a rational participant gains by publishing multiple transactions does not depend on her role as user or attacker. We therefore drop this distinction and consider a general setting with n participants P = {P1 , . . . , Pn }, which is both more general, covering any number of participants, and stronger, since the guarantee holds for every one of them. By time T , TXall collects, for all 1 ≤ i ≤ n, Pi ’s set of mi transactions with their final bids; we denote the mi bids (1) (m ) of Pi by a vector bi = (bi , . . . , bi i ) of length mi ≥ 0, (j) with bi > 0 for all 1 ≤ j ≤ mi . The empty vector bi = () denotes abstention. Without loss of generality, we assume P1 publishes more than one transaction, i.e., m1 > 1; the total weight of her Pm1 (j) k transactions is W1 = j=1 (b1 ) . Denote by b̄1 the single bid that has the same total weight: !1/k m1 X (j) k b̄1 := (b1 ) . (4) j=1
4.4.2. Revenue. We analyze each participant’s revenue in two scenarios: the original one, in which P1 publishes b1 , and an alternative one, which is identical except that P1 publishes the single bid b̄1 instead. We detail the notation for the original scenario; the alternative scenario is obtained by substituting (b̄1 ) for b1 throughout. The participants’ bids excluding P1 ’s, b−1 = (b2 , . . . , bn ), are fixed. Denote by W (b1 , b−1 ) the total weight of all transactions: W (b1 , b−1 ) =
mi n X X (j) (bi )k . i=1 j=1
Since the replacement bid b̄1 has the same weight as b1 (Equation 4), the total weight is the same in both scenarios: W (b1 , b−1 ) = W ((b̄1 ), b−1 ).
Denote by q(b, b−1 , b1 ) the probability that a transaction of bid b is ordered first: q(b, b−1 , b1 ) =
bk . W (b1 , b−1 )
(5)
Denote by Ci (b1 , b−1 ) the expected total payment of participant Pi . Recall that a transaction pays the ratio γ of its bid whether or not it is ordered first, and the one ordered first pays its bid in full, that is, an additional (1 − γ) of (j) (j) it. So a transaction of bid bi pays γ bi for sure, plus the
(j)
(j)
extra (1−γ) bi with probability q(bi , b−1 , b1 ). Summing this expected payment over all of Pi ’s transactions, mi X (j) (j) (j) Ci (b1 , b−1 ) = γ bi + (1 − γ) q(bi , b−1 , b1 ) bi . j=1
(6) The revenue ui (b1 , b−1 ) of Pi is the expected reward from winning minus the expected payment ui (b1 , b−1 ) = R
mi X
(j) q(bi , b−1 , b1 ) − Ci (b1 , b−1 ).
(7)
j=1
4.4.3. Other participants are unaffected. Replacing P1 ’s bid vector b1 with the single bid (b̄1 ) preserves the total Pm1 (j) k weight, since b̄k1 = j=1 (b1 ) (Equation 4). Every other participant’s winning probability and payment depend on b1 only through the total weight (Equations 5–7), so both, and hence her revenue, are unchanged, implying the following proposition. Proposition 1 (Merging is externality-free). For every i ̸= 1, replacing P1 ’s bid vector b1 with the single bid (b̄1 ) leaves participant Pi ’s revenue unchanged, ui (b̄1 ), b−1 = ui (b1 , b−1 ). 4.4.4. Lower bound for the exponent k . Intuitively, the larger k is, the more weight a higher bid carries, so the single bid b̄1 (Equation 4) that matches the total weight of P1 ’s bids can be much smaller than their sum. Since each transaction pays a fee proportional to its bid, a large enough k makes merging profitable for P1 . We thereby provide a tight lower bound on k that guarantees Anti-Spam. Theorem 2 (Anti-Spam Threshold). Fix the exponent parameter k > 1 and the losing-fee rate γ > 0. For every bid vector b1 of P1 and every profile b−1 of the other participants’ bids, replacing b1 with the single bid (b̄1 ) does not decrease P1 ’s revenue, u1 (b̄1 ), b−1 ≥ u1 (b1 , b−1 ), if and only if k ≥
ln 2 . ln(1 + γ)
To prove this, we note that replacing P1 ’s bids with the single equal-weight bid leaves her winning probability, and hence her expected reward, unchanged, so it raises her revenue exactly when it lowers her expected cost. This is hardest when she uses two equal bids and no other weight competes, which gives the threshold k ≥ ln 2/ ln(1 + γ); being the hardest case, it makes the same threshold suffice for any number of bids. The proof is in Appendix C.
4.5. Profitability of Deterrence Profitability requires the user to obtain strictly positive expected revenue when following the deterrence strategy. Since the attacker would not compete, the user wins the
k,γ reward R and pays the deterrence bid bk,γ dtr . Denote by udtr the user’s revenue under the deterrence strategy: 1/k ! (k − 1)k−1 k,γ k,γ udtr := R − bdtr = R 1 − . γ kk
We now show that whenever PRECEDE meets the AntiSpam threshold of Theorem 2, it also satisfies Profitability. ln 2 Proposition 2 (Deterrence is profitable). If k ≥ ln(1+γ) , then the deterrence strategy results in strictly positive revenue, namely uk,γ dtr > 0.
Intuitively, the deterrence strategy is profitable exactly when the deterrence bid is strictly smaller than the reward R. A larger exponent k pushes the deterrence bid below R, so Profitability reduces to a lower bound on k . The Anti-Spam threshold from Theorem 2 imposes a stronger lower bound on k , and therefore automatically guarantees Profitability. The proof is in Appendix D.
5. Game-Theoretic Analysis Our model gives rise to a sequential game played by a user and an attacker (§5.1). We first solve a two-step version (§5.2), where the user leads and the attacker responds, proving that the user playing the deterrence strategy and the attacker abstaining form an SPNE; we then extend this result to the full game with an arbitrary number of steps (§5.3).
5.1. Game Model The competition for reward gives rise to a sequential game. Throughout the game analysis, we assume k ≥ ln 2/ ln(1 + γ), which ensures both Anti-Spam and Profitability. We specify the game’s players (§5.1.1), their actions (§5.1.2), their utilities (§5.1.3), and the solution concept we adopt (§5.1.4). 5.1.1. Players. There are two players: a regular user P1 and a single attacker P2 . Modeling a single attacker is not a reduction of our model with multiple attackers, but rather a worst-case assumption: It captures all attackers colluding under one shared utility, whereas independent attackers would also compete among themselves and make deterrence easier for the user. 5.1.2. Game progress and actions. The two players compete during the collection window [0, T ], which we discretize into 2m steps (for any m ≥ 1). The user P1 and the attacker P2 move in alternating turns: P1 on the odd steps and P2 on the even steps, with each player observing all earlier actions before acting. The number of steps is even so that the attacker moves last, capturing her advantage in observing and reacting to others’ transactions, be it due to lower network latency or to her control over the set of placed transactions as the validator. At each of her steps, a player may publish new transactions or increase the bids of those she has already published (§3.3). By Theorem 2, replacing any set of a player’s
transactions by a single bid of the same total weight never lowers her own revenue, so a rational player gains nothing by publishing more than one transaction. By Proposition 1, the same replacement leaves the other player’s revenue unchanged. Without loss of generality, we therefore restrict our attention to strategies in which each player publishes at most a single transaction. Under this restriction, the action of P1 on her j -th step (j) (step 2j − 1) is a bid b1 ∈ R≥0 , and that of P2 on her (j) j -th step (step 2j ) is a bid b2 ∈ R≥0 , for j = 1, . . . , m; a bid of 0 denotes publishing no transaction. The bid is non(j) (j+1) decreasing, bi ≤ bi , and although a player acts at every (j+1) (j) step of the game, a step with no bid increase (bi = bi ) requires no action from her in practice. Since only P1 knows (j) the reward initially, she moves first, and b1 = 0 forces (j) b2 = 0: Without observing P1 ’s transaction, P2 cannot publish. We denote this 2m-step game with parameters m, k,γ k , and γ by Gm . 5.1.3. Utility. The ordering protocol uses only each player’s (m) final bid bi : It weighs a transaction by w(b) = bk and charges its creator on that same bid (Algorithm 1). Hence the winner, the payments, and each player’s utility depend (m) (m) only on the two final-step bids b1 and b2 , not on the (m) (m) intermediate steps. In particular, if b1 = b2 = 0, no transaction is published and both utilities are 0. The total weight of the two transactions is k (m) (m) (m) k := b(m) W b1 , b2 + b2 , 1 and Pi wins with probability (m) (m) qi b1 , b2
(m) k
bi
:=
(m)
(m)
(8)
W b1 , b2
(m) (m) b1 , b2 > 0, and qi
(m) (m) b1 , b2 = 0 other-
when W wise. The utility of Pi is her expected revenue. Specializing the general formula in Equation 7 to the two-player singlebid setting, (m) (m) (m) (m) ui b1 , b2 = − γ bi + R qi − (1 − γ) qi bi (m) (m) = q i R − bi − 1 − q i γ bi . (9)
5.1.4. Solution concept. Our solution concept is the Subgame-Perfect Nash Equilibrium (SPNE): The players’ strategies are a Nash equilibrium in every subgame. Here, a subgame is the game from some step t onward, given the bids placed in the previous steps 1, . . . , t − 1.
5.2. Two-Step Equilibrium We first analyze a simple version of the game with only two steps (m = 1), so each player acts once and the game G1k,γ degenerates to a Stackelberg game [133].
By backward induction, we derive the attacker’s best response (§5.2.1), then the user’s (§5.2.2), and combine them into an SPNE (§5.2.3). 5.2.1. P2 ’s best response. If b1 = 0, then P2 cannot publish, so the best response is b2 = 0. By Lemma 1, if b1 ≥ bk,γ dtr , every bid earns P2 non-positive utility, so P2 abstains and the best response is b2 = 0. For 0 < b1 < bk,γ dtr , Lemma 1 instead guarantees that some b2 > 0 earns P2 a strictly positive utility. Since u2 (b1 , ·) is continuous and tends to −∞ as b2 → ∞, P2 ’s set of best responses BR2 (b1 ) := arg max u2 (b1 , b2 ) b2 ≥0
is nonempty and compact. This set may contain several bids, so we adopt the standard assumption of breaking ties in favor of a designated player [134], [135], [136], here P1 : Among P2 ’s best responses we select the one maximizing P1 ’s utility. This choice is also natural in our game: A higher attacker bid only lowers P1 ’s utility (Equation 9), so favoring P1 selects the attacker’s lowest best-response bid: b∗2 (b1 ) = min BR2 (b1 ), which is well defined because BR2 (b1 ) is nonempty and compact. Selecting the lowest bid also minimizes the attacker’s effort: Her best responses all yield her the same utility, so the lowest one attains that utility at the smallest expected payment. In summary, P2 ’s best response is ( 0, b1 = 0 or b1 ≥ bk,γ dtr , ∗ b2 (b1 ) = k,γ min BR2 (b1 ), 0 < b1 < bdtr . 5.2.2. P1 ’s best response. Given P2 ’s best response function b∗2 (b1 ), P1 chooses the bid b1 ≥ 0 that maximizes her utility u1 b1 , b∗2 (b1 ) . ∗ If b1 ≥ bk,γ dtr , then b2 (b1 ) = 0 and u1 (b1 , 0) = R − b1 , so P1 ’s utility is highest at the smallest deterring bid k,γ b1 = bk,γ dtr , where it equals udtr > 0 (Proposition 2). When k,γ b1 = 0, her utility is 0 < udtr , so abstention is never optimal for P1 . ∗ When 0 < b1 < bk,γ dtr , P2 ’s best response b2 (b1 ) is to publish a positive bid. We call this the accommodation strategy of P1 . Denote by uk,γ acc the maximum utility P1 can earn by the accommodation strategy assuming P2 adopts her best response: uk,γ sup u1 b1 , b∗2 (b1 ) . (10) acc := 0<b1 <bk,γ dtr
This supremum is finite, since u1 ≤ R for every bid profile. k,γ Therefore, when uk,γ dtr > uacc , the only best response for P1 is the deterrence strategy. Unlike the closed-form uk,γ dtr , we do not have a closedform expression for uk,γ . Computing it requires the atacc tacker’s best response b∗2 (b1 ), the positive bid that maximizes P2 ’s utility at each b1 in the accommodation range.
Since it is positive, b∗2 (b1 ) is an interior optimum and thus satisfies the first-order condition ∂u2 /∂b2 = 0. This condition is transcendental in b2 because the winning probability weighs bids by the power bk (Equation 8), and for general k and γ we cannot solve it in closed form, leaving us without a closed form for b∗2 (b1 ) or for uk,γ acc .
makes deterrence the equilibrium. We record this explicit sufficient condition on k as the following corollary.
5.2.3. Equilibrium. We want deterrence to be an equilibrium, with P1 publishing the deterring bid bk,γ dtr and P2 abstaining. The following theorem gives the condition under which this holds.
5.3. Multiple-Step Equilibrium
Theorem 3 (Deterrence equilibrium). Fix γ > 0 and k > 1 k,γ satisfying k ≥ ln 2/ ln(1 + γ). If uk,γ dtr > uacc , then P1 k,γ publishing the deterring bid b∗1 = bdtr and P2 abstaining, b∗2 (b∗1 ) = 0, form an SPNE of the game G1k,γ . The theorem follows directly from the best-response k,γ analysis: When uk,γ dtr > uacc , deterrence is P1 ’s unique best response (§5.2.2), to which P2 responds by abstaining (§5.2.1), so the profile is an SPNE. Theorem 3 reduces the design problem to compark,γ k,γ ing uk,γ dtr with uacc . The following lemma upper-bounds uacc by a closed-form expression. Lemma 2 (Accommodation utility bound). For any γ > 0 and k > 1, the accommodation utility uk,γ acc satisfies uk,γ acc ≤
R . k min{1, γ}
When P1 accommodates, she wins with probability q1∗ and so earns q1∗ R in expectation, ignoring the payment. We show that the attacker’s optimal entry keeps q1∗ below 1/(k min{1, γ}), so the user’s utility is below R/(k min{1, γ}). The proof is in Appendix E. The lemma above caps the accommodation utility at R/(k min{1, γ}). Deterrence is therefore the equilibrium whenever the deterrence utility exceeds this cap, which we show holds if k is large enough.
Corollary 1. Fix γ > 0. If k ≥ max{2, exp(1/γ)/γ}, then P1 publishing the deterring bid b∗1 = bk,γ dtr and P2 abstaining, b∗2 (b∗1 ) = 0, form an SPNE of the game G1k,γ .
k,γ We now extend the result to the full 2m-step game Gm for any m ≥ 1. Intuitively, the two-step equilibrium should persist: P1 publishes the deterring bid at her first step and never raises it, while P2 never enters. Because P2 still moves last, any state at which P1 has failed to deter reduces to the accommodation scenario of the two-step game; so, just as before, deterrence should be the equilibrium whenever its utility is no less than the accommodation utility. However, there is still a gap in this argument. SPNE demands an equilibrium in every subgame, that is, after every possible sequence of past bids, even those that rational play would never reach. Standard backward induction would require solving these off-path subgames explicitly, which is prohibitively complicated. Instead, we first show that each such subgame has an SPNE (§5.3.1), then bound the utility P1 can obtain in any SPNE starting from her first positive bid (§5.3.2), and finally extend the two-step result k,γ by backward induction (§5.3.3). to Gm
5.3.1. Existence of SPNE. We first show the existence of an SPNE in any subgame where the user has already published a positive bid. Fix a step t ∈ {1, . . . , 2m}. A history ht−1 at the beginning of step t is the bids players published in the earlier steps 1, . . . , t − 1. Such a history fixes each player’s latest bid, the last one she has (0) (0) placed. For convenience of notation, we set b1 = b2 = 0, meaning that neither player has yet published a bid before the first step. We denote by x1 (ht−1 ) the latest bid of P1 and by x2 (ht−1 ) that of P2 : (⌊t/2⌋)
Lemma 3 (Deterrence utility bound). Fix γ > 0. If exp(1/γ) k ≥ max 2, , γ R then the utility of the deterrence strategy exceeds k min{1,γ} :
uk,γ dtr >
R . k min{1, γ}
For γ > 1, we bound the deterrence bid by its value at γ = 1, leaving a utility above R/k = R/(k min{1, γ}). For 0 < γ ≤ 1, we reduce the desired utility bound R/(k min{1, γ}) = R/(kγ) to a one-variable inequality monotone in kγ , then check it at the smallest value permitted by the hypothesis, kγ = exp(1/γ). The proof is in Appendix F. Combining the two bounds gives a bound on k : Once k ≥ max{2, exp(1/γ)/γ}, Lemmas 3 and 2 imk,γ ply uk,γ dtr > R/(k min{1, γ}) ≥ uacc . Therefore, Theorem 3
x1 (ht−1 ) := b1
,
(⌊(t−1)/2⌋)
x2 (ht−1 ) := b2
.
The floor indices count how many times each player has acted before step t: Before an odd step 2j − 1, both P1 and P2 have acted j − 1 times; before an even step 2j , P1 has acted j times and P2 has still acted j − 1 times. We show that every subgame in which P1 ’s latest bid is positive, x1 (ht−1 ) > 0, has a pure-strategy SPNE. Lemma 4 (SPNE existence after a positive user bid). Consider a subgame starting from step t with any history ht−1 such that (⌊t/2⌋) x1 (ht−1 ) = b1 > 0. Then the subgame admits a pure-strategy SPNE. By Hellwig and Leininger [137, Theorem 1], a finite-horizon perfect-information game has a pure-strategy SPNE whenever every decision has a compact action set, the feasible-action correspondence is nonempty, compactvalued, and continuous in the history, and the utilities are
continuous. Our game satisfies these conditions except that its bid space is unbounded. We therefore restrict the remaining bids to sufficiently large bounded intervals. The lower endpoint of each interval is the acting player’s latest bid, so the restriction respects the no-decrease constraint. We then choose the upper bounds large enough so that every excluded bid is strictly worse than simply keeping the latest bid. Thus an SPNE of the restricted compact game is also an SPNE of the original unbounded subgame. The proof is in Appendix G.
We prove the result by backward induction over all-zero subgames. The last all-zero subgame is exactly the twostep game. For an earlier all-zero subgame, publishing the deterring bid gives P1 revenue uk,γ dtr , publishing zero moves the game to the next all-zero subgame, and the revenue of publishing any positive alternative bid is bounded by k,γ Lemma 5. Since uk,γ dtr > uacc , no deviation can improve on deterrence. The proof is in Appendix I. The full game is itself the all-zero subgame beginning at step t = 1, so the above theorem induces a deterrence equilibrium for the whole game.
5.3.2. Bounding the utility. We call a history at the beginning of an odd step an all-zero state if both players’ latest bids are zero, and a subgame all-zero if it begins at an allzero state. We bound the utility P1 can obtain by entering with a positive bid from an all-zero state.
Corollary 2 (Multi-step deterrence SPNE). If
Lemma 5 (Positive-entry continuation bound). Consider a subgame immediately after P1 publishes a positive bid from (m) (m) an all-zero state, and let b1 , b2 be the final bids under any SPNE of this subgame. Then n o (m) (m) k,γ u1 b1 , b2 ≤ max uk,γ dtr , uacc . In the two-step game, P1 either deters P2 and earns uk,γ dtr , or accommodates her and earns at most uk,γ acc . The lemma asserts that the multi-step continuation, the actions the players take in the subgame after P1 ’s positive bid, cannot beat the larger of the two. Since P1 ’s utility depends only on the (m) (m) final bids (b1 , b2 ), the continuation is effectively a single two-step interaction, except that P2 ’s final bid is bounded (m−1) below by her earlier bid b2 . This lower bound can only hurt P1 : Were it absent, P2 would bid no higher, and a lower bid by P2 only raises P1 ’s winning probability and hence her utility whenever that utility is positive (and if it is already negative, the bound is immediate). P1 ’s utility is therefore at most that of the corresponding two-step outcome, which is in turn at most the deterrence or the accommodation utility. The proof is in Appendix H. 5.3.3. Extension of the two-step SPNE. We now extend the two-step deterrence equilibrium to the full 2m-step game. The above lemma caps the utility P1 can gain by entering with a positive bid from an all-zero state. With this bound in hand, we construct a deterrence equilibrium in every all-zero subgame by backward induction. Theorem 4 (Deterrence from every all-zero subgame). Supk,γ pose uk,γ dtr > uacc . For every odd step t = 2j − 1, consider an all-zero subgame beginning at step t, that is, (⌊t/2⌋)
b1
and
(⌊(t−1)/2⌋)
b2
(j−1)
= b1
=0
(j−1)
= b2
= 0.
Then this all-zero subgame admits an SPNE in which (ℓ)
b1 = bk,γ dtr
and
(ℓ)
b2 = 0
for every ℓ = j, . . . , m.
k,γ uk,γ dtr > uacc , k,γ then the full game Gm has an SPNE in which (j)
b1 = bk,γ dtr
and
(j)
b2 = 0
for every j = 1, . . . , m.
In all, our game-theoretic analysis indicates that, whenever deterrence is more profitable than accommodation, the user would publish the deterring bid, and the attacker would abstain. No rational participant gains by deviating.
6. Parameter Selection and User Revenue Corollary 1 only gives a sufficient condition on k for deterrence to be the equilibrium at a specific losing-fee rate γ . We first show how to choose a single k that covers a range of γ values (§6.1). We then show how the user’s revenue grows with γ (§6.2), and derive the k that maximizes the user’s revenue (§6.3).
6.1. Choosing k in Practice For a fixed γ , our analysis gives two bounds on k . The Anti-Spam bound k ≥ ln 2/ ln(1 + γ) (Theorem 2) is tight and hence necessary. For deterrence to be the equilibrium, k,γ k,γ the exact condition is uk,γ dtr > uacc (Theorem 3); since uacc has no closed form, we instead use the sufficient bound k ≥ max{2, exp(1/γ)/γ} (Corollary 1). Clearing both is safe, and since both grow as γ shrinks, choosing k for the smallest γ in a target range covers the whole range. We now turn to choosing k in practice to deter frontrunning. We first measure the losing-fee rate γ for arbitrage on Ethereum’s Uniswap V2 [138] and V3 [139] (§A). To defend against front-running on both, the designer must cover the smaller of the two rates, γ = 0.259. At this γ , the two bounds we must clear are the Anti-Spam bound k ≥ ln 2/ ln(1 + γ) ≈ 3.010 and the sufficient deterrence bound k ≥ max{2, exp(1/γ)/γ} ≈ 184. Clearing both requires their maximum, k ≥ 184, an impractically large exponent dictated entirely by the sufficient bound. Setting k = 184, Equation 3 gives a deterrence bid bk,γ dtr ≈ 0.974R, so the user is left with almost nothing, k,γ a revenue of only uk,γ dtr = R − bdtr ≈ 0.026R. This is no accident: By Equation 3, the deterrence bid approaches R
as k grows, so an unnecessarily large k drives the user’s revenue toward zero. However, we show that this sufficient bound is far looser than necessary. We conduct a numerical simulation (§J) to find the smallest k that meets our requirements. For γ = 0.259, the Anti-Spam bound requires only k ≥ 3.010, which already satisfies the exact deterrence conk,γ dition uk,γ dtr > uacc for both Uniswap V2 and V3. We now compute the user’s revenue at k = 3.010. This revenue depends on the losing-fee rate γ : We compute the deterrence bid bk,γ dtr from Equation 3 and the user’s revenue k,γ is then given by the difference uk,γ dtr = R − bdtr . For a V2 k,γ arbitrage, γ = 0.259 gives bdtr ≈ 0.830R, so the user earns k,γ revenue uk,γ dtr = R − bdtr ≈ 0.170R; for a V3 arbitrage, k,γ γ = 0.867 gives bdtr ≈ 0.555R, so the user earns revenue k,γ uk,γ dtr = R − bdtr ≈ 0.445R. This is much better than the revenue of only 0.026R when selecting k = 184.
the opposite trend, rising and then falling. The proof is in Appendix K. The revenue-optimal exponent k = 1 + γ1 depends on γ , so no single k maximizes revenue across a range of γ values. A designer who chooses a single k therefore trades off the revenues of users facing different γ values.
6.2. Design Implications for γ
7.1. Sandwich Model
The example above already hints that a larger γ raises the user’s revenue: Holding k = 3.010, the revenue grows from about 0.170R to 0.445R as γ rises from 0.259 to 0.867. This holds in general: The revenue rises with γ at every admissible k .
In a sandwich attack, the user publishes a transaction txU that buys an asset (e.g., a swap on an automated decentralized exchange [6]), and an attacker brackets it with two transactions of her own. The front-running transaction txF buys the same asset ahead of txU and raises its price, so the user overpays; the back-running transaction txB then sells at this raised price, and the user’s overpayment becomes the attacker’s profit [11], [52]. If the attack succeeds, this trading profit V > 0 is exactly the user’s loss [52]; here V counts only the trade, neglecting transaction fees. Since PRECEDE orders at random, the attacker can rarely place txF and txB in the slots immediately adjacent to txU . Following Tumas et al. [105], we therefore grant the attacker the weakest success condition: The sandwich succeeds whenever txF is ordered before txU and txB after it, regardless of any transactions ordered in between.
Proposition 3 (Revenue monotonicity at every k ). Fix any k > 1. The deterrence bid bk,γ dtr (k, γ) is strictly decreasing in γ > 0, and consequently the user’s revenue uk,γ dtr (k, γ) = R − bk,γ (k, γ) is strictly increasing in γ . dtr This follows directly from the closed form of the deter−1/k rence bid (Equation 3): bk,γ is strictly decreasing dtr ∝ γ k,γ k,γ in γ for every k > 1, so udtr = R − bdtr strictly increases. The implication for system design is direct: Although γ is not freely tunable, charging losing transactions a higher γ raises user revenue at every k .
7. Sandwich Resistance We finally show that PRECEDE also defends against the sandwich attack [11], a prominent attack built on frontrunning. We model the attack (§7.1), show that under PRECEDE defending against a sandwich attack is no harder than defending against front-running (§7.2), and conclude that the user stops it at a cost below the loss she would otherwise suffer (§7.3).
6.3. Optimization of User Revenue
7.2. Reduction to Front-Running
The previous analysis sets k only to ensure Anti-Spam and to make deterrence the equilibrium. We now determine, for a fixed γ , the choice of k that maximizes the user’s deterrence revenue.
We now show that, under PRECEDE, defending against the sandwich attack is no harder than defending against front-running with reward R = V . First, the back-run is free. The back-run only needs txB ordered after txU , and txB needs no weight to achieve this: Since txU carries a positive bid, a bid close to 0 already places txB after txU with probability close to one. The backrun cost is thus negligible. What remains matches our front-running model. Being ordered first is worth V to both sides: If txF precedes txU , the attacker collects V and the user loses it; if txU stays first, the attacker gets nothing. This is precisely a single competition (§3.2) with reward R = V , awarded to whichever of the user’s txU and the attacker’s txF is ordered first. The whole front-running analysis therefore applies with R replaced by V .
Proposition 4 (Revenue-optimal k ). Fix γ > 0. The user’s deterrence revenue uk,γ a function of dtr (k, γ), viewed as k > 1, is strictly increasing on 1, 1 + γ1 and strictly decreasing on 1 + γ1 , ∞ . Its maximum, attained uniquely at k = 1 + γ1 , is γ 1 uk,γ 1 + , γ = R. dtr γ 1+γ Intuitively, we track the trend through the deterrence bid: Its derivative in k shows that bk,γ dtr first decreases and k,γ then increases. Since uk,γ = R − b dtr dtr , the revenue follows
7.3. Cheaper Defense by PRECEDE
[7]
H. Chen, Y. Ke, X. Deng, and I. Eyal, “Prrr: Personal random rewards for blockchain reporting,” in 2026 IEEE Symposium on Security and Privacy (SP). IEEE, 2026, pp. 3835–3853.
[8]
M. Mouallem, L. Breidenbach, I. Eyal, and A. Juels, “Resilient alerting protocols for blockchains,” in Proceedings of the 33rd ACM Conference on Computer and Communications Security (CCS ’26). Association for Computing Machinery, 2026, to appear.
[9]
P. Daian, S. Goldfeder, T. Kell, Y. Li, X. Zhao, I. Bentov, L. Breidenbach, and A. Juels, “Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability,” in 2020 IEEE Symposium on Security and Privacy (SP). IEEE, 2020, pp. 910–927.
[10]
C. F. Torres, R. Camino, and R. State, “Frontrunner Jones and the raiders of the dark forest: An empirical study of frontrunning on the Ethereum blockchain,” in 30th USENIX Security Symposium, 2021, pp. 1343–1359.
[11]
L. Zhou, K. Qin, C. F. Torres, D. V. Le, and A. Gervais, “Highfrequency trading on decentralized on-chain exchanges,” in 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021, pp. 428–445.
[12]
M. Bartoletti and R. Zunino, “A theoretical basis for MEV,” in International Conference on Financial Cryptography and Data Security. Springer, 2025, pp. 225–242.
[13]
L. Heimbach and R. Wattenhofer, “Sok: Preventing transaction reordering manipulations in decentralized finance,” in Proceedings of the 4th ACM Conference on Advances in Financial Technologies, 2022, pp. 47–60.
[14]
S. Blackshear, A. Chursin, G. Danezis, A. Kichidis, L. KokorisKogias, X. Li, M. Logan, A. Menon, T. Nowacki, A. Sonnino et al., “Sui Lutris: A blockchain combining broadcast and consensus,” in Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, 2024, pp. 2606–2620.
[15]
Z. Li, J. Li, Z. He, X. Luo, T. Wang, X. Ni, W. Yang, X. Chen, and T. Chen, “Demystifying DeFi MEV activities in flashbots bundle,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023, pp. 165–179.
[16]
R. McLaughlin, C. Kruegel, and G. Vigna, “A large scale study of the Ethereum arbitrage ecosystem,” in 32nd USENIX Security Symposium (USENIX Security 23), 2023, pp. 3295–3312.
[17]
M. Kelkar, F. Zhang, S. Goldfeder, and A. Juels, “Order-fairness for Byzantine consensus,” in Advances in Cryptology - CRYPTO 2020: 40th Annual International Cryptology Conference, Santa Barbara, CA, USA, Proceedings, Part III, 2020, pp. 451–480.
[18]
Y. Khatri, “Crypto market cap tops $3 trillion as bitcoin and ether reach record highs,” https://www.theblock.co/linked/123762/ crypto-market-cap-3-trillion-bitcoin-ether-reach-record-highs, Nov. 2021, accessed, January 2026.
M. Kelkar, S. Deb, S. Long, A. Juels, and S. Kannan, “Themis: Fast, strong order-fairness in Byzantine consensus,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023, pp. 475–489.
[19]
O. Knight, “Defi TVL rebounds to $170b, erasing Terra-era bear market losses,” https://www.coindesk.com/business/2025/09/18/ defi-tvl-rebounds-to-usd170b-erasing-terra-era-bear-market-losses, 2025, accessed, November 2025.
K. Kursawe, “Wendy, the good little fairness widget: Achieving order fairness for blockchains,” in Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, 2020, pp. 25– 36.
[20]
Y. Zhang, S. Setty, Q. Chen, L. Zhou, and L. Alvisi, “Byzantine ordered consensus without Byzantine oligarchy,” in 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), 2020, pp. 633–649.
[21]
E. Park, T. Yoon, H. Nam, D. Maram, and M. S. Kang, “On frontrunning risks in batch-order fair systems for blockchains,” in Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, 2025, pp. 918–932.
[22]
XRPLF, “Transaction set canonical ordering,” https://github.com/XRPLF/rippled/blob/ e32bc674aa2a035ea0f05fe43d2f301b203f1827/src/ripple/app/ misc/CanonicalTXSet.cpp, 2022, accessed, February 2026.
By the reduction, the user defends against sandwich attacks exactly as she defends against front-running: She publishes the deterrence bid bk,γ dtr (Equation 3) evaluated at R = V , and no attack is profitable. When k ≥ ln 2/ ln(1 + γ), this bid is strictly below V (Proposition 2), so the user defends at a cost smaller than the loss V she would otherwise suffer. Empirically, with k = 3.010 covering Uniswap V2 and V3 (§6.1), the user stops a sandwich at a cost of 0.830V on V2 and 0.555V on V3, well below the loss V she would suffer in practical blockchains. Practical blockchains order by descending bid [3], [5], which is the k → ∞ limit of PRECEDE (§4.1). In this limit, the deterrence bid is V itself. To keep txU ahead of the front-run, the user must then pay her entire potential loss: Any smaller bid lets the attacker outbid her and profit, so the user would lose both V and her defense cost. The defense under PRECEDE is therefore strictly cheaper than under practical systems.
8. Conclusion Front-running is a central security problem for blockchains. Despite theoretical work and practical mitigation efforts, existing defenses fall short, as enforcing a causal order is fundamentally hard. We presented PRECEDE, which prevents front-running by removing its incentive rather than trusting any party. By ordering transactions through a power-weighted randomized lottery, PRECEDE allows a user to deter every entrant with a single bid. PRECEDE guarantees Causal Ordering, Anti-Spam, Profitability, and in particular defense against sandwich attacks. A user playing this deterrence strategy while the attacker abstains forms a subgame-perfect Nash equilibrium, so no rational attacker can profit by deviating. Every censorship-resistant blockchain can benefit from PRECEDE simply by updating its ordering function.
References [1]
[2]
[3]
V. Buterin, “Ethereum white paper,” GitHub repository, vol. 1, no. 22-23, pp. 5–7, 2013.
[4]
S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2008.
[5]
A. Yakovenko, “Solana: A new architecture for a high performance blockchain v0.8.13,” https://solana.com/solana-whitepaper. pdf, 2018, accessed, April 2024.
[6]
G. Angeris and T. Chitra, “Improved price oracles: Constant function market makers,” in Proceedings of the 2nd ACM Conference on Advances in Financial Technologies, 2020, pp. 80–91.
[23]
A. Kavousi, D. V. Le, P. Jovanovic, and G. Danezis, “Blindperm: Efficient MEV mitigation with an encrypted mempool and permutation,” in 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2026, pp. 36–1.
[24]
B. Mazorra, C. Schlegel, and A. Mamageishvili, “Timing games: Probabilistic backrunning and spam,” arXiv preprint arXiv:2602.22032, 2026.
[25]
go-ethereum Contributors, “Random ordering of priced transactions incentivises competitive https://github.com/ethereum/go-ethereum/issues/21350, accessed, February 2026.
[26]
W. Wang, A. Saraf, L. Heimbach, K. Babel, and F. Zhang, “Blockspace under pressure: An analysis of spam MEV on highthroughput blockchains,” arXiv preprint arXiv:2604.00234, 2026.
[27]
equallyspam,” 2023,
V. Tumas, B. B. F. Pontiveros, C. F. Torres, and R. State, “A ripple for change: Analysis of frontrunning in the XRP ledger,” in 2023 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 2023, pp. 1–9.
[28]
H. Zhang, L.-H. Merino, Z. Qu, M. Bastankhah, V. EstradaGaliñanes, and B. Ford, “F3b: A low-overhead blockchain architecture with per-transaction front-running protection,” arXiv preprint arXiv:2205.08529, 2022.
[29]
C. Stathakopoulou, S. Rüsch, M. Brandenburger, and M. Vukolić, “Adding fairness to order: Preventing front-running attacks in BFT protocols using TEEs,” in 2021 40th International Symposium on Reliable Distributed Systems (SRDS). IEEE, 2021, pp. 34–45.
[30]
J. H.-y. Chiang, B. David, I. Eyal, and T. Gong, “FairPoS: Input fairness in proof-of-stake with adaptive security.” IACR Cryptol. ePrint Arch., vol. 2022, p. 1442, 2022.
[31]
A. Canidio and V. Danos, “Commitment against front-running attacks,” Management Science, vol. 70, no. 7, pp. 4429–4440, 2024.
[32]
J. Bormet, S. Faust, H. Othman, and Z. Qu, “BEAT-MEV: Epochless approach to batched threshold encryption for MEV prevention,” in 34th USENIX Security Symposium (USENIX Security 25), 2025, pp. 3457–3476.
[33]
P. Garimidi, J. Bonneau, and L. Heimbach, “On the limits of encrypted mempools,” a16z crypto Research, Jul. 2025. [Online]. Available: https://a16zcrypto.com/posts/article/ limits-encrypted-mempools/
[34]
L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Communications of the ACM, vol. 21, no. 7, pp. 558–565, 1978.
[35]
M. K. Reiter and K. P. Birman, “How to securely replicate services,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 16, no. 3, pp. 986–1009, 1994.
[36]
C. Cachin, K. Kursawe, F. Petzold, and V. Shoup, “Secure and efficient asynchronous broadcast protocols,” in Annual International Cryptology Conference. Springer, 2001, pp. 524–541.
[37]
[38]
[39]
[40]
S. Duan, M. K. Reiter, and H. Zhang, “Secure causal atomic broadcast, revisited,” in 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, 2017, pp. 61–72. I. Tsabary, M. Yechieli, A. Manuskin, and I. Eyal, “MAD-HTLC: because HTLC is crazy-cheap to attack,” in 2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021, pp. 1230–1248. L. S. Brugger, L. Kovács, A. Petkovic Komel, S. Rain, and M. Rawson, “Checkmate: Automated game-theoretic security reasoning,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023, pp. 1407–1421. A. Yaish, G. Stern, and A. Zohar, “Uncle maker:(time) stamping out the competition in Ethereum,” in Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, 2023, pp. 135–149.
[41]
M. Mirkin, Y. Ji, J. Pang, A. Klages-Mundt, I. Eyal, and A. Juels, “Bdos: Blockchain denial-of-service,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, 2020, pp. 601–619.
[42]
M. Carlsten, H. Kalodner, S. M. Weinberg, and A. Narayanan, “On the instability of Bitcoin without the block reward,” in Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, 2016, pp. 154–167.
[43]
I. Eyal and E. G. Sirer, “Majority is not enough: Bitcoin mining is vulnerable,” Communications of the ACM, vol. 61, no. 7, pp. 95– 102, 2018.
[44]
J. Byers, “Combating front-running in the blockchain ecosystem,” Master’s thesis, Lehigh University, 2022.
[45]
H. Zecirovic, “Analysis of front running vulnerabilities in solidity smart contracts,” Ph.D. dissertation, Technische Universität Wien, 2024.
[46]
J. Zhang, W. Chen, S. Luo, T. Gong, Z. Hong, and A. Kate, “Front-running attack in sharded blockchains and fair cross-shard consensus,” arXiv preprint arXiv:2306.06299, 2023.
[47]
J. Zhang and A. Kate, “No fish is too big for flash boys! frontrunning on DAG-based blockchains,” in 2025 IEEE Annual Computer Security Applications Conference (ACSAC). IEEE, 2025, pp. 1065– 1080.
[48]
X. Zhang, R. Li, Q. Wang, Q. Wang, and S. Duan, “Timemanipulation attack: Breaking fairness against proof of authority Aura,” in Proceedings of the ACM Web Conference 2023, 2023, pp. 2076–2086.
[49]
Y. Zhang, G. Wang, P. Li, X. Li, W. Gu, M. Chen, and H. Chen, “Transfront: Bi-path feature fusion for detecting front-running attack in decentralized finance,” in 2024 IEEE 23rd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). IEEE, 2024, pp. 600–607.
[50]
K. Qin, S. Chaliasos, L. Zhou, B. Livshits, D. Song, and A. Gervais, “The blockchain imitation game,” in 32nd USENIX Security Symposium, 2023, pp. 3961–3978.
[51]
Y. Wang, J. Lou, Z. Wang, and J. Li, “Front-running attacks in Hash-based transaction sharding blockchains,” in 23rd IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom, 2024, pp. 205–212.
[52]
L. Heimbach and R. Wattenhofer, “Eliminating sandwich attacks with the help of game theory,” in Proceedings of the 2022 ACM on Asia Conference on Computer and Communications Security, 2022, pp. 153–167.
[53]
M. V. Xavier Ferreira and D. C. Parkes, “Credible decentralized exchange design via verifiable sequencing rules,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, pp. 723–736.
[54]
D. Li, K. Zhang, L. Wang, and G. Du, “A Geth-based real-time detection system for sandwich attacks in Ethereum,” Discover Computing, vol. 27, no. 1, p. 11, 2024.
[55]
A. Adams, B. Y. Chan, S. Markovich, and X. Wan, “Don’t let MEV slip: The costs of swapping on the Uniswap protocol,” in International Conference on Financial Cryptography and Data Security. Springer, 2024, pp. 172–191.
[56]
Y. Ji and J. Grimmelmann, “Regulatory implications of MEV mitigations,” in International Conference on Financial Cryptography and Data Security. Springer, 2024, pp. 335–363.
[57]
J. Wang, J. Li, Z. Li, X. Deng, and B. Xiao, “n-MVTL attack: Optimal transaction reordering attack on DeFi,” in European Symposium on Research in Computer Security. Springer, 2023, pp. 367–386.
[58]
M. Bartoletti, J. H.-y. Chiang, and A. Lluch Lafuente, “Maximizing extractable value from automated market makers,” in International Conference on Financial Cryptography and Data Security. Springer, 2022, pp. 3–19.
[59]
C. Baum, J. Hsin-yu Chiang, B. David, T. K. Frederiksen, and L. Gentile, “Sok: Mitigation of front-running in decentralized finance,” in International Conference on Financial Cryptography and Data Security. Springer, 2022, pp. 250–271.
[60]
M. Raikwar, N. Polyanskii, and S. Müller, “Fairness notions in DAG-based DLTs,” in 2023 5th Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS). IEEE, 2023, pp. 1–8.
[61]
L. Baird, “The Swirlds hashgraph consensus algorithm: Fair, fast, Byzantine fault tolerance,” Swirlds Tech Reports SWIRLDS-TR2016-01, Tech. Rep, vol. 34, pp. 9–11, 2016.
[62]
W. V. Gehrlein, “Condorcet’s paradox,” Theory and Decision, vol. 15, no. 2, pp. 161–197, 1983.
[63]
M. A. Vafadar and M. Khabbazian, “Condorcet attack against fair transaction ordering,” arXiv preprint arXiv:2306.15743, 2023.
[64]
M. Kelkar, S. Deb, and S. Kannan, “Order-fair consensus in the permissionless setting,” in Proceedings of the 9th ACM on ASIA Public-Key Cryptography Workshop, 2022, pp. 3–14.
[65]
C. Cachin, J. Mićić, N. Steinhauer, and L. Zanolini, “Quick order fairness,” in International Conference on Financial Cryptography and Data Security. Springer, 2022, pp. 316–333.
[66]
H. Nagda, S. P. Singhal, M. J. Amiri, and B. T. Loo, “Rashnu: datadependent order-fairness,” Proceedings of the VLDB Endowment, vol. 17, no. 9, 2024.
[67]
H. Nagda, S. Sankhe, S. Sinha, K. Attarha, M. J. Amiri, and B. T. Loo, “DAG of DAGs: Order-fairness made practical,” Proceedings of the ACM on Management of Data, vol. 3, no. 6, pp. 1–27, 2025.
[68]
Y. Hay, O. Rottenstreich, and D. Cohen, “An optimistic approach to transaction-order fairness protocols,” in 2025 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 2025, pp. 1–5.
[69]
Y. Wang, X. Xing, G. Wang, Y. Zhang, and P. Li, “Dikaios: positionanchored group ordering with reputation for fair and efficient Byzantine consensus,” Computer Networks, vol. 269, p. 111423, 2025.
[70]
P. Ren, H. Dong, N. Sohrabi, Z. Tari, and P. Zhang, “Proof-carrying fair ordering: Asymmetric verification for BFT via incremental graphs,” CoRR, vol. abs/2510.14186, 2025.
[71]
D. Kang, J. Chen, T. T. A. Dinh, and M. Sadoghi, “FairDAG: consensus fairness over multi-proposer causal design,” arXiv preprint arXiv:2504.02194, 2025.
[72]
C. Cachin and J. Mićić, “Quick order fairness: Implementation and evaluation,” in 2024 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 2024, pp. 230–234.
[73]
J. Yu, S. Duan, and Z. Fang, “Efficient fair ordering protocol with 2-hop receiver fairness,” in 2025 44th International Symposium on Reliable Distributed Systems (SRDS). IEEE, 2025, pp. 195–206.
[74]
G. Ramseyer and A. Goel, “Fair ordering in replicated systems via streaming social choice,” in International Conference on Web and Internet Economics. Springer, 2024, pp. 438–456.
[75]
K. Kursawe, “Wendy grows up: More order fairness,” in International Conference on Financial Cryptography and Data Security. Springer, 2021, pp. 191–196.
[76]
[77]
[78]
A. Constantinescu, D. Ghinea, L. Heimbach, Z. Wang, and R. Wattenhofer, “A fair and resilient decentralized clock network for transaction ordering,” in 27th International Conference on Principles of Distributed Systems, OPODIS 2023, ser. LIPIcs, vol. 286, 2023, pp. 8:1–8:20. Z. Zhang, L. Zhang, Z. Wang, Y. Li, R. Lu, and Y. Yu, “Chronos: an efficient asynchronous Byzantine ordered consensus,” The Computer Journal, vol. 67, no. 3, pp. 1153–1162, 2024. V. Gramoli, Z. Lu, Q. Tang, and P. Zarbafian, “AOAB: optimal and fair ordering of financial transactions,” in 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). IEEE, 2024, pp. 377–388.
[79]
P. Zarbafian and V. Gramoli, “Aion: secure transaction ordering using TEEs,” in European Symposium on Research in Computer Security. Springer, 2023, pp. 332–350.
[80]
G. Wang, L. Cai, F. Gai, and J. Niu, “Phalanx: A practical Byzantine ordered consensus protocol,” CoRR, vol. abs/2209.08512, 2022.
[81]
B. Xue and S. Kannan, “Travelers: A scalable fair ordering BFT system,” arXiv preprint arXiv:2401.02030, 2024.
[82]
A. Kiayias, N. Leonardos, and Y. Shen, “Ordering transactions with bounded unfairness: definitions, complexity and constructions,” in Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 2024, pp. 34–63.
[83]
A. Agarwal, K. Babel, S. Das, B. P. Gilkalaye, A. Mondal, B. Pinkas, P. Rindal, and A. Yadav, “Weighted batched threshold encryption with applications to mempool privacy,” Cryptology ePrint Archive, 2025.
[84]
D. Yakira, A. Asayag, G. Cohen, I. Grayevsky, M. Leshkowitz, O. Rottenstreich, and R. Tamari, “Helix: A fair blockchain consensus protocol resistant to ordering manipulation,” IEEE Transactions on Network and Service Management, vol. 18, no. 2, pp. 1584–1597, 2021.
[85]
D. Malkhi and P. Szalachowski, “Maximal extractable value (MEV) protection on a DAG,” arXiv preprint arXiv:2208.00940, 2022.
[86]
J. Bormet, A. R. Choudhuri, S. Faust, S. Garg, H. Othman, G.-V. Policharla, Z. Qu, and M. Wang, “BEAST-MEV: Batched threshold encryption with silent setup for MEV prevention,” Cryptology ePrint Archive, 2025.
[87]
S. Cai, L. Fan, S. Liu, and H.-S. Zhou, “EquiBFT: A framework for achieving fairness in BFT consensus,” in 2025 IEEE 45th International Conference on Distributed Computing Systems (ICDCS). IEEE, 2025, pp. 341–351.
[88]
P. Zarbafian and V. Gramoli, “Lyra: Fast and scalable resilience to reordering attacks in blockchains,” in 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2023, pp. 929–939.
[89]
M. Ciampi, A. Kiayias, and Y. Shen, “Universally composable transaction order fairness: Refined definitions and adaptive security,” in International Conference on the Theory and Application of Cryptology and Information Security. Springer, 2025, pp. 305–337.
[90]
P. Momeni, S. Gorbunov, and B. Zhang, “Fairblock: Preventing blockchain front-running with minimal overheads,” in International Conference on Security and Privacy in Communication Systems. Springer, 2022, pp. 250–271.
[91]
A. R. Choudhuri, S. Garg, G. V. Policharla, and M. Wang, “Practical mempool privacy via one-time setup batched threshold encryption,” in 34th USENIX Security Symposium (USENIX Security 25), 2025, pp. 3477–3495.
[92]
A. R. Choudhuri, S. Garg, J. Piet, and G.-V. Policharla, “Mempool privacy via batched threshold encryption: Attacks and defenses,” in 33rd USENIX Security Symposium (USENIX Security 24), 2024, pp. 3513–3529.
[93]
B. Riva, A. Sonnino, and L. Kokoris-Kogias, “Seahorse: Efficiently mixing encrypted and normal transactions,” in Financial Cryptography and Data Security - 29th International Conference, FC 2025. Springer, 2025, pp. 36–52.
[94]
M. Sabt, M. Achemlal, and A. Bouabdallah, “Trusted execution environment: What it is, and what it is not,” in 2015 IEEE Trustcom/BigDataSE/ISPA, vol. 1, 2015, pp. 57–64.
[95]
R. Li, X. Hu, Q. Wang, S. Duan, and Q. Wang, “Transaction fairness in blockchains, revisited,” IEEE Transactions on Dependable and Secure Computing, 2025.
[96]
M. Ciampi, A. Kiayias, and Y. Shen, “Universal composable transaction serialization with order fairness,” in Annual International Cryptology Conference. Springer, 2024, pp. 147–180.
[97]
M. Rodriguez, L. R. Motati, and T. Mohamed, “Cryptographically enforced fairness protocols for algorithmic trading on distributed ledger infrastructures,” Artificial Intelligence, Machine Learning, and Autonomous Systems, vol. 9, pp. 212–245, 2025.
[116] E. Mahe, R. Abdallah, S. Tucci-Piergiovanni, and P.-Y. Piriou, “Adversary-augmented simulation to evaluate order-fairness on Hyperledger Fabric,” in Proceedings of the 13th Latin-American Symposium on Dependable and Secure Computing, 2024, pp. 126–135.
[98]
A. Khajehpour, H. Akbarinodehi, M. Jahanara, and C. Feng, “A mempool encryption scheme for Ethereum via multiparty delay encryption,” Cryptology ePrint Archive, Paper 2023/1612, 2023.
[99]
S. Agrawal and V. J. Ribeiro, “Timelock shield: A robust defense against MEV and censorship attacks in blockchain,” in Crypto Valley Conference, CVC 2025. IEEE, 2025, pp. 127–137.
[117] E. Mahe and S. Tucci-Piergiovanni, “Order fairness evaluation of DAG-based ledgers,” in 2025 7th International Conference on Blockchain Computing and Applications (BCCA). IEEE, 2025, pp. 106–114. [118] S. Cohen, N. Basu, S. Basu, and L. Alvisi, “On fair ordering and differential privacy,” CoRR, vol. abs/2501.05535, 2025.
[100] K. Babel, N. Jean-Louis, Y. Ji, U. Misra, M. Kelkar, K. Y. Mudiyanselage, A. Miller, and A. Juels, “Prof: Protected order flow in a profit-seeking world,” arXiv preprint arXiv:2408.02303, 2024.
[119] Y. Zhang, H. Ni, S. Basu, S. Cohen, M. Yin, L. Alvisi, R. van Renesse, Q. Chen, and L. Zhou, “Ordered consensus with equal opportunity,” CoRR, vol. abs/2509.09868, 2025.
[101] C. McMenamin, V. Daza, M. Fitzi, and P. O’Donoghue, “FairTraDEX: A decentralised exchange preventing value extraction,” in Proceedings of the 2022 ACM CCS Workshop on Decentralized Finance and Security, 2022, pp. 39–46.
[120] H. Atwi, T. Lichtenstein, C. Pautasso, and M. Weske, “Transparent transaction ordering in blockchain-based collaborative processes,” in Business Process Management: Blockchain, Robotic Process Automation, Central and Eastern European, Educators and Industry Forum - BPM 2024, 2024, pp. 25–39.
[102] C. McMenamin and V. Daza, “Private, anonymous, collateralizable commitments vs. MEV,” in IEEE International Conference on Blockchain and Cryptocurrency, ICBC 2024. IEEE, 2024, pp. 521– 527.
[121] B. Nasrulin, G. Ishmaev, J. Decouchant, and J. Pouwelse, “Lo: An accountable mempool for MEV resistance,” in Proceedings of the 24th International Middleware Conference, 2023, pp. 98–110.
[103] A. Rondelet and Q. Kilbourn, “Mempool privacy: An economic perspective,” arXiv preprint arXiv:2307.10878, 2023. [104] S. Wadhwa, L. Zanolini, A. Asgaonkar, F. D’Amato, C. Fang, F. Zhang, and K. Nayak, “Data independent order policy enforcement: Limitations and solutions,” in Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, 2024, pp. 378–392. [105] V. Tumas and A. Malhotra, “The AMMazing frontrunner: Practical frontrunning on the XRP ledger automated market maker,” in 2024 IEEE International Conference on Blockchain and Cryptocurrency (ICBC). IEEE, 2024, pp. 1–7. [106] T. Chitra, G. Angeris, and A. Evans, “Differential privacy in constant function market makers,” in International Conference on Financial Cryptography and Data Security. Springer, 2022, pp. 149–178. [107] A. Canidio and R. Fritsch, “Batching trades on automated market makers,” in 5th Conference on Advances in Financial Technologies (AFT 2023), 2023, pp. 24–1.
[122] J. Albrecht and G. Karame, “On the effectiveness of mempool-based transaction auditing,” in Proceedings of the ACM Web Conference 2026, WWW 2026, H. Hacid, Y. Maarek, F. Bonchi, I. Guy, and E. Yilmaz, Eds., 2026, pp. 2983–2994. [123] R. Gelashvili, A. Spiegelman, Z. Xiang, G. Danezis, Z. Li, D. Malkhi, Y. Xia, and R. Zhou, “Block-STM: Scaling blockchain execution by turning ordering curse to a performance blessing,” in Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, 2023, pp. 232– 244. [124] A. Mamageishvili, M. Kelkar, J. C. Schlegel, and E. W. Felten, “Buying time: Latency racing vs. bidding for transaction ordering,” in 5th Conference on Advances in Financial Technologies, AFT 2023, vol. 282, 2023, pp. 23:1–23:22. [125] G. Tullock, “Efficient rent seeking,” Toward a Theory of the RentSeeking Society, vol. 97, p. 112, 1980. [126] S. Skaperdas, “Contest success functions,” Economic Theory, vol. 7, no. 2, pp. 283–290, 1996.
[108] T. Chan, K. Wu, and E. Shi, “Mechanism design for automated market makers,” arXiv preprint arXiv:2402.09357, 2024.
[127] L. Gao, J. Lu, and Z. Wang, Equilibria in Two-Player Sequential Tullock Contests. SSRN, 2023.
[109] O. Alpos, I. Amores-Sesar, C. Cachin, and M. Yeo, “Eating sandwiches: Modular and lightweight elimination of transaction reordering attacks,” arXiv preprint arXiv:2307.02954, 2023.
[128] T. Hinnosaar, “Optimal sequential contests,” Theoretical Economics, vol. 19, no. 1, pp. 207–244, 2024.
[110] L. Zhou, K. Qin, and A. Gervais, “A2MM: Mitigating frontrunning, transaction reordering and consensus instability in decentralized exchanges,” ArXiv, vol. abs/2106.07371, 2021. [111] S. Jiang, J. Chen, J. Li, Z. Liu, and Y. Li, “ARMM: Sandwich-attack resilient automated market maker,” IEEE Transactions on Services Computing, 2025. [112] X. Zhao, H.-W. Long, Z. Li, J. Liu, and Y.-W. Si, “Mitigating blockchain extractable value threats by distributed transaction sequencing,” Digital Communications and Networks, vol. 11, no. 5, pp. 1394–1409, 2025.
[129] S. Das, V. Krishnan, I. M. Isaac, and L. Ren, “SPURT: Scalable distributed randomness beacon with transparent setup,” in 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022, pp. 2502–2517. [130] A. Bhat, N. Shrestha, Z. Luo, A. Kate, and K. Nayak, “Randpiper– reconfiguration-friendly random beacons with quadratic communication,” in Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, 2021, pp. 3502–3524. [131] H. Chung and E. Shi, “Foundations of transaction fee mechanism design,” in Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2023, pp. 3856–3899.
[113] N. Durvasula, “The monotone priority system: Foundations of contract-specific sequencing,” arXiv preprint arXiv:2601.20783, 2026.
[132] P. S. Efraimidis and P. G. Spirakis, “Weighted random sampling with a reservoir,” Information Processing Letters, vol. 97, no. 5, pp. 181–185, 2006.
[114] A. Ahuja, R. Vigneswaran, M. Rajan, and S. Lodha, “Myochain: A blockchain protocol for delay bounded transaction confirmation,” in 2023 15th International Conference on Communication Systems & Networks (COMSNETS). IEEE, 2023, pp. 114–118.
[133] H. Von Stackelberg, Market structure and equilibrium. Science & Business Media, 2010.
[115] Y. Sokolik and O. Rottenstreich, “Age-aware fairness in blockchain transaction ordering,” in 2020 IEEE/ACM 28th International Symposium on Quality of Service (IWQOS). IEEE, 2020, pp. 1–9.
[135] P. Dütting, T. Roughgarden, and I. Talgam-Cohen, “Simple versus optimal contracts,” in Proceedings of the 2019 ACM Conference on Economics and Computation, 2019, pp. 369–387.
Springer
[134] J. C. Harsanyi and R. Selten, “A general theory of equilibrium selection in games,” MIT Press Books, vol. 1, 1988.
[136] N. Collina, A. Roth, and H. Shao, “Efficient prior-free mechanisms for no-regret agents,” in Proceedings of the 25th ACM Conference on Economics and Computation, 2024, pp. 511–541. [137] M. Hellwig and W. Leininger, “On the existence of subgame-perfect equilibrium in infinite-action games of perfect information,” Journal of Economic Theory, vol. 43, no. 1, pp. 55–75, 1987. [138] H. Adams, N. Zinsmeister, and D. Robinson, “Uniswap v2 core,” https://app.uniswap.org/whitepaper.pdf, 2020, accessed: jun 2026. [139] H. Adams, N. Zinsmeister, M. Salem, R. Keefer, and D. Robinson, “Uniswap v3 core,” https://app.uniswap.org/whitepaper-v3.pdf, 2021, accessed: jun 2026. [140] Foundry Development Team, “Foundry,” https://github.com/ foundry-rs/foundry, Jun. 2026, gitHub repository.
Appendix A. Practical Losing-Fee Rates We measure practical values of the losing-fee rate γ for arbitrage on Ethereum. A transaction consumes resources measured in gas and bids a price per unit of gas, so its total payment is the product of the gas price and the gas it consumes; this is the bid b in our model. Winning the front-running competition, it executes fully and pays this b; losing, it reverts after consuming a ratio γ of that gas, and so pays γb. Therefore, γ is simply the ratio of the gas a transaction consumes if it loses to that if it wins. The value of γ varies across arbitrages, but a participant can simulate her transaction before publishing it to find γ in advance, so the user can set her deterrence bid accordingly. An arbitrage is simply a token swap, so we measure γ by running swaps on a local simulator (an Ethereum [3] mainnet fork served by Foundry’s Anvil [140]), across the ten most-traded pools of Uniswap, the leading decentralized exchange on Ethereum, in 2025, of which two use version 2 (V2) [138] and eight use version 3 (V3) [139], listed in Table 1. Each pool swaps one pair of tokens at a fixed trading fee rate; since V3 offers the same pair in several pools at different rates, we annotate each pool with its rate. We uniformly sample 10 blocks at random from all Ethereum blocks in 2025. For each pool, at each sampled block, we send five identical swaps: The first succeeds and the remaining four fail. Every pool pairs tokens among WETH and WBTC, the digital tokens standing for Ether [3] and Bitcoin [4], and US-dollar stablecoins (USDT, USDC, DAI), digital tokens each worth one US dollar. We publish each swap with a fixed input amount: 1 WETH or 1 WBTC when the pool holds ether or bitcoin, and 1,000 USDT in the stablecoin-only pool. In Uniswap V3, a failing swap follows a different computation path than a successful one and can consume more gas. A rational participant caps her exposure with a gas limit, but cannot set it to the exact success cost: A successful execution needs some headroom to complete, so she sets the limit somewhat above the gas a success consumes, and a failing swap may consume up to this higher limit, pushing γ slightly above 1. In every pool and block, the four failing swaps consume exactly the same amount of gas as one another. Across the
two V2 pools, γ is stable at about 0.26, that is, a failing swap uses less gas than a successful one. Across the eight V3 pools, γ is more variable, ranging over [0.867, 1.087], that is, a failing swap uses nearly as much gas as a successful one. Table 1 details, for each pool, the minimum and maximum of gas consumption and γ over all 100 samples (10 blocks for each of the 10 pools).
Appendix B. Proof of Lemma 1
Lemma 1 (Deterrence weight, restated). Fix the exponent parameter k > 1 and the losing-fee rate γ > 0, and let W be the total weight of transactions the attacker observes. Then the attacker’s expected revenue with any single bid b > 0 satisfies u(b; W ) ≤ 0 if and only if W ≥
(k − 1)k−1 k R . γ kk
Proof. For b > 0, the factors b and bk +W in Equation 2 are positive, so u(b; W ) has the same sign as R bk−1 −bk −γ W . Hence u(b; W ) ≤ 0 for all b > 0 if and only if R bk−1 − bk ≤ γ W
for all b > 0.
(11)
That is, if and only if γ W is at least the maximum of g(b) := R bk−1 − bk over b > 0. We compute this maximum through differentiation. The derivative of g is g ′ (b) = (k − 1)R bk−2 − k bk−1 = bk−2 (k − 1)R − k b . For b > 0 the factor bk−2 is positive, so g ′ (b) has the sign of (k − 1)R − k b, which is positive for b < k−1 k R and negative for b > k−1 R . We denote this point by k k−1 R. k Thus g(b) increases up to b⋆ and decreases afterwards, attaining its maximum at b⋆ . Since R − b⋆ = R/k , the maximum of g(b) is b⋆ :=
max g(b) =g(b⋆ ) b>0
=(b⋆ )k−1 (R − b⋆ ) k−1 k−1 R = R k k (k − 1)k−1 k = R . kk Substituting this into Equation 11, the condition k−1 u(b; W ) ≤ 0 for all b > 0 becomes γ W ≥ (k−1) Rk . kk Therefore, u(b; W ) ≤ 0 for all b > 0 if and only if W ≥
(k − 1)k−1 k R . γ kk
γ
Pool Name
Success Gas
Failure Gas
Contract Address
Uniswap V2 USDT/WETH USDC/WETH
[121,047, 121,059] [120,603, 120,615]
[31,330, 31,342] [31,360, 31,372]
[0.259, 0.259] 0x0d4a11d5eeaac28ec3f61d100daf4d40471f1852 [0.260, 0.260] 0xb4e16d0168e52d35cacd2c6185b44281ec28c9dc
Uniswap V3 USDT/WETH 0.01% USDC/WETH 0.01% USDC/WETH 0.05% USDT/WETH 0.05% WBTC/WETH 0.05% USDT/WBTC 0.05% USDC/USDT 0.01% DAI/WETH 0.05%
[130,219, 131,545] [129,565, 130,617] [120,911, 130,649] [121,912, 131,678] [113,934, 122,696] [125,941, 134,727] [133,600, 133,698] [120,054, 150,186]
[117,826, 118,247] [116,214, 141,948] [113,466, 123,078] [115,436, 124,149] [105,555, 115,121] [117,524, 127,214] [126,125, 126,223] [105,877, 159,114]
[0.898, 0.905] 0xc7bbec68d12a0d1830360f8ec58fa599ba1b0e9b [0.890, 1.087] 0xe0554a476a092703abdb3ef35c80e0d76d32939f [0.890, 1.010] 0x88e6a0c2ddd26feeb64f039a2c41296fcb3f5640 [0.877, 1.017] 0x11b815efb8f581194ae79006d24e0d814b7697f6 [0.867, 1.010] 0x4585fe77225b41b697c938b018e2ac67ac5a20c0 [0.873, 1.009] 0x56534741cd8b152df6d48adf7ac51f75169a83b2 [0.944, 0.944] 0x3416cf6c708da44db2624d63ea0aaef7113527c6 [0.881, 1.059] 0x60594a405d53811d3bc4766596efd80fd545a270
TABLE 1. P RACTICAL γ ON A MAINNET FORK (10 BLOCK SAMPLES PER POOL ).
Appendix C. Proof of Theorem 2
b1 , Equation 6 gives m1 X (j) (j) (j) C1 (b1 , b−1 ) = γ b1 + (1 − γ) q(b1 , b−1 , b1 ) b1 j=1 m1 X
Theorem 2 (Anti-Spam Threshold, restated). Fix the exponent parameter k > 1 and the losing-fee rate γ > 0. For every bid vector b1 of P1 and every profile b−1 of the other participants’ bids, replacing b1 with the single bid (b̄1 ) does not decrease P1 ’s revenue, u1 (b̄1 ), b−1 ≥ u1 (b1 , b−1 ), if and only if k ≥
ln 2 . ln(1 + γ)
Proof. We show that the single bid (b̄1 ) weakly dominates the original split vector b1 for P1 . We first reduce this revenue comparison to a single inequality between expected payments, and then treat the cases γ ≥ 1 and 0 < γ < 1 separately. The single bid and the split win with the same probability, since they have the same total weight: m1 X
(j)
q(b1 , b−1 , b1 ) = q(b̄1 , b−1 , (b̄1 )).
j=1
Recall that P1 ’s revenue is her expected reward minus her expected payment C1 (Equation 7). Since the winning probability is unchanged, the difference in revenue between the single bid and the split is u1 (b̄1 ), b−1 − u1 (b1 , b−1 ) m1 X (j) =R q(b̄1 , b−1 , (b̄1 )) − R q(b1 , b−1 , b1 ) j=1
+ C1 (b1 , b−1 ) − C1 (b̄1 ), b−1 =C1 (b1 , b−1 ) − C1 (b̄1 ), b−1 .
We expand both payments by Equation 6. Under the split
=γ
(j) b1 + (1 − γ)
j=1
m1 X
(j)
(j)
q(b1 , b−1 , b1 ) b1
j=1
(j) k+1 m1 j=1 (b1 ) (j) =γ b1 + (1 − γ) Pn Pm (l) . i k j=1 i=1 l=1 (bi ) m1 X
P
Pm1 (j) k Denote P1 ’s total weight by S := = j=1 (b1 ) b̄k1 , and the total weight from other participants by P Pmi (l) k Pm1 (j) Ω := (bi ) . Denoting L := and j=1 b1 Pmi̸1=1 (j)l=1 Λ := j=1 (b1 )k+1 , we obtain C1 (b1 , b−1 ) = γL + (1 − γ)
Λ . S+Ω
Under the surrogate (b̄1 ), P1 holds the single bid b̄1 , so Equation 6 gives C1 (b̄1 ), b−1 = γ b̄1 + (1 − γ) q b̄1 , b−1 , (b̄1 ) b̄1 b̄k = γ b̄1 + (1 − γ) k 1 b̄1 b̄1 + Ω S b̄1 . = γ b̄1 + (1 − γ) S+Ω Substituting the two payments into the revenue difference C1 (b1 , b−1 ) − C1 (b̄1 ), b−1 , u1 (b̄1 ), b−1 − u1 (b1 , b−1 ) = C1 (b1 , b−1 ) − C1 (b̄1 ), b−1 S b̄1 − Λ = γ(L − b̄1 ) − (1 − γ) . S+Ω Therefore, the single bid weakly dominates the split, u1 (b̄1 ), b−1 ≥ u1 (b1 , b−1 ), if and only if this difference is non-negative, that is, γ(L − b̄1 ) ≥ (1 − γ)
S b̄1 − Λ . S+Ω
(12)
(j)
Since b1 ≤ b̄1 for every j , we have Λ=
Dividing Equation 14 by b̄1 gives L Λ γ − 1 ≥ (1 − γ) 1 − . S b̄1 b̄1
m1 m1 X X (j) (j) (j) (b1 )k b1 ≤ b̄1 (b1 )k = S b̄1 . j=1
j=1
By the definitions of L and Λ, with S (j) (j) p(j) = (b1 )k /b̄k1 , and b1 /b̄1 = (p(j) )a ,
Therefore, we have S b̄1 − Λ ≥ 0.
(13)
m1 X
m1 X
j=1
j=1
(j) (b1 )k ≤ (
m1 X j=1
p(j) =
m1 (j) X (b )k 1
j=1
S
(j)
p
(p
m1 X ) = (p(j) )1+a .
(j) a
j=1
Substituting these into the inequality above gives ! ! m1 m1 X X (j) 1+a (j) a . (15) (p ) (p ) − 1 ≥ (1 − γ) 1 − γ j=1
j=1
Let p = (p(1) , . . . , p(m1 ) ) bePthe resulting share m1 vector. For a split, define F (p) := j=1 (p(j) )a − 1, and Pm1 (j) 1+a G(p) := 1 − j=1 (p ) . By the definitions of F and G, Equation 15 is exactly γF (p) ≥ (1 − γ)G(p). Both terms are positive: F (p) > 0 since xa is strictly concave on (0, 1), and G(p) > 0 since (p(j) )1+a < p(j) for every component strictly between 0 and 1. Hence F (p) + G(p) > 0, so dividing by it, the inequality is equivalent to γ≥
G(p) . F (p) + G(p)
(16)
The single bid therefore weakly dominates every split if and only if γ satisfies Equation 16 for all split vectors p, that is, γ ≥ sup p
G(p) . F (p) + G(p)
This supremum is the exact threshold on γ . Step 2: A necessary bound from the worst binary split. The threshold is the supremum over all splits, so any particular split lower-bounds it and thus yields a necessary condition on γ . We therefore probe with the simplest family, the splits p = (z, 1 − z) for z ∈ (0, 1) (recall that P two-bid (j) p = 1 ). Among these we identify the worst one, the j split that maximizes the ratio in Equation 16 and so requires the largest γ . Specializing F and G to this two-component vector, denote F2 (z) := F (z, 1 − z) = z a + (1 − z)a − 1, (17) G2 (z) := G (z, 1 − z) = 1 − z 1+a − (1 − z)1+a . Both are symmetric under z 7→ 1 − z , so (z, 1 − z) and its mirror image (1 − z, z) give the same ratio; we may therefore restrict to z ∈ (0, 1/2]. For this binary split, the required lower bound on γ is
(j)
b1 = (p(j) )a , b̄1
and
=
m1 X j=1
We now reformulate the inequality in terms of P1 ’s weight shares, the fractions of her total weight S carried by her individual bids. For each bid j , denote this share by p(j) , and let a := 1/k be the reciprocal exponent: ! (j) (j) k 1 (b1 )k b1 (j) . a := ∈ (0, 1), p := = k S b̄1 We have
m1 (j) (j) X Λ (b1 )k b1 = S b̄1 b̄k1 b̄1 j=1
(j) (b1 ))k = Lk ,
so b̄1 ≤ L. The right-hand side (1 − γ)(S b̄1 − Λ)/(S + Ω) is non-positive, since 1−γ ≤ 0 and S b̄1 −Λ ≥ 0 (Equation 13). Hence Equation 12 holds. This is consistent with Theorem 2: For γ ≥ 1 the Anti-Spam bound is automatically met, as ln 2/ ln(1 + γ) ≤ 1 < k . Second, we consider the case where 0 < γ < 1. We first show that, for a fixed k , the single bid weakly dominates every split if and only if γ is not below a threshold γ0 that depends on k . We then deduce the stated bound on k . We proceed in four steps. Step 1 reformulates the dominance condition as a threshold on γ . Step 2 evaluates this supremum at the equal two-way split, which gives the necessary threshold γ0 = 21/k − 1. Step 3 shows, by a merging argument, that no finer split requires a larger γ , so γ0 is also sufficient. Step 4 returns to k , rearranging γ ≥ γ0 into the bound k ≥ ln 2/ ln(1 + γ). Step 1: Reformulation as a threshold on γ . Since 1 − γ > 0 and S b̄1 − Λ ≥ 0 (Equation 13), the right-hand side of Equation 12 is non-negative and decreasing in Ω. Hence, it holds for every Ω ≥ 0 if and only if it holds at Ω = 0, where the right-hand side is largest and the inequality is hardest to satisfy. It therefore suffices to prove the inequality at Ω = 0, Λ . (14) γ(L − b̄1 ) ≥ (1 − γ) b̄1 − S
b̄k1 ,
m1 (j) m1 X X L b1 = = (p(j) )a , b̄1 b̄ 1 j=1 j=1
Now we discuss the two cases for γ . First, if γ ≥ 1, the single bid weakly dominates the split for every b1 and every profile b−1 . The left-hand side γ(L − b̄1 ) of Equation 12 is (j) non-negative: Since k > 1 and b1 ≤ L for every j , b̄k1 =
=
= 1.
G2 (z) G2 (z)/F2 (z) = . F2 (z) + G2 (z) 1 + G2 (z)/F2 (z)
This increases with the ratio G2 (z)/F2 (z), so maximizing the bound is the same as maximizing G2 (z)/F2 (z). We show that G2 (z)/F2 (z) is increasing on (0, 1/2]. Both functions vanish at the left endpoint, since F2 (0) = 0a + 1 − 1 = 0 and G2 (0) = 1 − 0 − 1 = 0, so by the monotone form of l’Hôpital’s rule it suffices to show that the ratio of derivatives G′2 (z)/F2′ (z) is increasing on (0, 1/2]. Indeed, F2′ (z) = a z a−1 − (1 − z)a−1 > 0, and
G′2 (z) = (1 + a) ((1 − z)a − z a ) > 0.
Dividing the two derivatives,
It remains to transfer this back to z . Since r = z/(1−z) is increasing in z and maps (0, 1/2] onto (0, 1], G′2 (z)/F2′ (z) is increasing on (0, 1/2]. The rule above then lifts this to G2 (z)/F2 (z), which is increasing on (0, 1/2] and hence maximal at z = 1/2. The binary ratio increases with G2 /F2 , so it too is maximal at z = 1/2: The worst binary split is the equal split z = 1/2. At this split, F2 (1/2) = 21−a − 1,
1 + a (1 − z)a − z a G′2 (z) . = F2′ (z) a z a−1 − (1 − z)a−1
G2 (1/2) = 1 − 2−a ,
and hence the binary ratio at z = 1/2 is
Dividing the numerator and denominator by (1 − z)a , a z G′2 (z) 1 + a (1 − z) 1 − 1−z . = a−1 z F2′ (z) a −1 1−z z Using 1 − z = 1/ 1 + 1−z , the right-hand side depends on z z only through 1−z , a z 1 − 1−z G′2 (z) 1+a = z a−1 . F2′ (z) a −1 1+ z 1−z
is decreasing on (0, 1], and since ψ(1) = 0, we get ψ > 0 on (0, 1), the inequality we needed.
G2 (1/2) = 2a − 1. F2 (1/2) + G2 (1/2)
Denote γ0 := 2a − 1. Since the binary ratio is maximized at z = 1/2, every z ∈ (0, 1) satisfies G2 (z)/(F2 (z) + G2 (z)) ≤ γ0 , that is, γ0 F2 (z) ≥ (1 − γ0 ) G2 (z).
(19)
The worst binary split therefore requires γ ≥ γ0 , the necessary bound on the threshold.
1−z
z Let r = 1−z ; then we have
1+a 1 − ra G′2 (z) . = F2′ (z) a (1 + r) ra−1 − 1
(18)
We now show the right-hand side of Equation 18 is 1 − ra . increasing in r ∈ (0, 1]. Let h(r) := (1 + r) ra−1 − 1 Differentiating, 1 − r2a−2 + (1 − a) ra−2 1 − r2 ′ h (r) = . 2 (1 + r)2 ra−1 − 1 The denominator is positive, so h′ has the sign of its 2a−2 numerator, which + (1 − we denote ψ(r) := 1 − r a) ra−2 1 − r2 . It suffices to show ψ > 0 on (0, 1): Then h′ > 0 on (0, 1), so h is increasing on (0, 1]. We have ψ(1) = 0 and ψ ′ (r) = (1 − a) ra−3 2ra − ar2 + (a − 2) . With χ(r) := 2ra − ar2 + (a − 2) and (1 − a) ra−3 > 0 on (0, 1), we have ψ ′ (r) > 0 if and only if χ(r) > 0. We have χ(1) = 2 − a + a − 2 = 0, and χ′ (r) = 2a ra−1 − 2a r = 2a r ra−2 − 1 . For r ∈ (0, 1) the exponent a − 2 is negative, so ra−2 > 1 and hence χ′ (r) > 0. Thus χ is increasing on (0, 1], and since χ(1) = 0, we get χ < 0 on (0, 1). Returning to ψ ′ (r) = (1 − a) ra−3 χ(r), on (0, 1) the factors 1 − a and ra−3 are positive while χ(r) < 0, so ψ ′ (r) < 0. Thus ψ
Step 3: Sufficiency by a merging argument. We now show that this binary-split bound is generally sufficient: G(p) . We turn to the For every split p, γ0 is at least F (p)+G(p) equivalent form of this: Every split satisfies Equation 15 when γ = γ0 .
Setting γ = γ0 in Equation 15 and using γ0 + (1 − γ0 ) = 1, the inequality is equivalent to a sum over the shares, m1 X γ0 (p(j) )a + (1 − γ0 )(p(j) )1+a ≥ 1.
(20)
j=1
Denote the contribution of a single share by f (x) := γ0 xa + (1 − γ0 )x1+a .
Note that f (1) = 1, so Equation 20 is exactly m1 X
f (p(j) ) ≥ f (1).
(21)
j=1
We prove Equation 21 by a merging argument. Take any two components x, y > 0, let t = x+y ≤ 1, and denote ζ = x/t,
so that x = ζt and y = (1 − ζ)t; then we have
Therefore, it is now sufficient to show that the above equaln 2 tion is satisfied when k ≥ ln(1+γ) , which is equivalent 1/k to γ ≥ 2 − 1. Hence it suffices to prove that, for every k > 1, (k − 1)k−1 . (24) 21/k − 1 > kk This inequality says exactly that the weakest losing-fee rate required for Anti-Spam is already strictly larger than the weakest losing-fee rate required for the deterrence bid to be below R. Denote y := k1 ∈ (0, 1). Then
f (x) + f (y) − f (t) = γ0 xa + (1 − γ0 )x1+a + γ0 y a + (1 − γ0 )y 1+a − γ0 ta − (1 − γ0 )t1+a = γ0 xa + y a − ta + (1 − γ0 ) x1+a + y 1+a − t1+a = γ0 ta ζ a + (1 − ζ)a − 1 + (1 − γ0 )t1+a ζ 1+a + (1 − ζ)1+a − 1 (17)
= γ0 ta F2 (ζ) − (1 − γ0 )t1+a G2 (ζ) = ta γ0 F2 (ζ) − (1 − γ0 ) t G2 (ζ) ≥ ta γ0 F2 (ζ) − (1 − γ0 )G2 (ζ)
(k − 1)k−1 = y(1 − y)(1−y)/y . kk Thus Equation 24 becomes
(19)
≥ 0.
Therefore, f (x) + f (y) ≥ f (x + y). Iteratively merging the components of any split vector p yields ! m1 m1 X X (j) (j) f (p ) ≥ f p = f (1) = 1, j=1
2y − 1 > y(1 − y)(1−y)/y .
We first upper bound the right-hand side. Since ln(1 − y) < −y for y ̸= 0, multiplying by (1 − y)/y , which is positive,
j=1
which proves Equation 21. Hence γ ≥ γ0 is sufficient: The single bid weakly dominates every split. Step 4: Bound on k . Together with the necessary bound from the worst binary split, this shows that for 0< γ < 1 the single bid weakly dominates every split if and only if γ ≥ γ0 = 21/k − 1,
or, equivalently, k≥
ln 2 . ln(1 + γ)
(22)
Conclusion. For any γ > 0, the single bid weakly dominates every split if and only if k ≥ ln 2/ ln(1+γ): For γ ≥ 1 this holds automatically, as ln 2/ ln(1 + γ) ≤ 1 < k , and for 0 < γ < 1 it is the condition just derived (Equation 22).
Appendix D. Proof of Proposition 2
Proof. We show that Profitability holds exactly when the losing-fee rate satisfies γ > (k − 1)k−1 /k k , and that the Anti-Spam threshold is stricter, hence guarantees it. 1/k (k−1)k−1 Recall that the deterrence bid is bk,γ k dtr = R γk (Equation 3), and hence the user’s revenue under deterrence k,γ is uk,γ dtr = R − bdtr . Therefore, deterrence is profitable if and k,γ only if bdtr < R. Since R > 0, this condition is equivalent 1/k k−1 to (k−1) < 1, or, equivalently, γkk (k − 1)k−1 . kk
1−y 1−y ln(1 − y) < (−y) y y = −(1 − y).
Therefore, y(1 − y)
(1−y)/y
= y exp
1−y ln(1 − y) y
(26)
< ye−(1−y) = yey−1 .
Therefore, to prove Equation 25 it suffices to show that yey−1 < 2y − 1. Define ξ(y) := 2y − 1 − yey−1 . Then ξ(0) = ξ(1) = 0. Moreover, ξ ′′ (y) = (ln 2)2 2y − (y + 2)ey−1 .
We claim that ξ ′′ (y) < 0 for every y ∈ [0, 1]. Since (y + 2)ey−1 > 0, ξ ′′ (y) < 0 is equivalent to
Proposition 2 (Deterrence is profitable, restated). If ln 2 k ≥ ln(1+γ) , then the deterrence strategy results in strictly positive revenue, namely uk,γ dtr > 0.
γ>
(25)
(23)
(ln 2)2 2y < 1. (y + 2)ey−1
The logarithm of this ratio is 2 ln(ln 2) + y ln 2 − ln(y + 2) − (y − 1).
Its derivative, the logarithmic derivative of the ratio, equals 1 ln 2 − 1 − y+2 < 0, so this ratio is decreasing on [0, 1], 2
hence maximized at y = 0. At y = 0 it is e(ln22) < 1. Hence the ratio is strictly smaller than 1 on [0, 1], which proves ξ ′′ (y) < 0. Thus ξ is strictly concave on [0, 1]. Since ξ(0) = ξ(1) = 0, strict concavity gives ξ(y) > 0 for every y ∈ (0, 1). Equivalently, yey−1 < 2y − 1
for all y ∈ (0, 1).
(27)
product rule on b2 q2 ,
Combining Equation 26 and Equation 27, we obtain
∂u2 ∂q2 ∂q2 =R − γ − (1 − γ) q2 + b2 ∂b2 ∂b2 ∂b2 ∂q2 R − (1 − γ)b2 − γ − (1 − γ)q2 = ∂b2 k = q1 q2 R − (1 − γ)b2 − γ − (1 − γ)q2 . b2
y(1 − y)(1−y)/y < 2y − 1,
which proves Equation 25, and therefore Equation 24. Consequently, γ ≥ 21/k − 1 >
(k − 1)k−1 . kk
By Equation 23, this implies bk,γ < R. Hence dtr k,γ uk,γ = R − b > 0. This proves Profitability. dtr dtr
Since b∗2 (b1 ) > 0 lies in the interior of [0, ∞) and maximizes u2 (b1 , ·), ∂u2 /∂b2 = 0; multiplying by b∗2 (b1 ) gives the first-order condition kq1∗ q2∗ R − (1 − γ)b∗2 (b1 ) = b∗2 (b1 ) γ + (1 − γ)q2∗ . (30)
Appendix E. Proof of Lemma 2
Next substitute Equation 30 into P2 ’s utility (Equation 29): u∗2 = q2∗ R − b∗2 (b1 ) γ + (1 − γ)q2∗ n o = q2∗ R − kq1∗ R − (1 − γ)b∗2 (b1 ) . (31) u∗2 is the product of q2∗ and R − kq1∗ R − (1 − γ)b∗2 (b1 ) (Equation 31). Since this product is positive (u∗2 > 0) and its first factor is positive (q2∗ > 0), the second factor must be positive as well, that is, kq1∗ R − (1 − γ)b∗2 (b1 ) < R.
Lemma 2 (Accommodation utility bound, restated). For any γ > 0 and k > 1, the accommodation utility uk,γ acc satisfies uk,γ acc ≤
R . k min{1, γ}
Proof. We bound P1 ’s utility by q1∗ R, and bound the winning probability q1∗ using P2 ’s first-order optimality condition. ∗ Fix any b1 ∈ (0, bk,γ dtr ), and recall that b2 (b1 ) is P2 ’s selected best response (§5.2.1). Since b1 is below the deterring bid, Lemma 1 implies that some positive bid gives P2 positive utility. Therefore the best response also gives positive utility:
u∗2 := u2 (b1 , b∗2 (b1 )) > 0.
In particular, b∗2 (b1 ) > 0. Moreover, no bid b2 ≥ R can be a best response. For such a bid, Equation 9 gives u2 (b1 , b2 ) = q2 (R − b2 ) − (1 − q2 )γb2 , in which the winning payoff R − b2 ≤ 0 and the losing payoff −γb2 < 0. Because b1 > 0 makes q1 > 0, and hence q2 < 1, the losing event carries positive weight 1 − q2 > 0, so u2 (b1 , b2 ) < 0. Since u∗2 > 0, the best response therefore satisfies b∗2 (b1 ) < R.
(28)
Let qi∗ := qi (b1 , b∗2 (b1 )) be the winning probabilities at this best response. Since b1 > 0 and b∗2 (b1 ) > 0, both probabilities are positive and q1∗ + q2∗ = 1. We now express P2 ’s utility (Equation 9) as a function of her own bid, holding b1 fixed: u2 (b1 , b2 ) = q2 (b1 , b2 )R − b2 γ + (1 − γ)q2 (b1 , b2 ) . (29) For b2 > 0, since q2 = bk2 /(bk1 + bk2 ) (Equation 8), ∂q2 k k bk bk−1 = k 1 2 k 2 = q1 q2 . ∂b2 b2 (b1 + b2 )
Differentiating u2 (Equation 29) term by term, with the
∗ Since b∗2 (b1 ) < R (Equation 28), we bound R−(1−γ)b 2 (b1 ) ∗ in two cases: For 0 < γ ≤ 1, (1 − γ) R − b2 (b1 ) ≥ 0 gives R − (1 − γ)b∗2 (b1 ) ≥ γR; for γ > 1, R − (1 − γ)b∗2 (b1 ) = R + (γ − 1)b∗2 (b1 ) ≥ R since b∗2 (b1 ) ≥ 0. In short,
R − (1 − γ)b∗2 (b1 ) ≥ min{1, γ}R.
Combining the last two inequalities yields 1 R ≤ . q1∗ < k min{1, γ} k R − (1 − γ)b∗2 (b1 )
Finally, bound P1 ’s utility at this accommodated outcome: R u1 (b1 , b∗2 (b1 )) = q1∗ (R−b1 )−q2∗ γb1 ≤ q1∗ R < . k min{1, γ} This holds for every b1 ∈ (0, bk,γ dtr ). Taking the supremum over exactly this interval gives uk,γ acc ≤ R/(k min{1, γ}).
Appendix F. Proof of Lemma 3 Lemma 3 (Deterrence utility bound, restated). Fix γ > 0. If exp(1/γ) k ≥ max 2, , γ R : then the utility of the deterrence strategy exceeds k min{1,γ}
uk,γ dtr >
R . k min{1, γ}
(32)
Proof. We treat the two cases γ > 1 and 0 < γ ≤ 1 separately. First suppose γ > 1. The idea is to bound the deterrence bid by its value at γ = 1, where it is largest, and then bound that value crudely using k ≥ 2. By the closed form (Equation 3), k−1 k 1/k −1/k bk,γ /R = (k − 1) /(γk ) is proportional to γ , dtr hence strictly decreasing in γ . Raising γ past 1 therefore only lowers the bid: k,1 bk,γ dtr < bdtr .
(33)
We next bound bk,1 dtr . Because k ≥ 2, we have k − 1 ≥ 1, so (k − 1)k−1 ≤ (k − 1)k . Therefore, 1/k bk,1 k−1 (k − 1)k−1 dtr ≤ = . (34) k R k k Combining Equation 33 and Equation 34, we have k−1 R. k Therefore, we have a lower bound on the deterrence utility: bk,γ dtr <
k−1 R R= . k k Finally, since γ > 1, we have min{1, γ} = 1, so that uk,γ dtr > R/(k min{1, γ}). Now suppose 0 < γ ≤ 1. Our goal is to show that uk,γ dtr > R/(k min{1, γ}), which in this case is uk,γ > R/(kγ) , whenever k ≥ exp(1/γ)/γ . dtr := Denoting z kγ , the hypothesis becomes z ≥ exp(1/γ) > 1. The idea is to reduce this utility bound to a one-variable inequality in z , monotone in z , and then verify it at the smallest admissible value z = exp(1/γ). By the deterrence bid (Equation 3), 1/k bk,γ (k − 1)k−1 dtr = R γk k (k − 1) ln(k − 1) − ln γ − k ln k = exp k (k − 1) ln(1 − 1/k) − ln k − ln γ = exp k (k − 1) ln(1 − 1/k) − ln z = exp . (35) k k,γ uk,γ dtr = R − bdtr > R −
Since ln(1 − 1/k) ≤ −1/k , we have (k − 1) ln(1 − 1/k) ≤ −(1 − 1/k).
Combining this with Equation 35, we have bk,γ −(1 − 1/k) − ln z dtr ≤ exp . R k
equals −d, so bk,γ dtr ≤ exp(−d). R It remains to turn this bound on the bid into the utility bound k,γ in Equation 32. Since uk,γ dtr /R = 1 − bdtr /R, the bound k,γ bdtr /R ≤ exp(−d) gives uk,γ dtr ≥ 1 − exp(−d). R Our next goal is therefore to prove 1 − exp(−d) >
(36)
together with uk,γ dtr /R ≥ 1 − exp(−d), this gives the desired bound uk,γ /R > 1/z . dtr We weaken the left-hand side of Equation 36 using the elementary inequality 1−exp(−d) ≥ d/(1+d), which holds for every d ≥ 0. So it suffices to prove 1 d > . 1+d z Multiplying through by the positive quantities z and 1 + d, this is equivalent to (z − 1)d > 1. It is convenient to express (z−1)d in closed form. Recall that d = (ln z + 1 − 1/k)/k , and that k = z/γ , so that 1/k = γ/z . Substituting both occurrences of 1/k gives γ γ d = ln z + 1 − . z z Multiplying by z − 1 and using (z − 1)/z = 1 − 1/z , we obtain 1 γ 1− . Fγ (z) := (z − 1) d = γ ln z + 1 − z z
Our goal is now to show that Fγ (z) > 1 for every z ≥ exp(1/γ). We first show that Fγ is strictly increasing in z > 1. Differentiating the closed form gives Fγ′ (z) 1 γ 1 ln z + 1 − γ/z = + 2 1− + . γ z z z z2 The first product is positive, since z > 1 makes both of its factors positive. In the second term, the numerator ln z +1− γ/z is increasing in z , and at z = 1 it equals 1 − γ , which is non-negative because γ ≤ 1. Hence the numerator is nonnegative for all z ≥ 1. Both terms are therefore non-negative and the first is strictly positive, so Fγ′ (z) > 0. Because Fγ is increasing, over the range z ≥ exp(1/γ) it is smallest at the left endpoint z = exp(1/γ). It is therefore enough to check that Fγ (exp(1/γ)) > 1. Set t := 1/γ , so that t ≥ 1 because γ ≤ 1. Substituting z = exp(t) and γ = 1/t into the closed form and simplifying yields Fγ (exp(1/γ)) − 1 = γ 2 exp(−t) g(t),
Define
ln z + 1 − 1/k . d := k Since −(1 − 1/k) − ln z = −(ln z + 1 − 1/k), the exponent
1 ; z
where g(t) := t exp(t) + exp(−t) − t2 − t − 1.
Since γ 2 exp(−t) > 0, it remains to show that g(t) > 0 for t ≥ 1, which we build up from its derivatives. The second derivative g ′′ (t) = (2 + t) exp(t) + exp(−t) − 2
is positive for t ≥ 1, so g ′ is increasing on [1, ∞). At the left endpoint, g ′ (1) = 2e − 1/e − 3 > 0, so g ′ is positive throughout [1, ∞), and hence g is increasing there. Finally g(1) = e + 1/e − 3 > 0, so g(t) ≥ g(1) > 0 for all t ≥ 1. This gives Fγ (exp(1/γ)) > 1, and by monotonicity Fγ (z) > 1 for every z ≥ exp(1/γ). Collecting the inequalities, for every z ≥ exp(1/γ) we have bk,γ uk,γ dtr = 1 − dtr ≥ 1 − exp(−d) R R 1 1 1 d > = = , ≥ 1+d z kγ k min{1, γ}
where the strict inequality is precisely (z−1)d = Fγ (z) > 1. In all, when k ≥ max{2, exp(1/γ)/γ}, we have uk,γ dtr > R/(k min{1, γ}) for every γ > 0.
Appendix G. Proof of Lemma 4 Lemma 4 (SPNE existence after a positive user bid, restated). Consider a subgame starting from step t with any history ht−1 such that (⌊t/2⌋)
x1 (ht−1 ) = b1
> 0.
Then the subgame admits a pure-strategy SPNE. Proof. Consider the subgame that starts from a history ht−1 at the beginning of step t at which P1 ’s latest bid is positive, x1 (ht−1 ) > 0. By Hellwig and Leininger [137, Theorem 1], a game has a pure-strategy SPNE provided that (i) it has a finite horizon, (ii) it has perfect information, (iii) the action sets are compact, (iv) the utility functions are continuous, and (v) the constraint correspondence, which assigns to each history the set of actions then feasible, is closed-valued and continuous in the history. The subgame has a finite horizon and perfect information, so conditions (i) and (ii) hold. The acting player Pi chooses a bid from R≥0 , and since bids are non-decreasing her feasible set is the closed interval [xi (h), ∞), where xi (h) is her latest bid. This interval is closed, and its lower endpoint xi (h) varies continuously with the history, so the constraint correspondence is closed-valued and continuous in the history, and condition (v) holds. The action set R≥0 , however, is not compact, so condition (iii) fails and the theorem does not apply to the subgame directly. We proceed in three steps. Step 1 verifies condition (iv), the continuity of the utilities. Step 2 constructs a new game with compact action sets, satisfying all of the conditions (i)–(v), and applies the theorem to establish the existence of a purestrategy SPNE of that game. Step 3 extends this equilibrium to the original subgame by induction.
Step 1: Continuity of the utilities. Because bids are nondecreasing, P1 ’s final bid satisfies (m)
b1
≥ x1 (ht−1 ) > 0,
and consequently k (m) (m) (b1 )k + (b2 )k ≥ x1 (ht−1 ) > 0. The total weight W is therefore strictly positive, so the winning probabilities are continuous in the final bids. By Equation 9, the utility functions are continuous. Step 2: Construction of a compact game. We now construct a new game by capping each bid, so that the unbounded action sets become compact intervals. We choose each cap so high that exceeding it is never worthwhile, which keeps the equilibria unchanged. How high this upper bound must be follows from comparing two options for the acting player: raising her bid, or keeping her latest bid unchanged. We denote γ := min{γ, 1}, and γ := max{γ, 1}.
Suppose Pi acts at some step, with history h and latest bid xi (h). Keeping her bid at xi (h) through all of her remaining steps guarantees her a utility of at least −γxi (h): If her final bid remains xi (h), then by Equation 9 her utility at any final winning probability qi ∈ [0, 1] is ui = qi R − xi (h) − (1 − qi )γxi (h) = qi R − γ + (1 − γ)qi xi (h), which is at least −γxi (h) because γ + (1 − γ)qi ≤ γ and qi R ≥ 0. Suppose instead that she raises her bid to some b′ at this step. Let bbi be her resulting final bid; since bids are non-decreasing, bbi ≥ b′ . Equation 9 gives ui = qi R − γ + (1 − γ)qi bbi ≤ R − γbbi ≤ R − γb′ , where the first inequality uses γ + (1 − γ)qi ≥ γ . Hence, as soon as R + γxi (h) b′ > , γ we have ui ≤ R − γb′ < −γxi (h), so raising the bid to b′ is strictly worse than keeping xi (h). We call this the exclusion bound: Any bid above (R + γxi (h))/γ can be safely excluded. We turn this principle into a compact game by induction on the number of remaining steps r := 2m − t + 1.
The base case r = 0 leaves no step to play, so the claim vacuously holds. For the inductive step, suppose r ≥ 1 and that the claim holds for every subgame in which P1 ’s latest bid is positive, with fewer than r remaining steps. Guided by the exclusion bound, we construct a new game, the restricted game, that coincides with the subgame except that every bid is capped, so that the action sets become compact intervals. The caps are a deterministic
sequence of bounds B0 , B1 , . . . , Br ,
where Bℓ bounds both players’ latest bids after ℓ of the remaining steps have been played. Starting from the latest bids, we set B0 := max{x1 (ht−1 ), x2 (ht−1 )}.
For ℓ = 0, . . . , r − 1, define Bℓ+1 :=
R + γBℓ , γ
the exclusion bound’s threshold with the latest bid xi (h) replaced by its upper bound Bℓ . Because R > 0, γ ≤ 1, and γ ≥ 1, we have Bℓ+1 > Bℓ
for every ℓ. Consider the (ℓ + 1)-st remaining step, where ℓ = 0, . . . , r − 1. Let the latest bid pair of this step be (x1 , x2 ). In the restricted game, we maintain the invariant x1 (ht−1 ) ≤ x1 ≤ Bℓ ,
0 ≤ x2 ≤ Bℓ .
The invariant holds at ℓ = 0 by the definition of B0 . If it holds before the (ℓ + 1)-st remaining step, then the acting player is allowed to choose a bid only up to Bℓ+1 , while the non-acting player’s bid is unchanged. Hence the invariant holds at the next step as well. More explicitly, the (ℓ + 1)-st remaining step is step number s := t + ℓ of the full 2m-step game. If s is odd, then P1 acts and her feasible bids in the restricted game are [x1 , Bℓ+1 ].
If s is even, then P2 acts and her feasible bids in the restricted game are [x2 , Bℓ+1 ]. The action set at each step is the compact interval [0, Bℓ+1 ], and the constraint correspondence assigns the nonempty closed subinterval [xi , Bℓ+1 ]. This correspondence is continuous, because its lower endpoint is the acting player’s latest bid and its upper endpoint is fixed at that step. The state transition is also continuous: After a bid b by P1 , the new latest bid pair is (b, x2 ); after a bid b by P2 , it is (x1 , b). Together with the continuity of the utilities from Step 1, the restricted game is a finite-horizon game of perfect information with compact action sets, a closed-valued continuous constraint correspondence, and continuous utilities. By Theorem 1 of Hellwig and Leininger [137], it admits a pure-strategy SPNE. Step 3: Extension to the unbounded subgame. It remains to show that this restricted-game SPNE is also an SPNE of the original unbounded subgame. Consider any history h inside the compact region before the (ℓ + 1)-st remaining
step, and let Pi be the acting player with the latest bid xi (h), so that xi (h) ≤ Bℓ by the invariant. Suppose she deviates outside the restricted feasible set to some bid b > Bℓ+1 . Then R + γBℓ R + γxi (h) b > Bℓ+1 = ≥ , γ γ so by the exclusion bound of Step 2 this deviation gives her utility strictly below −γxi (h). Keeping her bid at xi (h), on the other hand, is feasible in the restricted game and guarantees her at least −γxi (h). Hence no excluded bid is a profitable deviation. We now assemble an equilibrium of the original unbounded subgame. On histories that remain inside the compact region, use the SPNE of the restricted game. If a player nevertheless chooses a bid outside the compact region, the resulting subgame has fewer than r remaining steps, and P1 ’s latest bid is still positive: If P1 deviates, her own bid remains positive; if P2 deviates, P1 ’s positive bid is unchanged. By the induction hypothesis, fix a pure-strategy SPNE for each such off-path subgame. The resulting strategy profile is sequentially optimal at every history. At histories inside the compact region, deviations within the compact action set are unprofitable by the restricted-game SPNE, while deviations outside the compact action set are unprofitable by the exclusion bound. At histories outside the compact region, sequential optimality follows from the induction hypothesis. Hence the constructed strategy profile is an SPNE of the original subgame. This completes the induction and proves the lemma.
Appendix H. Proof of Lemma 5 Lemma 5 (Positive-entry continuation bound, restated). Consider a subgame immediately after P1 publishes a pos(m) (m) itive bid from an all-zero state, and let b1 , b2 be the final bids under any SPNE of this subgame. Then n o (m) (m) k,γ u1 b1 , b2 ≤ max uk,γ dtr , uacc . Proof. We proceed in three steps. Step 1 bounds P2 ’s final bid below by her smallest best response over all nonnegative bids. Step 2 shows that lowering P2 ’s final bid to that smallest best response does not decrease P1 ’s utility, reducing the bound to a single two-step outcome. Step 3 bounds this two-step outcome by either the deterrence or the accommodation utility. Before carrying out these steps, we dispose of a trivial case. If P1 ’s utility is nonpositive, then the bound is immediate: k,γ k,γ (m) (m) u1 b1 , b2 ≤ 0 < uk,γ dtr ≤ max udtr , uacc , where uk,γ dtr > 0 by Proposition 2. It therefore remains to consider the case (m) (m) u1 b1 , b2 > 0. (37)
Step 1: A lower bound on P2 ’s final bid. Recall that (m−1) b2 is P2 ’s bid immediately before her final action. Since the strategy is subgame perfect, P2 ’s final bid solves the constrained best-response problem (m)
b2
(m) ∈ arg max u2 b1 , b2 .
(m)
k,γ k,γ b1 < bk,γ dtr , which yield the bounds udtr and uacc , respectively. (m) (m) If b1 ≥ bk,γ dtr , using q1 b1 , b2 ≤ 1 and Equation 38, we obtain i h (m) (m) (m) (m) u1 b1 , b2 = −γb1 + q1 b1 , b2 R − (1 − γ)b1
(m−1)
b2 ≥b2
(m)
≤ −γb1
(m) We now consider P2 ’s best response to b1 over all non-
negative bids, which coincides with her best response in the two-step game. Because P1 has published a positive bid (m) and bids are non-decreasing, we have b1 > 0. The twostep analysis (§5.2.1) shows that P2 ’s best-response corre(m) spondence BR2 b1 is nonempty and compact. Denote its smallest element by (m) b2 := min BR2 b1 . (m)
We now show that b2 is a lower bound on b2 , that (m) is, b2 ≤ b2 . If b2 lies below P2 ’s minimal feasible final (m−1) bid, that is, b2 < b2 , the claim is immediate from (m) (m−1) (m−1) b2 ≥ b2 . Otherwise b2 ≥ b2 , so b2 is feasible in the constrained final-step problem. Since b2 already maxi(m) mizes u2 (b1 , ·) over all non-negative bids, the constrained (m) and unconstrained maxima coincide, so b2 is itself an unconstrained best response: (m) (m) b2 ∈ BR2 b1 . By the minimality of b2 , we again obtain
Step 2: Lowering P2 ’s final bid does not decrease P1 ’s (m) utility. We show that replacing b2 by b2 does not decrease P1 ’s utility u1 . Using the utility formula (Equation 9), we obtain (m) (m) u1 b1 , b2 = h i (m) (m) (m) (m) − γb1 + q1 b1 , b2 R − (1 − γ)b1 . (m) (m) By Equation 37, u1 b1 , b2 > 0, which is possible only if (m) R − (1 − γ)b1 > 0. (38) (m)
Since b2 ≤ b2 , lowering P2 ’s final bid weakly increases P1 ’s winning probability: (m) (m) (m) q1 b1 , b2 ≥ q1 b1 , b2 . Together with Equation 38, this implies (m) (m) (m) ≤ u1 b1 , b2 . u1 b1 , b2 Step 3: Comparison with the deterrence and accommodation utilities. It remains to show that (m) k,γ u1 b1 , b2 ≤ max uk,γ dtr , uacc . (m)
(m)
= R − b1
≤ R − bk,γ dtr = uk,γ dtr . (m) (m) is If instead 0 < b1 < bk,γ dtr , then b2 = min BR2 b1 (m) by definition P2 ’s selected best response b∗2 b1 (§5.2.1). (m) Since b1 lies in the accommodation range, the definition of uk,γ acc as a supremum over that range (Equation 10) yields (m) (m) (m) u1 b1 , b2 = u1 b1 , b∗2 (b1 ) ≤ uk,γ acc .
Combining the two cases, we have (m) k,γ u1 b1 , b2 ≤ max uk,γ dtr , uacc . Summary. Chaining the conclusions of Steps 2 and 3, we obtain (m) (m) (m) k,γ u1 b1 , b2 ≤ u1 b1 , b2 ≤ max uk,γ dtr , uacc , which proves the lemma.
Appendix I. Proof of Theorem 4
(m) b2 ≤ b2 .
We treat separately the two cases b1
(m)
+ R − (1 − γ)b1
≥ bk,γ dtr and 0 <
Theorem 4 (Deterrence from every all-zero subgame, rek,γ stated). Suppose uk,γ dtr > uacc . For every odd step t = 2j −1, consider an all-zero subgame beginning at step t, that is, (⌊t/2⌋)
b1
and
(⌊(t−1)/2⌋)
b2
(j−1)
= b1
=0
(j−1)
= b2
= 0.
Then this all-zero subgame admits an SPNE in which (ℓ)
b1 = bk,γ dtr
and
(ℓ)
b2 = 0
for every ℓ = j, . . . , m.
Proof. We proceed by backward induction on j . When j = m, the all-zero subgame consists only of steps 2m − 1 and 2m. The claim is therefore exactly the two-step deterrence equilibrium in Theorem 3. For the induction step, fix j < m and assume the theorem holds for index j + 1, that is, for the all-zero subgame beginning at step 2(j + 1) − 1 = 2j + 1. Before the concrete induction analysis, we first specify a continuation, the actions the players take in the subgame afterwards, to be used after a deterring bid has been published. Consider any history h at which P1 ’s latest bid satisfies x1 (h) ≥ bk,γ dtr and P2 ’s latest bid satisfies x2 (h) = 0. Prescribe that both players leave their bids unchanged for the rest of the game. If P2 deviates to any positive bid, then
switch to a pure-strategy SPNE of the resulting positive-user subgame, whose existence is guaranteed by Lemma 4. We verify that this prescription is sequentially optimal. If P2 deviates to a positive bid, then under any continuation her final bid remains positive, and P1 ’s final bid remains at least bk,γ Therefore the dtr because bids are non-decreasing. k,γ k k,γ final weight of P1 is at least bdtr = Wdtr . By Lemma 1, P2 ’s terminal utility is at most zero, regardless of her final positive bid. Staying at zero also gives her utility zero. Hence P2 has no profitable deviation. While P2 stays at zero, P1 wins for sure and earns R−x1 (h). Since bids cannot be decreased, raising P1 ’s bid from x1 (h) only lowers this utility. Thus P1 also has no profitable deviation. Therefore this prescription is an SPNE of every such deterring subgame. We now carry out the concrete analysis for the all-zero subgame beginning at step 2j − 1. We prescribe that P1 (j) chooses b1 = bk,γ dtr and then follows the deterring continuk,γ ation described above. This gives P1 utility uk,γ dtr = R−bdtr . We now check that P1 has no profitable deviation at step 2j − 1. There are three relevant cases. First, if she follows the prescribed strategy and pubk,γ lishes bk,γ dtr , she obtains udtr by the deterring continuation. (j)
Second, if she chooses b1 = 0, then P2 has not observed any transaction and therefore has no feasible positive (j) entry action at step 2j , i.e., b2 = 0. The game then reaches the all-zero subgame beginning at step 2j + 1, and the induction hypothesis gives P1 utility uk,γ dtr . (j)
Third, if she chooses some other positive bid b1 > 0, then the game enters a positive-user subgame. For that continuation, choose a pure-strategy SPNE supplied by Lemma 4. Let (m) (m) b1 , b2 be the final bids under this continuation. By Lemma 5, n o (m) (m) k,γ k,γ u1 b1 , b2 ≤ max uk,γ , u acc = udtr , dtr where the equality uses the hypothesis
Appendix J. Numerical Simulation for k Values We numerically find the exponent parameter k that makes PRECEDE Anti-Spam and deterrence the equilibrium. For a given γ , a valid k satisfies the deterrence k,γ condition uk,γ dtr > uacc (Theorem 3), the Anti-Spam bound k ≥ ln 2/ ln(1+γ) (Theorem 2), and k > 1 by PRECEDE’s definition (§4.2). Since we have no closed form for uk,γ acc , we evaluate these conditions numerically. We target a range γ ∈ [γmin , γmax ] and seek k values that work across it. We set this range from our empirical measurements of γ (§A), in two cases: to secure against front-running on Uniswap V3 alone, [0.867, 1.087], and to secure both V2 and V3, [0.259, 1.087]. k,γ Because the deterrence advantage uk,γ dtr −uacc need not be monotone in k , checking the smallest feasible k alone does not suffice: A larger k may fail where a smaller one works. We therefore require that every k above kmin meets all three conditions over the entire γ range, and we find the smallest such kmin . A numerical search must be bounded, so we check the conditions across [kmin , kmax ] with kmax = 20, and make no claim for k > kmax . We set R = 1 without loss of generality, since all revenues scale with it. We find kmin by bisection, starting from the Anti-Spam bound ln 2/ ln(1 + γmin ), the smallest k the range admits, verifying for each candidate that all conditions hold across the rectangle [γmin , γmax ] × [kmin , kmax ], where we search for the worst point by differential evolution, a continuous global optimizer. We then verify the resulting rectangle twice over: On a uniform 101 × 101 grid, and by five differential-evolution searches, which explore the rectangle continuously to catch violations hiding between grid points. For γ ∈ [0.867, 1.087], the search yields kmin ≈ 1.146, above the Anti-Spam bound ≈ 1.111, so the deterrence condition is what pushes kmin up. For γ ∈ [0.259, 1.087], it yields kmin ≈ 3.010, the Anti-Spam bound itself, so the search stops where it starts and Anti-Spam alone determines kmin . Both kmin values are rounded up, since kmin is a lower bound on the admissible k .
k,γ uk,γ dtr > uacc .
Thus no positive deviation can give P1 more than the prescribed deterring bid. It remains only to specify the continuation after histories not covered by the prescribed path. If the play reaches a later all-zero subgame, we use the SPNE given by the induction hypothesis. If the play reaches a positive-user subgame, we use an SPNE supplied by Lemma 4, except in the deterring continuation described above, which has already been shown to be an SPNE. Therefore every continuation following the prescribed action is subgame perfect, and P1 has no profitable deviation at the current all-zero state. The prescribed strategies consequently form an SPNE of the allzero subgame beginning at step 2j − 1. This completes the backward induction.
Appendix K. Proof of Proposition 4 Proposition 4 (Revenue-optimal k , restated). Fix γ > 0. The user’s deterrence revenue uk,γ dtr (k, γ), viewed as a function of k > 1, is strictly increasing on 1, 1+ γ1 and strictly decreasing on 1 + γ1 , ∞ . Its maximum, attained uniquely at k = 1 + γ1 , is γ 1 uk,γ 1 + , γ = R. dtr γ 1+γ Proof. Differentiating uk,γ dtr in k directly is cumbersome, so we instead study the bid bk,γ dtr and recover the revenue
k,γ through uk,γ dtr = R − bdtr . Let
bk,γ dtr (k, γ) R (k − 1) ln(k − 1) − k ln k − ln γ = . k Differentiating term by term, the numerator satisfies d (k − 1) ln(k − 1) − k ln k = ln 1 − k1 , dk so that, after collecting terms, ln γ(k − 1) ′ L (k) = , k2 L(k) := ln
so L′ (k) < 0 for k < 1 + γ1 and L′ (k) > 0 for k > 1 + γ1 . 1 Hence bk,γ dtr is minimized uniquely at k = 1 + γ , and k,γ k,γ udtr = R − bdtr is correspondingly maximized there. At k = 1 + γ1 , k − 1 = γ1 and k = 1+γ γ , so (k − 1) ln(k − 1) − k ln k − ln γ ln(1 + γ) − ln γ − ln γ = − γ1 ln γ − 1+γ γ = − 1+γ γ ln(1 + γ),
where the ln γ contributions cancel (their coefficients sum to − γ1 + 1+γ by k = 1+γ gives γ − 1 = 0). Dividing γ k,γ R 1 L = − ln(1 + γ), i.e. bdtr 1 + γ , γ = 1+γ . Therefore, we obtain the desired result: γR k,γ 1 uk,γ . dtr 1 + γ , γ = R − bdtr = 1+γ