Brief Announcement: Fast and Gas-efficient Private Sealed-bid Auctions

Abstract

We consider the classical problem of running a decentralized and trustless auction, using a smart contract, on a programmable block-chain such as Ethereum. In our setting, there are n bidders who have paid a deposit to join the protocol. Each bidder i can make a bid 1 ≤ bi ≤ m and our goal is to find the highest bid (maxi bi) and its corresponding bidder (argmaxi bi) in a publicly-verifiable manner. Each bidder must be unaware of others' bids when making their own and should not be able to change their bid after having committed to it. Additionally, and most importantly, we aim to provide privacy to the losing bidders, ensuring that their bids remain undisclosed. This is particularly crucial in use-cases with repeated auctions in which knowledge of the bids in the previous auctions can affect the bidders' strategies. Formally, the information gained by any observer, whether a participant in the protocol or not, should precisely consist of the winning bid and its bidder and nothing more. We present a novel yet simple protocol for private sealed-bid auctions on the blockchain. Our protocol is decentralized and trustless. It is also both time- and gas-efficient. Our approach takes O(log m) time and costs O(log m) units of gas for each bidder. It also guarantees observational determinism with respect to all losing bids.