diff options
Diffstat (limited to 'design-documents/032-brandt-vickrey-auctions.rst')
| -rw-r--r-- | design-documents/032-brandt-vickrey-auctions.rst | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/design-documents/032-brandt-vickrey-auctions.rst b/design-documents/032-brandt-vickrey-auctions.rst new file mode 100644 index 00000000..18660289 --- /dev/null +++ b/design-documents/032-brandt-vickrey-auctions.rst @@ -0,0 +1,312 @@ +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.) |