From 2d73ca9e187835a6364abd8c0a623002efae4d45 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 24 Jun 2020 23:02:53 +0200 Subject: Publish BST auction post --- src/blog/bst-auction.html | 245 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 245 insertions(+) create mode 100644 src/blog/bst-auction.html 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 +--- +

+ this post assumes familiarity with the concept of smart contracts and + uses Ethereum and Solidity for concrete examples +

+ +

Multiunit auctions

+

+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. +

+ +

Designing an auction smart contract

+ +

+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 A is being sold for currency B: + +

    +
  1. + The auctioneer decides he wants to sell a pot of x units of + A. +
    2. +
  2. + Users submit bids that say "I want to buy y units of + A for z units of B." +
    3. +
  3. + We go through the bids from highest z/y ratio to + lowest, filling them as we go. We stop if the sum of paid out + ys reaches the size of the pot x. + 1 +
    4. +
+ +A higher z/y ratio means a higher price (in +B) is being offered by the user, so step 3 ensures that the +winners of the auction are the highest bidders, as we'd expect. +

+ +

+To make this all a little more concrete, let's define an interface we might +expect from an auction smart contract: + +

+interface IAuction {
+    function start(uint pot);
+    function bid(uint sellAmount, uint buyAmount) returns (uint bidId);
+    function end();
+    function fill(uint bidId);
+}
+
+

+ +

+The above is very similar to + + an example from the Solidity tutorial + +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 and how many +units of the auctioned asset we're bidding +on.2 +

+ +

+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 O(nlogn) operation, and even the linear scan +would greatly limit the allowable number of participants in an auction given +block gas limits. +

+ +

Sorting

+ +

+The solution to this problem, as is often the case in computer science, comes in +the shape of a tree. +

+ +

+We'll have bid 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. +

+ +

+Here's a scaffold of what bid could look like: + +

+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 bid(uint sellAmount, uint buyAmount) payable returns (uint bidId) {
+        bidId = tree.length;
+        tree.push(Node(sellAmount, buyAmount, 0, 0, 0, false));
+        ... // do RBT insertion with greaterThan as the comparison function
+    }
+
+    ...
+}
+
+

+ +

+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 z amount of +B so now I deserve y amount of A!", +we need to be able to verify that their bid actually fit into the pot and can be +filled. +

+ +

+At this point, when implementing fill naively, we would still need +a linear traversal to determine whether a given bidId should be +filled or not. To finish off this auction design, we'll augment the BST such +that we can implement an O(logn) fill. +

+ +

Filling

+ +

+We'll augment each node of the tree to contain the total amount of +buyToken in the node's subtree. This will allow us to quickly +calculate the amount of buyToken in all nodes with a better price +than a given bid. +

+ +

+This augmentation is possible because updating this total is efficient when +updating the tree. We only need to modify the insert and rotation operations: + +

+function insert(Bid bid, uint bidId) {
+    uint current = tree.root;
+    uint parent = current;
+    while (current != 0) {
+        parent = current;
+
+        // Increase totals on the path from root to newly inserted node
+        tree.[parent].total = tree[parent].total + bid.buyAmount;
+
+        if (greaterThan(bid, tree.bids[current])) {
+            current = tree.bids[current].left;
+        } else {
+            current = tree.bids[current].right;
+        }
+    }
+    
+    // ...
+}
+
+// Called at the end of each rotation operation
+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
+}
+
+ +

+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). + +

+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) {
+      if (tree[parent].right == currentNode) {
+        total += tree[tree[parent].left].total;
+        total += tree[parent].buyAmount;
+      }
+
+      currentNode = parent;
+      parent = tree[parent].parent;
+    }
+
+    return total;
+}
+
+

+ +

+fill can now use totalFromHigherExchangeRates 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. +

+ +

Origin

+

+I originally came up with this auction design while working on +Celo's 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. +

+ +

+Later we came up with an even more clever stabilization mechanism, one that can +function continuously. It's based on Uniswap +and you can read more about it in + + this Medium post +. + +

+1. 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. +

+ +

+2. 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. +

-- cgit v1.2.3