this post assumes familiarity with the concept of smart contracts and uses Ethereum and Solidity for concrete examples
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.
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:
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.
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.
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.
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.