taler-docs

032-brandt-vickrey-auctions.rst (13802B)

---

 DD 32: Brandt-Vickrey 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".
 
 The support for these types of auctions will be in the form of an extension for
 a deposit policy.
 
 
 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 ``policy_vickrey_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/policy_brandt_vickrey_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/policy_brandt_vickrey_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 losing 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.
 
 Transcripts
 ^^^^^^^^^^^
 
 A transcript of a Brandt-Vickrey auction is the JSON encoding of an object of
 type `BrandtVickreyAuctionTranscript`.
 
   .. ts:def:: BrandtVickreyAuctionTranscript
 
     // This structure defines the transcript of an auction of Brandt-Vickrey kind.
     interface BrandtVickreyAuctionTranscript {
       // The auction definition.
       auction: BrandtVickreyAuction;
 
       // The public keys of the bidders, in Crockford Base32 encoding.
       bidders: EddsaPublicKey[];
 
       // Signatures of the auction in Crockford Base32 encoding.
       // One signature per bidder.
       signatures: EddsaSignature[];
 
       // List of policy hash codes that identify policy details associated with
       // each bidder.  Those codes were generated by the policy extension
       // policy_brandt_vickrey_auction during the deposit of coins for this
       // auction.
       policy_hash_codes: HashCode[];
 
       // The transcript of all messages received by the seller.
       transcript: BrandtVickreyAuctionMessage[];
 
       // Optionally, the seller can provide the winners it had calculated.
       winners?: BrandtVickreyAuctionWinner[];
 
       // The signature over the hash of this JSON object, without the
       // key ``sig`` and in normalized form, basically over
       //   H(auction, bidders, signatures, transcripts, winners?)
       // It is signed by the private key that corresponds to the public key
       // in `BrandtVickreyAuction`.``pubkey``.
       // This signature is in Crockford Base32 encoding.
       sig: EddsaSignature;
     }
 
 
   .. ts:def:: BrandtVickreyAuctionMessage
 
    interface BrandtVickreyAuctionMessage {
      // The index of the bidder into the
      // `BrandtVickreyAuctionTranscript`.``bidders`` array.
      bidder: number;
 
      // The raw message in Crockford Base32 encoding.
      msg: string;
 
      // The signature over the message.  The signature is in Crockford Base32
      // encoding.  It must be signed by the private key corresponding to the
      // bidder's public key in `BrandtVickreyAuctionTranscript`.``bidders``.
      sig: EddsaSignature;
    }
 
 
 
   .. ts:def:: BrandtVickreyAuctionWinner
 
    interface BrandtVickreyAuctionWinner {
      // The index of the bidder into the
      // `BrandtVickreyAuctionTranscript`.bidder array.
      bidder: number;
 
      // The index of the winning price into the
      // `BrandtVickreyAuction`.prices array.
      price_idx: number;
 
      // The winning price
      price: Amount;
    }
 
 
 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.)