Blockchain Based M+1st-Price Auction With Exponential Bid Upper Bound

An auction is commonly used to sell limited resources in modern society. M+1st-price auction sells M identical goods to B bidders. The top M winners can buy the goods at the M+1st-price. Each bidder sends their bids secretly as a bit-slice bidding vector to a trusted manager. Bit-slice is commonly used to compare secret values without revealing them. However, the bit-slice bidding vector also limits the upper bound of a bid as the length of the bidding vector. A binary format bidding vector was proposed to increase the bid upper bound to an exponential scale. For example, given a bidding vector with length 32, a binary format bidding vector can increase the bid upper bound from 32 to two to the power of 32. However, previous protocols that use binary format bidding vectors require a somewhat homomorphic encryption (SHE) and a trusted manager. To make sure no party except the bidder itself knows its bid, our protocol does not have any managers. Instead, each bidder interacts with the Smart Contract independently. We propose a zero-knowledge proof that allows our protocol only requires partially homomorphic encryption such as an ElGamal encryption. To our best knowledge, our protocol is the first secure M+1st-price auction protocol that can reach an exponential bid upper bound without a manager and SHE.

Automated summary

An auction is a common method used to sell limited resources in modern society. M+1st-price auction sells M identical goods to B bidders, and the top M winners can buy the goods at the M+1st-price. Bidders send their bids secretly as a bit-slice bidding vector to a trusted manager, but the bidding vector's length also limits the upper bound of a bid.