1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
|
title: Decentralized Auction Variants
date: November 25, 2020 22:39
---
<p>
This is a follow up to my previous post on <a href='<%= path_to "blog_bst-auction"%>'>
smart contract auctions
</a> - it assumes familiarity with the algorithm introduced there.
</p>
<p>
It turns out the original design is very flexible. We can modify the auction's
properties to incentivize different behaviors or handle specific scenarios. For
example, we'll be able to mimic the auction mechanism used by Google's AdWords
to auction off search results positions.
</p>
<h4>Quick recap</h4>
<p>
The previous article introduced an auction that works in two phases:
<ol>
<li><b>bid</b> phase
<p>
Users submit bids stating "I'm willing to pay <i>x</i> XYZ for
<i>y</i> ABC." The transaction should include a payment of <i>x</i> XYZ
so the user can't back out later.
</p>
<p>
The user's transaction not only records this bid in the contract's
storage, but also inserts it into a balanced BST (sorted by XYZ/ABC
ratios).
</p>
</li>
<li><b>fill</b> phase
<p>
Users with highest XYZ/ABC ratios can receive their bought ABC, while
the remaining users are refunded their locked up XYZ. We can determine
which bids to fill and which to refund thanks to an additional value
we've been keeping in our BST's nodes (the total amount of ABC in the
node's subtree)
</p>
</li>
</ol>
Our modifications will involve adding and/or modifying phases to the process,
but the generic idea of using a BST to store sorted bids remains the same.
</p>
<h3>Blind Auction</h3>
<p>
As mentioned in a footnote to the previous article, we can hide users' bids
during the auctioning phase. This is something that's probably desired in most
smart contract auctions of this sort, for example to avoid frontrunning or block
congestion in the last few moment's of the bidding phase. In an open bid
auction, bidders could compete for the final strike price in the gas auction if
all bids were open.
</p>
<p>
Closed bids also mean that users submit their own personal valuation of the
auctioned asset, rather than one influenced by other market players.
</p>
<p>
Blinding bids was omitted from the original description for brevity and clarity.
The central idea in the first article was using a BST for an on-chain auction,
blinding bids is just a technical detail. Here's how we can implement it.
</p>
<p>
We replace the <b>bid</b> phase with a <b>commit</b> phase and a
<b>reveal</b> phase:
<ul>
<li>
In the <b>commit</b> phase, users submit a hash of their bid
information (<code>buyAmount</code>, <code>sellAmount</code>), and a
random <code>salt</code>. They also send a prepayment that should be
equal to or greater than their <code>sellAmount</code>. We save this
hash and the amount sent in the smart contract.
</li>
<li>
<p>
The <b>reveal</b> phase is very similar to the original <b>bid</b>
phase, where users submit their <code>buyAmount</code> and
<code>sellAmount</code>. Now they additionally reveal their
<code>salt</code>. The smart contract hashes these inputs and verifies
this hash matches the one submitted during <b>commit</b> — if it
does not, the bid is invalid and will not participate in the auction. We
also verify that the amount prepaid during <b>commit</b> was at least as
much as the revealed <code>sellAmount</code>.
</p>
<p>
After these additional verification steps, we proceed as in <b>bid</b>,
sorting the bid information into a BST.
</p>
</li>
</ul>
</p>
<p>
Note a positive property that this auction has over a simple single-unit blind
auction. While the prepayment sent with <b>commit</b> reveals an upper bound of
how much the bidder is willing to invest in this auction, it doesn't reveal
anything about how they price the sold asset — they could be sending a bid
with a high price purchasing few tokens, or vice versa, attempting to purchase a
lot of tokens but for a low price.
</p>
<h3>Second price auction</h3>
<p>
A second price auction<a href='#note-1' id='ref-1'><sup>1</sup></a> is the
Google AdWords mechanism mentioned in the introduction. In this type of auction,
users bid on multiple items (e.g. ordered slots on a search results page). The
items are distributed to the highest bidders, but the bidders actually pay less
than they bid. Specifically, the highest bidder pays the second-highest bidder's
price, the second pays the third's, and so on.
</p>
<p>
We can implement this in our BST auction design by modifying the <b>fill</b>
phase. When filling a user's bid, we can check the next highest bid's price by
walking to the next node in the inorder traversal order. On a balanced tree
like we're keeping, this will take time <i>O</i>(log n).
</p>
<h3>Uniform price auction</h3>
<p>
A similar modification we can make is to have all the auction participants pay
the same exact price — that of the last winning bidder. We will add a
<b>set price</b> phase in which the smart contract finds and verifies this
lowest accepted price. During the <b>fill</b> phase, we will charge winning
bidders based on this price, refunding them the rest of their prepayment.
</p>
<p>
This modification is possible thanks to the <code>total</code> value we've
decorated our BST's nodes with. In our new <b>set price</b> phase, we can start
in the tree's root and binary search down to the last bid that is fillable. We
note down this node's price as the strike price of the auction for all
participants.
</p>
<p>
Note that we described <b>set price</b> as a separate phase, but it could
instead be included into the <b>fill</b> phase, running the above algorithm on
the first call to <code>fill</code>.
</p>
<h3>Conclusions</h3>
<p>
In these two articles I described several novel smart contract decentralized
auction designs. They can be implemented to be completely trustless,
tamperproof, and censorship resistant, leveraging these properties of
blockchains.
</p>
<p>
The important thing to note about these designs is that, while offering the
above properties, they are relatively gas efficient. Individual operations
work in time (and thus gas cost) <i>O</i>(log n), where n is the number of
auction participants. This can still get fairly expensive, especially given the
number of storage writes when inserting into a BST. However, we spread the cost
of these operations evenly between auction participants.
</p>
<p>
The classic Dutch auction wins out on the efficiency front, having very cheap
<i>O</i>(1) operations, but has its problems. Dutch auction bids can be easily
frontrun. These auctions can cause sudden block congestion spikes when a price
favored by many participants is reached. And in some cases, you just want an
auction with different game theoretic properties than those the Dutch auction
offers. The BST auctions described here widen your decentralized auction
toolbox.
</p>
<p id='note-1'>
<a href='#ref-1'>1.</a> Or more precisely, a <i>generalized</i> second price
auction. The term <i>second price auction</i> (also known as a Vickrey auction)
is usually reserved for single unit auctions.
</p>
|