Censorship-Resistant Sealed-Bid Auctions on Blockchains Orestis Alpos Common Prefix
Lioba Heimbach Category Labs
Kartik Nayak Duke University
Sarisht Wadhwa
arXiv:2606.14939v1 [cs.CR] 12 Jun 2026
Duke University
Abstract Auctions are now central to blockchain markets, settling NFT sales, token launches, DeFi liquidations, and arbitrage opportunities. Each on-chain bid is a public transaction whose inclusion is decided by a single consensus proposer per block. The proposer can observe pending bids, exclude competitors, and submit bids of their own, breaking the fairness guarantees of classical sealed-bid auctions. To enable latency-sensitive sealed-bid auctions in blockchain settings, we formalize four properties – each necessary to prevent a concrete attack – and design a protocol achieving all four: hiding bid contents, existence, and bidder identity until reveal (Hiding); counting all timely honest bids and rejecting late adversarial bids (Simultaneous Release); preventing silent withdrawal of committed bids (No Free Bid Withdrawal); and charging on-chain fees only to winners (Auction Participation Efficiency). Our protocol uses a timestamping oracle (instantiated with a committee of 2fts + 1 timestampers) and a censorship-resistant inclusion predicate (instantiated using a FOCIL-based inclusion list), with only the winning bid settled on-chain. Our construction relies on two zero-knowledge proofs: an eligibility proof that anonymously proves deposit membership to the timestamping committee, and an auction proof that binds a bid to a specific auction for the inclusion list committee. We implement both using Groth16 over BN254 with Poseidon hashing in arkworks/Rust: the auction proof generates in 13 ms and verifies in under 1 ms; eligibility proofs for Merkle trees up to 232 bidders generate in 47–159 ms and verify in ∼1 ms. Together, this yields a sealed-bid auction primitive practical for high-value, time-sensitive blockchain settings. 2012 ACM Subject Classification Security and privacy → Cryptography Keywords and phrases sealed-bid auctions, blockchains, censorship resistance, commit-and-reveal
1
Introduction
Auctions decide a growing share of outcomes in blockchain markets, from NFT and token sales to blockspace allocation, DeFi liquidations, and arbitrage capture. Yet implementing auctions on a blockchain introduces a unique structural challenge: every bid passes through a single consensus proposer per slot, who can observe pending bids, decide which competitors to include, and add its own bid to the auction. This proposer monopoly has produced a multibillion-dollar MEV economy [21] and is most damaging in latency-sensitive, high-value sealed-bid auctions, where a single proposer’s actions in one slot determine the outcome. The proposer’s monopoly creates several distinct failure modes for on-chain sealed-bid auctions. Pending bids sit in the (public) mempool, where the proposer and other observers can read their values, identities, and submission times before inclusion. The proposer can then censor honest bids, condition its own bid on those it sees, and bid with a latency
2
Censorship-Resistant Sealed-Bid Auctions on Blockchains
advantage over other bidders. An on-chain auction implemented as a smart contract does not address these failures: the contract sees only the bids the proposer has included, leaving consensus-layer censorship and the proposer’s ability to insert its own bid after observing others (i.e., a last-look advantage) untouched. Commit-and-reveal mitigates visibility by hiding bids until a reveal phase, but it introduces a different problem: a bidder can withhold their reveal once others’ bids leak [3]. Even absent any manipulation, a fully on-chain auction requires every bid to be submitted as a transaction. These transactions pay inclusion fees regardless of the auction outcome, so losing bidders incur a cost not present in traditional sealed-bid settings. The damage is sharpest in latency-sensitive, high-value auctions such as DeFi liquidations, batch auctions, and time-bounded arbitrage windows. A single slot of proposer-induced delay (around 12 seconds on Ethereum) is enough for asset prices to move materially: a delayed liquidation may settle against a different reference price, a batched auction may exclude a bid that would have moved the uniform clearing price, and an arbitrage opportunity may evaporate before the next slot. An effective blockchain sealed-bid auction protocol must therefore satisfy four properties: three that defend the auction against adversarial proposers and bidders, and one that aligns its payoff structure with classical auctions. 1. Hiding. Until the auction deadline, in an ideal world, no one learns what a given user bid, when a bid was submitted, or even whether a user bid. Without hiding, an attacker (such as a late-arriving bidder, or the next block proposer) can condition their own bid on observed bids: they outbid only when the asset’s value exceeds the observed bid and walk away otherwise, effectively diminishing the auction [34]. 2. Simultaneous Release. In an ideal world, the auction counts every honest bid submitted before the deadline and rejects every bid after it. Without this, a proposer can censor all rival bids and submit a near-zero bid of their own, winning the item essentially for free [34]. 3. No Free Bid Withdrawal. Once a user submits a bid, they cannot retract it without cost. Without this, in a commit-and-reveal scheme, a bidder can wait for other bids to leak during reveal and refuse to open their own commitment whenever doing so is unfavorable. Adverse selection then re-enters through the back door. 4. Auction Participation Efficiency (APE). On-chain auctions should match the payoff dynamics of their classical counterparts, i.e., only the winning bidder pays. Without APE, every bidder pays an inclusion fee regardless of outcome, so losing bidders earn negative expected utility from participating. The first three properties form the security backbone of the platform, while the fourth property is an efficiency property. Together, they recover the structural assumptions under which sealed-bid auctions are analyzed in the classical auction-theory literature. An ideal platform achieving all four properties thus places the auction in the same strategic setting assumed by Vickrey [50], Myerson [43], Riley and Samuelson [46], and Krishna [37], so that, conditional on the standard economic assumptions of the value environment also holding (e.g., independent private values, risk-neutral bidders, no collusion), the classical equilibrium and revenue results apply. Achieving all four properties simultaneously is hard, and prior work has addressed only subsets. Some proposals remove the single-proposer monopoly by restructuring consensus [34] to achieve certain properties; however, they still fail to achieve all the above, notably lacking APE since every bidder must still pay on-chain inclusion fees. Lighter approaches add inclusion [48, 51] or commit-and-reveal [49, 52, 44] mechanisms on top of existing chains, but lack hiding and cannot guarantee inclusion in narrow, time-bounded windows. None of the
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
At any time
Pre-Phase A
3
(AucID, item, tstart , tend )
auctioneer
Deposit Contract
Pre-Phase B (Au , Cu , D)
user
Deposit Contract
generate ρ, Cu
Phase 1: Timestamping
(hu , cm, πum )
For each auction
user u
gossip (cm, ti )σi
Timestampers Pts (nts = 2fts + 1)
wait for 2fts +1 votes or timeout 2∆g pad missing votes, create certificate σ
Phase 2: Bid submission user u
(tx, σ)
IL Proposers (existential honesty) running FOCIL
compute set of valid bids B compute local winning bid b
slot S
Figure 1 Overview of the auction protocol. Pre-Phase A registers an auction; Pre-Phase B is a one-time user registration covering all later auctions. Phase 1 (timestamping) delivers Hiding via a hidden commitment submitted to the timestamping oracle. Phase 2 (bid reveal) delivers Simultaneous Release via a censorship-resistant inclusion scheme enforcing timestamp certificates received in Phase 1. At settlement slot S, only the winning bid is posted on-chain, delivering APE.
previous works are able to reduce the cost to losing bidders and achieve APE. Protocol at a glance. We close this gap with a lightweight protocol built on two modular primitives: a timestamping oracle that attests bid creation times, and a censorship-resistant inclusion scheme that admits valid bids before the deadline and rejects late ones. We instantiate the oracle with a 2fts + 1 timestamping committee and the inclusion scheme with a FOCIL [48]-based mechanism; any other constructions providing the same guarantees would suffice. The protocol runs two preparatory phases ahead of any auction and two per-auction phases; Figure 1 gives an overview. In Pre-Phase A, an auctioneer registers an auction with a deposit contract. In Pre-Phase B, each user makes a one-time deposit and posts a commitment Cu to a private secret ρ, enabling later anonymous proofs of registration. The same deposit and commitment cover the user’s participation in any number of subsequent auctions; the locked deposit underpins No Free Bid Withdrawal, since a user who fails to reveal a committed bid forfeits it. For each auction, the protocol then runs two phases. In Phase 1 (timestamping), a user gossips a hiding commitment to its bid, paired with an anonymous proof of registration, to the timestampers. The user aggregates the timestampers’ signed responses into a single timestamp certificate that attests the bid was generated before tend . The commitment delivers Hiding, assuming that the network preserves sender anonymity [28]. In Phase 2 (bid submission), the user reveals the bid to an inclusion scheme which ensures censorship-resistance of the reveal. We achieve this by using a modified FOCIL [48] based scheme, paired with the verification of timestamp certificate received from the Phase 1. The inclusion scheme ensures that every bid backed by a valid pre-tend certificate is included and that any bid generated after tend is rejected, delivering Simultaneous Release. At settlement slot S, only the winning bid is posted on-chain, delivering APE.
4
Censorship-Resistant Sealed-Bid Auctions on Blockchains
Contributions. We summarize our contributions as follows. 1. Property formalization. We refine and formalize four properties for sealed-bid auctions in latency-sensitive blockchain settings: a strengthened hiding property capturing three leakage channels (bid value, bid existence, bidder identity); Simultaneous Release, combining short-term censorship resistance with post-deadline exclusion, parameterized by two network-dependent gaps: the lead time an honest user must allow before the deadline, and the window in which a late adversarial bid is still admitted; No Free Bid Withdrawal; and Auction Participation Efficiency. Hiding and auction participation efficiency are posed as ideal targets together with attainable relaxations. 2. Protocol design. We design a protocol using two primitives – a timestamping oracle and a censorship-resistant inclusion scheme – which we instantiate using a 2fts + 1 timestamping committee and a FOCIL-based inclusion list mechanism. Only the winning bid is settled on-chain; all other auction state lives off-chain. 3. Implementation and benchmarks. We implement the protocol’s two zero-knowledge proofs – the eligibility proof πum proving anonymous deposit membership for the timestamping committee and the auction proof πua binding a handle to a specific auction ID for the IL committee – using Groth16 [36] over BN254 with Poseidon hashing [35] in arkworks/Rust. The auction proof generates in 13 ms and verifies in under 1 ms; eligibility proofs for Merkle trees up to 232 bidders generate in 47–159 ms and verify in ∼1 ms. To the best of our knowledge, our protocol is the first to combine all four of these properties in a single design, by separating off-chain bid timestamping and inclusion enforcement from on-chain settlement. Table 2 shows the comparison with other related schemes.
2
Model and Notation
Our goal is to design a protocol that enables traditional sealed-bid auctions to be conducted on-chain while ensuring that every bid is included during the auction.
2.1
Notation
In pseudocode, the keyword function denotes a method of a smart contract, i.e., a method that is executed on-chain, while keyword offline denotes a block of code executed by users off-chain. If a require statement is not satisfied, the contract reverts without state changes. When referring to zero-knowledge proofs, we denote by ZkPrv(statement, witness) a function that returns a proof π that statement is true with respect to witness, and by ZkVrf(statement, π) a function that verifies that π is a valid proof for statement.
2.2
Network and Participants
Network Model. We assume a synchronous network where any message sent by an honest party is guaranteed to be received by all other honest parties within a known maximum delay ∆. This also means that we assume a ∆-synchronized clock for all parties, i.e., the clocks they maintain are within ∆ of each other. Synchrony is necessary for our setting: under asynchrony, an honest bid may never be delivered before the auction deadline, trivially breaking censorship resistance and rendering sealed-bid auctions impossible to implement with any meaningful timeliness guarantee. Communication model. Parts of our protocol use an anonymous broadcast channel. This channel allows any party to send a message such that (i) the message is delivered to all parties
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
within delay ∆g , and (ii) no party – including a network-level adversary – can link the message to its sender beyond the prior distribution over potential senders. Replies are routed through the same channel using a message-specific identifier (e.g., a freshly sampled tag included in the original message), without revealing the original sender’s identity. Such channels can be instantiated using mix networks [14, 25], anonymous broadcast protocols [20, 19], or Tor-based gossip overlays [26] with appropriate latency-bandwidth tradeoffs. System Participants. We call any participant in the protocol as a party. Our system consists of three main types of parties: Users (U): A set of entities that wish to participate in an auction. A user u ∈ U creates a transaction tx, which includes its contents (i.e., a bid) and a fee φ. A user uses the gossip network to interact with the timestamping replicas. To represent the value of a bid contained in the transaction tx, we use the notation val(tx) Timestamping Replicas (Pts ): A permissioned set of nts = 2fts +1 replicas, responsible for providing a timestamp for any transaction they receive. On receiving a transaction (or a blinded transaction, e.g., its hash), a timestamping replica Pts ∈ Pts signs the transaction after attaching the current local clock time. We assume an honest replica timestamps every transaction it receives, and that the adversary controls at most fts timestamping replicas. Inclusion List (IL) Proposers (Pil ): A permissioned committee of nil parties, responsible for censorship resistance. Each inclusion list proposer Pil ∈ Pil contributes to constructing the inclusion list by choosing transactions from the mempool. We assume the adversary controls at most fil of the IL Proposers. The exact value for fil depends on the inclusion-list mechanism used. In this paper, we will be using FOCIL [48], hence we assume existential honesty in the set Pil , i.e., fil = |Pil | − 1. In addition, an Auctioneer (a) registers each auction by specifying its parameters in the on-chain deposit contract (see Section 5.1). The auctioneer is not trusted for safety: any party can act as an auctioneer, and the protocol’s security properties hold regardless of the auctioneer’s behavior. The sets Pts , Pil , and U can overlap, but for simplicity we assume in our analysis that the sets are disjoint. For all of these sets, we call corrupted a party controlled by the adversary – in which case the party can behave arbitrarily – and honest otherwise.
3
Desired Properties
A secure sealed-bid auction protocol in our model must satisfy the following four core properties. We argue that each is necessary in the sense that violating any one of them enables a concrete attack that undermines the auction: dropping Hiding allows the adversary to condition its bid on observed bids, resulting in violation of the sealed-bid part of the auction; dropping Simultaneous Release allows an adversary to censor all rival bids and win at an arbitrarily low price or the [30, 34]; dropping No Free Bid Withdrawal allows a bidder to selectively abort after observing others’ bids, reintroducing adverse selection via the “free option” problem [3]; and dropping APE transforms the auction into one with entry fees, changing the equilibrium bidding strategy and reducing participation [41]. Hiding. Existing definitions of hiding in sealed-bid auctions typically guarantee only value indistinguishability [34, 52]. However, this is incomplete for latency-sensitive auctions. First,
5
6
Censorship-Resistant Sealed-Bid Auctions on Blockchains
the timing of bid creation leaks information: in an auction where prices fluctuate, knowing when a bid was generated can reveal its value even if it is cryptographically hidden [34]. Second, the existence of a bid leaks strategic information: if an adversary knows no other bids have been submitted, it can safely underbid. Third, the identity of the bidder can leak the expected bid amount based on the adversary’s prior. Thus, it is not enough to hide the value; one must also obfuscate which auction a bid belongs to and which user submitted it. We capture these three channels in a single hiding definition. Let AucSet(τ ) denote the set of auctions active at time τ , and let U denote the set of registered users. ▶ Definition 1 (th -Hiding). Let negl(·) denote a negligible function. For an auction with submission deadline tend , let th > tend denote a point in time. We define the following three games: (i) Value Indistinguishability. A outputs two transactions (tx0 , tx1 ). A challenger $
samples b ← − {0, 1} and submits txb to the protocol. At time th , A outputs a guess b′ . 1 ′ The advantage is Advind A (λ) := | Pr[b = b] − 2 |. (ii) Existential Obfuscation within AucSet(τ ). A outputs a transaction tx at time τ $
and two auction IDs AucID0 , AucID1 ∈ AucSet(τ ). A challenger samples b ← − {0, 1} ′ and submits tx for auction AucIDb . At time th , A outputs a guess b . The advantage 1 ′ is Advexist A (λ) := | Pr[b = b] − 2 |. (iii) User Obfuscation within U. A outputs a transaction tx and two user identifiers $
u0 , u1 ∈ U. A challenger samples b ← − {0, 1} and submits tx on behalf of user ub . At 1 ′ time th , A outputs a guess b′ . The advantage is Advuser A (λ) := | Pr[b = b] − 2 |. hiding ind exist user Define AdvA (λ) := max{Adv , Adv , Adv }. A protocol satisfies th -Hiding if for every PPT A: Advhiding (λ) ≤ negl(λ). A Games (ii) and (iii) are parameterized by the sets AucSet and U, which bound the adversary’s uncertainty. Larger sets yield stronger guarantees. ▶ Remark 2 (Ideal Hiding). An ideal hiding property would replace Existential Obfuscation with full Existential Indistinguishability (the adversary cannot tell whether any bid was submitted) and User Obfuscation with full User Anonymity (over all parties, not just registered users). We leave the question of whether a protocol can achieve this ideal as an open problem. Simultaneous Release. This property combines censorship resistance and post-auction exclusion. Fox et al. [30] show the importance of censorship resistance for on-chain auctions – without it, a malicious bidder can always ensure that honest bidders have lower utility than in classical auctions. Post-auction exclusion states that once the auction completes and bid values may lose privacy, no adversarial bids can be generated, preventing the adversary from inserting bids after that point. In blockchains, censorship resistance has traditionally been defined as a form of liveness: an honest user’s transaction is guaranteed to be included eventually, assuming blocks continue to be produced. For sealed-bid auctions, eventual inclusion is insufficient. Bids must be included before the auction deadline tend for the bidder to participate. Even a short delay, e.g., a malicious proposer withholding an honest bid and instead including its own lower bid just before the deadline, can prevent the honest bid from being included in the auction. While prior work has introduced short-term notions of censorship resistance, these guarantees apply only conditional on the block for that slot being produced [34]. If the adversary controls the final proposer before the auction deadline tend and knows that no subsequent block will be built, it can prevent timely honest bids from being included simply
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
by not producing the final block, while still including its own bid in the preceding block. Auctions therefore require a form of short-term censorship resistance that guarantees inclusion in the auction’s input set before tend , independent of whether a particular block is produced. We refer to this as Short-Term (ST) Censorship Resistance. In a synchronous network with zero gossip delay and perfectly synchronized clocks, ST Censorship Resistance and Post-Auction Exclusion collapse into a single hard deadline at tend . In practice, however, honest users submit bids through a gossip network, incurring a propagation delay of up to ∆g in addition to clock skew ∆, whereas an adversary can submit directly and may submit up to ∆ after the deadline. We make this asymmetry explicit by parameterizing the property by two values: δi , the lead time an honest user must allow before tend to be guaranteed inclusion, and δe , the late-arrival window in which an adversarial bid may still be admitted. ▶ Definition 3 ((δi , δe , tend )-Simultaneous Release). A sealed-bid auction protocol with deadline tend satisfies (δi , δe , tend )-Simultaneous Release if both of the following hold: δi -ST Censorship Resistance. For every auction and every honest bidder u, if u’s bid tx is sent to the protocol at least δi before tend , then tx is included in the auction’s input bid set used to determine the outcome. δe -Post-Auction Exclusion. For every auction, if an adversary’s bid tx is sent to the protocol more than δe after tend , then tx is not included in the auction’s input bid set. Setting δi = δe = 0 recovers the ideal one-shot deadline; the achievable values depend on the network. Concretely, δi must absorb the time an honest bid spends traversing the gossip overlay and obtaining its timestamp certificate, while δe must absorb the clock skew an adversary can exploit at the deadline. Our construction achieves (∆g + ∆, ∆, tend )Simultaneous Release (Theorem 7). No Free Bid Withdrawal. From the Hiding property we have that, until time th , the adversary has no information about the bids that have been submitted. After time th , the protocol may allow bids to be revealed. Of course, for the Hiding property to make sense, the protocol will not allow new bids to be created after this point, ensured by Simultaneous Release. However, this is not sufficient – if the adversary has the ability to cancel bids, i.e., to hide their existence or remove them from the protocol, then this would be effectively the same as being able to create bids after th . For example, an adversary could submit many bids and suppress all but the one that yields the most favorable outcome. Such manipulations arise broadly in commit-and-reveal schemes, where the ability to decide whether a bid becomes visible after observing partial information from others enables strategic withholding or selective abort. Hence, we require a No Free Bid Withdrawal property, complementing the Hiding property. ▶ Definition 4 (No Free Bid Withdrawal). A sealed-bid auction protocol satisfies the No Free Bid Withdrawal property if the following holds. Consider an execution of the protocol in which all users are honest after time th and the winning bid is the bid contained in transaction tx. Now consider a second execution that allows adversarial users after time th , resulting in a winning bid contained in transaction tx′ . If the bid b′ in tx′ is strictly smaller than the bid b in tx, i.e., b′ < b, then the user submitting tx must incur a cost for doing so. The intuition is that, if an execution e exists where transaction tx′ contains the winner bid b′ and b′ < b, whereas the honest execution returns b as the winner bid, then the user that submitted bid b has effectively withdrawn b in execution e. In other words, the adversary is not able to change the winner bid after time th to a lower bid b′ without incurring a cost.
7
8
Censorship-Resistant Sealed-Bid Auctions on Blockchains
Auction Participation Efficiency. We introduce a fourth property – Auction Participation Efficiency – which captures how closely an on-chain auction emulates the payoff dynamics of its classical counterparts. In traditional auctions, only the winning bidder(s) pay their bid amounts, while all other participants incur no cost for participation. In contrast, on-chain implementations require every bidder to submit a transaction containing their bid, each of which must pay an inclusion fee regardless of the auction outcome. This leads to a situation in which most parties end up with a negative utility at the end of the auction; their expected value is inflated by the cost incurred when they do not win. This changes the auction to a design with entry fee [41, 37], which changes the strategy that a bidder must take. ▶ Definition 5 (ϵ-Auction Participation Efficiency). An on-chain auction protocol satisfies Auction Participation Efficiency (APE) if there is at most ϵ cost incurred by losing bidders. In an ideal world, ϵ = 0 fully recreates the payoff structure of offline auctions. However, achieving ϵ = 0 together with Hiding and No Free Bid Withdrawal is impossible: if participating is entirely free, a bidder can submit a hidden bid, observe the outcome after reveal, and selectively withhold its commitment whenever doing so is profitable – precisely the free-option attack that No Free Bid Withdrawal is designed to prevent. Hence any protocol satisfying all four properties must impose a non-zero cost on bidders, which may be amortized across multiple auctions. Our protocol achieves this by requiring a one-time deposit that is returned upon honest participation, so that the amortized cost per auction tends to 0.
4
Background
Overview of the FOCIL Protocol. FOCIL (Fork-choice enforced Inclusion Lists) [45] has been proposed as a mechanism to improve transaction-inclusion guarantees on Ethereum by imposing constraints on Ethereum block builders. An instance of the FOCIL protocol is run for each Ethereum slot, which, according to the Ethereum consensus protocol, has a duration of 12 seconds. Each instance involves a set of IL Proposers, a set of Attesters, and a set of Validators, one of which is the block builder. An instance works as follows. A set of IL proposers is selected from the validator set. Each IL proposer monitors the public mempool and constructs an IL of Ethereum transactions. Each IL can be at most 8 KB, and proposers are free to choose their own construction policy – for example, prioritizing transactions by highest priority fee. Once built, the IL is gossiped to validators and to the block builder for the current slot. Once a validator receives an IL, it verifies certain conditions: (1) the size of the IL does not exceed the maximum allowed size, (2) the IL is for the current slot, (3) it is signed by an IL proposer of the current slot, and (4) that IL proposer has not sent a different IL for the current slot. If verified, the validator propagates the IL. The block proposer collects ILs and builds a block consisting of the transactions in all valid ILs it has received – except for transactions that do not fit in the block, which the block proposer may choose to omit. The block is propagated to the rest of the validators. A set of IL attesters is also chosen from the set of all validators. An attester receives the block for the current slot and only votes for it if it does not omit any transaction from an IL locally seen – except for transactions that do not fit in the block. A block not signed by sufficiently many attesters is not considered canonical and cannot be part of the canonical chain. Looking forward, we will use FOCIL as the second sub-protocol in our construction, but with some modifications that we introduce later.
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
Blockchain Protocol. We assume a standard single-leader proof-of-stake (PoS) blockchain with a deterministic slot schedule that supports smart contracts (e.g., Ethereum). The deterministic slot schedule means that slots occur at precise, pre-defined intervals known to all participants, allowing the network to remain synchronized. In each slot a validator acts as the leader, collects transactions, executes them, and propose a new block, while other validators attest to finalize it under the protocol’s fork-choice rule. This fork-choice incorporates validity conditions, for our construction specified in Section 5.4. This base protocol ensures consensus on both the order of transactions and the resulting on-chain state. In our construction, we only modify it to require that the inclusion of winning auction bids is enforced through a fork-choice–based mechanism, as described in Section 5.4.
5
Protocol Description
Before presenting the details, we describe the protocol as an abstraction from the point of view of the parties that interact with it, the users U and the auctioneer a. The former wish to submit a bid to an auction. Each user registers in a pre-phase by locking a deposit and generating a private commitment that will later be used to prove eligibility. The auction protocol will require a user u ∈ U to act twice, i.e., to send a message, receive responses from the protocol, and then send a second message during the bidding phase. The auctioneer is specified in the underlying PoS protocol. It registers the auction during a preparatory phase, specifying parameters such as the auction identifier, start and end times, and the item being auctioned. The auctioneer then obtains the bids from our protocol. Our protocol enables censorship-resistant sealed-bid auctions. It combines two subprotocols: a timestamping network that provides verifiable bid creation times, and a censorship-resistant inclusion mechanism based on ILs. Together, they achieve the properties presented in Section 3. At a high level, the protocol operates as follows. Pre-Phase A (Auction Registration): The auctioneer registers the auction AucID in the global deposit contract DC. During this process, the auctioneer specifies the parameters and reserves settlement capacity on-chain. This ensures unique and verifiable auctions and limits concurrent auctions to guarantee sufficient on-chain settlement capacity. Pre-Phase B (User Deposit and Membership Proof): Each user u registers by locking a deposit D in the global contract DC and committing to a private secret ρu , forming Cu = Hash(ρu ) that is stored in a public Merkle-tree registry. The deposit mechanism will be used to ensure that bidders cannot submit multiple bids and selectively reveal only the most favorable one. Each deposit will remain locked until the user, for each auction it has participated in, either reveals its bid or proves that the bid was smaller than the winning bid. This will assist in achieving the No Free Bid Withdrawal property. We remark that a user u registers only once with a fixed deposit D. The deposit remains active until the user withdraws it and enables u to participate in all auctions under the global contract DC, as long as it follows the protocol in each auction. Phase 1 (Timestamping): For every auction AucID, the user proves its eligibility to participate by deriving a pseudonymous handle hu = Hash(ρu ∥ AucID) and generating a zero-knowledge proof of membership, showing that hu corresponds (through the secret ρu ) to an active deposit. An eligible user obtains a timestamp for a commitment of its bid by interacting with the timestampers Pts . A timestamper only signs a commitment if the user provides a handle hu and a verifying proof. Collectively, Pts certify the creation time of the bid without learning its content, producing a timestamp certificate as public evidence of bid existence prior to the auction deadline. This phase will assist in achieving
9
10
Censorship-Resistant Sealed-Bid Auctions on Blockchains
the th -Hiding property, ensuring that all bids can be revealed simultaneously at release time while remaining hidden beforehand. Phase 2 (Bid Submission and Inclusion): Each user now reveals its bid by submitting it, together with the timestamp certificate, to the inclusion list proposers Pil , which ensure that all valid bids reaching the network before the auction deadline are eligible for inclusion. The protocol enforces that the winning bid is included by requiring validators to check an external validity predicate – namely, that the block contains the highest valid bid among all declared inclusion lists. In our Ethereum-based instantiation, this predicate is enforced through the fork-choice rule (see Section 5.4), but the construction generalizes to any consensus mechanism that supports such a predicate. This phase will assist in achieving the ST censorship resistance property.
5.1
Pre-Phase A: Auction Registration
Before any user deposits or bids can occur, each auctioneer must register its auction in the global on-chain deposit contract. This pre-phase ensures that all subsequent auctions are uniquely identifiable, at most nA -overlapping, i.e., our protocol supports nA parallel auctions. Each auctioneer a registers an auction in a global contract DC that maintains the registry of deposits and auction parameters. In Algorithm 1 we show the algorithm exposed by DC for this purpose. Each registered auction is identified by a unique and strictly increasing Auction ID (AucID). The protocol supports at most nA auctions ongoing at the same time. For each auction, the auctioneer specifies (AucID, item, tstart , tend ), where item denotes the asset being auctioned, and tstart < tend define the auction’s active window. We assume a proof-of-stake blockchain protocol with a deterministic slot schedule. A small fraction of blockspace in each slot is reserved for auction-settlement transactions. This reserved blockspace unconditionally includes the winning bids on chain; since only a single winning bid must be posted per auction (see Section 5.4) and at most nA auctions run in parallel, the total reserved capacity required per slot is small. If one or more preceding slots fail to produce a block, the protocol automatically increases the reserved capacity in the next available slot to ensure that all pending auction settlements can be included. Note that with Pre-Phase A, we ensure the uniqueness and public verifiability of auction results, as all participants agree on the existence and the parameters of each auction. We also ensure that the number of concurrent auctions remains limited, so that sufficient capacity exists to unconditionally enforce the inclusion of bids. This foundation enables subsequent phases to rely on consistent auction timelines and prevents equivocation by auctioneers. In practice, to prevent the auction contract from being dominated by low-value auctions, one could introduce a permissioned set of auctioneers, a reputation-based mechanism, or a dynamic registration fee for creating auctions. We discuss these design choices further in Section 9.
5.2
Pre-Phase B: Deposit
We now describe how a user u ∈ U registers for participation in our auction mechanism, in a way that will later allow u to prove eligibility to participate in an auction. The protocol is shown in Algorithm 1. Merkle-Tree-Based Registry. As shown in function deposit() of Algorithm 1, user u deposits a deposit amount D by committing to a private secret ρu , sampled uniformly from
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
11
Algorithm 1 Pre-Phases A and B: Auctioneer Setup and User Deposit Require: Auctioneer identifier a, user u Ensure: Register auctions (at most nA -overlap) and users with deposits Pre-Phase A: Auctioneer Registration On-chain functions on contract DC: 1: global ctr ← 0 2: global aucsPerSlot[i] ← 0, ∀i ∈ N 3: global auctions ← ∅▷ map, holds auction param. 4: function regAuction(a, item, tstart , tend ) 5: for t ∈ [tstart , tend ] do ▷ max nA per slot 6: require aucsPerSlot[t] < nA 7: aucsPerSlot[t] ← aucsPerSlot[t] + 1 8: AucID ← ctr 9: auctions[AucID] ← (item, tstart , tend , S) 10: ctr ← ctr + 1 11: function getAucRecord(AucID): 12: return auctions[AucID] Pre-Phase B: User Deposit Local for user u: 13: offline deposit(D)▷ Run by user with address Au 14: ρu ←r {0, 1}λ 15: Cu ← Hash(ρu ) 16: registerDeposit(Au , Cu , D)
Called by IL Proposer if |U[u]| ≥ nA (U defined in Algorithm 3): 27: function makeInactive(Au ) 28: require sender ∈ Pil ▷ IL Proposers only 29: require (Au , Cu ) in deposits 30: start nA auction timer 31: at end of nA timer: 32: insert (Au , Cu ) in inactives 33: remove (Au , Cu ) from deposits 34: function updateActivity(Au , Π) 35: require sender ∈ Pil ∨ sender = Au 36: require inactives contains (Au , Cu ) 37: call updateHistory(Π) 38: insert (Au , Cu ) in deposits 39: remove (Au , Cu ) from inactives ′
40: function slashUsr(hu , (cm, πum ), (cm′ , πum )) 41: require elgVrf(hu , cm, πum ) ′ 42: require elgVrf(hu , cm′ , πum ) 43: slashed.add(hu )
44: function slash(Au , hu , Π) 45: verify signature on Π from Au On-chain functions on contract DC: 46: if hu ∈ Π and hu ∈ slashed then 17: global deposits ▷ Merkle tree, holds user deposits 47: remove (Au , Cu ) from deposits 18: global inactives ▷ Users made inactive 48: function withdraw(Au , Π) 19: global slashed ▷ Slashed deposit handles 49: verify message signed by user 20: global minDeposit ▷ Minimum deposit 50: verify signature on Π from Au 21: function registerDeposit(Au , Cu , D) 51: updateHistory(Π) 22: require sender = Au ▷ caller is Au 52: remove (Au , Cu ) from deposits 23: require D ≥ minDeposit 53: pay minDeposit to Au 24: record (A , C , D) u
25:
u
insert (Au , Cu ) in deposits
{0, 1}λ and setting: Cu = Hash(ρu ). The contract DC records (Cu , D) in a Merkle-tree-based registry. For a slot s, an observer (user or timestamper) can determine the root of the Merkle tree roots , as well as all registered users and their commitments, (Au , Cu ). This will later serve as public reference for zeroknowledge membership proofs – users will use roots to create the proof and timestampers will use the same roots to verify the proof. Activity requirement. Each deposit must remain active by submitting either (1) a valid bid commitment, such that the bid is revealed to each timestamper in the reveal phase (winning or losing), or (2) a no-operation proof of non-participation, in every auction until withdrawn. The proofs can be submitted after the auction ends, but being inactive in more than nA auctions can trigger a makeInactive() call by an IL Proposer on-chain. Once the user becomes inactive, it must submit a proof of non-participation to regain eligibility. Failure to do so invalidates the deposit, stopping the user from withdrawing the amount. If such proof does not exist (due to misbehaviour), the bidder can never withdraw the deposit, and is effectively slashed. Withdrawal. A withdrawal can be initiated by referencing the deposit record and signing with the key associated with the address Au of user u. At that time, the deposit of u must be
12
Censorship-Resistant Sealed-Bid Auctions on Blockchains
active, according to the activity requirement conditions, and u must have revealed its bids in all auctions in which it has participated. If u has not participated in some concluded auctions (these can be at most nA , otherwise makeInactive() would have been called, stopping withdrawals), it can submit a proof of non-participation using proveNOP() (Algorithm 3) for these and for the currently ongoing nA auctions, verifying that it is not currently using its deposit. The entry for the bidder is instantly removed from the list of bidders, and u is refunded its deposit. We show this in function withdraw(). Inactivity. If u has not revealed its bids (winning or losing; see Section 5.4) for nA auctions, then any IL Proposer can call the function makeInactive() to start an nA -long auction window, after which u will be removed from the list of bidders and added to an inactive-bidders list. During this period, u can call function updateActivity() to directly submit a proof of non-participation for the auctions it did not participate in, or reveal a bid lower than the winning bid for that auction on-chain (we explain in Section 5.4 how the user generates the proof of non-participation Π using function proveNOP()). Note that during the nA -auction window, u can still get its bid timestamped, but if u is inactive when the auction ends then the bid can never be revealed as the winning bid. According to the above, users need to submit proof of non-participation or reveal bids for a certain number of past auctions, at most 3nA − 1 (nA auctions before the window starts, nA auctions during the window, and nA − 1 other auctions that might have started before the end of auctions in the nA auction window). This is re-stated in Lemma 13. Slashing users. A user can be slashed if a handle hu and two different bid commitments cm, cm′ are given as evidence to function slashUsr(), along with verifying proofs πum , πum ′ . This evidence can be provided by timestamperes (see function signCom() in Algorithm 2). However, the true identity of the user is still unknown at this point, and thus hu is marked as slashed. Whenever the user tries to use that handle (either to prove NOP or reveal its bid), slash is called on the user’s address, with requirement that one of the handles that the user sent is in the slashed set. Security Rationale. This pre-phase will later assist in achieving the following properties: 1. Duplicate Prevention and Sybil Resistance: Each bid handle hu is unique per auction and per deposit, thus the same deposit cannot be used for multiple bids. 2. Anonymity: The ZK membership proofs hide Au and ρu while proving that u has a deposit that is active for the duration. 3. No Free Bid Withdrawal: Users must either bid or explicitly issue a NOP proof each round, and no user cannot have more than 3nA − 1 auctions (from Lemma 13) for which such a proof does not exist. 4. Withdrawal Safety: The enforced waiting period ensures no pending bids remain, hence the user can safely withdraw its deposit.
5.3
Phase 1: Timestamping
Goal. Produce a public, verifiable certificate that a bid commitment existed before the auction deadline, without revealing the bid or the bidder’s identity. Inputs and outputs. A user u with address Au who registered a deposit in Algorithm 1 with secret ρu wishes to submit a bid transaction tx for auction AucID. The output of the phase is a timestamp certificate σ = {(cm, ti )σi : i ∈ Pts }, together with its median timestamp τ = median({ti : i ∈ Pts }). In this output, at most fts timestamps can be from a Byzantine timestamper, thus at least fts + 1 timestamps exist from honest timestampers. If a timestamp is not received from a timestamper, then it is considered to be ∞.
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
Zero-Knowledge proof of membership. User u must first prove that it has registered a deposit in the registry with root roots . We show this in function elgPrv() in Algorithm 2. Specifically, u creates a pseudonymous handle hu and a commitment cm to its transaction tx (which contains a bid):hu = Hash(ρu ∥ AucID), cm = Hash(tx ∥ Cu ). Observe that the handle is unique per auction and deposit, hence the user cannot submit more than one bid for each deposit made in the deposit contract, and that the commitment blinds the actual bid of the user. Furthermore, u creates a zero-knowledge proof πum with public elements (statement) roots , hu , and cm, and private elements (witness) ρu , Au , the Merkle path from roots to (Au , Cu ), AucID, and tx, attesting that hu = Hash(ρu ∥ AucID) ∧ ∃ Cu : Cu = Hash(ρu ) ∧ (Au , Cu ) ∈ merkle(roots ) ∧ cm = Hash(tx ∥ Cu ) Essentially this is a proof of membership in roots . Specifically, the proof demonstrates that: (i) the user knows a secret ρu which produces the public handle hu , (ii) the secret ρu corresponds (through the relationship Cu = Hash(ρu )) to a deposit record (Au , Cu ) in the registry with root roots , (iii) the commitment cm has been created by hashing some transaction tx and Cu , and (iv) the deposit is active. At the same time, no information about Au or ρu is revealed. Note that AucID is part of the handle, but πum does not prove anything about it – we will use this later in Section 5.4. Protocol for users to obtain timestamp certificate. The user sends the handle hu , bid commitment cm, and eligibility proof πum to the timestampers Pts through the gossip network, as shown in function submitCom(). User u waits to collect 2fts + 1 valid responses from parties in Pts , and for at most 2∆g time. After that timeout, u assumes all other parties have sent ∞ as their timestamp. When it receives 2fts + 1 responses, u runs receivedTimestamps() to create the timestamp certificate σ with median timestamp τ , thereby concluding this phase of the protocol. Protocol for timestampers. Upon receiving such request from a user, the timestampers run the function signCom() of Algorithm 2, which, if successful, signs the commitment and gossips the timestamp certificate to the user. In order to verify the proof, the timestampers locally run function elgVrf(), which contains the verification part of the proof constructed in elgPrv(). It recovers the Merkle root roots from the slot s and verifies that the proof πum is valid for the handle hu and commitment cm. Security intuition. Because at most fts replicas are faulty, the (fts +1)-st order statistic (the median) is within the interval spanned by honest clocks (Lemma 11). This bounds the median value for all users to be between the timestamps provided by two honest parties and prevents early or late skew beyond a threshold. Since the tuple contains only cm, a handle hu and is sent back a timestamp τ independent of AucID, the content and identity remain hidden pre-release, while the adversary learns that a bid was placed for one of the nA (cannot distinguish which) at clock time τ .
5.4
Phase 2: Bid-submission
Goal. Ensure that every timely bid (i.e., with τ ≤ tend ) is considered for the auction outcome and that the authenticated winner cannot be censored within the slot. The IL proposers verify these bids, enforce inactivity penalties. Only the winner is ultimately settled on-chain to achieve Auction Participation Efficiency (APE).
13
14
Censorship-Resistant Sealed-Bid Auctions on Blockchains
Algorithm 2 Phase 1: ObtainTimestamp Require: User u (with address Au and deposit secret ρu ), transaction tx, timestamping validators Pts . Ensure: Obtain certificate σ and median timestamp τ . Local for timestamper Pts,i : Local for user u: local ids ← {} ▷ Handles observed by Pts,i 1: offline elgPrv(ρu , Au , AucID, tx, s): 17: offline elgVrf(hu , cm, πum , s): 2: Cu ← Hash(ρu ); hu ← Hash(ρu ∥ AucID) 18: roots ← Merkle root for deposits at slot s 3: cm ← Hash(tx ∥ Cu ) 19: require ZkVrf((roots , hu , cm), πum ) 4: roots ← Merkle root for deposits at slot s 5: path ← path from roots to (Au , Cu ) Run by Pts,i on receiving (hu , cm, πum , s): 6: πum ← ZkPrv((roots , hu , cm), (ρu , Au , path, tx)) 20: offline signCom(cm, hu , πum , s) 7: return (hu , cm, πum ) 21: ti ← local clock time 22: require elgVrf(hu , cm, πum , s) 8: offline submitCom(tx, ρu , Au , AucID, s): ′ 9: (hu , cm, πum ) ← elgPrv(ρu , Au , AucID, tx, s) 23: if ids[hu ] = (cm′ ̸= cm, πum , s′ ) then gossip ′ m m 10: (hu , cm, πu , s) −−−−→ Pts 24: slashUsr(hu , (cm, πu , s), (cm′ , πum , s′ )) else On receiving 2fts + 1 responses or waiting for 25: ids.add(hu , cm, πum , s) 2∆g time from submitCom, and padding the 26: gossip 27: (cm, ti )σi −−−−→ u ▷ σi is the sig. of Pts,i timestamps not received with ∞: 11: offline receivedTimestamps({(cm, tj )}j∈[2fts +1] ) 12: τ ← median({t1 , . . . , t2fts +1 }) 13: σ ← {(cm, tj )σj : j ∈ [2fts + 1]}. 14: return (τ, σ).
Inputs and Outputs. The reveal phase takes as input the user’s bid transaction tx for a given auction AucID and the timestamp certificate (τ, σ) obtained during Phase 1. To make the proof for inactivity, the user inputs AucIDℓ , the last auction the user revealed for. On the IL proposer’s side, the inputs are the message (tx, AucID, (τ, σ), Π) received from the user, the local record of valid bids B, the user activity mapping U, and the global registries of active and slashed deposits (deposits, slashed). At the end of this phase, all honest IL Proposers would have a set of valid bids B, on top of which any auction logic can be run. The local winning bids are included in the Inclusion List for the reserved slot S for the auction. Overview. Before presenting the pseudocode in Algorithm 3, we provide an overview. Each user who participated in auction AucID submits its bid transaction tx together with its timestamp certificate (τ, σ) and a proof of inactivity Π. The proof of inactivity serves two purposes: (1) it demonstrates that, for all auctions between the user’s last revealed auction AucIDℓ and the current one, the user either revealed a valid bid or explicitly declared a no-operation (NOP); and (2) it enables IL proposers to detect users who attempt to hide activity or submit multiple bids, allowing timestampers to slash the associated deposits. Once received, IL proposers verify the proof, update user-activity records, and include the bid in their local set of bids B. The winning bid – according to some pre-defined auction logic – is included in their Inclusion Lists. Only those bids, whose median timestamp τ precedes the auction’s end time tend , and that are revealed to the IL Proposer before slot S, are considered. The inclusion of the winning bid in all honest ILs guarantees censorship resistance within the slot. To prove that the bid presented was generated for the particular auction ID, we require the u to create another zero-knowledge proof πua with public elements (statement) hu , AucID, Cu and private elements (witness) ρu , attesting that hu = Hash(ρu ∥AucID) ∧ Cu = Hash(ρu ) . Along with this, the user must also send a history of handles it can generate for all auctions it did not participate in. This is done through a NOP transaction, which the IL Proposer
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
gossips to the timestampers, so they can check for any repetition of handle. The IL Proposer then updates its local view of user’s activity. Algorithm 3 Phase 2: BidReveal Require: auction AucID with end time tend , transaction tx, IL Proposers Pil Ensure: IL contains bAucID = max(B) for slot S w Local for user u: local AucIDℓ ▷ Auction last revealed for At time t ≥ tend + ∆g run: 1: offline revealBid(tx, AucID, (τ, σ)) 2: Π ← proveNOP(AucID) 3: πua ← ZkPrv((hu , AucID, Cu ), ρu ) 4: for Pil ∈ Pil do DIRECT 5: (tx, AucID, (τ, σ), πua , Π) −−−−−→ Pil 6: AucIDℓ ← AucID
Local for IL Proposer Pil : local B ← {}, U ← {} ▷ B: valid bids, U: map from U to AucIDs for which user has not revealed.
On receiving (tx, AucID, (τ, σ), πua , Π) from u: 13: offline processBid(tx, AucID, (τ, σ), πua , Π) 14: require ZkVrf((hu , AucID, Cu ), πua ) 15: updateHistory(Π) 16: for (i, hiu , cmi , πum ,i , NOP) ∈ Π do 17: if hiu ∈ slashed then 18: call slash (Au , Cu ) on-chain, abort 7: offline proveNOP(AucID) 19: require Au ∈ deposits ▷ deposits at current s 8: AucIDmax ← min(AucID, AucIDℓ + 3nA − 1) 20: (·, ·, ·, tend , S) ← getAucRecord(AucID) 9: Π ← [] 21: if τ ≤ tend ∧ clock time ≤ S.time then 10: for i ∈ [AucIDℓ , AucIDmax ] do 22: require verify certificate σ i i m ,i (hu , cm , πu ) ←elgPrv(ρu , Au , i, NOP, s) 23: 11: B.insert(tx) i i m ,i 12: Π.append(i, hu , cm , πu , NOP) 24: U[u].remove(AucID) 13: return (Π)σu ▷ signed proof 25: offline updateHistory(Au , Π) 26: Verify signature on Π 27: for (i, hiu , cmi , πum ,i , NOP) ∈ Π do gossip 28: (hiu , (NOP, cmi , πum ,i )) −−−−→ Pts 29: wait for 4∆g ▷ Allow Pts, to slash 30: for (i, hiu , cmi , πum ,i , NOP) ∈ Π do 31: U[u].remove(i) Description: In slot S of AucID, each IL Proposer runs the auction logic on B and includes the winner in the local inclusion list. Users that did not reveal get AucID added to set U. The proposer for a PoS blockchain only needs to include the winning bid among all local inclusion lists. This is then verified by the attesters in the PoS chain.
FOCIL in our construction. We use a construction similar to FOCIL (Section 4) to obtain censorship resistance against a malicious auctioneer, with the following modifications. First, the protocol is equipped with a validity predicate, and a transaction can only be included in an IL if it satisfies the predicate. A transaction-certificate tuple (tx, τ, σ) is valid if it satisfies the following conditions: 1. All signatures in (σ) are valid and correspond to the same commitment (cm) and timestamp values are valid. 2. The median timestamp τ is within the valid window for the current slot; specifically, the network enforces that τ ≤ t, where t denotes the cutoff time to submit bids. 3. The bid satisfies auction rules (e.g., valid fee, bid format). If these conditions hold, an IL Proposer adds tx to its IL, otherwise tx is ignored. The timestamp certificate σ ensures that only transactions created before the cutoff t are accepted. Second, an IL in our construction does not contain all transactions received by its proposer but only the one – the winning bid. This also implies that we define no limit size for an IL, as it only contains one transaction. Finally, the rest of the parties relevant in FOCIL, i.e., validators, block builder, and attesters, are assumed to be part of underlying blockchain protocol. We assume the following fork-choice rule: If a set of rules defined by auctions logic is not followed by the proposer on all declared inclusion lists (which are singleton for each auction ID) of setbids before, then fork choice invalidates the block (i.e., the consensus rejects the block, and the next block will be created as if previous block did not arrive). Note
15
16
Censorship-Resistant Sealed-Bid Auctions on Blockchains
that we assume that if an IL Proposer declares tx1 as its local winning bid, and another IL Proposer declares tx2 , then the proposer (and attesters) must be able to identify which transaction is the correct winning bid. Protocol for users. We now present the construction in Algorithm 3. The entry point for a user is function revealBid(), which sends (tx, AucID, (τ, σ), πua , Π) to each IL Proposer. Here, πua is a proof that the AucID is the same as the one used in hu . Π contains proofs for previous auctions, which the user must submit in case it did not participate in some of them. These proofs can be generated by function proveNOP(). The proveNOP() function locally remembers the last auction AucIDℓ for which the user revealed a bid. It then generates proofs for all auction numbers i between AucIDℓ and the current auction AucID (and for at most 3nA − 1 after AucIDℓ , which represents the maximum number of auctions the user could have received a timestamp for without being considered inactive.). Each of those proofs is exactly the membership proof for auction i, as presented in Section 5.3, but for a specific transaction, denoted as NOP, indicating that user did not participate in auction i. Protocol for IL Proposers. An IL Proposer Pil handles the received (tx, AucID, (τ, σ), πua , Π) from a user as shown in function processBid(). The first step for Pil is to forward all the proofs of inactivity Π to the timestampers (who process them using the function elgVrf() of Algorithm 1 as described in the previous section). Then the IL Proposer waits for the timestampers to process the proofs, which may result in the user being slashed (if the timestampers detect that the user has submitted a different bid commitment for the same handle). If this is the case, the IL Proposer does not further process the received transaction. The next step for Pil is to verify the proof πua and the certificate σ (as described previously). If successful, Pil inserts the transaction tx into its set of valid bids B. Keeping users’ deposit active. Finally, we explain how users can make sure their deposit remains active. If a user is actively sending revealed bids to the IL Proposer, then each honest IL Proposer would have the history of handles generated by the user. This implies that the user would be active for the honest IL Proposer. A malicious IL Proposer can trigger the inactivity notice for any user; however, given the nA window in which the user’s deposit is still active, the user can send a reveal to any honest IL Proposer that can update user’s activity on-chain. The user can also prove its activity or Non Participation directly on-chain. In case the user goes offline or sparingly participates in auctions, any IL Proposer could make the user’s deposit inactive. Being inactive helps the user to not prove its entire history when it comes back online; instead it just has to prove its non-participation in 3nA − 1 auctions since it went offline. This number is derived from the fact that any user can have at most 3nA − 1 auctions that it has not revealed in before being added to inactives set (Lemma 13).
5.5
Security Analysis
▶ Definition 6 (Security assumptions). In all the following lemmas and theorems, we assume the following: The network is synchronous with a delay of at most ∆. All parties have a ∆-synchronized clock. The gossip network has a delay of at most ∆g and provides user anonymity. Static corruption with at most fts Byzantine replicas in Pts , the rest being honest. Static corruption with existential honesty in Pil
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
Implicitly assume that the majority of attesters in the Proof-of-Stake chain are honest. This assumption is only required to use FOCIL as a subroutine, and not a strict requirement. Under the above assumptions, we prove the following theorem statements in Section A. ▶ Theorem 7 ((δi , δe , tend )-Simultaneous Release). Assume an auction that spans Algorithms 1– 3, concludes at time tend , and has some pre-defined settlement slot S. The auction satisfies δi -ST Censorship Resistance with δi = ∆g + ∆ and δe -Post-Auction Exclusion with δe = ∆ (per Definition 3). ▶ Theorem 8 (th −Hiding). Assume an auction that spans Algorithms 1–3, concludes at time tend . Given th = tend + ∆ (the time at which all users can start revealing their bids), let AucSet(τ ) represent the ongoing parallel auctions at clock time τ . Let U = {Au : (Au , _) ∈ deposits} represent the honest users in deposits in the slot right before clock time τ . The auction satisfies the following items from the th -Hiding property (Definition 1): (i) Indistinguishability (ii) Existential Obfuscation within AucSet(τ ) (iii) User Obfuscation within U. ▶ Theorem 9 (No Free Bid Withdrawal). Assume an auction that spans Algorithms 1– 3, concludes at time tend , and has some pre-defined settlement slot S. If minDeposit ≥ (3nA − 1) · u, meaning that, by not revealing a commited bid, the adversary pays an amount of at least u per auction, the auction satisfies the No Free Bid Withdrawal property. ▶ Theorem 10 (Auction Participation Efficiency). Assume an auction that spans Algorithms 1– 3, concludes at time tend , and has some pre-defined settlement slot S. The cost to an honest active user if it does not win an auction tends to 0.
6
Benchmarks
In this section, we evaluate the computational cost of the two zero-knowledge proofs Table 1 Proof generation and verification times that constitute the core of our protocol: (in ms) for the auction and eligibility proofs. the eligibility proof πum from Phase 1 (Sec# Bidders Prove Verify tion 5.3) and the auction proof πua from Proof Phase 2 (Section 5.4). We implement both Auction πua — 12.9 ± 1.6 0.9 ± 0.1 proofs using the Groth16 [36] proof system 8 2 46.7 ± 3.3 0.9 ± 0.0 over the BN254 curve, as implemented in Eligibility 216 72.9 ± 3.7 0.9 ± 0.0 Rust in the arkworks library,1 and employ πum 224 103.4 ± 16.7 1.0 ± 0.1 the Poseidon hash function [35] for all hash 232 159.4 ± 43.2 1.0 ± 0.2 m computations. For the eligibility proof πu we vary the depth of the Merkle tree to support different total numbers of bidders, ranging from 28 to 232 . For each configuration we report the mean and standard deviation of the proof generation and verification times over 10 iterations with independently sampled random inputs. The benchmarks were run on a Macbook with the Apple M3 CPU and 24 GB of RAM. The repository for the proofs is github.com/OrestisAlpos/proofs-censorship-resistant-auctions. The auction proof πua is lightweight, requiring approx. only 13 ms to generate and 0.9 ms to verify. Even in the most demanding configuration, with a Merkle tree supporting over four billion bidders, the eligibility proof πum can be generated in under 160 ms and verified in 1 ms. 1
https://arkworks.rs
17
18
Censorship-Resistant Sealed-Bid Auctions on Blockchains
7
Discussions
Pure hiding vs. cryptographic hiding. A distinctive feature of our hiding construction is that it is purely information-theoretic: bid values are hidden behind a hash commitment and never encrypted under any shared or threshold key. This contrasts with thresholdencryption-based approaches (e.g., encrypted mempools [27, 17, 11]), where hiding relies on a cryptographic threshold: if the decryption committee colludes or is compromised, every submitted bid is decrypted, revealing its full content to the adversary. In our protocol, the timestamping committee is trusted only for liveness: if a majority of timestampers collude, the worst outcome is that a user’s bid does not receive a valid timestamp and thus cannot participate. The bid value itself is never at risk of exposure, since the commitment cm = Hash(tx ∥ Cu ) is information-theoretically hiding (given the randomness in Cu ) and is never opened to the timestampers. In other words, a corrupted committee degrades to a denial-of-service rather than a privacy breach – a strictly preferable failure mode for high-value auctions. This is an added advantage over works like [34] which rely on HECC in order to ensure hiding. Limitations of existing anonymous channels. We stress that the anonymous broadcast channel is an idealization; no deployed system simultaneously achieves strong sender anonymity, low latency, and a deterministic delivery bound. Tor-based overlays [26] offer reasonable anonymity but add multi-second latency and provide no worst-case delivery guarantee. Mix networks [14, 25] offer stronger anonymity but incur higher latency and are vulnerable to intersection attacks under low traffic. Protocols with provable anonymity such as Dissent [20] or Riposte [19] achieve strong guarantees but only for small groups and incur latency measured in seconds to minutes. The choice of instantiation introduces a tradeoff between hiding strength and the parameter ∆g : a lower-latency overlay reduces ∆g but weakens the User Obfuscation and Existential Obfuscation guarantees (while Indistinguishability remains unaffected, since it relies on the commitment scheme and ZK proofs). For Ethereum-based auctions with 12 s slots, a gossip delay of ∆g ∈ [1 s, 4 s] (achievable with Tor-like overlays or lightweight mix networks) leaves ample time within a slot for both phases. We view the design of anonymous gossip layers with formal latency bounds as complementary future work. Strength of obfuscation. When |AucSet| = 1 or only one user is registered for the auction, existential obfuscation is trivial – the adversary knows which auction the bid belongs to and/or who the user is. This is inherent: when only one auction is active, submitting a bid commitment reveals participation regardless of the protocol. Even then, our definition still guarantees Indistinguishability (bid value hidden) and User Obfuscation (bidder identity hidden among registered users), which together are strictly stronger than prior commitand-reveal designs. In practice, high-value blockchain auctions tend to overlap temporally, making |AucSet| ≫ 1 the common case.
8
Related Work
Auctions are a foundational economic tool, and blockchains provide a novel but adversarial environment for their implementation. We survey prior designs relevant to sealed bids, off-chain execution, and protocol-level resource allocation. Open On-Chain Auctions. Open auctions, particularly English and Dutch formats, are widely deployed on-chain due to their simplicity. English auctions [42] suffer from frontrunning
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
19
Table 2 Comparison of sealed-bid auction protocols against the four properties. ✓: achieved, ✗: not achieved, ∼: partially achieved or with caveats. Protocol
Hiding
Simul. Release
No Free Withdraw
APE
Commit-and-reveal [2] ∼ ✗ ✗ ✗ FAST [22] ∼ ✗ ✓ ✗ Riggs [49] ∼ ✗ ✓ ✗ Cryptobazaar [44] ∼ ✗ ✓ ✗ ZeroAuction [52] ∼ ✗ ✓ ✗ MCP [34] ∼a ✗b ✓ ✗ This work ✓c ✓ ✓ ✓ a Value indistinguishability via HECC, but no existential obfuscation or user obfuscation. b Single-slot only; multi-slot auctions are vulnerable to cross-slot censorship. c Existential obfuscation within AucSet; see Remark 2 for the ideal strengthening.
and sniping because bids are publicly visible, prompting mitigations such as randomized or extended closing times, e.g., Polkadot’s candle auction [6]. Dutch auctions [50] reduce interaction and settle faster; MakerDAO adopted them for liquidations [4]. Nevertheless, public bid visibility fundamentally limits ST censorship resistance, even with ordering or timing mitigations. Commit-and-Reveal Sealed-Bid Auctions. Sealed-bid auctions are harder to implement on-chain due to transparency. The standard commit-and-reveal approach hides bids during commitment and reveals them later, enabling formats such as Vickrey auctions [50]. Early deployments, including ENS auctions [2], demonstrated feasibility but also exposed drawbacks such as latency, inclusion fees for losing bidders, and reveal-phase manipulation, leading to subsequent redesigns [3, 13, 38, 39, 15]. Commit-and-reveal introduces multiple rounds, operational overhead, and incentives to delay or withhold reveals. Even with commitments, known deadlines induce bid clustering and grant proposers temporary inclusion power, enabling selective censorship or timing-based bias. Our work avoids these issues by eliminating on-chain reveals and preventing proposers from influencing bid inclusion. Cryptographic and TEE-Based Designs. Several proposals enhance sealed-bid auctions using cryptography or trusted execution. Encrypted mempools hide transaction contents until inclusion [29, 17, 11, 16, 9, 12]. FAST [22] implements sealed-bid auctions using confidential transactions and penalties, assuming underlying privacy support. Other systems rely on semi-trusted auctioneers with verifiable computation [8, 18, 24, 31, 47], trusted hardware enclaves [23], or multi-party computation [10]. Riggs [49] employs time-lock puzzles to ensure eventual revelation. Cryptobazaar [44] and ZeroAuction [52] reduce on-chain leakage via encrypted bids and delayed decryption, but still incur ST censorship risk and inclusion costs for losing bids. These designs improve privacy but typically rely on additional trust assumptions or coordination mechanisms. Our approach avoids trusted parties and records only the winning bid on-chain while mitigating ST censorship. Off-Chain Auctions. Many systems move auctions off-chain to reduce costs. NFT marketplaces such as OpenSea rely on off-chain signed bids [40], while CoW Protocol uses an off-chain orderbook with competing solvers [1]. At the infrastructure level, priority gas auctions [21] evolved into private off-chain auctions via Flashbots [7], and later into Proposer-Builder Separation (PBS) implemented through MEV-Boost [5], effectively treating blockspace as a recurring first-price auction. While off-chain auctions scale efficiently, they depend on intermediaries that can censor or delay bids. Our design removes this reliance while retaining auction efficiency. Protocol-Level Censorship Resistance. Protocol mechanisms such as FOCIL [48, 45]
20
Censorship-Resistant Sealed-Bid Auctions on Blockchains
introduce committee-based inclusion lists to raise censorship costs but rely on existential honesty and remain vulnerable to block-filling. AUCIL [51] strengthens these guarantees in a rational model using auctions over inclusion lists, but still grants proposers a latency advantage. Multiple Concurrent Proposers (MCP) [34] provide stronger ST censorship resistance via architectural changes, at the cost of higher complexity and deployability constraints. Our work occupies a middle ground, offering auction-level ST censorship resistance without modifying the underlying consensus protocol. Rational Auction Protocols. A related line of work studies sealed-bid auctions under rational adversaries. Ganesh et al. [33, 32] design cryptographic protocols for first-price and Vickrey auctions that ensure incentive compatibility via punishments and commitments. These works focus on strategic correctness among rational bidders, but do not address blockchain-specific challenges such as ST censorship or timing leakage. In contrast, our construction targets permissionless deployment and directly mitigates inclusion-time censorship and bid-existence leakage using timestamp certificates and inclusion lists, while minimizing losing-bidder fees through our APE objective.
9
Conclusion and Future Work
Our protocol fits into a broader effort to make sealed-bid auctions practical on blockchains. Conventional sealed-bid designs do not address ST censorship: because the block proposer has monopoly control for the duration of its slot, a malicious proposer can suppress timely honest bids or exploit its latency advantage to react strategically to information that other bidders were not able to observe. More recent approaches remove the proposer monopoly by employing multiple concurrent proposers, but doing so demands substantial modifications to consensus, introduces considerable protocol complexity, and imposes significant on-chain load. Our work takes a different direction. We describe a lightweight, consensus-adjacent mechanism that achieves the strengthened properties required for high-value, time-sensitive auctions. In particular, our protocol provides (i) (∆g + ∆, ∆, tend )-simultaneous release, (ii) th -hiding, (iii) no free bid withdrawal, and (iv) auction participation efficiency. Importantly, because most of the mechanism operates off-chain, it places minimal demand on blockspace, though this necessitates a more involved deposit mechanism and eligibility proofs. Future Work. First, a key direction for future work is designing incentive mechanisms for timestampers. Our protocol currently relies on an honest majority among timestampers to produce correct and timely certificates; replacing this assumption with explicit economic incentives would provide stronger robustness and make the timestamping layer secure even under strategic behavior. A related question exists for IL proposers, though it is less pressing in our setting – since we require only existential honesty – and prior work has already made progress on incentivizing IL proposers [51]. Second, our protocol does not yet include a Sybil-resistance mechanism for auctioneers to prevent malicious parties from spamming many low-value auctions. This could be addressed through a reservation fee mechanism for slot reservations, which would also allow auctioneers to explicitly reserve capacity only for the slots in which their auctions run. More generally, fee or deposit-based eligibility rules, or the simpler option of treating auctioneers as a permissioned set, remain important directions for future work. Finally, a full economic analysis remains open. This includes determining appropriate penalties for non-reveals, incentives for block proposers to include auction-settlement transactions, and – if timestampers are made rational rather than honest – the corresponding
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
incentive structure for correct and timely timestamping. References 1 2 3
4 5 6
7 8
9
10
11
12
13
14 15
16
17
18
CoW Protocol Solver Auctions. https://docs.cow.fi/. Accessed: 2025-11-01. ENS: A beginner’s guide to buying an ENS domain. https://weka.medium.com/a-beginne rs-guide-to-buying-an-ens-domain-3ccac2bdc770. Accessed: 2025-11-01. ENS: Refund of unrevealed bids. https://support.ens.domains/en/articles/9739338-r eclaim-app-reclaim-ens-domains-claim-deposits-from-2017-ens-auctions. Accessed: 2025-11-01. MakerDAO Liquidations 2.0. https://docs.makerdao.com/smart-contract-modules/dog -and-clipper-detailed-documentation. Accessed: 2025-11-01. MEV-Boost Architecture Overview. https://boost.flashbots.net/. Accessed: 2025-11-01. Polkadot parachain slot auctions explained. https://support.polkadot.network/support /solutions/articles/65000182287-how-do-parachain-slot-auctions-work-. Accessed: 2025-11-01. Flashbots: Frontrunning the MEV Crisis. https://writings.flashbots.net/frontrunnin g-mev-crisis, 2021. Accessed: 2025-11-07. Hussein Abulkasim, Atefeh Mashatan, and Shohini Ghose. Quantum-based privacy-preserving sealed-bid auction on the blockchain. Optik, 242:167039, 2021. URL: https://www.sciencedir ect.com/science/article/pii/S0030402621007233, doi:10.1016/j.ijleo.2021.167039. Amit Agarwal, Rex Fernando, and Benny Pinkas. Efficiently-thresholdizable batched identitybased encryption, with applications. In Advances in Cryptology – CRYPTO 2025, Lecture Notes in Computer Science. Springer, 2025. doi:10.1007/978-3-032-01881-6_3. Erik-Oliver Blass and Florian Kerschbaum. Strain: A secure auction for blockchains. In Computer Security – ESORICS 2018, pages 87–110. Springer, 2018. URL: https://eprint.i acr.org/2017/1044, doi:10.1007/978-3-319-99073-6_5. Dan Boneh, Evan Laufer, and Ertem Nusret Tas. Batch decryption without epochs and its application to encrypted mempools. Cryptology ePrint Archive, Paper 2025/1254, 2024. URL: https://eprint.iacr.org/2025/1254. Jan Bormet, Sebastian Faust, Hussien Othman, and Ziyan Qu. BEAT-MEV: Epochless approach to batched threshold encryption for MEV prevention. In 34th USENIX Security Symposium (USENIX Security 25), 2025. URL: https://www.usenix.org/conference/usen ixsecurity25/presentation/bormet. Chiara Braghin, Stelvio Cimato, Ernesto Damiani, and Michael Baronchelli. Designing smartcontract based auctions. In Security with Intelligent Computing and Big-data Services, pages 180–191. Springer, 2018. doi:10.1007/978-3-030-16946-6_5. David L Chaum. Untraceable electronic mail, return addresses, and digital pseudonyms. Communications of the ACM, 24(2):84–90, 1981. Biwen Chen, Xue Li, Tao Xiang, and Peng Wang. SBRAC: Blockchain-based sealed-bid auction with bidding price privacy and public verifiability. Journal of Information Security and Applications, 68:103235, 2022. doi:10.1016/j.jisa.2021.103082. Arka Rai Choudhuri, Sanjam Garg, Julien Piet, and Guru-Vamsi Policharla. Mempool privacy via batched threshold encryption: Attacks and defenses. In 33rd USENIX Security Symposium (USENIX Security 24), pages 3513–3529, 2024. URL: https://www.usenix.org/conference/ usenixsecurity24/presentation/choudhuri. Arka Rai Choudhuri, Sanjam Garg, Guru Vamsi Policharla, and Mingyuan Wang. Practical mempool privacy via one-time setup batched threshold encryption. In 34th USENIX Security Symposium (USENIX Security 25), 2025. URL: https://www.usenix.org/system/files/co nference/usenixsecurity25/sec25cycle1-prepub-1216-choudhuri.pdf. Theodoros Constantinides and John Cartlidge. Block auction: A general blockchain protocol for privacy-preserving and verifiable periodic double auctions. In 2021 IEEE International
21
22
Censorship-Resistant Sealed-Bid Auctions on Blockchains
Conference on Blockchain (Blockchain), pages 513–520, 2021. doi:10.1109/Blockchain5384 5.2021.00078. 19
Henry Corrigan-Gibbs, Dan Boneh, and David Mazières. Riposte: An anonymous messaging system handling millions of users. In 2015 IEEE Symposium on Security and Privacy, pages 321–338. IEEE, 2015.
20
Henry Corrigan-Gibbs and Bryan Ford. Dissent: accountable anonymous group messaging. In Proceedings of the 17th ACM conference on Computer and communications security, pages 340–350, 2010.
21
Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE symposium on security and privacy (SP), pages 910–927. IEEE, 2020.
22
Bernardo David, Lorenzo Gentile, and Mohsen Pourpouneh. FAST: Fair Auctions via Secret Transactions. In Applied Cryptography and Network Security, pages 727–747. Springer, 2022. doi:10.1007/978-3-031-09234-3_36.
23
Harsh Desai and Murat Kantarcioglu. Secauctee: Securing auction smart contracts using trusted execution environments. In 2021 IEEE International Conference on Blockchain (Blockchain), pages 448–455, 2021. doi:10.1109/Blockchain53845.2021.00069.
24
Harsh Desai, Murat Kantarcioglu, and Lalana Kagal. A hybrid blockchain architecture for privacy-enabled and accountable auctions. In 2019 IEEE International Conference on Blockchain (Blockchain), pages 34–43. IEEE, 2019. doi:10.1109/Blockchain.2019.00014.
25
Claudia Diaz, Harry Halpin, and Aggelos Kiayias. The nym network. 2021.
26
Roger Dingledine, Nick Mathewson, and Paul Syverson. Tor: The second-generation onion router. 2004.
27
Stefan Dziembowski, Sebastian Faust, and Jannik Luhn. Shutter network: Private transactions from threshold cryptography. Cryptology ePrint Archive, Paper 2024/1981, 2024. URL: https://eprint.iacr.org/2024/1981.
28
Giulia Fanti, Shaileshh Bojja Venkatakrishnan, Surya Bakshi, Bradley Denby, Shruti Bhargava, Andrew Miller, and Pramod Viswanath. Dandelion++ lightweight cryptocurrency networking with formal anonymity guarantees. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(2):1–35, 2018.
29
Rex Fernando, Guru-Vamsi Policharla, Andrei Tonkikh, and Zhuolun Xiang. TrX: Encrypted Mempools in High Performance BFT Protocols. Cryptology ePrint Archive, Paper 2025/077, 2025. URL: https://eprint.iacr.org/2025/2032.
30
Elijah Fox, Mallesh Pai, and Max Resnick. Censorship resistance in on-chain auctions. In 5th Conference on Advances in Financial Technologies (AFT), LIPIcs, pages 19:1–19:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.
31
Hisham S. Galal and Amr M. Youssef. Verifiable sealed-bid auction on the ethereum blockchain. In Financial Cryptography and Data Security: FC 2018 International Workshops, BITCOIN, VOTING, and WTSC, Nieuwpoort, Curaçao, March 2, 2018, Revised Selected Papers, page 265–278, Berlin, Heidelberg, 2018. Springer-Verlag. doi:10.1007/978-3-662-58820-8_18.
32
Chaya Ganesh, Shreyas Gupta, Bhavana Kanukurthi, and Girisha Shankar. Secure vickrey auctions with rational parties. In Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security, pages 4062–4076, 2024. doi:10.1145/3658644.3670 311.
33
Chaya Ganesh, Bhavana Kanukurthi, and Girisha Shankar. Secure auctions in the presence of rational adversaries. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1173–1186, 2022. doi:10.1145/3548606.3560706.
34
Pranav Garimidi, Joachim Neu, and Max Resnick. Multiple concurrent proposers: Why and how, 2025. URL: https://arxiv.org/abs/2509.23984, arXiv:2509.23984.
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
35
36 37 38
39
40
41
42
43 44
45 46 47
48
49
50 51
52
Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon: A new hash function for zero-knowledge proof systems. In USENIX Security Symposium, pages 519–535. USENIX Association, 2021. Jens Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT (2), volume 9666 of Lecture Notes in Computer Science, pages 305–326. Springer, 2016. Vijay Krishna. Auction theory. Academic press, 2009. Michal Król, Alberto Sonnino, Argyrios G. Tasiopoulos, Ioannis Psaras, and Etienne Rivière. PASTRAMI: privacy-preserving, auditable, scalable & trustworthy auctions for multiple items. In Proceedings of the 21st International Middleware Conference (Middleware), pages 296–310. ACM, 2020. doi:10.1145/3423211.3425669. Genhua Lu, Yi Zhang, Zhongxiang Lu, Jun Shao, and Guiyi Wei. Blockchain-based sealed-bid domain name auction protocol. In Bo Chen and Xinyi Huang, editors, Applied Cryptography in Computer and Communications, pages 25–38, Cham, 2021. Springer International Publishing. Lunaray. How nfts are traded on opensea and how hackers can transfer your nfts. https: //medium.com/coinmonks/how-nfts-are-traded-on-opensea-and-how-hackers-can-tra nsfer-your-nfts-c491455087, 2022. Accessed: 2025-11-07. R.Preston McAfee and John McMillan. Auctions with entry. Economics Letters, 23(4):343–347, 1987. URL: https://www.sciencedirect.com/science/article/pii/016517658790142X, doi:10.1016/0165-1765(87)90142-X. Paul R. Milgrom and Robert J. Weber. A theory of auctions and competitive bidding. Econometrica, 50(5):1089–1122, 1982. URL: https://cramton.umd.edu/market-design-pap ers/milgrom-weber-a-theory-of-auctions-and-competitive-bidding.pdf. Roger B Myerson. Optimal auction design. Mathematics of operations research, 6(1):58–73, 1981. Andrija Novakovic, Alireza Kavousi, Kobi Gurkan, and Philipp Jovanovic. Cryptobazaar: Private sealed-bid auctions at scale. In 31st Annual Network and Distributed System Security Symposium (NDSS). The Internet Society, 2026. Ethereum Improvement Proposals. Eip-7805: Fork-choice enforced inclusion lists (focil) [draft], November 2024. URL: https://eips.ethereum.org/EIPS/eip-7805. John G Riley and William F Samuelson. Optimal auctions. The American Economic Review, 71(3):381–392, 1981. Gaurav Sharma, Denis Verstraeten, Vishal Saraswat, Jean-Michel Dricot, and Olivier Markowitch. Anonymous sealed-bid auction on ethereum. Electronics, 10(19):2340, 2021. doi:10.3390/electronics10192340. Thomas Thiery, Barnabé Monnot, Francesco D’Amato, and Julian Ma. Fork-Choice-Enforced Inclusion Lists (FOCIL): A Simple Committee-Based Inclusion List Proposal. https://ethr esear.ch/t/fork-choice-enforced-inclusion-lists-focil-a-simple-committee-based -inclusion-list-proposal/19870, 2024. Ethereum Research. Nirvan Tyagi, Arasu Arun, Cody Freitag, Riad S. Wahby, Joseph Bonneau, and David Mazières. Riggs: Decentralized sealed-bid auctions. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security (CCS), pages 1227–1241. ACM, 2023. doi:10.1145/3576915.3623118. William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of Finance, 16(1):8–37, 1961. URL: https://www.jstor.org/stable/2977633. Sarisht Wadhwa, Julian Ma, Thomas Thiery, Barnabe Monnot, Luca Zanolini, Fan Zhang, and Kartik Nayak. AUCIL: An Inclusion List Design for Rational Parties. Cryptology ePrint Archive, Paper 2025/194, 2025. URL: https://eprint.iacr.org/2025/194. Haoqian Zhang, Michelle Yeo, Vero Estrada-Galiñanes, and Bryan Ford. Zeroauction: Zerodeposit sealed-bid auction via delayed execution. In Financial Cryptography and Data Security. FC 2024 International Workshops, pages 170–188. Springer, 2024. doi:10.1007/978-3-031 -69231-4_12.
23
24
Censorship-Resistant Sealed-Bid Auctions on Blockchains
A
Security Analysis
A.1
Intermediate results
We first prove some intermediate results, which we then use to prove the main theorems for our construction. ▶ Lemma 11 (Median robustness of timestamp certificate). Let Pts be a committee of timestampers with at most fts corrupted, where |Pts | = 2fts + 1. Let T = {τi : i ∈ Pts } be the set of timestamps that the user collects on the commitment cm, where at most fts timestamps of T may be adversarially chosen. Given ∆g as the maximum delay of the gossip network and ∆-synchronized clocks, and assuming that the user treats any missing stamps at timeout as ∞. Let τ be the median of T , and Thon represents the subset received from honest parties. Then: 1. Honest span. min(Thon ) ≤ τ ≤ max(Thon ), In particular, the adversary cannot move the median outside the honest span. 2. User drift bound. If tu represents the time at which user sends its transaction max(Thon ) − tu ≤ ∆g + ∆, min(Thon ) − tu ≥ −∆, 3. Drift bound. max(Thon ) − min(Thon ) ≤ 2∆ + ∆g , hence τ deviates from any honest stamp by at most 2∆ + ∆g . Proof. Honest span. We prove this statement by Pigeon Hole Principle. There exist fts values before and after the median timestamp. Since we have fts + 1 honest timestamps, either the median timestamp is honest, or at least one of the timestamps before or after the median is filled with an honest timestamp. Thus min(Thon ) ≤ τ and max(Thon ) ≥ τ . ◀ User drift bound. If the user sends the transaction at their local clocktime tu , then from the perspective of an honest timestamper (Pts,i ), the sending time of the transaction (accounting for the clock drift) must be ts,i tu − ∆ ≤ tP ≤ tu + ∆. u
The time it receives the transaction and assigns it a timestamp is thus ts,i tu − ∆ ≤ τi = (tP + ∆g ) ≤ tu + ∆ + ∆g . u
Thus, for all honest Pts,i , the assigned timestamp is given by the previous equation. In other words, max(Thon ) ≤ tu + ∆ + ∆g
(1)
and min(Thon ) ≥ tu − ∆
(2)
which proves the statement.
◀
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
25
Drift bound. Subtracting Equations (1) and (2), we get max(Thon ) − min(Thon ) ≤ 2∆ + ∆g ◀ ▶ Lemma 12 (Completeness of membership proofs). An honest user can always create a statement (roots , hu , cm) and verifying membership proof πum for any auction AucID. Proof. An honest user u registers by choosing ρu and computing Cu , which then gets added in the deposits variable of DC (see registerDeposit() in Algorithm 1). The deposit (Au , Cu ) can only be removed from deposits through function makeInactive(), slash() or withdraw() (see Algorithm 1). For an honest u, no honest IL Proposer will call makeInactive(Au ), because u reveals its bid commitments or participates in all auctions using a NOP bid. A malicious IL Proposer can call makeInactive(Au ) against honest u, however, this gives the honest user (or any other honest IL Proposer) a nA window in which it can use updateActivity() to avoid becoming inactive. Moreover, slash() or withdraw() can only be called if either the user uses a hu twice or withdraws its own funds, which the honest does not do. Hence, deposits (Au , Cu ) of honest u will remain in the deposits. This means that u can create the path variable from roots (the root of the merkle tree that contains all deposits in deposits) to (Au , Cu ) for some slot s (see elgPrv() in Algorithm 2). Moreover, u can create the handle hu = Hash(ρu ∥ AucID) for any auction AucID and commitment cm = Hash(tx ∥ Cu ) for its transaction tx. Hence, u can compute a valid witness (ρu , Au , path, tx) for the statement (roots , hu , cm) and, from the completeness property of the zero-knowledge proof system, a verifying membership proof πum for any auction AucID. ◀ ▶ Lemma 13 (Max Inactivity). A user can get a timestamp certificate for at most nc = 3nA −1 auctions without revealing the corresponding bids. Proof. Let a user’s last revealed auction id be AucIDℓ . If the user does not participate for nA auctions, at least honest IL Proposer will call makeOffline(). This starts a nA -auction countdown, for which the user remains active (and thus can get timestamp certificates). When the last of these auctions is about to end, there can be at most nA − 1 more auctions started and still be running. A valid certificate can be generated for all of these 3nA − 1 auctions; however, as soon as the last auction ends, the user’s deposit becomes inactive and no other hu can be generated with a valid πum . ◀ ▶ Lemma 14 (Uniqueness of handle per deposit). For each deposit (as indicated by Cu ) and auction AucID, the user can create at most one handle hu , such that πum is a verifying membership proof for the statement (roots , hu , cm). Proof. Assuming that Hash() is a collision-resistant hash function, a user u cannot come up with ρ′u ̸= ρu , such that Hash(ρ′u ) = Cu′ and Cu′ = Cu . Hence, u would have to use ρ′ to create a valid membership proof πum for a statement (roots , h′u , cm′ ), where h′u = Hash(ρ′u ∥ AucID) and cm′ = Hash(tx′ ∥ Cu′ ), for an entry (Au , Cu′ ) that does not exist in the merkle tree roots . This is impossible, except with negligible probability, because it would contradict the collision resistance of Hash(), used to implement the Merkle tree. ◀
26
Censorship-Resistant Sealed-Bid Auctions on Blockchains
A.2
Proofs for the Entire Construction
▶ Theorem 7 ((δi , δe , tend )-Simultaneous Release). Assume an auction that spans Algorithms 1– 3, concludes at time tend , and has some pre-defined settlement slot S. The auction satisfies δi -ST Censorship Resistance with δi = ∆g + ∆ and δe -Post-Auction Exclusion with δe = ∆ (per Definition 3). Proof. (Censorship Resistance) For every honest user u ∈ U, let tx be a bid transaction created by u for auction AucID and sent to timestampers before clock time tend − δi (i.e., tu ≤ tend − (∆g + ∆)). From Lemma 12, the honest user can always create such a bid. By Lemma 11, User Drift Bound, we know that max(Thon ) ≤ tu + ∆ + ∆g . Also from Lemma 11, Honest Span, we get that τ ≤ max(Thon ) ≤ tu + ∆ + ∆g ≤ tend , i.e., the median timestamp obtained has value at most tend . Thus, if such a bid transaction with timestamp is sent to Pil , it is still considered valid. Then, tx is included in the input bid set of auction AucID used by all honest IL Proposers when computing the auction outcome. (Post Auction Exclusion) From Lemma 11, if a transaction is generated by an adversary at time tu , then the minimum timestamp it can receive is τ ≥ min(Thon ) ≥ tu − ∆ If the bid is valid, i.e., τ ≤ tend then tu ≤ tend + ∆. Thus, no adversarial bids sent after ∆ of auction end tend is valid, satisfying post-auction exclusion. ◀ ▶ Theorem 8 (th −Hiding). Assume an auction that spans Algorithms 1–3, concludes at time tend . Given th = tend + ∆ (the time at which all users can start revealing their bids), let AucSet(τ ) represent the ongoing parallel auctions at clock time τ . Let U = {Au : (Au , _) ∈ deposits} represent the honest users in deposits in the slot right before clock time τ . The auction satisfies the following items from the th -Hiding property (Definition 1): (i) Indistinguishability (ii) Existential Obfuscation within AucSet(τ ) (iii) User Obfuscation within U. Proof. Indistinguishability. Let us consider, towards a contradiction, that an auction protocol violates indistinguishability. We will show that using this auction’s adversary as a subroutine, we can design an adversary that has an advantage in the decision game for the pre-image of a hash function or learning witness of a zero knowledge proof. Concretely, A outputs two transactions (tx0 , tx1 ) and is given a challenge commitment cmb = Hash(txb ∥ Cu ) together with a ZK membership proof created as πum ,b ← ZkPrv((roots , hu , cmb ), (ρu , Au , path, txb )), where b ← {0, 1} is drawn uniformly at random. Before time th , all information available to A consists of: the handle hu = Hash(ρu ∥ AucID), the commitment cmb , the proof πum ,b , and the timestamp certificate (τ, σ),
O. Alpos, L. Heimbach, K. Nayak, and S. Wadhwa
none of which reveals txb directly. i) Since hu is independent of txb , there is no advantage that the adversary gains from this information. By hash function’s pre-image resistance, ρu and AucID remain hidden with no advantage more than random guessing. ii) the timestamp certificate (τ, σ) contains only timestamps and signatures. Again no information about txb is available here. By assumption, the adversary outputs a guess b′ such that Pr[b′ = b] − 21 ≥ ϵ(λ) for some non-neglibile function ϵ. Now, for the commitment cmb = Hash(txb ∥ Cu ), consider an adversary A1 (A), such that, when A outputs two messages (tx0 , tx1 ), the adversary A1 outputs (m0 = (tx0 ∥ Cu ), m1 = (tx1 ∥ Cu )). The challenger to the pre-image resistance function returns Hash(mb ) and this value is passed to A. When A outputs b, A1 outputs the same b. Since A1 must not have any advantage (by definition of Hash() being pre-image resistant), A can also not obtain any advantage through the commitment cmb . Lastly, for the proof πum ,b , consider an adversary A2 (A). When A outputs two messages (tx0 , tx1 ), adversary A2 chooses a random b ← {0, 1} and constructs the corresponding commitment cmb = Hash(txb ∥ Cu ). It then submits the ZK statement (roots , hu , cmb ) to its ZK challenger, receiving either a real or simulated proof π ∗ depending on the hidden bit β. A2 now continues the protocol with πum ,b = π ∗ and sends to A the tuple (hu , cmb , πum ,b , (τ, σ)). Adversary A outputs b′ . If b = b′ , A2 outputs β = simulated. Otherwise, output β = real. However, since A2 must have no advantage in the zero-knowledge game, A cannot have an advantage in the indistinguishability game. ◀ Existential Obfuscation within AucSet(τ ). Let us consider, towards a contradiction, that this advantage is not neglible. Before time th , all information available to A consists of: the handle hbu = Hash(ρu ∥ AucIDb ), the commitment cm = Hash(tx ∥ Cu ), the proof πum ,b , and the timestamp certificate (τ, σ), The proof follows the same arguments as indistinguishability. Only information hbu = Hash(ρu ∥ AucIDb ) and the proof πum ,b are dependent on the auction ID. The timestampingcertificate time τ only reveals that AucIDb ∈ AucSet(τ ) and thus the adversary A can be used to build adversaries that have an advantage in learning a pre-image of a hash function or learning witness of a zero knowledge proof. ◀ User obfuscation within U. Before time th , all information available to A consists of: the handle hbu = Hash(ρb ∥ AucID), the commitment cmb = Hash(tx ∥ Cb ), the proof πum ,b , and the timestamp certificate (τ, σ),
27
28
Censorship-Resistant Sealed-Bid Auctions on Blockchains
Here, the timestamp certificate (τ, σ) reveals only that whoever submitted the transaction is in U. The other three elements are all similar to previous proofs: if advantage is obtained from either the handle hbu or cmb , then we can make an adversary with an advantage in pre-image of a hash function, and if the advantage is obtained from proof πum ,b , then we can make an adversary with an advantage in learning witness of a zero knowledge proof. ◀ ▶ Theorem 10 (Auction Participation Efficiency). Assume an auction that spans Algorithms 1– 3, concludes at time tend , and has some pre-defined settlement slot S. The cost to an honest active user if it does not win an auction tends to 0. Informal Proof. If the user is active and honest, then after depositing, the user never needs to make an on-chain call. This can be done by revealing its bids for auctions it participates in, and by submitting a proof of non-participation immediately if it does not. Even if a malicious IL Proposer calls makeInactive(), an honest IL proposer with its history will always call updateActivity() before the user is ever made inactive. Thus, the only time the user pays a fee is when it registers its deposit, and thus the amortized cost over many auctions that the user participates but does not win in, will tend to 0. ◀ ▶ Theorem 9 (No Free Bid Withdrawal). Assume an auction that spans Algorithms 1– 3, concludes at time tend , and has some pre-defined settlement slot S. If minDeposit ≥ (3nA − 1) · u, meaning that, by not revealing a commited bid, the adversary pays an amount of at least u per auction, the auction satisfies the No Free Bid Withdrawal property. Proof. Consider that a bidder decides not to reveal a bid tx after receiving a timestamp certificate for some auction id AucID. The handle for this auction is unique, as proved in Lemma 14, and was used to get the timestamp for tx. Thus, creating a proof of nonparticipation for hu would double-use hu , causing slash() to be called on-chain. Thus, this would imply that the user can never generate a proof of non-participation for such an AucID. Thus, it can never withdraw its deposit from the contract loosing its deposit. However, the bidder can do so for at most nc = 3nA − 1 auctions (from Lemma 13) and thus the amortized cost for not revealing any valid winning bid is at least minDeposit , which is nc at least u, per the theorem statement. ◀