Publish BST auction post

1 files changed, 245 insertions, 0 deletions

diff --git a/src/blog/bst-auction.html b/src/blog/bst-auction.html
new file mode 100644
index 0000000..569a422
--- /dev/null
+++ b/src/blog/bst-auction.html
@@ -0,0 +1,245 @@
+title: How to Build a Decentralized Auction
+date: June 24, 2020
+---
+<p><em>
+    this post assumes familiarity with the concept of smart contracts and
+    uses Ethereum and Solidity for concrete examples
+</em></p>
+
+<h3>Multiunit auctions</h3>
+<p>
+Multiunit auctions are a generic financial primitive that could be useful in
+various decentralized financial systems. I'd like to present an alternative to
+the Dutch auction that may be more suitable in certain situations.
+</p>
+
+<h3>Designing an auction smart contract</h3>
+
+<p>
+Let's first define the basic behavior we want from our auction. Then we'll be
+able to see which steps would break if implemented naively, and how to address
+those problems. Let's frame it in the context of a currency auction, where
+currency <strong>A</strong> is being sold for currency <strong>B</strong>:
+
+<ol>
+    <li>
+        The auctioneer decides he wants to sell a pot of <em>x</em> units of
+        <strong>A</strong>.
+    </li>
+    <li>
+        Users submit bids that say "I want to buy <em>y</em> units of
+        <strong>A</strong> for <em>z</em> units of <strong>B</strong>."
+    </li>
+    <li>
+        We go through the bids from highest <em>z</em>/<em>y</em> ratio to
+        lowest, filling them as we go. We stop if the sum of paid out
+        <em>y</em>s reaches the size of the pot <em>x</em>.
+        <a href='#note-1' id='ref-1'><sup>1</sup></a>
+    </li>
+</ol>
+
+A higher <em>z</em>/<em>y</em> ratio means a higher price (in
+<strong>B</strong>) is being offered by the user, so step 3 ensures that the
+winners of the auction are the highest bidders, as we'd expect.
+</p>
+
+<p>
+To make this all a little more concrete, let's define an interface we might
+expect from an auction smart contract:
+
+<pre>
+interface IAuction {
+    function start(uint pot);
+    function bid(uint sellAmount, uint buyAmount) returns (uint bidId);
+    function end();
+    function fill(uint bidId);
+}
+</pre>
+</p>
+
+<p>
+The above is very similar to
+<a href='https://solidity.readthedocs.io/en/v0.5.11/solidity-by-example.html#blind-auction'>
+    an example from the Solidity tutorial
+</a>
+showing how to build a single unit auction. The big difference is that when
+making a bid, we specify how much we're willing to pay <em>and</em> how many
+units of the auctioned asset we're bidding
+on.<a href='#note-2' id='ref-2'><sup>2</sup></a>
+</p>
+
+<p>
+The problem, as hinted at earlier, is that we can't just sort the list of bids
+and go through it, bid by bid, when implementing step 3 of our protocol. Sorting
+is an <em>O</em>(<em>n</em>log<em>n</em>) operation, and even the linear scan
+would greatly limit the allowable number of participants in an auction given
+block gas limits.
+</p>
+
+<h3>Sorting</h3>
+
+<p>
+The solution to this problem, as is often the case in computer science, comes in
+the shape of a tree.
+</p>
+
+<p>
+We'll have <code>bid</code> store bids in a balanced binary search tree. The
+in-order traversal of the resulting tree gives us a sorted list of all bids.
+We're essentially having each auction participant pay the necessary gas to sort
+just their bid into the data structure.
+</p>
+
+<p>
+Here's a scaffold of what <code>bid</code> could look like:
+
+<pre>
+contract Auction {
+    // Node in a red-black tree
+    struct Node {
+        uint sellAmount;
+        uint buyAmount;
+        uint left;
+        uint right;
+        uint parent;
+        bool red;
+    }
+
+    Node[] tree;
+    uint root;
+
+    function greaterThan(Node n1, Node n2) {
+        return n1.sellAmount * n2.buyAmount &gt;= n1.buyAmount * n2.sellAmount;
+    }
+
+    function <b>bid</b>(uint sellAmount, uint buyAmount) payable returns (uint bidId) {
+        bidId = tree.length;
+        tree.push(Node(sellAmount, buyAmount, 0, 0, 0, false));
+        ... // <b>do RBT insertion with greaterThan as the comparison function</b>
+    }
+
+    ...
+}
+</pre>
+</p>
+
+<p>
+When all bids have been submitted and sorted into the tree, we need to be able
+to fill the bids of those users that submitted the highest bids. When a user
+comes in and says "Hey, look at my bid, I paid <em>z</em> amount of
+<strong>B</strong> so now I deserve <em>y</em> amount of <strong>A</strong>!",
+we need to be able to verify that their bid actually fit into the pot and can be
+filled.
+</p>
+
+<p>
+At this point, when implementing <code>fill</code> naively, we would still need
+a linear traversal to determine whether a given <code>bidId</code> should be
+filled or not. To finish off this auction design, we'll augment the BST such
+that we can implement an <em>O</em>(log<em>n</em>) <code>fill</code>.
+</p>
+
+<h3>Filling</h3>
+
+<p>
+We'll augment each node of the tree to contain the total amount of
+<code>buyToken</code> in the node's subtree. This will allow us to quickly
+calculate the amount of <code>buyToken</code> in all nodes with a better price
+than a given bid.
+</p>
+
+<p>
+This augmentation is possible because updating this total is efficient when
+updating the tree. We only need to modify the insert and rotation operations:
+
+<pre>
+function insert(Bid bid, uint bidId) {
+    uint current = tree.root;
+    uint parent = current;
+    while (current != 0) {
+        parent = current;
+
+        <b>// Increase totals on the path from root to newly inserted node
+        tree.[parent].total = tree[parent].total + bid.buyAmount;</b>
+
+        if (greaterThan(bid, tree.bids[current])) {
+            current = tree.bids[current].left;
+        } else {
+            current = tree.bids[current].right;
+        }
+    }
+    
+    // ...
+}
+
+<b>// Called at the end of each rotation operation</b>
+function recalculateTotalsAfterRotation(uint n, uint pivot) {
+    tree[pivot].total = tree[n].total;
+    tree[n].total = tree[tree.bids[n].left].total +
+        tree[tree[n].right].total +
+        tree[n].buyAmount
+}
+</pre>
+
+<p>
+This in our data structure gives us a logarithmic algorithm for checking how
+much of the token would be bought by bidders at higher exchange rates. We walk
+up from our node to the root. Any time we step up from a right child, we'll add
+the total from our sibling's subtree and parent node's value (since, by the BST
+property, those are the nodes with greater rates than our starting node).
+
+<pre>
+function totalFromHigherExchangeRates(uint bidId) view returns (uint) {
+    uint total = tree[tree[bidId].left].total;
+    uint parent = tree[bidId].parent;
+    uint currentNode = bidId;
+
+    while (parent != 0) {
+      <b>if (tree[parent].right == currentNode) {
+        total += tree[tree[parent].left].total;
+        total += tree[parent].buyAmount;
+      }</b>
+
+      currentNode = parent;
+      parent = tree[parent].parent;
+    }
+
+    return total;
+}
+</pre>
+</p>
+
+<p>
+<code>fill</code> can now use <code>totalFromHigherExchangeRates</code> to
+determine whether or not a given bid should be filled. The per-bid
+computational complexity (and thus gas cost) is logarithmic with respect to the
+total number of bids.
+</p>
+
+<h3>Origin</h3>
+<p>
+I originally came up with this auction design while working on
+<a href="https://celo.org">Celo's</a> on-chain stability mechanism. The idea was
+to use periodic currency auctions to expand or contract the supply of a token to
+match demand, thus stabilizing its price.
+</p>
+
+<p>
+Later we came up with an even more clever stabilization mechanism, one that can
+function continuously. It's based on <a href="https://uniswap.io/">Uniswap</a>
+and you can read more about it in
+<a href="https://medium.com/celohq/zooming-in-on-the-celo-expansion-contraction-mechanism-446ca7abe4f">
+    this Medium post
+</a>.
+
+<p id='note-1'>
+<a href='#ref-1'>1.</a> The last successful bid might only be partially filled.
+This is a detail that needs to be addressed, but it's easy to do so. For
+simplicity of the rest of the text, I'll avoid discussing it.
+</p>
+
+<p id='note-2'>
+<a href='#ref-2'>2.</a> For simplicity, we'll talk about a two phase, open bid
+auction. As with the single unit auction, this could be modified to a hidden bid
+auction by adding a commit step.
+</p>