Comparison of Onchain Auction Designs

In my previous post, On Auctions, Privacy, and Blockchains, I provided an introduction to why auctions are useful, why bid privacy matters for token auctions, and what bid privacy means. This purpose of this post is to review onchain sealed bid auction designs and evaluate their tradeoffs, specifically for multi-unit auctions (e.g. fungible tokens). In the process, I introduce a new design that we've developed and will be releasing soon at Axis.

Onchain auctions are characterized by having onchain bid submission, evaluation, and settlement, i.e. all auction logic is executed on the blockchain in smart contracts. I believe that a hybrid onchain and offchain system may be the best solution long-term, but the current state of availability of various enabling technologies makes this difficult to implement in a decentralized and transparent manner at the moment. These drawbacks impact some of our design goals. I plan to explore these further in a future post.

I previously described some goals for developing the ideal auction system:

• Bid Privacy
• Auction Fairness, including Completeness and Accuracy of the settlement
• Decentralization
• User Experience (UX)

To this list, I think it's also important to add "Portability". A generic auction system is a piece of infrastructure. Ideally, it should be able to be used wherever it's needed, similar to AMMs. In simple terms, it means that relying on privacy-preserving or other features of specific chains beyond standard programmability and widely supported precompiles should be avoided. There are a couple arguments that can be made against this requirement such as:

1. Any sufficiently popular/useful feature that is deployed on a newer chain will be replicated elsewhere.
2. If the solution is good enough, sellers may migrate their assets to the host chain to use it.

However, it is more convenient to have a service be available everywhere and "just work".

Based on the above, you may also notice that I'm focused more heavily on the current, practical usage of these systems rather than theoretical solutions that may be possible in the future. This will inevitably skew my view towards certain solutions and away from others.

Gnosis Auction

Before diving into sealed bid versions, I think it's important to compare these potential solutions against the existing go-to solution for multi-unit batch auctions: Gnosis Auction. Gnosis launched their auction product in 2021 after seeing issues with ICO token launches. What they came up with is an open bid batch auction for ERC20 tokens. It is efficient, has been used for large auctions, and generally viewed as a reliable solution. This is the bar that any new solution must clear to replace it.

It is also fully onchain and achieves all of our goals except for bid privacy. Not having bid privacy is a boon during the implementation and allowed them to have all tokens distributed to users when the auction is settled, improving UX. Unfortunately, this is a significant drawback for token auctions, as I described previously. However, Gnosis deserves a lot of credit for originating the idea and putting out the first usable version of a marginal price auction for tokens.

Commit-Reveal

A solution to the problem of on-chain sealed bid auctions was described last year in several papers by a16z. They detailed what has become known as a "Commit-Reveal" format where bidders submit a cryptographic hash of their bids during the auction period and then reveal it after the auction ends. This is accomplished by having the bidder provide the actual bid info which can be verified against the hash. Once the bids are revealed, the auction is settled.

Their implementations were focused on single unit auctions, and so it was important to conceal the amount of collateral provided. They do this using a clever scheme of deterministic vault contract deployments and state proofs. Ironically, you do not need to disguise the collateral in multi-unit auctions since knowing the amount bid is not enough to determine the price paid (since you don't know how many tokens it is for). As such, Commit-Reveal can be used for multi-unit auctions without the need for the vault scheme.

Commit-Reveal is a great solution and has many nice properties, including low gas costs to bid and settle the auction. However, there are a couple drawbacks.

1. Bidders do not all reveal their bids at the same time. Imagine a "high" bidder goes to reveal their bid and observes that other bidders have bid much lower than them for the item. They may revise their estimate of the items value and decide they bid too much. Since they only submitted a hash of their bid, no one else will know what it is unless they reveal it. They choose not to reveal and someone with a lower bid wins the auction. This resembles the Open Bid scenario we described above. The solution for this is to implement a slashing penalty against their collateral if a bidder doesn't reveal their bid. Unfortunately, even with collateral slashing, it can skew the outcome of an auction to the detriment of the seller.

2. Bidders are required to execute 3 transactions: one to submit the bid, one to reveal the bid, and one to claim the payout. While not terrible, it is a bit of a UX burden. If you also need to add an approval transaction for a token, it increases to 4.

Encrypted Bids

In my opinion, commit-reveal systems require too many actions and a slashing mechanism that reduces UX. A different approach could be to flip the bid reveal dynamic on its head. Instead of having a bidder be the one to reveal their bid, it would be better if the seller (or anyone) could reveal all the bids at the end of the auction. By not requiring action from the bidder, we simplify the UX and remove their ability to not reveal the bid if it's disadvantageous to them. This is a large improvement and forgoes the need to implement slashing penalties for bidders on non-reveal. It's also fairly easy to implement. We can do this using a simplified form of the Elliptic Curve Integrated Encryption Scheme (ECIES).

1. Seller creates an auction for token XYZ and provides a fresh public key for bidders to use to encrypt their bids.

2. Bidders create a fresh private key and derive a shared secret by multiplying (using elliptic curve multiplication) the auction public key by the private key. The shared secret is used to encrypt the amount out of the bid. The bidder also creates a "bid" public key by from the private key. They submit the encrypted amount out and the bid public key to the contract along with the amount in (in plaintext) that they're bidding. The amount in is transferred when the bid is placed, but the price they are bidding cannot be determined since the amount out is encrypted.

3. At the end of the auction, the Seller settles the auction by providing the private key for the previously provided auction public key. On settlement, bids are decrypted, sorted, and a marginal price is determined. If a bid price is below the minimum or the bid size is too small, it is skipped.

4. After settlement, bidders can claim their payout and/or refund (they will have both if a partial fill).

The only elliptic curve with addition and multiplication precompiles on Ethereum is the BN254 curve, also known as Alt_BN128. This isn't ideal given that its estimated security has been reduced by attacks to ~98 bits. If the BLS12-381 curve operations precompile is added in the future, the scheme could be transitioned to using that curve, which is thought to be more secure.

The gas cost for decrypting a single bid is roughly 15,000 gas. For auctions with a large number of bids, this may be prohibitive on Ethereum mainnet. However, this may be workable on some L2s or alt L1s. Additionally, all bids submitted to an auction are revealed when it is settled because the private key is published by the seller. This allows participants to learn information about others bidding behavior that they may be able to use as a guide in future auctions.

Finally, the bidder must trust the Seller to not decrypt and reveal their bid off-chain before the auction is over. However, it's against the Seller's interest to do so since they may face social consequences, and bidders may not participate in their auctions in the future. Instead, off-chain key management services could be used to create a key that isn't revealed until after the auction concludes. One promising solution is Lit Protocol, which uses threshold encryption and trusted execution environments to provide decentralized encryption and decryption operations, among other things. However, they only support BLS and ECDSA keys at the moment. If the above mentioned BLS precompile is added, it may allow for decentralized key management.

ZK and FHE-based Auctions

TODO

Settlement Considerations

Previous batch auction implementations, such as Gnosis Auction, have tried to improve the user experience by having all of the payouts and refunds transferred to bidders when the auction is settled. However, the diagrams that were presented above show a two-step settlement where the auction is settled and then bidders independently claim their payout and/or refund (it could be both if their bid is partially filled). The reason for this is that you can avoid concerns on reaching the gas limit if there are a large number of winning bids. Most implementations require a minimum bid size to avoid these issues, but for large auctions, this minimum may need to be set at a level that is prohibitive for many would-be bidders. For example, if you're trying to raise $10,000,000 from a token auction and the minimum bid size is 0.1%, then anyone with less than $10,000 to spend is kept out. 0.1% implies up to 1,000 winners, which is not small. Allowing for iterative settlement and a pull-based claim after settlement avoids this issue. However, allowing for many small bids will increase the gas costs to settle an auction, so it's something the seller should consider.

How do they stack up?

Let's compare the described systems according to some desired (or undesired) properties of auctions.

* Assumes signature-based token approvals are used instead of an extra approval transaction (e.g. with EIP-2612 permit or Uniswap's Permit2 contract for tokens that do not support). Also, Gnosis Auction sends payouts on settle, but we assume the sealed bid versions would use a pull-based claim to avoid gas limit issues.

** Decryption of a large number of bids will be expensive and possibly prohibitive on Ethereum mainnet. It's currently manageable on L2s and alt L1s.

*** A preferable option for the management of auction private keys would be a decentralized key management service that can create a private key, provide its public key, and not reveal this key until the auction ends. Lit Protocol, as mentioned before, is a promising development in this direction. A hosted key management service with a trusted operator may be an okay near-term solution.

Conclusion

Encrypted bid systems are likely the best onchain option multi-unit auction at the moment. They have settlement guarantees that are not provided by Commit-Reveal schemes and do not require collateral slashing mechanisms. The key limitation is determining a suitable auction key management system or trusting the seller to not reveal bids early. Advances in privacy-preserving chains, zero knowledge (validity) proofs, homomorphic encryption, trusted execution environments, and generalized intent networks will open up the aperture in the future, but these solutions are not yet ready for broad deployment.

We're currently finishing an implementation of an auction system using the Encrypted Bid concept at Axis. Be sure to check it out once it's released!