Enigma Auctions: Privacy-Preserving Multi-Party Auctions with Noir, MPC and ZK-Verified Local Elo Scores

[vaughanlove]

Title: Enigma Auctions: A Framework for Custom Privacy-Preserving Auctions using Noir and REP3 MPC

Summary:
Enigma Auctions is a framework that enables anyone to create custom privacy-preserving auctions using Noir circuits and TACEO's REP3 MPC protocol. The system allows auction creators to define their own scoring rules and input requirements while maintaining bid privacy through MPC. Rather than being limited to specific auction types, the framework supports arbitrary Noir circuits that can implement any scoring logic, making it suitable for government contracts, energy markets, real estate, or any other domain-specific auction needs.

Methodology:

1. Auction Creation:

   • Creator defines:
     • Required bid inputs (e.g., amount, timeline, credentials)
     • Custom Noir circuit for bid validation and scoring
     • Auction parameters (duration, minimum/maximum participants)
   • System validates circuit and generates bidder interface

2. Bid Submission:

   • Bidders submit inputs as defined by auction creator
   • Framework automatically:
     • Fragments and distributes inputs using secret sharing
     • TACEO's REP3 implementation manages communication between nodes

3. Winner Selection:

   • REP3 MPC nodes:
     • Execute creator's Noir circuit
     • Generate ZK proof of correct execution
     • Output winner identifier and optional public data

4. Final ZK proof:

   • Any external party can independently verify the winner of the auction, without revealing bidders

side note: We briefly discussed generating the extended witness client-side to offload some of the computation, since witness generation is going to be the bottleneck. As I currently understand though, that wouldn't be possible to generate unless each bidder had everyone else's bid as well. Please correct me if I am wrong!

Assumptions:

• Assume 2/3 provers are acting honestly. Limitation of REP3 is the fact it cannot scale past 3 parties, open question is how to trustlessly scale this system.
• Noir language and compiler are sufficiently expressive and performant for defining and verifying auction bid constraints.
• TACEO's REP3 implementation can support range checks in noir for input validation.
• Mature company identification ZK tech can be integrated for participant verification.

Timeline and Deliverables:

Month 1 (November 2024):

• Week 1-2: Circuit Development
  • Build circuit validation and compilation system for user defined auctions
  • Deliverable: Custom Noir circuit upload and validation system
• Week 3-4: MPC Integration
  • Set up REP3 MPC nodes using TACEO's implementation
  • Create circuit deployment to REP3 MPC and testing
  • Deliverable: Functioning MPC node network integration

Month 2 (December 2024):

• Week 1-2: User Interface Development

  • Develop auction creation interface with parameter configuration
  • Build dynamic bid interface with secure input handling
  • Deliverables:
    • Auction creation system with custom circuit support
    • Bidding interface with dynamic form generation
    • Bid status tracking functionality

• Week 3-4: Verification Systems

  • Create proof verification system
  • Build verification frontend
  • Deliverables:
    • Automated MPC execution system
    • Proof generation and verification pipeline
    • Result publication mechanism

Month 3 (January 2025):

• Week 1-2: Example Implementation

  • Build example circuits library including:
    • Basic highest-bid auction
    • Multi-parameter auction
  • Testing and performance optimization
  • Deliverable: Functional example auction library

• Week 3-4: Documentation & Release

  • Documentation and tutorials creation
  • Open source release
  • Deliverable: Complete documentation and public codebase release

Future work:

• The framework will be built with the intent of adding the two features below:
  • Add the ability to add a ZK ID as input
  • Adding local state, specifically for elo initially. Similar to how Renegade handles their local state: (https://docs.renegade.fi/core-concepts/mpc-zkp)

Team:

• Vaughan Love: Software Engineer, Applied Mathematics Engineering graduate
  • 6 years blockchain experience
  • Full-stack development and Solana smart contracts
  • Email: [email protected]

Start Date:

• November 8, 2024

[Savio-Sou]

Hi @vaughanlove, thanks for submitting the proposal!

A few comments:

1. Could you elaborate on which MPC protocol are you planning to build with?
2. Could you elaborate on how the MPC protocol will compare bids? Is it going to verify the Noir bid proofs submitted by bidders?
   • Highly recommend adding an E2E workflow diagram, that should make details easier to comprehend, discuss and iterate upon
3. Could you elaborate on why Elo scores are useful for this use case, and how will they be calculated?
4. Could you elaborate MVP(s) of which target application domain would be included in this project, and in what form?
5. Could you elaborate on what you mean by collusion resistance?
   • Recommend describing trust assumptions of this project in the "Assumptions" section

[vaughanlove]

Thanks for the comments!

"Could you elaborate on which MPC protocol are you planning to build with?"
TACEO’s REP3 implementation using co-noir. At the moment TACEO has REP3 and Shamir implementations. REP3 would be more performant because it is a maximum 3 party protocol and most of the MPC's compute time will go into read/write with the other nodes.

"Could you elaborate on how the MPC protocol will compare bids? Is it going to verify the Noir bid proofs submitted by bidders?"
The MPC protocol will compare bids according to some hard-coded scoring algorithm inside of the noir circuit being proven by the MPC protocol. The most basic implementation of the scoring rule will be very simple, accept the bid which is highest. I want auction-creators to be able to specify inputs and the scoring rule that computes a winner from those inputs.

I got some clarity when talking to the TACEO team at their office hours about my implementation.

1. The initial step is for N bidders to create their bids, potentially including specific credentials and other auction-specific details.
2. The bidders fragment their input and secret-share the input fragments to the 3 provers in the REP3 MPC protocol.
3. Given the N bidder inputs, the provers can then create a zero-knowledge proof using Noir that will run input checks like credential validation and a scoring rule (http://www.johnasker.com/Scoring.pdf) that picks the winner of the auction.
4. The MPC protocol returns to each bidder with a verifiable ZK proof and the identifier of the winner. Without any node knowing the inputs!

We briefly discussed generating the extended witness client-side to offload some of the computation, since witness generation is going to be the bottleneck. As I currently understand though, that wouldn't be possible to generate unless each bidder had everyone else's bid as well. Please correct me if I am wrong!

”Could you elaborate on why Elo scores are useful for this use case, and how will they be calculated?”
I was trying to think of ways to disincentivize bad actors from submitting fraudulent bids. Elo is one way the system could maintain a reputation for each bidder. For example, imagine that a grid wants to purchase 200MW of power over the next 2 hours. The grid puts up an open auction for anyone to bid on. Energy producers place their bids and are uniquely identified, with some elo retrieved (maybe from a blockchain). Then the noir circuit used to pick the winning bid should take elo into consideration when picking a winner (maybe some simple weighted avg of X=(1/elo)*bid, where winner is lowest X). If using elo, the noir circuit could output an array of elo changes for each bidder that participated and commit that to some ledger.

I think that every industry probably has a different way that they would want to calculate elo, but in this case, start every producer at some arbitrary number and then simply increase that elo by some weighted power x time after sufficient power has successfully been provided over the contract period. Exponential decrease for sequential failures to provide energy on time.

”Could you elaborate MVP(s) of which target application domain would be included in this project, and in what form?”
The MVP I want to include in this project would be for a scoring auction in government contracts. Bidders would submit their bid on a contract, an estimate of cost to them, lead time, and time to completion. A basic scoring rule will pick the winner. It will be a web-app.

Depending on how much time, I would also try to implement some credentials as input.

”Could you elaborate on what you mean by collusion resistance?”
REP3 provides semi-honest security with honest-majority. Which means that it assumes 2/3 parties or more are operating without being malicious. Collusion resistance is referring to protection against the event that the 2/3 parties running the MPC have ill-intent against a specific bidder or have a vested interest to accept a specific bid that isn't necessarily the most competitive offer.

[vaughanlove]

Also, should I edit the initial proposal with all this additional information + assumptions?

[Savio-Sou]

Also, should I edit the initial proposal with all this additional information + assumptions?

That would be awesome! 👍

[vaughanlove]

Updated!

[Savio-Sou]

Separately minor note on:

Start Date: November 1st

We will strive to announce selected proposals as soon as possible, by November 8th, 2024 latest.

[vaughanlove]

Ah yes, my mistake! My start date is ASAP then

[Savio-Sou]

Deadline to update proposals is now extended to October 28th, 2024 if it helps buy a bit of extra time to supplement details. Good luck!
https://github.com/orgs/noir-lang/discussions/6289#discussioncomment-11052718