auction dd

1 files changed, 234 insertions, 0 deletions

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.)