commit 87c7bcbbba06e09c42ca27dab2bc63a8deb02e25
parent c17313a9e478d0aa072853dce41b291a56409e58
Author: Özgür Kesim <oec-taler@kesim.org>
Date: Thu, 6 Oct 2022 14:44:21 +0200
-rename file; rename field
Diffstat:
4 files changed, 308 insertions(+), 305 deletions(-)
diff --git a/core/api-exchange.rst b/core/api-exchange.rst
@@ -2265,7 +2265,7 @@ proof to the seller for the escrow of sufficient fund.
// winning price. This field is not relevant for the replay of a
// transcript, as the transcript must be provided by the seller who sees
// the winner(s) and winning price of the auction.
- public: boolean;
+ is_public: boolean;
// The public key of the seller.
pubkey: EddsaPublicKey;
diff --git a/design-documents/032-auctions.rst b/design-documents/032-auctions.rst
@@ -1,303 +0,0 @@
-DD32: 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".
-
-
-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 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.
-
-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[];
-
- // 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.)
diff --git a/design-documents/032-brandt-vickrey-auctions.rst b/design-documents/032-brandt-vickrey-auctions.rst
@@ -0,0 +1,306 @@
+DD32: 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 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.
+
+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[];
+
+ // 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.)
diff --git a/design-documents/index.rst b/design-documents/index.rst
@@ -40,5 +40,5 @@ and protocol.
029-mobile-ui
030-offline-payments
031-invoicing
- 032-auctions
+ 032-brandt-vickrey-auctions
999-template
