ZK-Auctions Toolkit Grant Proposal and Progress Tracking

• the bidders submit their sealed-bid as homomorphic commitments on the contract.
• zero knowledge proof protocols are used to verify the correctness of the claim made by the aucitoneer of some winner.
• To be precise, no information about the losing bids is leaked
• The authors also emphasize on how sealed-bid auctions encourage the bidders to bid according to their monetary valuation of the asset. But, at the same time, highlight the conflicting goals of preserving the privacy of the bids and trusting the auctioneer to determine the winner.
• The authors utilize Pedersen commitment scheme with zero-knowledge proof of interval membership to create the underlying protocol.

• The authors emphasize that even though sealed-bid auctions are generally preferred since they do not impact the revenue while maintaining some sort of privacy, the auctioneer can at any time leak the bids or manipulate the results of said auction.

  In a word, the behaviours of the auctioneer can be malicious, once bids are obtained before the bid-opening day.

• The authors highlight challenges in sealed-bid auctions due to the need to maintain the following four properties at the same time:
  1. All bids cannot be shared to the auctioneer before the bid-opening day.
  2. All bids cannot be exposed to any bidders during the auction.
  3. All the bidders can publicly verify the bid comparison result that is published by the auctioneer.
  4. The whole sealed-bid scheme must be efficient in practice.
• Particularly highlighted challenges are:

  1. How to compute the winner correctly over ciphertexts while not exposing the bids during the auction?

     How to accurately find the highest bidder among multiple bidders without revealing privacy is the challenge we want to solve.

  2. How to efficiently execute the auction protocol with multiple participants while the underlying secure circuits mechanically compare bids?

  3. How to construct a secure auction protocol while allowing participants to quit during auction?

     Since some users leave halfway may cause the protocol to fail, it is necessary to consider an additional punishment mechanism to restrain their behavior when designing such a system…Therefore, our protocol needs to support the fact that a bidder’s choice to leave the auction even after losing competitiveness will not have an impact on subsequent comparisons.

     Note: The severity (in terms of the computational integrity) of such issue for the zk-auctions toolkit will be determined upon deciding the protocol that will be followed, and the punishment mechanism, should it be needed, will be designed accordingly.

blockchain-based auction where all encrypted bids are compared pair-by-pair via homomorphic circuit and the winner is declared by using ZK proofs.

At the heart, we improve Fischlin’s comparison protocol in several key aspects tailored for adoption in blockchains.

• Very nice work. Section "Dedicated Auction Protocols" could inspire our work.

• \(\star\) In (Bag, Samiran and Hao, Feng and Shahandashti, Siamak F. and Ray, Indranil Ghosh, 2020), the authors propose an auctioneer-free sealed-bid auction protocol where each bidder has to publish a zero-knowledge eproof about the relationship between com

  ---

• What are the existing gaps?
  • The work of (Galal, Hisham S. and Youssef, Amr M., 2019) does not protect the privacy of bids from all parties including the auctioneer.
• The output of this task should influence the implementation of the pseudocode in “Algorithm Design”.
  • The following listicle was suggested in (Galal, Hisham S. and Youssef, Amr M., 2019):
    1. "Bid privacy. All bidders cannot know the bids submitted by the others before committing to their own. This property is also guaranteed even in a collusion with a malicious auctioneer."
    2. "Posterior privacy. Given a semi-honest auctioneer, all committed bids are maintained private from the bidders and public users."
    3. "Bid Binding. Once the bid interval is closed, bidders cannot change their commitments."
    4. "Public verifiable correctness. The auction contract verifies the correctness of the auctioneer’s work to determine the auctioneer winner."
    5. "Financial fairness. Bidders or auctioneer may attempt to deviate from the protocol and prematurely abort to affect the behavior of the auction protocol. The aborting parties are financially penalized while honest parties are refunded after a specific timeout."
    6. "Non-Interactivity. Bidders do not participate in complex interactions with the underlying protocol of the auction contract. In fact, no extra communications between the bidders and the auction contract are required aside from the submission of the bid commitments and the associated opening values."
• <2024-02-15 Thu> 0xisk advised that we steer away from SPARTAN and instead use PSE's Halo2 verifier, which operates on PLONK (Yet to expound on the rationale behind the decision, however it is relevant to this issue).

• Example of the equations are:

  • \(max(b_1, b_2, \cdots, b_n)\), where \(b_i\) is the bid of participant \(i \in P\), and \(P\) is the set of participants.

  Moreover, the public inputs could either be the winning bid, or the amount the winner required to pay (but the latter may need a different formulation)