PaperlayerView exact revision on arXiv

Source-linked AI summary

Censorship Resistance in On-Chain Auctions

Elijah Fox, Mallesh Pai, Max Resnick

arXiv:2301.13321v2econ.THcs.GT

TL;DR

Financial applications need timely transaction inclusion, but eventual liveness does not ensure it against a motivated censor. The paper defines censorship resistance through adversarial cost as a function of tip and applies it to auctions, finding limitations in single-block and rotating-proposer designs while proposing conditional tips with concurrent proposers. Its auction analysis also finds that colluders gain an advantage as honest bidders increase, and that public tips can reveal sealed bids.

  • Problem

    Eventual liveness does not guarantee timely transaction inclusion for financial applications facing a motivated censor.

    Source: §1 · p. 2

  • Method

    The paper defines censorship resistance as the cost to make a tipped write fail within a time window and analyzes this measure in on-chain auctions.

    Source: §1 · p. 2

  • Results

    As honest bidders increase, a colluding bidder wins increasingly often and captures an increasingly large share of auction surplus.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Rotating-proposer auctions achieve sufficient censorship resistance only when block count grows faster than bidder count, while conditional tips among concurrent proposers can make censorship costly.

    Source: §1 · pp. 3–4

    Analytical results for non-uniform bidder 0 values appear out of reach; the qualitative findings are suggested, rather than established, to carry over.

    Source: §5.3 · p. 16

Abstract

from arXiv · show

Modern blockchains guarantee that submitted transactions will be included eventually; a property formally known as liveness. But financial activity requires transactions to be included in a timely manner. Unfortunately, classical liveness is not strong enough to guarantee this, particularly in the presence of a motivated adversary who benefits from censoring transactions. We define censorship resistance as the amount it would cost the adversary to censor a transaction for a fixed interval of time as a function of the associated tip. This definition has two advantages, first it captures the fact that transactions with a higher miner tip can be more costly to censor, and therefore are more likely to swiftly make their way onto the chain. Second, it applies to a finite time window, so it can be used to assess whether a blockchain is capable of hosting financial activity that relies on timely inclusion. We apply this definition in the context of auctions. Auctions are a building block for many financial applications, and censoring competing bids offers an easy-to-model motivation for our adversary. Traditional proof-of-stake blockchains have poor enough censorship resistance that it is difficult to retain the integrity of an auction when bids can only be submitted in a single block. As the number of bidders $n$ in a single block auction increases, the probability that the winner is not the adversary, and the economic efficiency of the auction, both decrease faster than $1/n$. Running the auction over multiple blocks, each with a different proposer, alleviates the problem only if the number of blocks grows faster than the number of bidders. We argue that blockchains with more than one concurrent proposer have can have strong censorship resistance. We achieve this by setting up a prisoner's dilemma among the proposers using conditional tips.

1. INTRODUCTION

Eventual inclusion is insufficient for time-sensitive finance, motivating a censorship-resistance measure that relates adversarial censorship cost to a transaction’s tip and a fixed time window. Applying it to auctions, the paper finds that single-block auctions disadvantage honest bidders as their number grows, while alternative proposer designs trade off censorship resistance and speed.

1. INTRODUCTION

  • Censorship resistance measures the minimum adversarial cost to make a transaction fail as a function of its tip, for a specified time window.The measure is intended to capture both tip-dependent censoring cost and the trade-off between censorship resistance and speed for a particular bulletin board.Source: §1 · p. 2
  • The auction analysis models a single colluding bidder who may bribe a proposer to omit competing transactions, against proposers with autonomy over block contents.The paper considers on-chain auctions because censorship costs and the benefits of omitting competing bids are quantifiable in this setting.Source: §1 · pp. 2–3
  • As honest bidders increase, the colluding bidder wins increasingly often and captures an increasingly large share of auction surplus.Inclusion tips secure other transactions but benefit their payer only if they win; omission bribes privately benefit the colluder and harm other bidders in equilibrium.Source: §1 · p. 3
  • In sealed-bid auctions, the colluder can infer private bids from public tips, so encrypted bids or commit-reveal alone are not a silver bullet against censorship.The colluder chooses which transactions to target based only on their associated tips.Source: §1 · p. 3
  • Rotating proposers across multiple blocks provide sufficient censorship resistance only when the number of blocks grows faster than the number of bidders.This is undesirable when auctions need to finish quickly; MEV auctions need to clear at least once every slot, or 12 seconds on Ethereum.Source: §1 · p. 3
  • With multiple concurrent proposers, tips conditioned on how many proposers include a bid can create a proposer prisoner’s dilemma that makes censorship costly.Offering T when only one proposer includes and t ≪ T when multiple include incentivizes each proposer to include; censoring then costs kT while expected tips are kt.Source: §1 · pp. 3–4

2. RELATED LITERATURE

Related work covers censorship in block production, cryptographic sealed-bid auctions, and auctions used to order or include transactions. The paper situates its focus on censorship alongside prior research on fairness, MEV, and on-chain auction applications.

2. RELATED LITERATURE

  • Proposer Builder Separation gives block builders control over transaction inclusion, while OFAC-related exclusions prompted study of censorship and its effects (Buterin (2021); Wahrstätter et al. (2023)).The discussion notes that builders may purchase block-building rights and intentionally omit transactions.Source: §2 · p. 4
  • Cryptographic auction designs include commitment-based second-price auctions and methods that hide information beyond auction results (Ferreira and Weinberg (2020); Akbarpour and Li (2018, 2020); Lee et al. (2001); Elkind and Lipmaa (2004); Suzuki and Yokoo (2003)).The cited work addresses optimality, strategy-proofness, credibility, and combinatorial auctions.Source: §2 · p. 4
  • Auctions have been proposed for smart-contract computation and transaction ordering, from early blockchain contract ideas to mechanisms aimed at mitigating MEV (Szabo (1997); Galal and Youssef (2019); Blass and Kerschbaum (2018); Kulkarni et al. (2022)).Source: §2 · pp. 4–5
  • MEV-related auction mechanisms have evolved from priority gas auctions to selling block inclusion and ordering rights to builders (Daian et al. (2020); Flashbots (2022)).Flashbots’ SUAVE aims to move these auctions on-chain.Source: §2 · p. 5
  • Prior MEV mitigation research focused on fairness, while other work considers order-agnostic mechanisms and transaction ordering power (Kelkar et al. (2020, 2021); Ferreira and Parkes (2022); Johnson et al. (2022)).Ferreira and Parkes (2022) show that each liquidity-pool trade sequencing rule permits proposer non-zero risk-free profits.Source: §2 · p. 5
  • On-chain auction research also studies NFT sales, including gradual Dutch auctions and the possibility of auctioneers artificially raising prices (Milionis et al. (2022); Frankie et al. (2022); Kulkarni et al. (2023)).Source: §2 · p. 5

3. FORMALIZING CENSORSHIP RESISTANCE

The paper abstracts a blockchain as a public bulletin board with write and read operations, then defines censorship resistance by the cost of making a tipped write fail. This formulation supports comparisons across designs while accounting for tip size and time to inclusion.

3. FORMALIZING CENSORSHIP RESISTANCE

  • The bulletin-board abstraction separates writing a message from reading successfully written messages, with the paper assuming reads occur without friction.This models bid submission and subsequent auction execution without representing blockchain internals.Source: §3 · pp. 5–6
  • Including the tip as a write input models proposer tips and validator bribes, since write success can depend on tip size.The paper notes that a transaction on Ethereum is unlikely to succeed without a sufficient tip.Source: §3 · p. 6
  • The write operation is defined over a chosen inclusion window: one block for a single-block design, or any of k blocks for rotating proposers.The associated censorship cost can then be assessed within that window; the examples give costs t for an uncongested single block and kt for k rotating proposers.Source: §3 · pp. 6–7
  • Censorship resistance is a function mapping a write’s tip to the minimum cost a motivated adversary must pay to make that write fail.The write operation receives a message and tip; read returns messages written to the board.Source: §3 · p. 6
  • The definition can compare boards with different internal mechanisms and extends to multidimensional tips by mapping tip vectors to censorship costs.Source: §3 · p. 6

4. MODELLING THE AUCTION

The model studies a second-price sealed-bid auction on a blockchain, where bids are transactions and a designated bidder may bribe a proposer to omit competitors. It analyzes equilibria under stated bidder-value assumptions and a refinement to address multiplicity.

4. MODELLING THE AUCTION

  • The model assumes n + 1 bidders with independent private values on [0, 1], with bidder 0 potentially drawn from a different distribution; several results specialize to uniform values.Source: §4 · p. 7
  • The seller’s auction is a second-price sealed-bid auction with reserve price r, computed from included bids after bidders commit and proposers include transactions.The highest included bid wins if it meets the reserve and pays the greater of the reserve and the next-highest bid.Source: §4 · p. 7
  • Bids may be cryptographically committed, but the existence of each bid is public; the model abstracts away from block-size constraints and congestion.Source: §4 · p. 7
  • After other bids are submitted but before revelation, bidder 0 can offer the proposer a bribe to exclude a subset of bids; the proposer then determines which transactions enter the block.The auction outcome is computed from the bids included in the block.Source: §4 · p. 8
  • The game uses Perfect Bayes-Nash Equilibrium, with strategies and beliefs required to be optimal and on-path beliefs consistent with Bayesian updating.Source: §4 · p. 8
  • Because the game has multiple PBEs, the analysis focuses on equilibria where honest bidders bid truthfully and use symmetric tipping, while bidder 0 bids truthfully when he may win.This refinement restricts attention to a tractable class; the original game has other equilibria, including ones in weakly dominated strategies.Source: §4 · p. 9

5. RESULTS

In the two-bidder and larger-auction equilibria, the colluding bidder is advantaged; as the number of bidders grows, that bidder's win probability approaches 1 and seller revenue approaches the reserve-price benchmark.

5.1. Two Bidder Case

  • 3/4: bidder 0 wins with probability 3/4 and has expected surplus 1/12; seller revenue is 0 and proposer tip revenue is 1/4.The two-bidder result leaves the proposer with all auction revenue, while bidder 0 is advantaged by observing bidder 1's tip before deciding whether to bribe.Source: §5.1 · p. 10
  • Even when bids are sealed, transaction-inclusion mechanics can make private bids effectively recoverable from tips; positive tips are perfectly revealing in the two-bidder result.Tips are weakly monotone in bid, and a non-empty interval of values tips zero.Source: §5.1 · pp. 11–12
  • With two bidders and reserve r>0, bidder 1 bids truthfully and tips v1/2 − r when v1>2r, otherwise 0; bidder 0 bribes to omit bidder 1 when offered.The proposer accepts the bribe and omits bidder 1's bid; otherwise both bids are included.Source: §5.1 · pp. 11–12
  • The seller’s expected revenue is r(1−r²), the same as revenue from posting a “buy it now” price of r; the proposer’s expected revenue is 1/4(1−2r)².The seller receives no benefit from running an auction relative to posting a “buy it now” price of r.Source: §5.1 · p. 12

5.2. Three or more bidders

  • When each honest bidder's tip is at most their value divided by n, bidder 0's best response is to buy out all bids rather than a subset.In the equilibrium, bidder 0 bribes by paying the sum of tips to omit all other transactions.Source: §5.2 · pp. 13–14
  • As n grows, total tips decline, bidder 0's win probability approaches 1, and expected auction revenue approaches the revenue from posting reserve price r.The paper attributes declining tips to their public-good properties; seller revenue occurs with vanishing probability as n grows.Source: §5.2 · p. 14

5.3. General Distributions

  • With i.i.d. honest-bidder values from a distribution satisfying Assumption 1, the equilibrium has truthful bids, value-based tips, and a proposer who accepts an offered bribe to omit the other bids.The paper uses this result to compute expected total tips across bidder counts for Beta distributions.Source: §5.3 · pp. 15–16
  • Analytical results for non-uniform bidder-0 values are out of reach; the paper suggests, but does not establish, that its qualitative results carry over.Uniform bidder-0 values make the increase in the probability of avoiding buyout constant, simplifying the optimality condition.Source: §5.3 · p. 16

6. RESTORING CENSORSHIP RESISTANCE

The paper compares running auctions across multiple sequential blocks with using concurrent proposers to improve censorship resistance. Sequential blocks require a long auction window when bidder numbers are high, while concurrent proposers can restore the desired outcome within one slot.

6.1. Auction over Multiple Blocks

  • In the sequential-block model, independent proposers act in successive periods while bidder 0 can offer to exclude bids not yet included.Included bids leave the mempool and cannot be included again in later blocks.Source: §6.1 · pp. 16–17
  • If bidder 0 instead has value U[0, 1], honest bidders’ multi-block tipping is weakly lower than in the one-block case; this is shown numerically, not analytically.The stated equilibrium comparison applies when m > 1.Source: §6.1 · p. 17
  • For auctions over m < n blocks, the desired outcome requires more blocks than bidders, which can keep the auction open too long for financial applications.The paper reports that bidder tipping is unaffected when m < n and that the probability bidder 0 refrains from censoring collapses as n grows when m grows sublinearly.Source: §6.1 · pp. 17–18

6.2. Multiple Concurrent Block Proposers

  • Conditional tips set T when only one proposer includes a bid and t when multiple proposers include it, making censorship cost kT while inclusion costs kt.When T ≫ t, censorship is much more expensive than inclusion.Source: §6.2 · p. 18
  • Even two concurrent proposers restore the desired auction outcome for multiple honest bidders, with no on-path bribe and tips that do not reveal bids.The equilibrium outcome matches a standard second-price auction; bidders pay zero tips on path.Source: §6.2 · pp. 19–20

7. DISCUSSION

The discussion examines how proposer control over inclusion relates to MEV, and weighs conditional tipping with concurrent proposers against its practical and theoretical boundaries. It also identifies settings where censorship resistance matters and directions for further study.

7. DISCUSSION

  • Whether censorship or transaction ordering drives MEV changes the outlook: order-agnostic mechanisms may address ordering-based MEV but remain susceptible to extraction from censorship power.The second-price auction studied in the paper is among the order-agnostic mechanisms discussed.Source: §7 · p. 21
  • Even with encrypted bids, public tips may reveal private bids, so encrypting mempool transactions does not by itself remove this potential MEV source.The discussion contrasts this with the claim that public mempool transactions can be front-run.Source: §7 · p. 21
  • An MPC approach to privately select the top-k tips would require consensus changes to bind proposer inclusion, and a proposer could still accept a bribe exceeding expected top-k tips.As a private-mempool-only solution, MPC computes the highest tips but does not prevent profitable censorship.Source: §7 · p. 21
  • The model assumes one potential colluding bidder, while multiple proposers may complicate transaction ordering, increase DDOS exposure, and create redundancy and state bloat.With multiple possible colluders, a proposer could sell the right to collude; the paper describes MEV-boost as a direct channel for selling censorship rights.Source: §7 · p. 20, §7.1 · p. 22

7.2. Future Directions

  • The analysis leaves open how censorship affects auction equilibria with interdependent or common bidder values, and how auctioning the right to collude after bids are submitted changes outcomes.The paper says results still hold when that right is auctioned before bids, as a subgame, but post-bid auctioning could slightly warp equilibrium.Source: §7.2 · p. 22
  • Censorship resistance also matters for timely oracle feeds, options exercise, and optimistic-rollup fraud proofs; stronger resistance could permit faster rollup finality at the same security.The paper notes optimistic rollups currently leave a long fraud-proof submission window, for example seven days.Source: §7.2 · pp. 22–23

7.1. Multiple Concurrent Proposers in the Real world

  • Proposer rents from temporary inclusion monopolies shrink sharply under multiple concurrent proposers using conditional tips; MEV-boost payments to Ethereum proposers totaled $245 million since September 2022.The discussion says these payments are large compared with total MEV value and contribute to high transaction fees.Source: §7.1 · p. 21, §7.2 · p. 23

7.2. Future Directions

  • A data-availability layer could host bids without requiring its curating nodes to participate in consensus, potentially easing integration of multiple proposers.The paper presents this as another possible tool against on-chain censorship.Source: §7.2 · p. 23

A.1. Proof of Proposition 3

The proof derives a bidder’s optimal tipping condition and checks that the colluding bidder’s bribing strategy is a best response. Its tractability relies on a uniform value distribution for bidder 0.

A.1. Proof of Proposition 3

  • The bidder’s expected utility is expressed as expected auction profit minus the expected cost of a tip, which is charged when the bid is not censored.The proof considers bidder 1 when the other honest bidders use t(·) and bidder 0 censors bids whenever total tips do not exceed its value.Source: §A.1 · p. 26
  • Optimality requires the tipping function t(v) to satisfy a condition, with its inequality binding whenever t(v) > 0.The proof defines c as the expected tip E[t(v_j)].Source: §A.1 · p. 26
  • Under the derived tipping function, the proof verifies t(v) ≤ v/n and concludes bidder 0’s bribing strategy is a best response.The proof uses Lemma 1 for this best-response conclusion.Source: §A.1 · p. 27
  • The proof’s expected-utility calculation is analytically tractable because bidder 0’s value is uniform, which is why the authors cannot generalize beyond that distribution here.The uniform distribution makes F0 of the total tips equal to the total tips in the stated range.Source: §A.1 · pp. 26–27

A.2. Proof of Proposition 4

This proof bounds the solution parameter v_n by testing the optimality condition at candidate values. Those bounds also constrain aggregate expected tips.

A.2. Proof of Proposition 4

  • Substituting v_n = 1/√n makes the left side of condition (13) positive, yielding v_n ≤ 1/√n and n c ≤ 1/((n−1)√n).The proof says the leading term is O(1/n^(3/2)), while the other two terms are smaller.Source: §A.2 · p. 27
  • At v_n = 1/n, the leading term is O(1/n^3) and the second is approximately O(1/n^2), making the left side negative for large n.This is the proof’s comparison at the lower candidate value.Source: §A.2 · p. 28

A.3. Proof of Proposition 5

For a positive reserve price, the proof adjusts the bidder’s utility and optimal tipping condition to account for the reserve. It concludes that equilibrium tips remain asymptotically small.

A.3. Proof of Proposition 5

  • With reserve r, the proof writes a bidder’s interim utility from tip t against the other bidders’ tipping strategy and uses the reserve-adjusted value distribution.It identifies the first two terms as interim expected surplus in a second-price auction with reserve price r.Source: §A.3 · p. 28
  • For positive tips, optimality requires the reserve-adjusted tipping condition to hold with equality; the proof denotes expected tips by c_r.The condition is stated after substituting the reserve-price auction surplus.Source: §A.3 · p. 29
  • When r > 0, equilibrium tipping functions are first-order stochastically dominated by those at r = 0, so total tips still collapse to zero at a super-linear rate as n grows.The proof derives this conclusion from the result for r = 0 in Proposition 4.Source: §A.3 · p. 29

A.4. Proof of Proposition 6

For bidders drawn from F, the proof derives a first-order condition and states that it binds whenever t(v) > 0. Under Assumption 1, the resulting tips make bidder 0’s bribing strategy a best response.

A.4. Proof of Proposition 6

  • For bidders drawn from F, the first-order condition binds whenever t(v) > 0.The proof obtains this condition by repeating the calculation of Proposition 3 and taking first-order conditions.Source: §A.4 · p. 29
  • The proof also imposes a condition equating an integral of tips under F to c.It states that c and v jointly solve the condition.Source: §A.4 · pp. 29–30
  • Under Assumption 1, t(v) ≤ v/n satisfies Lemma 1’s condition, so bidder 0’s bribing strategy is a best response to these tips.The proof states that this conclusion continues to hold for the distribution F.Source: §A.4 · p. 30

A.5. Proof of Proposition 7

The proof extends the Proposition 3 argument to bidder 0’s uniform distribution on [0, κ]. It then analyzes a proposer-censoring subgame and concludes that (t, T) = (0, 1) is a best response for bidder 1.

A.5. Proof of Proposition 7

  • For bidder 0 distributed uniformly on [0, κ], the proof of Proposition 3 still applies because the total tip is below bidder 0’s highest possible value.The distribution changes equation (11) by a multiplicative constant 1/κ, which does not affect the optimization.Source: §A.5 · p. 30

A.6. Proof of Proposition 8

  • The Proposition 8 proof uses backward induction to analyze proposers’ censoring probabilities after tips (t, T) and bribe z are offered.It derives a symmetric mixed-equilibrium condition and the probability of successfully censoring for z ∈ [t, T].Source: §A.6 · pp. 30–31
  • The expected-utility expression is convex in q, restricting the solution to tip t or T; the proof also states that C ≤ v0.Here q ≡ z − t, and C is the value of censorship relative to no censorship.Source: §A.6 · p. 31
  • (t, T) = (0, 1) is a best response for bidder 1 because it results in bidder 0 offering a bribe of 0.The proof concludes this after noting that the bribing bidder’s expected utility is convex in q, so the solution is at t or T.Source: §A.6 · p. 31

Related papers

Loading 2301.13321v2…