# Trustless Sealed Bid Auctions
<!-- [toc] -->
<!-- ### Why are auctions important? -->
> 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](https://a16zcrypto.com/how-auction-theory-informs-implementations/)
>
### 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

graph LR
server([trusted server])
user1 -->|bid| server
user2 -->|bid| server
user3 -->|bid| server
server -->|After deadline send prize to winner| winner

## 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. :warning:

### 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.

graph TD
root([merkel root])
N1[" "]
N2[" "]
N3[" "]
N4[" "]
N5[" "]
N6[" "]
N7["hash(commitments)"]

subgraph commit[Vault Contract]
    root
end
root --> N1
N1 --> N2
N1 --> N3
N2 --> N4
N2 --> N5
N3 --> N6
N3 --> N7

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

graph LR
subgraph _
C1[commitment 1 <li>value: $$$$</li> <li>lock: 0x0..0</li> <li>salt: xxxxxx</li>] 
C1 -->|lock funds| C2
C2[commitment 1 <li>value: $$$$</li> <li>lock: 0xb6..</li> <li>salt: xxxxxx</li>]
C2 --> Condition{if auction Lost?}

Condition -->|Yes| Y[[can update <b>lock</b> to new address]]
Condition -->|No| Lock[[<a>the auction contract gets the amount</a><p>generate new commitment with the difference</p> ]]
end

graph LR
subgraph _
    
    subgraph contract[Vault Contract]
         root([merkel root])
    end
    
user[User] -->|deposits tokens| root
user -.add list of commitments.-> root

root -->|withdraw tokens| user1[User]
user1 -.burn commitments.-> root

end

:::info
*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.

:::

:::info
*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.

graph LR
server([server/public mempool])
B1([Biders])
B2([Biders])
V1([Vault])
SC1([SmartContract])
SC2([SmartContract])
S{{winner is determined from all the revealed bids}}
subgraph _
subgraph commit[Commit Phase]
    B1 -->|deposits funds| V1
    B1 -->|commit bid on-chain & lock funds in vault| SC1
end

subgraph Reveal[Reveal Phase]
B2-->|reveal their commitments| server
S
winner -->|submits proof of winning|SC2
end
end

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. :thinking_face:

#### 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.

graph LR
B1([Biders])
V1([Vault])
SC1([SmartContract])
SC2([SmartContract])
S{{calculates the winning bid}}
subgraph _
subgraph commit[Commit Phase]
    B1 -->|deposits funds| V1
    B1 -->|commit bid on-chain & lock funds in vault| SC1
end

subgraph Reveal[Reveal Phase]
N[network of nodes with private key] --- S
winner -->|submits proof of winning|SC2
m{{winner's funds are locked in the vault}}
end
end

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](https://litprotocol.com/)

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](https://pub.dss.in.tum.de/brandt-research/fc2003.pdf).
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