path: root/src/blog/bst-auction.html

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>