Publish auction variants blog post

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> &mdash; 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 &mdash; 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 &mdash; 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>