m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/blog/bst-auction.html245
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>