Blog.



Decentralized Auction Variants

(November 25, 2020)

This is a follow up to my previous post on smart contract auctions - it assumes familiarity with the algorithm introduced there.

It turns out the original design is very flexible. We can modify the auction's properties to incentivize different behaviors or handle specific scenarios. For example, we'll be able to mimic the auction mechanism used by Google's AdWords to auction off search results positions.

Quick recap

The previous article introduced an auction that works in two phases:

  1. bid phase

    Users submit bids stating "I'm willing to pay x XYZ for y ABC." The transaction should include a payment of x XYZ so the user can't back out later.

    The user's transaction not only records this bid in the contract's storage, but also inserts it into a balanced BST (sorted by XYZ/ABC ratios).

  2. fill phase

    Users with highest XYZ/ABC ratios can receive their bought ABC, while the remaining users are refunded their locked up XYZ. We can determine which bids to fill and which to refund thanks to an additional value we've been keeping in our BST's nodes (the total amount of ABC in the node's subtree)

Our modifications will involve adding and/or modifying phases to the process, but the generic idea of using a BST to store sorted bids remains the same.

Blind Auction

As mentioned in a footnote to the previous article, we can hide users' bids during the auctioning phase. This is something that's probably desired in most smart contract auctions of this sort, for example to avoid frontrunning or block congestion in the last few moment's of the bidding phase. In an open bid auction, bidders could compete for the final strike price in the gas auction if all bids were open.

Closed bids also mean that users submit their own personal valuation of the auctioned asset, rather than one influenced by other market players.

Blinding bids was omitted from the original description for brevity and clarity. The central idea in the first article was using a BST for an on-chain auction, blinding bids is just a technical detail. Here's how we can implement it.

We replace the bid phase with a commit phase and a reveal phase:

Note a positive property that this auction has over a simple single-unit blind auction. While the prepayment sent with commit reveals an upper bound of how much the bidder is willing to invest in this auction, it doesn't reveal anything about how they price the sold asset — they could be sending a bid with a high price purchasing few tokens, or vice versa, attempting to purchase a lot of tokens but for a low price.

Second price auction

A second price auction1 is the Google AdWords mechanism mentioned in the introduction. In this type of auction, users bid on multiple items (e.g. ordered slots on a search results page). The items are distributed to the highest bidders, but the bidders actually pay less than they bid. Specifically, the highest bidder pays the second-highest bidder's price, the second pays the third's, and so on.

We can implement this in our BST auction design by modifying the fill phase. When filling a user's bid, we can check the next highest bid's price by walking to the next node in the inorder traversal order. On a balanced tree like we're keeping, this will take time O(log n).

Uniform price auction

A similar modification we can make is to have all the auction participants pay the same exact price — that of the last winning bidder. We will add a set price phase in which the smart contract finds and verifies this lowest accepted price. During the fill phase, we will charge winning bidders based on this price, refunding them the rest of their prepayment.

This modification is possible thanks to the total value we've decorated our BST's nodes with. In our new set price phase, we can start in the tree's root and binary search down to the last bid that is fillable. We note down this node's price as the strike price of the auction for all participants.

Note that we described set price as a separate phase, but it could instead be included into the fill phase, running the above algorithm on the first call to fill.

Conclusions

In these two articles I described several novel smart contract decentralized auction designs. They can be implemented to be completely trustless, tamperproof, and censorship resistant, leveraging these properties of blockchains.

The important thing to note about these designs is that, while offering the above properties, they are relatively gas efficient. Individual operations work in time (and thus gas cost) O(log n), where n is the number of auction participants. This can still get fairly expensive, especially given the number of storage writes when inserting into a BST. However, we spread the cost of these operations evenly between auction participants.

The classic Dutch auction wins out on the efficiency front, having very cheap O(1) operations, but has its problems. Dutch auction bids can be easily frontrun. These auctions can cause sudden block congestion spikes when a price favored by many participants is reached. And in some cases, you just want an auction with different game theoretic properties than those the Dutch auction offers. The BST auctions described here widen your decentralized auction toolbox.

1. Or more precisely, a generalized second price auction. The term second price auction (also known as a Vickrey auction) is usually reserved for single unit auctions.

If you have any questions or comments about this post or site in general, feel free to email me.