diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/blog/decentralized-auction-variants.html | 182 |
1 files changed, 182 insertions, 0 deletions
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 +--- +<p> +This is a follow up to my previous post on <a href='<%= path_to "blog_bst-auction"%>'> + smart contract auctions +</a> - it assumes familiarity with the algorithm introduced there. +</p> + +<p> +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. +</p> + +<h4>Quick recap</h4> + +<p> +The previous article introduced an auction that works in two phases: + +<ol> + <li><b>bid</b> phase + <p> + Users submit bids stating "I'm willing to pay <i>x</i> XYZ for + <i>y</i> ABC." The transaction should include a payment of <i>x</i> XYZ + so the user can't back out later. + </p> + <p> + 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). + </p> + </li> + <li><b>fill</b> phase + <p> + 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) + </p> + </li> +</ol> + +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. +</p> + +<h3>Blind Auction</h3> +<p> +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. +</p> + +<p> +Closed bids also mean that users submit their own personal valuation of the +auctioned asset, rather than one influenced by other market players. +</p> + +<p> +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. +</p> + +<p> +We replace the <b>bid</b> phase with a <b>commit</b> phase and a +<b>reveal</b> phase: + +<ul> + <li> + In the <b>commit</b> phase, users submit a hash of their bid + information (<code>buyAmount</code>, <code>sellAmount</code>), and a + random <code>salt</code>. They also send a prepayment that should be + equal to or greater than their <code>sellAmount</code>. We save this + hash and the amount sent in the smart contract. + </li> + <li> + <p> + The <b>reveal</b> phase is very similar to the original <b>bid</b> + phase, where users submit their <code>buyAmount</code> and + <code>sellAmount</code>. Now they additionally reveal their + <code>salt</code>. The smart contract hashes these inputs and verifies + this hash matches the one submitted during <b>commit</b> — if it + does not, the bid is invalid and will not participate in the auction. We + also verify that the amount prepaid during <b>commit</b> was at least as + much as the revealed <code>sellAmount</code>. + </p> + <p> + After these additional verification steps, we proceed as in <b>bid</b>, + sorting the bid information into a BST. + </p> + </li> +</ul> +</p> + +<p> +Note a positive property that this auction has over a simple single-unit blind +auction. While the prepayment sent with <b>commit</b> 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. +</p> + +<h3>Second price auction</h3> +<p> +A second price auction<a href='#note-1' id='ref-1'><sup>1</sup></a> 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. +</p> + +<p> +We can implement this in our BST auction design by modifying the <b>fill</b> +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 <i>O</i>(log n). +</p> + +<h3>Uniform price auction</h3> +<p> +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 +<b>set price</b> phase in which the smart contract finds and verifies this +lowest accepted price. During the <b>fill</b> phase, we will charge winning +bidders based on this price, refunding them the rest of their prepayment. +</p> + +<p> +This modification is possible thanks to the <code>total</code> value we've +decorated our BST's nodes with. In our new <b>set price</b> 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. +</p> + +<p> +Note that we described <b>set price</b> as a separate phase, but it could +instead be included into the <b>fill</b> phase, running the above algorithm on +the first call to <code>fill</code>. +</p> + +<h3>Conclusions</h3> +<p> +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. +</p> + +<p> +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) <i>O</i>(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. +</p> + +<p> +The classic Dutch auction wins out on the efficiency front, having very cheap +<i>O</i>(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. +</p> + +<p id='note-1'> +<a href='#ref-1'>1.</a> Or more precisely, a <i>generalized</i> second price +auction. The term <i>second price auction</i> (also known as a Vickrey auction) +is usually reserved for single unit auctions. +</p> |