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
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
DD32: Auctions
##############
Summary
=======
This document describes the design for how (SMC) auctions could be done with
funds held in escrow by a Taler exchange. It is taking major inspiration from
Markus Teich's Master's thesis on "Implementing Privacy Preserving Auction
Protocols".
Motivation
==========
Escrow is a key capability of payment systems. With SMC auctions we can
broaden the escrow functionality beyond the (simplistic) refunds we currently
offer. This provides a first new use-case for the extension mechanism. By
using SMC auctions (libbrandt), we also provide privacy for another business
process.
We expect the design to be useful for three primary use-cases:
* Auctions in the style of Ebay (consumer goods)
* Auctions for commodities and stock trading
* Auctions in currency exchange, including crypto-currencies
We do not consider the use-case of high-value art auctions, as here the Taler
payment system is likely unsuitable for the high transaction values, the
privacy for the buyer would still be problematic from a money-laundering
perspective, and the cost of a trusted auctioneer manually running the auction
is small compared to the transaction value, so the benefits from automation
are also minor.
Requirements
============
The discovery of ongoing auctions and the exchange of meta-data about the
auction (duration, price ranges, conditions of the sale, etc.) is considered
out-of-scope for the Taler protocol. Taler is only used to escrow a payment
once participants have decided to make a bid on an aution.
* Support libbrandt-style SMC multiparty computation to determine
auction winner. No party is trusted to learn the bids during
the bidding phase, including the exchange. This implies that
participants have to always escrow the largest possible amount
in the auction, even if their actual bid is much lower.
* Integrate nicely with existing exchange functionality, including
minimal changes to existing endpoints and introducing as few new
endpoints as reasonable.
* Verifiablity of the auction outcome by the exchange and the
auditor. There is not supposed to be any trusted third party.
Naturally, when selling real-world goods, external enforcement
of the transfer of the good may be required.
* Guaranteed payment. If the auction is successful (there were at
least two bidders), the seller must unconditionally receive the
payment.
* Participants pay fees (possibly even just for participation),
to ensure only truly interested parties with skin in the game
participate (protection against denial-of-service attacks).
* To ensure participants can perform the required computations
in each round, the number of bidders on an auction may need
to be limited.
Proposed Solution
=================
We will for now consider five types of parties involved in
the auction:
* A seller, who is offering an item and who sets some basic
rules for the auction (like the price range, duration of
rounds, delivery conditions, seller's bank account,
auction operator, etc.).
* A number of bidders, who make bids on the auction, with
the highest bidder winnig the auction and paying the
second highest price to the seller.
* An auction operator, who collects messages from the seller
and the bidders and ultimately announces the (then universally
verifiable) outcome. In the original paper of Brand, this
would be the ``blackboard``. The auction operator may
also facilitate the discovery of auctions, but this is out
of scope. The auction operator may charge fees for setting
up and running an auction. However, from the Taler perspective,
paying an auction operator to run an auction is the same
as paying any other merchant and thus out of scope for this
design document.
* An exchange that supports the ``auction`` extension and holds
the funds for bids in escrow for the duration of the auction.
Upon completion of the auction, the exchange pays the seller
from the auction's winner and refunds the other bidders.
* An auditor that verifies that the exchange made the payments
correctly.
The high-level protocol for a bidder's interaction with the auction operator
and the Taler exchange is already described in Teich's thesis in Figure 3.2:
the bidder begins by registering (say with an ephemeral EdDSA key) at the
auction operator. Further messages from the bidder during this auction must
then always be signed by the respective private key.
The auction operator checks if there is a free slot (to limit the number of
bidders per auction) and if one is free, gives the bidder a (modest) timeout
until when it must prove that it escrowed an appropriate amount at the
exchange. If no slots are free, the auction operator may allow the
prospective bidder to long-poll for slots to become available (say because
another prospective bidder failed to provide a proof of escrow on time).
The bidder then uses the existing ``/deposit`` endpoint at the exchange to
escrow the maximum bid. Escrowing the maximum bid ensures that no information
about the actual bid is leaked to the exchange, and that any bid that could be
made by the bidder can always be executed. In the ``/deposit``, the contract
hash is set to information that includes those private parts of the auction
meta data that do not concern the exchange (such as information about the item
being sold). The seller's account information is included as the receiver of
the funds. Additionally, the ``/deposit`` handler accepts an extension object
which specifies the (SMC auction) extension and relevant meta-data about the
auction (in particular, the bidder's ephemeral EdDSA public key, until when
the auction runs, and (possibly) key material about the auction operator).
The resulting proofs of deposits (plural, as there may be multiple coins
involved) are then returned to the bidder. Note that the deposit confirmation
signatures cover both the hash of the contract terms and the extension object.
The deposit confirmations are then forwarded by the bidder to the auction
operator, possibly already together with first (sealed) information about the
bid.
The auction operator then runs the auction protocol with all participants
until conclusion. Once the winner and price have been determined, the auction
operator POSTs the resulting transcript to a new ``/extensions/auction``
endpoint of the exchange. Here, the extension-specific logic stores the
transcript in its database (in a new table) and then simulates the auction
again (using libbrandt), again determining the winner and price. The
extension configuration (and thus ``/keys``) may stipendulate some fee(s)
charged by the exchange to handle the ``/extensions/auction`` request. The
fees should be covered by the seller. We note that the transcript inherently
contains the deposit confirmations originally issued by the exchange for the
auction. So, the exchange can identify all of the coins that were escrowed (it
should also double-check that the coins were escrowed for the correct
auction). It then refunds the bids from the loosing bidders, pays the price
to the seller from the winner (minus auction fee), and partially refunds the
winner the difference between the escrowed amount and the winning bid.
.. note::
Partial refunds are currently implemented using the ``refunds`` table.
The refunds table requires refund message signatures by the merchant's
public key. Thus, this table will need to be generalized to include
some indicator as to whether the refund signature is valid or
whether some other mechanism justified the refund. The most trivial
way would probably be to allow NULL values for the signature. However,
likely a link to the extension transcript should then be stored in
another column to make it easier for the auditor to look for
"alternative" justifications in those cases.
In case participants are identified as malicious, the auction meta data should
specify the penalty those participants must pay to the seller. Again, the
exchange should assess the auction transcript and then trigger the correct
transactions.
The auditor of the exchange can again simulate the auction protocol and can
thus confirm that the exchange's ultimate transactions were correct.
Alternatives
============
If currency is sold for currency in an auction, the seller could also escrow
the currency being sold. This could be done by a simple parallel extension
for sellers that provides the seller's escrow proof as input into the auction
protocol. The result would effectively be an auction-driven equivalent of the
atomic swap protocols for crytocurrencies.
Instead of the exchange and the auditor re-running the auction protocol
internally against the transcript, it might suffice if the auction operator,
seller and all bidders jointly attest to the outcome. However, this presumes
that there are no malicious participants. Thus, this is an optimization that
can help, but likely should not be relied upon. The exchange may stipendulate
different fees if auction participants provide signatures demonstrating that
they agree upon the outcome of the auction.
Drawbacks
=========
Forcing participants to escrow the largest possible bid may exclude some
bidders. However, it can be assumed that the seller (wanting to get as many
high bids as possible) will set a reasonable bidding range to not exclude
realistic bids. If the seller set the bidding range wrong and receives no bids
as a result, the auction can of course simply be repeated. Finally, excluding
bidders that can only make rather low bids may help keep the number of
participants managable. Given the three application domains we focus on,
it seems that the number of bidders regularly excluded from the auction due
to this constraint should be acceptable.
Discussion / Q&A
================
A possible challenge that may require more thought is how to deal with auction
participants dropping out and not sending any more messages and the
equivalent attack from the auction operator of suppressing messages from
certain participants. The latter case can likely be addressed partially by
network-level anonymization of all participants, as then the auction operator
doesn't have the ability to target specific users. However, a conspirator
could still deanonymize themselves to the auctioneer with the objective of the
auction operator then suppressing messages from other (anonymous)
participants and thereby possibly excluding higher bids from those users.
.. note::
As described above, the Master's thesis of Markus Teich proposes to
address the issue of bidders dropping out of the protocol by fining them,
for example by keeping (some of) the escrowed funds. This may work, but
only if we assume that the auction operator is not maliciously dropping
messages from some bidders.
(This should be filled in with results from discussions on mailing lists / personal communication.)
|
