Sealed-bid auctions that run entirely off-chain when everyone is honest — and cost only $O(k)$ on-chain when $k$ bidders misbehave, instead of $O(n)$.
1Visa Research · 2IMDEA Software Institute · 3Georgia Institute of Technology · 4MIT
In three numbers
Blockchain auctions today are not small because demand is small. They are small because every extra bidder costs gas. We move the auction off-chain and put only the misbehaviour back on it.
Deploy, start, submit sealed bids, reveal winner — independent of the number of bidders. Bidders themselves send zero on-chain transactions.
The state-of-the-art comparison point, Riggs-TC, exhausts the block gas limit at roughly 20.
Only the channels of the $k$ bidders who deviate ever touch the chain.
The problem
A sealed-bid auction needs every bidder to commit, then open, then be compared against every other bid. Done on-chain, each of those steps is a transaction, so the total cost is $O(n)$ in the number of bidders $n$ — and a single Ethereum block only holds about 30 million gas.
Worse: existing off-chain constructions (state channels, rollups) fall back to $O(n)$ on-chain work as soon as one participant stops cooperating, because the dispute path drags every participant's state on-chain. Our design isolates the dispute to the misbehaving party's own channel.
The construction combines three pieces: programmable payment channels between a hub (the auctioneer) and each participant, Merkle commitments that bind the set of sealed bids, and a zkSNARK that lets the hub prove the winner is correct without revealing any losing bid. The hub is treated as fully malicious: it cannot steal funds, censor a bid, or abort without being financially punished.
Interactive · Figure 10 of the paper
Pick a bidder count. Bars are log-scale — each gridline is a factor of ten. The dashed rule is the Ethereum block gas limit; anything above it cannot fit in a single block.
Measured points only — the selector offers the four bidder counts that were actually benchmarked (128, 256, 512, 1024); nothing here is extrapolated. Our protocol's cost is flat because the zkSNARK verification and the Merkle root posting do not grow with $n$. Riggs-RP and Riggs-TC are plotted per the paper's extrapolation of their reported per-bidder gas (3,010,000 and 3,310,000 respectively), which is why both already exceed a single block at 128 bidders; the paper's protocol comparison separately reports Riggs-TC becoming infeasible at around 20 bidders.
Interactive · Figure 11 of the paper
Fix the auction at 1,024 bidders and let $k$ of them deviate — refuse to open their sealed bid, or get censored by a malicious hub. Each one forces exactly one on-chain covenant registration. Drag to see where the linear $O(k)$ climb finally meets a protocol that pays $O(n)$ up front.
All 1,024 bids settled off-chain.
cheaper at the current number of deviators.
Riggs-TC only wins once 78% of all bidders misbehave.
Data provenance. Base cost $2{,}441{,}430$ gas is the sum of the five optimistic on-chain operations in Table IV. Each deviator adds $3{,}029{,}708$ gas (registering the hub–bidder covenant) plus a $50{,}000$ gas hashing estimate, exactly as in the paper's malicious-bidder figure. The Riggs-TC reference line here is $2{,}410{,}000$ gas per bidder, the per-bidder figure used in that same figure; the six-protocol chart above uses the paper's other Riggs-TC accounting, $3{,}310{,}000$ gas per bidder. Each chart reproduces its own source figure rather than silently reconciling the two.
Background
The $O(k)$ result is not a cryptographic trick. It falls out of which off-chain primitive the auction is built on. Four layers, each one adding something the layer below could not express — click any of them.
Every layer but the last adds expressiveness. The last one adds isolation: because a dispute is confined to the channel it happened in, the blast radius of misbehaviour is one bidder rather than the whole auction. That is where $O(k)$ instead of $O(n)$ comes from.
| Auction protocol | All honest | k bidders deviate | Malicious auctioneer | Privacy |
|---|---|---|---|---|
| On-chain auction | $O(n)$ | $O(n)$ | — | No |
| State channels | $O(1)$ | $O(n)$ | — | No |
| Auction on a (zk)-rollup | $O(n)$ | $O(n)$ | — | No |
| This work | $O(1)$ | $O(k)$ | $O(n)$ | Yes |
Table I of the paper. A malicious auctioneer can force $O(n)$ on-chain work, but only by answering an on-chain challenge from each of the $n$ bidders itself — the asymmetry is what makes it irrational.
Interactive
The hub holds one programmable payment channel with each bidder. Click any bidder to make it misbehave. Honest channels stay off-chain no matter how many there are; a deviating channel resolves on-chain, on its own, without dragging the others down with it. That is the whole of $O(k)$.
Shown with 16 bidders for legibility; the argument does not depend on $n$. The four fixed hub calls are deploying the auction contract, starting the auction, submitting the sealed-bid root, and revealing the winner; the gas figure additionally includes the seller's one-off NFT approval (49,233 gas).
Interactive
Five stages. Choose a scenario, then step through. Note where the dispute activity actually sits: challenges fire during Opening, and Rebuttal is the buffer that answers them — it is not a separate dispute phase.
Interactive
Your bid is sealed into a commitment, the commitments form a Merkle tree, and the hub posts only the root on-chain. The hub hands you back an inclusion proof — a short list of sibling hashes. If the hub later pretends you never bid, that proof is what the contract checks, and the hub loses its collateral.
Click any leaf to follow its path to the root.
Commitment —
The animation uses a deliberately simple stand-in hash so the tree structure is visible; the real construction uses the Poseidon hash function, chosen because it is cheap both inside an arithmetic circuit and inside a smart contract.
Guarantees
| Property | What it means | How it is enforced |
|---|---|---|
| Correctness | The seller receives the highest bid; that bidder receives the asset. | zkSNARK proof of the winning condition, verified on-chain. |
| Bid privacy | No one — not even the hub — learns a bid during the bidding stage. | Fully sealed commitments; a uniform maximum-bid collateral so the locked amount leaks nothing. |
| Post-auction privacy | In the optimistic case, losing bids and bidder identities are never revealed. | Only the winner and winning amount leave the zero-knowledge proof. |
| Bid binding | A bidder cannot change a committed bid after seeing others. | The Merkle root fixes the bid set before any opening. |
| Non-malleability | The hub cannot favour a chosen bidder. | The hub never learns bids before the root is fixed. |
| Liveness | The auction terminates even under a malicious hub. | Covenant contracts let any party force settlement on-chain. |
| Financial fairness | Whoever deviates loses collateral. | The contract deterministically identifies the cheating party. |
| Non-interactivity | Bidders never talk to each other. | Hub-and-spoke topology; no bidder-to-bidder MPC. |
Measured
Circuits in Circom, Groth16 proofs via snarkjs, Poseidon hashing, ECDSA signatures. 1,156 lines of Solidity, plus Java and Python off-chain clients. Deployed to a private proof-of-work EVM chain (Hyperledger Besu 23.1.0); benchmarks on a 6-core 2.6 GHz Intel Core i7 with 16 GB of memory.
| Tree depth | Constraints | One-time setup | Key size | Proving time | Bidders supported |
|---|---|---|---|---|---|
| 4 | 14,444 | 33.2 s | 7.9 MB | 3.07 s | 16 |
| 6 | 54,626 | 56.0 s | 30.0 MB | 6.14 s | 64 |
| 8 | 213,896 | 268.5 s | 118 MB | 17.49 s | 256 |
| 10 | 849,518 | 1001.3 s | 468 MB | 61.35 s | 1,024 |
These costs are off-chain and borne by the hub; the on-chain cost is unchanged by tree depth. Merkle-tree generation and bid verification add about 51 ms for 1,024 bidders.
| Operation | Gas | Invoked by | Case |
|---|---|---|---|
| Deploying cryptographic libraries | 4,507,969 | Hub | One-time setup |
| Deploying the auction contract | 1,449,003 | Hub | Optimistic |
| approve NFT transfer | 49,233 | Seller | Optimistic |
| Start auction | 92,612 | Hub | Optimistic |
| Submit sealed bids (Merkle root) | 87,138 | Hub | Optimistic |
| Reveal winner (with zkSNARK proof) | 763,444 | Hub | Optimistic |
| Total, honest auction of any size (4 hub calls + seller approval) | 2,441,430 | Hub + seller | Optimistic |
| Register hub–seller covenant | 459,140 | Hub or seller | Pessimistic |
| Register hub–bidder covenant | 3,029,708 | Hub or bidder | Pessimistic |
Opening a programmable payment channel costs 3,243,988 gas and closing it 146,908 gas. That is a one-time cost per participant, amortised across every auction and every other off-chain application that reuses the same channel — so it is not part of the per-auction figures above.
Reference
@inproceedings{minaei2026scalable,
title = {Scalable Off-Chain Auctions},
author = {Minaei, Mohsen and Kumaresan, Ranjit and Beams, Andrew and
Moreno-Sanchez, Pedro and Yang, Yibin and Raghuraman, Srinivasan and
Chatzigiannis, Panagiotis and Zamani, Mahdi and Le, Duc V.},
booktitle = {Proceedings of the Network and Distributed System Security
Symposium (NDSS)},
year = {2026}
}
Source code. The implementation is not yet public — institutional open-sourcing approval is still in progress. The paper contains detailed pseudocode for the core algorithms, and the authors are open to discussing controlled access for testing purposes. Please contact the corresponding author.