Contents

12.32. DD 32: Brandt-Vickrey Auctions

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

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

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

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

12.32.4.1. Transcripts

A transcript of a Brandt-Vickrey auction is the JSON encoding of an object of type 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;
}

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;
}

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;
}

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

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

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

previous

12.31. DD 31: Invoicing

next

12.33. DD 33: Database Schema and Versioning