From 1eb898f99a0b186a7cd676f38c7d1dd0b073c1d1 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 25 Nov 2020 23:29:16 +0100 Subject: Publish auction variants blog post --- src/blog/decentralized-auction-variants.html | 182 +++++++++++++++++++++++++++ 1 file changed, 182 insertions(+) create mode 100644 src/blog/decentralized-auction-variants.html (limited to 'src') diff --git a/src/blog/decentralized-auction-variants.html b/src/blog/decentralized-auction-variants.html new file mode 100644 index 0000000..dce5437 --- /dev/null +++ b/src/blog/decentralized-auction-variants.html @@ -0,0 +1,182 @@ +title: Decentralized Auction Variants +date: November 25, 2020 22:39 +--- +

+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. +
  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) +

    +
    3. +
+ +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. +

-- cgit v1.2.3