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.
The previous article introduced an auction that works in two phases:
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).
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)
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:
buyAmount, sellAmount), and a
random salt. They also send a prepayment that should be
equal to or greater than their sellAmount. We save this
hash and the amount sent in the smart contract.
The reveal phase is very similar to the original bid
phase, where users submit their buyAmount and
sellAmount. Now they additionally reveal their
salt. The smart contract hashes these inputs and verifies
this hash matches the one submitted during commit — if it
does not, the bid is invalid and will not participate in the auction. We
also verify that the amount prepaid during commit was at least as
much as the revealed sellAmount.
After these additional verification steps, we proceed as in bid, sorting the bid information into a BST.
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.
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).
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.
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.