diff options
| -rw-r--r-- | src/blog/bst-auction.html | 245 |
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 >= 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> |