From 986e65c42ce2bac257aea68550a8cf20e24a4eb9 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Sun, 21 Aug 2022 21:22:54 +0200 Subject: auction dd --- design-documents/032-auctions.rst | 234 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 234 insertions(+) create mode 100644 design-documents/032-auctions.rst (limited to 'design-documents') diff --git a/design-documents/032-auctions.rst b/design-documents/032-auctions.rst new file mode 100644 index 00000000..737cb07a --- /dev/null +++ b/design-documents/032-auctions.rst @@ -0,0 +1,234 @@ +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.) -- cgit v1.2.3