Trustless Sealed Bid Auctions

Auctions are ubiquitous in crypto. From Maker collateral auctions, to Flashbots’ sealed-bid blockspace auctions and NFT auctions on OpenSea, auctions are suitable for a wide array of situations where price discovery, liquidity, or allocation of scarce resources is needed, both on and off-chain –a16zcrypto

What are Sealed Bid Auctions?

Sealed-bid first-price: Each bidder submits a sealed bid (e.g. in a sealed envelope) to the auctioneer/organizer. Once all bids are submitted, the auctioneer privately reads them and announces the winner (the highest bidder).

• Sealed-bid first-price auctions: The winner then pays the amount that they bid (Equivalent to Dutch Auction)
• Sealed-bid second-price (the “Vickrey auction”): Yhe winner pays the amount of the second-highest bid.(Equivalent to English Auction)

Issues with the current auctions held on chain?

Most common auctions that occur onchain are English or Dutch auctions which sometimes lead to bidding wars and gas wars. With sealed bid auctions a user has no incentive to bid multiple times or use bots. Were as marketplace like opensea performs auction off-chain to save gas but there is trust involved.

How sealed bid auctions are currently organised?

Web2 version

Architecture

Main challenges to solve this problem:

1. The bids needs to be kept secret untill a certain point of time.
2. How will the protocol force the winner to pay? if we force the bidders to lock funds during bidding it will indirectly reveal the bidding amount.

Proof of collateral

Shadow Vault

• users can deposit into the vault from any address and create commitments
• users can widraw from a different address by burning the commitments (similar to a coin mixers)
• Additionally one can also lock the commitments to a different smart-contract. After locking the user can no longer burn their commitments, they gets unlocked depending on the smartcontract state.

commitments are like shielded UTXOs

When a user bids for a auction, there is no way for others to find out how many commitments he has locked for a particular auction. So its not trivial to estimated an upper bound for a bid as One needs to know exactly how many addresses the bidders owns/controls. One can deposit from multiple addresses to the vault.

The vault contract store the root of the merkel tree off all the commitments and the mina deposited along with them.

Note
That the vault is not intented to be used as a mixer(tornado cash) as burning the commitments reveals which address deposited/created those commitments.

Proof of collateral
Users will lock funds in the vault and prove it to participate in the bidding process.

Auction Contract Architecture

This contract is responsible for managaing the auction process.

• submit sealed bids to a auction. we can use a merkel tree to records the bid commitments and store the root on-chain in the contract
• when auction ends. Record the winner and final price.

Option 1

modified commit reveal scheme.

Cons:

• its a two step process. Users need to reveal their commitments at a later point in time. Big difference from the web2 counter part.
• User needs multiple wallets for effective privacy.

Option 2

Using VDFs for reveal.

1. users commit by encrypting their bids
2. the decryption key is revealed after solving a VDF(verifiable delay function)

Pros:

• the userflow can be made similar to web2 counterpart.

Cons:

• No way of knowing when someone has solved the VDF. as they have no incentive to reveal the solution.

Option 3

Using DKG, where a network of nodes share the private key, for example with a 7/11 system one needs to corrupt atleast 7 nodes to gain access to the key.

This is similar to option 2, but the network of nodes publishes a public key, with which, every user will encrypt then after the time limit the network will work together to decrypt every bids and compute the final price. For example, with a 7/11 system as long as alteast 5 nodes are honest the system with work.

To make the network more decentralized and secure, we might need tokenomics incentive, slashing mechanics and the ability to join/leave the network permissionlessly.

Some projects already provide DKG as a service like.

• litprotocol

Pros:

• the userflow can be made similar to web2 counterpart.

Cons:

• Need to trust a committee of nodes. Is there a way to figure out if they have secretly gone rogue?

Option 4

Using homo-morphic encryption(Elgamal) the idea is taken from this paper.
A rough idea of how this scheme works,
First the bids are encoded into vectors,
for example, 2 => [0,1,0,0,..0], 4 => [0,0,0,1,..0]
Then it's encryted using elgamal, with the private key is shared between a group of participants.

Elgamal is a partially homomorphic encryption scheme that enables computations on encrypted data with either addition OR multiplication

After the bids are encrypted no one can figure out the bids, But all encrypted bid vectors can be added. Now, the idea is, if we multiply the summation of the bid vectors with a lower triangular matrix of all 1's the resultant vector will have 1 in the position of the highest bid and 2 in the position of the second highest bid and so on. The paper builds and imporoves on this idea such that only the winner of the auction can figure out the final selling price.

Pros:

• its similar to option 3 accept it improves upon the privacy. As only the winner of the auction can figure out the final selling price.

Cons:

• the way bids are encoded puts a limit on the maximum amount a user can bid, also reduces the granularity between bids. (as the size of the encoding vectors need to be fixed before hand.)
• similar to option 3, the private key needs to be disclosed by the network at a later point in time.
• its more complex than option 3