Publicly Verifiable Sealed-Bid Auctions with a Trustless Auctioneer
Sealed-bid auctions have a very easy protocol as long as there is a centralized trusted party as auctioneer. Public distribution of that trust is contradicting the confident nature of the bids.
In this article, we show a protocol supporting publicly verifiable private auctions, implementable as smart contracts on Ethereum blockchain. The bidders keep their bids private from the public view, revealing them after auction end only to a trustless auctioneer. The auctioneer determines the winner, providing publicly verifiable non-interactive zero-knowledge proofs to claim correctness.
Consequently, trust is distributed from a centralized auctioneer through public verifiability without revealing the actual bids.
Cryptographic Preliminaries
The proposed protocol is utilizing the following cryptographic primitives:
- Homomorphic commitment scheme that supports the addition and subtraction operations on the underlying values.
- Zero-knowledge range proofs, which claim that the committed value belongs to the fixed range
Homomorphic Commitments
The Pedersen commitment scheme¹ is perfectly hiding, computationally strongly binding and additively homomorphic commitment scheme under the discrete logarithm assumption. The key generation algorithm G outputs a description of a cyclic group G of prime order p and random generators g and h. The commitment key is ck=(G,p,g,h).
To commit to
the committer picks randomness
and computes
The Pedersen commitment scheme can be generalized for multiple messages, i.e. given messages
one can create a single commitment of the form
The Pedersen commitment scheme has homomorphic properties. In particular, for all correctly generated parameters the following equation holds
Bulletproofs
Bulletproofs² are zero-knowledge arguments of knowledge, proving that a secret committed value lies in a given interval. Unlike zk-SNARKS, bulletproofs do not require a trusted setup, and rely only on the standard cryptography assumption (discrete logarithm assumption).
Formally, let
be a Pedersen commitment to v using randomness γ. Then the proof system will convince the verifier that
In other words, the proof system proves the following relation
Bulletproofs are interactive protocols which can be made non-interactive by using the Fiat-Shamir heuristic in the random oracle model. For the original protocol details, we refer to the paper [2].
Protocol Overview
There are four types of parties interacting in the proposed protocol
- the Auctioneer
- N Bidders
- the Auction Contract
- the Auction Verification Contract
interacting in five sequential phases of the auction.
1. Auction Initiation: the Auctioneer initiates the auction by deploying the Auction Contract, which will store all encrypted bids as well as all zero-knowledge proofs generated during the protocol execution by Bidders and Auctioneer
2. Bid Commitments: the Bidders commit their bids by submitting the cryptographic commitments of their bid value. The bidder generates a random blinding factor r and commits the bid value x to the blockchain as
3. Sharing Bid Openings with the Auctioneer: after the auction is closed, Bidders have a pre-defined time to share their bid openings (the value x and the blinding factor r) with the Auctioneer using a public key provided by the Auctioneer. The ciphertext is published to the blockchain.
4. Proof Generation: for each pair of bids the Auctioneer generates a special range proof for the difference of the committed values. All zk-proofs are committed to the blockchain and can be verified through the Auction Verification Contract
5. Proof Verification: Each proof can be publicly verified by the Auction Verification Contract. The winner is claimed and verified.
Protocol Details
Auction Initiation
The Auctioneer creates an Auction Smart Contract which will store the
- auction duration,
- time limit for sharing the bid openings,
- all encrypted bids and their respective bidders and
- zero-knowledge proofs of the winning claim
Bid Commitments
After the Auction Initialization phase bidder commit to their bids by choosing a uniformly random blinding factor r and making the Pedersen commitment to their bid x as
p is the 256-bit prime number representing the order the elliptic curve. Along with the Pederson commitment, a zero-knowledge range proof Ri generated by the Bidder shows that the commitment is actually in the range
Sharing Bid Openings with the Auctioneer
After the auction closes, bidders have a pre-defined time to share the committed bid values and its opening with the auctioneer using a public key provided by the Auctioneer. The Auctioneer is the only party getting access to all unsealed bids.
Proof Generation
After the Bid Openings Sharing period, the Auctioneer selects the winning bid and provides a zero-knowledge proof of the correctness of the claim, without revealing any information about any committed value. This is accomplished based on the homomorphic commitments and the range proof primitives outlined earlier.
The Auctioneer can provide a zero-knowledge proof that the sorted first committed sealed bid is greater than the second sealed bid without revealing any information about the values.
Specifically, if the following three range proofs hold true the higher ordinality of a bid can be proven
The first two proofs have been provided by the respective Bidders already. Due to the homomorphic properties of the Pedersen commitment scheme, for each pair of bids, the following value can be publicly computed
This element is a valid Pedersen commitment to the value
using the blinding factor
As the Auctioneer possesses all the necessary secrets to generate a non-interactive range proof (Bulletproof) providing that the Pedersen Commitment Bi,j is a commitment of a non-negative value.
Since the Auctioneer needs to know all four secret values, all bids of Bidders who do not provide the values after the auction closes but before the Bid Openings Sharing period ends are ignored.
Proof Verification
The range-proof algorithm is an interactive algorithm, hence requiring some communication between the prover and the verifier during the proof generation phase. However, it can be made non-interactive the Fiat-Shamir heuristic. In the non-interactive setup, the auctioneer acts as a prover and the Auction Smart Contract acts as a Verifier which implements the bulletproof verification logic. The provided zero-knowledge range proofs can be verified not only by the smart contract but by any independently developed software as well.
Depending on the desired privacy level, only range proofs of the winning bid in relation to all other bids are necessary. Assuming the i-th bid is the winning bid, the Auctioneer generates range proofs for the following pairs
This protocol can also be used for Vickrey auctions. Assuming Bi corresponds to the highest bid and Bj corresponds to the second highest bid, this can be shown by providing range proofs for the following commitments
Bulletproof sizes are logarithmic of n. The proof is comprised of
group elements (each group element is 33 byte for secp256k1 curves) and 5 elements (each element is 32 byte integer) in Zp. Another major advantage of Bulletproofs is the possibility to aggregate the proofs for N values which is more efficient than conducting N individual range proofs. Specifically, the aggregated proof system can efficiently prove the following relation
The aggregated range proof for N different values uses
elliptic curve group elements and 5 elements in Zp. The proof size grows only by an additive term of
when conducting multiple range proofs as opposed to a multiplicative factor of N when creating N independent range proofs.
Summarizing, we have shown a protocol that allows for a decentralized sealed-bid auction using a trustless Auctioneer.
Vahe Andonians
Aram Jivanyan
Hyduke Noshadi
[1] Torben P. Pedersen. Non-interactive and information-theoretic secure verifiable secret sharing. In CRYPTO, volume 576 of Lecture Notes in Computer Science, pages 129 -140,1991.
[2] Benedikt Buenz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. Cryptology ePrint Archive, Report 2017/1066, 2017. https://eprint.iacr. org/2017/1066
