Keywords

1 Introduction

Auctions are a common way of allocating goods or services among a set of parties based on their bids, e.g., bandwidth spectrum, antiques, paintings, and slots for advertisements in the context of web search engines or social networks [17]. In the simplest form, there is a single indivisible object, and each bidder has a private valuation for the object. One of the main desirable properties in designing an auction is incentive compatibility, that is the auction must be designed in a way that the participating parties can maximize their expected utilities by bidding their true valuations of the object. According to design, the auction can be categorized into open auctions, and sealed-bid auctions [31].

We focus on the case of sealed-bid auctions, constructing protocols where parties holding a private bid do not have to rely on trusted third parties to ensure bid privacy. In a sealed bid auction, each bidder communicates her bid to the auctioneer privately. Then, the auctioneer is expected to declare the highest bidder as the winner and not to disclose the losing bids. In particular, in the sealed-bid first-price auction, the bidder submitting the highest bid wins the auction and pays what she bids, while in the sealed-bid second-price auction (i.e., the Vickrey auction [41]) the bidder submitting the highest bid wins the auction but pays the amount of the second-highest bid [30]. It is well-known that in the second-price auctions bidding truthfully is a dominant strategy, but no dominant strategy exists in the case of first-price auctions. Moreover, while in both first-price and second-price auctions, a dishonest auctioneer may disclose the losing bids, the second-price auction, in particular, highly depends on trusting the auctioneer. Indeed, a dishonest auctioneer may substitute the second-highest bid with a bid that is slightly smaller than the first bid to increase her revenue. Therefore, it may not be possible or expensive to apply it in certain scenarios. As a result, constructing cryptographic protocols for auctioneer-free and transparent auction solutions is of great interest.

1.1 Our Contributions

In this paper, we propose Fair Auctions via Secret Transactions (FAST), in which there is no trusted auctioneer and where rational adversaries are always incentivized to complete protocol execution through a secret collateral deposit. The proposed protocol is such that each party can make sure the winning bid is the actual bid submitted by the winning party, and malicious parties can be identified, financially punished and removed from the execution (guaranteeing a winner is always determined). Our contributions are summarized as follows:

  • We propose using secret collateral deposits dependent on private bids inputs to ensure that the optimal strategy is for parties to complete the protocol.

  • (Sect. 3) We propose methods for implementing a financial punishment mechanism based on secret deposits and standard public smart contracts, which can be used to ensure the fair execution of our protocols.

  • (Sects. 4) We propose cheater identifiable and publicly verifiable sealed bid auction protocols compatible with our secret deposit approach and more efficient than the state-of-the-art [3]. Our protocols are guaranteed to terminate, finding the winner, and paying the seller even if cheating occurs.

To achieve fairness in an auction setting, we require each party to provide a secret deposit of an amount of cryptocurrency equal to the party’s private bid plus the cost of executing the protocol. In case a party is found to be cheating, a smart contract automatically redistributes cheaters’ deposits among the honest parties, the cheater is eliminated and the remaining parties re-execute the protocol using their initial bids/deposits. Having a bid-dependent deposit guarantees that it is always more profitable to execute the protocol honestly than to cheat (as analyzed in Sect. 5).

However, previous works that considered the use of cryptocurrency deposits for achieving fairness (e.g. [2, 6, 8, 9, 18, 29]) crucially rely on deposits being public, thus using the same approach would reveal information about the bid. To overcome this, we propose using secret deposits that keep the value of the deposit secret until cheating is detected. Moreover, this ensures that the parties have sufficient funds to bid for the object (e.g., in a second-price auction, a party could bid very high just to figure out what is the second-highest price is and then claim her submitted bid was just a mistake). Our protocols are publicly verifiable, i.e. it is possible to prove to the smart contract (and to any third party verifier) that a party has cheated.

In relation to previous works (discussed in Sect. 1.3), we emphasize that:

  • While using deposits to achieve fairness represents a well-known technique, previous works considered public deposits only.

  • Public deposits are not suitable for applications such as sealed-bid auctions since in order to achieve fairness, bid-dependent deposits are required, and public deposits would reveal information about the bid. For this reason, we introduce secret deposits, which represent a novel technique.

  • From a sealed bid auction perspective, our protocol improves the state-of-the-art both in terms of efficiency and security guarantees, i.e., it achieves fairness (while in previous works the adversary may learn the outcome of the auction before honest parties and abort without suffering any consequences).

  • No previous work in this setting considers adaptive adversaries since it would drastically increase the complexity of the protocol. For this reason, we focus on the static adversary case only.

1.2 Our Techniques

We start with a first-price sealed-bid auction protocol that builds on a simple passively secure protocol similar to that of SEAL [3] and compile it to achieve active security. However, we not only obtain an actively secure protocol but also add cheater identification and public verifiability properties. We use these properties to add our financial punishment mechanism with secret deposits to this protocol. Even though our protocol achieves stronger security guarantees than SEAL (i.e., sequential composability and fairness guarantees), it is more efficient than the SEAL protocol as shown in Sect. 6.

A Toy Example: Our protocol uses a modified version of the Anonymous Veto Protocol from [25] as a building block. The anonymous veto protocol allows a set of n parties \(\mathcal {P} _1,\ldots ,\mathcal {P} _n\) to anonymously indicate whether they want to veto or not on a particular subject by essentially securely computing the logical-OR function of their inputs. In this protocol, each party \(\mathcal {P} _{i}\) has an input bit \(d_{i}\in \{0,1\}\) with 0 indicating no veto and 1 indicating veto, and they wish to compute \(\bigvee _{{i}=1}^{n} d_{i}\).

As proposed in [3], this simple anonymous veto protocol can be used for auctions by having parties evaluate their bids bit-by-bit, starting from the most significant bit and proceeding to execute the veto protocol for each bit in the following way: 1. Until there is no veto, all parties only veto (input \(d_{i}=1\) in the veto protocol) if and only if the current bit of their bid is 1; 2. After the first veto, a party only vetoes if the bit of her bid in the last time a veto happened was 1 and the current bit is also 1. In other words, in this toy protocol, parties stop vetoing once they realize that there is another party with a higher bid (i.e., there was a veto in a round when their own bit were 0) and the party with the highest bid continues vetoing according to her bid until the last bit. Therefore, the veto protocol output represents the highest bid. However, a malicious party can choose not to follow the protocol, altering the output.

Achieving Active Security with Cheater Identification and Public Verifiability: To achieve active security with cheater identification and public verifiability, we depart from a simple passively secure protocol and compile it into an active secure protocol using NIZKs following an approach similar to that of [26, 29]. This ensures that at every round of the protocol all parties’ inputs are computed according to the protocol rules, including previous rounds’ inputs and outputs. However, since the generic techniques from [26, 29] yield highly inefficient protocols, we carefully construct tailor-made efficient non-interactive zero-knowledge proofs for our specific protocol, ensuring it to be efficient.

Incentivizing Correct Behaviour with Secret Deposits: In order to create incentives for parties to behave honestly, a deposit based on their bids is required. However, a public deposit would leak information about the parties’ bids, which have to be kept secret. Hence, we do secret deposits as discussed below and keep the amount secret unless a party is identified as a cheater, in which case the cheater’s deposit is distributed among the honest parties. The cheater is then eliminated and the protocol is re-executed with the remaining parties using their initial bids/deposits so that a winner is determined. This makes it rational not to cheat both in the case of first and second-price auctions, i.e., cheating always implies a lower utility than behaving honestly (see Sect. 5).

Achieving On-Chain Efficiency: In order to minimize the amount of on-chain communication, an approach based on techniques from [5] is adopted. Every time a message is sent from a given party to the other parties, all of them sign the message received and send the signature to each other. Communication is only done on-chain (through the smart contract) in case of suspected cheating.

Secret Deposits to Public Smart Contracts: Since we use secret deposits based on confidential transactions [35], we need a mechanism to reveal the value of cheating parties’ deposits to the smart contract so it can punish cheaters. We do that by secret sharing trapdoor information used to reveal this value using a publicly verifiable secret sharing (PVSS) scheme [15] that allows us to prove in zero-knowledge both that the shares are valid and that they contain the trapdoor for a given deposit. These shares are held by a committee that does not act unless cheating is detected, in which case the committee members are reimbursed for reconstructing the trapdoor with funds from the cheater’s deposit itself. We discuss this approach in Sect. 3. Providing alternative methods for holding these deposits is an important open problem.

1.3 Related Work

Research on secure auctions started by the work of Nurmi and Salomaa [38] and Franklin and Reiter [23] in the late 1900s. However, in these first constructions, the auctioneers open all bids at the end of the protocol, which reveals the losing bids to all parties. Since then, many sealed bid auction protocols have been proposed to protect the privacy of the losing bids, e.g., [1, 4, 27, 32, 33]. However, in most of these protocols, privacy is obtained by distributing the computation of the final outcome to a group of auctioneers.

A lot of work has been done to remove the role of the trusted parties, e.g., by Brandt [11]. In these protocols, the bidders must compute the winning bid in a joint effort through emulating the role of the auctioneer. Moreover, the seller plays a role in the auction and it is assumed that the seller has no incentive to collude with other bidding parties. However, later by Dreier et al. [22] it was pointed out that if the seller and a group of bidding parties collude with each other, then they can learn the bids of other parties. Besides weak security guarantees, the main drawback of the protocol proposed by Brandt [11] is that it has exponential computational and communication complexities.

There have been implementations of auctions including [10], which have been deployed in practice for the annual sugar beets auction in Denmark. Other works [36] have considered the use of rational cryptography in enhancing privacy. Finally, the current state-of-the-art in protocols for secure First-Price Sealed-Bid Auctions was achieved in SEAL [3], which we compare with our protocols in detail in Sect. 6. To the best of our knowledge, none of these works considers incentives for the parties to complete the protocol or punishment for cheaters.

An often desired feature of Secure Multiparty Computation (MPC) is that if a cheating party obtains the output, then all the honest parties should do so as well. Protocols that guarantee this are also called fair and are known to be impossible to achieve with dishonest majorities [16]. Recently, Andrychowicz et al. [2] (and independently Bentov & Kumaresan [8]) initiated a line of research that aims at incentivizing fairness in MPC by imposing cryptocurrency-based financial penalties on misbehaving parties. A line of work [9, 18] culminating in [6] improved the performance of this approach with respect to the amount of on-chain storage and size of the collateral deposits from each party, while others obtained stronger notions of fairness [29]. However, all of these works focus on using public collateral deposits for incentivizing fairness, which is not possible for our application. Moreover, they rely on general-purpose MPC, while we provide a highly optimized specific purpose protocol for auctions with financial incentives. The protocols of [21, 24] are also based on cryptocurrencies. The work of [24] is the closest to ours as it leverages a cryptocurrency to ensure fairness, but it relies on SGX trusted execution enclaves.

2 Preliminaries

Let \(y {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}F(x)\) denote running the randomized algorithm F with input x and implicit randomness, obtaining the output y. When the randomness r is specified, we use \(y \leftarrow F(x;r)\). For a set \(\mathcal{X}\), let \(x {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal{X}\) denote x chosen uniformly at random from \(\mathcal{X}\); and for a distribution \(\mathcal{Y}\), let \(y {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathcal{Y}\) denote y sampled according to the distribution \(\mathcal{Y}\). We denote concatenation of two values x and y by x|y. We denote negligible functions as \({\text {negl}}(x)\). We denote two computationally indistinguishable ensembles \(X=\{X_{\kappa ,z}\}_{\kappa \in {{\mathbb N}}, z\in \{0,1\}^*}\) and \(Y=\{Y_{\kappa ,z}\}_{\kappa \in {{\mathbb N}}, z\in \{0,1\}^*}\) of binary random variables by \(X \approx _c Y\). For a field \(\mathbb {F}\) we denote by \(\mathbb {F}[X]_{\le m}\) the vector space of polynomials in \(\mathbb {F}[X]\) of degree at most m.

2.1 Security Model and Setup Assumptions

We prove our protocol secure in the real/ideal simulation paradigm with sequential composition. This paradigm is commonly used to analyse cryptographic protocol security and provides strong security guarantees, namely that several instances of the protocol can be executed in sequence while preserving their security. To prove security, a real world and an ideal world are defined and compared. In the real world, the protocol \(\pi \) is executed with the parties, some of which are corrupted and controlled by the adversary \(\mathcal {A}\). In the ideal world, the protocol is replaced by an ideal functionality \(\mathcal {F}\) and a simulator \(\mathcal {S}\) interacts with it. The ideal functionality \(\mathcal {F}\) describes the behaviour that is expected from the protocol and acts as a trusted entity. A protocol \(\pi \) is said to securely realize the ideal functionality \(\mathcal {F}\), if for every polynomial-time adversary \(\mathcal {A}\) in the real world, there is a polynomial-time simulator \(\mathcal {S}\) for the ideal world, such that the two worlds cannot be distinguished. In more detail, no probabilistic polynomial-time distinguisher \(\mathcal {D}\) can have a non-negligible advantage in distinguishing the concatenation of the output of the honest parties and of the adversary \(\mathcal {A}\) in the real world from the concatenation of the output of the honest parties (which come directly from \(\mathcal {F}\)) and of the simulator \(\mathcal {S}\) in the ideal world. More details about this model are in [14]. Our protocol uses the Random Oracle Model (ROM). Note that adopting the UC model, as an alternative, requires to use UC-secure NIZK (instead of those described subsequently), but reduces the efficiency of the protocol. Also, previous works consider the sequential composability model only.

Adversarial Model: We consider malicious adversaries that may deviate from the protocol in any arbitrary way. Moreover, we consider the static case, where the adversary is only allowed to corrupt parties before protocol execution starts and parties remain corrupted (or not) throughout the execution. Moreover, we assume that parties have access to synchronous communication channels, i.e., all messages are delivered within a given round with a known maximum delay.

Decisional Diffie Hellman (DDH) Assumption: The DDH problem consists in deciding whether \(c=ab\) or \(c {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {Z}_p\) in a tuple \((g,g^a,g^b,g^{c})\) where g is a generator of a group \(\mathbb {G}\) of order p, and \(a,b {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}\mathbb {Z}_p\). The DDH assumption states that the DDH problem is hard for every PPT distinguisher. It is well known that the DDH assumption implies the Discrete Logarithm assumption.

2.2 Building Blocks

Pedersen Commitments: Let p and q be large primes such that q divides \(p - 1\) and let \({{\mathbb G}}\) be the unique subgroup of \({{\mathbb Z}}^*_p\) of order q. All the computations in \({{\mathbb G}}\) are operations modulo p, however we omit the \(\text {mod } p\) to simplify the notation. Let g, h denote random generators of \({{\mathbb G}}\) such that nobody knows the discrete logarithm of h base g, i.e., a value w such that \(g^w = h\). The Pedersen commitment scheme [40] to an \(s \in {{\mathbb Z}}_q\) is obtained by sampling \(t {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}{{\mathbb Z}}_q\) and computing \(\text {com}(s,t)=g^sh^t\). Hence, the commitment \(\text {com}(s,t)\) is a value uniformly distributed in \({{\mathbb G}}\) and opening the commitment requires to reveal the values of s and t. The Pedersen commitments are additively homomorphic, i.e., starting from the commitment to \(s_1 \in {{\mathbb Z}}_q\) and \(s_2 \in {{\mathbb Z}}_q\), it is possible to compute a commitment to \(s_1 + s_2 \in {{\mathbb Z}}_q\), i.e., \(\text {com}(s_1,t_1) \cdot \text {com}(s_2,t_2) = \text {com}(s_1+s_2,t_1+t_2)\).

Simplified UTXO Model: In order to focus on the novel aspects of our protocol, we represent cryptocurrency transactions under a simplified version of the Bitcoin UTXO model [37]. For the sake of simplicity, we only consider operations of the “Pay to Public Key” (P2PK) output type, which we later show how to realize while keeping the values of transactions private. The formal description of the adopted simplified UTXO model is discussed in the full version [20].

Confidential Transactions: In the case of confidential transactions [35] the input and output amounts are kept secret using Pedersen commitments. However, in order to achieve public verifiability, the transactions contain a zero-knowledge proof that the sum of the inputs is equal to the sum of the outputs, and that all the outputs are between \([0, 2^l - 1]\) (which can be computed with Bullet Proofs [12]). Note that the input set \(\mathsf {In}\) in confidential transactions can also be public, (i.e. \( \mathsf {In}=\{(\mathtt {id}_1,\mathtt {in}_1),\ldots ,(\mathtt {id}_m,\mathtt {in}_m)\}\)), as long as the outputs are kept private. In particular, confidential transactions can be formally defined by modifying the simplified UTXO model described above as follows:

  • Representing inputs and outputs: Set \(\mathsf {In}\) is defined as \(\mathsf {In}=\{(\mathtt {id}_1,\text {com}({\mathtt {in}_1},r_{\mathtt {in}_1})),\ldots ,(\mathtt {id}_m,\text {com}({\mathtt {in}_m},r_{\mathtt {in}_m}))\}\) and set \(\mathsf {Out}\) is defined as \(\mathsf {Out}=\{(\text {com}({\mathtt {out}_1},r_{\mathtt {out}_1}),Addr_1),\ldots , (\text {com}({\mathtt {out}_n },r_{\mathtt {out}_n }), Addr_n)\}\).

  • Generate Transaction with \(\mathsf {In},\mathsf {Out}\): Compute \(\frac{\prod ^n_{j=1} \text {com}({\mathtt {out}_j},r_{\mathtt {out}_j})}{\prod ^m_{i=1} \text {com}({\mathtt {in}_i},r_{\mathtt {in}_i})}= \text {com} (0, \sum ^n_{j=1} r_{\mathtt {out}_j} - \sum ^m_{i=1} r_{\mathtt {in}_i})\) with \(r_{\mathtt {in}_i}, r_{\mathtt {out}_j} {\mathop {\leftarrow }\limits ^{{\scriptscriptstyle \$}}}{{\mathbb Z}}_q\), include in the transaction the randomness \(\sum ^n_{j=1} r_{\mathtt {out}_j} - \sum ^m_{i=1} r_{\mathtt {in}_i}\) and the range proofs \(\pi \) guaranteeing that \(\mathtt {out}_1, \cdots , \mathtt {out}_n\) are between \([0, 2^l - 1]\). The resulting transaction is then represented by \(\mathsf {tx}=(\mathtt {id},\mathsf {In},\mathsf {Out},\mathsf {Sig}, \sum ^n_{j=1} r_{\mathtt {out}_j} - \sum ^m_{i=1} r_{\mathtt {in}_i}, \pi )\).

  • Validate a Transaction \(\mathsf {tx}\): Compute \(\frac{\prod ^n_{j=1} \text {com}({\mathtt {out}_j},r_{\mathtt {out}_j})}{\prod ^m_{i=1} \text {com}({\mathtt {in}_i},r_{\mathtt {in}_i})}= \text {com}(s,t)\) and check if the obtained commitments is equal to \(\text {com}(0, \sum ^n_{j=1} r_{\mathtt {out}_j} - \sum ^m_{i=1} r_{\mathtt {in}_i})\), guaranteeing that \(\sum ^m_{i=1} \mathtt {in}_i = \sum ^n_{j=1} \mathtt {out}_j\), then check the validity of the range proofs \(\pi \).

  • Spend a transaction output \(\mathsf {Out}\): Parse \(\mathsf {Out}= (\text {com}({\mathtt {out}_i},r_{\mathtt {out}_i}),Addr_i)\). To spend \(\mathsf {Out}\), the commitment \(\text {com}({\mathtt {out}_i},r_{\mathtt {out}_i}) = g^{\mathtt {out}_i}h^{r_{\mathtt {out}_i}}\) has to be opened by revealing \(\mathtt {out}_i\) and \(r_{\mathtt {out}_i}\). Values \(\mathtt {out}_i\) and \(r_{\mathtt {out}_i}\) are included in a regular UTXO transaction and they are described in the full version [20]. Later on, this UTXO transaction can be validated by checking that \(\mathtt {out}_i,r_{\mathtt {out}_i}\) is a valid opening of \(\text {com}({\mathtt {out}_i},r_{\mathtt {out}_i})\) and following the steps of a regular UTXO transaction validation.

  • Spend a transaction output \(\mathsf {Out}\) with a NIZKPoK of \(r_{\mathtt {out}_i}\): Alternatively, an output \(\mathsf {Out}= (\text {com}({\mathtt {out}_i},r_{\mathtt {out}_i}),Addr_i)\) for which only \(\mathtt {out}_i\) and \(\hat{h}=h^{r_{\mathtt {out}_i}}\) (but not \(r_{\mathtt {out}_i}\)) are known can be spent if a NIZK \(\pi '\) proving knowledge of \(r_{\mathtt {out}_i}\) is also available. Notice that knowing \(\mathtt {out}_i\) is sufficient for validating the regular UTXO transaction created using \(\mathsf {Out}\) as an input. Moreover, it can be checked that \(g^{\mathtt {out}_i}h^{r_{\mathtt {out}_i}} = \text {com}({\mathtt {out}_i},r_{\mathtt {out}_i})\) given \(\mathtt {out}_i\) and \(\hat{h}=h^{r_{\mathtt {out}_i}}\), while the proof \(\pi '\) guarantees that \(\hat{h}=h^{r_{\mathtt {out}_i}}\) is well formed.Footnote 1 Values \(\mathtt {out}_i\), \(h^{r_{\mathtt {out}_i}}\) and the proof \(\pi '\) are included in a regular UTXO transaction generated and they are described in the full version [20]. Later on, this UTXO transaction can be validated by checking that \(g^{{\mathtt {out}_i}}h^{r_{\mathtt {out}_i}}=\text {com}({\mathtt {out}_i},r_{\mathtt {out}_i})\), checking that \(\pi '\) is valid and following the steps of a regular UTXO transaction validation.

Publicly Verifiable Secret Sharing (PVSS): In our work, we use the PVSS protocol \(\pi _{PVSS}\) from [15]. A PVSS protocol allows for a dealer to distribute encrypted shares to a set of parties in such a way that only one specific party can decrypt a share but any third party verifier can check that all shares are valid. Later on, each party can decrypt its corresponding share to allow for reconstruction while showing to any third-party verifier that the decrypted share corresponds to one of the initial encrypted shares. A deposit committee \(\mathcal {C}=\{\mathcal {C}_1,\ldots ,\mathcal {C}_m\}\) will execute this protocol verifying and decrypting shares provided as part of our secret deposit mechanism (further discussed in Sect. 3). Since the parties in \(\mathcal {C}\) executing \(\pi _{PVSS}\) must have public keys registered as part of a setup phase, we capture this requirement in \(\mathcal {F}_{\mathsf {SC}}\) as presented in Sect. 2.2.

NIZK for PVSS Share Consistency \(CC\): As part of our secret deposit mechanism (further discussed in Sect. 3), we will use a NIZK showing that shares computed with the PVSS protocol \(\pi _{PVSS}\) from [15] encode secrets \(g^m\) and \(h^r\) that are terms of a Pedersen commitment \(c=g^mh^r\). Formally, given generators \(g_1,\dots ,g_n,g,h\) of a cyclic group \(\mathbb {G}_q\) of prime order q, pairwise distinct elements \( \alpha _1,\dots ,\alpha _n\) in \({{\mathbb Z}}_q\) and a Pedersen commitment \(c=g^mh^r\) known by prover and verifier, for p(x) and m, r known by the prover, this NIZK is used to prove that \((\hat{\sigma }_1,\ldots ,\hat{\sigma }_n)\in \left\{ \left( g_1^{p(\alpha _1)},\dots ,g_n^{p(\alpha _n)}\right) : p\in {{\mathbb Z}}_q[X], p(-1)=g^m, p(-2)=h^r\right\} \). We denote this NIZK by \(CC((g_i)_{i\in [n]},(\alpha _i)_{i\in [n]}, g,h,c, (\hat{\sigma }_i)_{i\in [n]})\). Notice that this NIZK can be constructed using the techniques from [13] and integrated with the NIZK \(LDEI\) (Low-Degree Exponent Interpolation) defined in \(\pi _{PVSS}\) [15].

Modelling a Stateful Smart Contract: We employ a stateful smart contract functionality \(\mathcal {F}_{\mathsf {SC}}\) similar to that of [18] in order to model the smart contract that implements the financial punishment mechanism for our protocol. For the sake of simplicity, we assume that each instance of \(\mathcal {F}_{\mathsf {SC}}\) is already parameterized by the address of the auctioneer party who will receive the payment for the auctioned good, as well as by the identities (and public keys) of the parties in a secret deposit committee \(\mathcal {C}\) that will help the smart contract to open secret deposits given by parties in case cheating is detected. We also assume that \(\mathcal {F}_{\mathsf {SC}}\) has a protocol verification mechanism \(\mathsf {pv}\) for verifying the validity of protocol messages. For description of the \(\mathcal {F}_{\mathsf {SC}}\) see the full version [20].

3 Secret Deposits in Public Smart Contracts

When using secret deposits as in our application, it is implied that there exists a secret trapdoor that can be used to reveal the value of such deposits (and transfer them). However, since we base our financial punishment mechanism on a standard public smart contract, we cannot expose the trapdoor to the smart contract. Instead, we propose that a committee \(\mathcal {C}=\{\mathcal {C}_1,\ldots ,\mathcal {C}_m\}\) with \(m/2+2\) honest membersFootnote 2 holds this trapdoor in a secret shared form. This committee does not act unless a cheating party needs to be punished and the trapdoor needs to be reconstructed to allow the smart contract to transfer her collateral deposit. In this case, the committee can be reimbursed from the collateral funds. We present a practical construction following this approach. Proposing methods for keeping custody of such secret deposits is left as an important open problem.

A Possible Solution: A feasible but not practical approach to do this would be storing the trapdoor with the mechanism proposed in [7], where a secret is kept by obliviously and randomly chosen committees by means of a proactive secret sharing scheme where each current committee “encrypts the secret to the future” in such a way that the next committee can open it. However, it is also necessary to ensure that the secrets actually correspond to the trapdoor for the parties’ deposits. Providing such proofs with the scheme of [7] would require expensive generic zero-knowledge techniques (or a trusted setup for a zk-SNARK).

Fig. 1.
figure 1

Protocol \(\varPi _{\mathcal {C}}\)

Full size image

A Protocol Based on PVSS: As an alternative, we propose leveraging the structure of our confidential transaction based deposits to secret share their openings with a recent efficient publicly verifiable secret sharing (PVSS) scheme called Albatross [15]. Notice that the secret amount information \(b_{i}\) in these deposits is represented as a Pedersen commitment \(g^{b_{i}}h^{r_{i}}\) and that the Albatross PVSS scheme also allows for sharing a group element \(g^s\), while proving in zero-knowledge discrete logarithm relations involving \(g^s\) in such a way that they can be verified by any third party with access to the public encrypted share. Hence, we propose limiting the bid \(b_{i}\) bit length in such a way that we can employ the same trick as in lifted ElGamal and have each party \(\mathcal {P} _{i}\) share both \(g^{b_{i}}\) and \(h^{r_{i}}\) with the Albatross PVSS while proving that their public encrypted shares correspond to a secret deposit \(g^{b_{i}}h^{r_{i}}\). The validity of this claim can be verified by the committee \(\mathcal {C}\) itself or the smart contract during Stage 1 - Setup. Later on, if \(b_{i}\) needs to be recovered, \(\mathcal {C}\) can reconstruct \(g^{b_{i}}\), brute force \(b_{i}\) (because it has a restricted bit-length) and deliver it to the smart contract while proving it has been correctly computed from the encrypted shares. As we explain in Sect. 2, recovering \(b_{i}\) and \(g^{r_{i}}\) along with the proofs of share validity is sufficient for transferring the secret deposit.

In Fig. 1, we present Protocol \(\varPi _{\mathcal {C}}\) followed by the committee \(\mathcal {C}=\{\mathcal {C}_1,\ldots ,\mathcal {C}_m\}\) and executed as part of Protocols \(\varPi _{FPA}\) described in Sect. 4. The interaction of the other parties \(\mathcal {P} =\{\mathcal {P} _1,\ldots ,\mathcal {P} _n\}\) executing Protocols \(\varPi _{FPA}\) and \(\varPi _{SPA}\) with the committee \(\mathcal {C}\) is described as part of Stage 1 - Setup of these protocols.

Selecting Committees: In order to focus on the novel aspects of our constructions, we assume that the smart contract captured by \(\mathcal {F}_{\mathsf {SC}}\) described in the full version [20] is parameterized by a description of the committee \(\mathcal {C}=\{\mathcal {C}_1,\ldots ,\mathcal {C}_m\}\) and the public keys corresponding to each committee member. Notice that in practice this committee can be selected by the smart contract from the set of parties executing the underlying blockchain consensus protocol. The problem of selecting committees in a permissionless blockchain scenario has been extensively addressed in both Proof-of-Stake e.g. [19, 28] and Proof-of-Work [39] settings.

4 First-Price Auctions

In this section, we introduce our protocol for first-price auctions (while the case of second-price auctions is addressed in the full version [20]). We consider a setting with n parties \(\mathcal {P} _1,\ldots ,\mathcal {P} _n\), where each party \(\mathcal {P} _{i}\) has a l-bit bid \(b_{i}=b_{{i}1}|\dots |b_{{i}l}\), where \(b_{ir}\) denotes the \(r\)-th bit of party \(\mathcal {P} _{i}\)’s bid.

Fig. 2.
figure 2

Functionality \(\mathcal {F}_{FPA}\)

Full size image

Modelling Fair Auctions: First, we introduce an ideal model for fair auctions that we will use to prove the security of our protocol. For the sake of simplicity, when discussing this model, we use \(\mathsf {coins}(n)\) to indicate n currency tokens being transferred where n is represented in binary, instead of describing a full UTXO transaction. Our ideal functionality \(\mathcal {F}_{FPA}\) is described in Fig. 2. This functionality models the fact that the adversary may choose to abort but all it may learn is that it was the winner and the most significant bit where its bid differs from the second-highest bid. Regardless of adversarial actions, an auction result is always obtained and the auctioneer (i.e., the party selling the asset) is always paid. The second-price case is presented in the full version [20].

The Protocol: In Figs. 3, 4, 5 and 6, we construct a Protocol \(\varPi _{FPA}\) that realizes \(\mathcal {F}_{FPA}\). This protocol is executed by n parties \(\mathcal {P} _1,\ldots ,\mathcal {P} _n\), where each party \(\mathcal {P} _{i}\) has a l-bit bid \(b_{i}=b_{{i}1}|\dots |b_{{i}l}\) and a deposit committee \(\mathcal {C}=\{\mathcal {C}_1,\ldots ,\mathcal {C}_m\}\) that helps open secret deposits from corrupted parties in the Recovery Stage. The protocol consists of 4 main stages plus a recovery stage, which is only executed in case of suspected (or detected) cheating. In the first stage, every party \(i\) sends to the smart contract a secret deposit, whose structure will be explained in detail later. In the second and third stages, all parties jointly compute the maximum bid (bit-by-bit) by using an anonymous veto protocol that computes a logical OR on private inputs. To this aim, the parties start from the most significant bit position. Then, they apply the anonymous veto protocol according to their bits \(b_{ir}\), with 0 representing a no veto and 1 representing a veto. If the outcome of the veto protocol (i.e., the logical-OR of the the inputs) is 1, then each party \(\mathcal {P} _{i}\) with input \(b_{ir} = 0\) figures out that there is at least another party \(\mathcal {P} _k\) whose bid \(b_k\) is higher than \(b_{i}\) and \(\mathcal {P} _{i}\) discovers that she cannot win the auction. Therefore, from this point on, \(\mathcal {P} _{i}\) stops vetoing, disregarding her actual bit \(b_{ir}\) in the next rounds. Otherwise, \(\mathcal {P} _{i}\) is expected to keep vetoing or not according to her bit \(b_{ir}\). Finally, in Stage 4 the winning party \(\mathcal {P} _w\) executes the payment to the auctioneer (i.e., the party selling the asset). Throughout all stages, the parties must provide proofs that they have correctly computed all protocol messages. If a party is identified as dishonest at any point, the Recovery Stage has to be executed.

Security Analysis: It is clear that this protocol correctly computes the highest bid. The ideal smart contract enforces payment once a winner is determined and punishments otherwise. The security of this protocol is formally stated in the following theorem. A game-theoretical analysis is presented in Sect. 5, where it is shown that the best strategy for any rational party is to follow the protocol.

Theorem 1

Under the DDH Assumption, Protocol \(\varPi _{FPA}\) securely computes \(\mathcal {F}_{FPA}\) in the \(\mathcal {F}_{\mathsf {SC}}\)-hybrid, random oracle model against a malicious static adversary \(\mathcal {A}\) corrupting all but one parties \(\mathcal {P} _i \in \mathcal {P} \) and \(m/2-2\) parties \(\mathcal {C}_i \in \mathcal {C}\).

Due to space limits, we leave the full proof to the full version [20].

Fig. 3.
figure 3

Protocol \(\varPi _{FPA}\) (Off-chain messages exchange)

Full size image
Fig. 4.
figure 4

Protocol \(\varPi _{FPA}\) (Stage 1)

Full size image
Fig. 5.
figure 5

Protocol \(\varPi _{FPA}\) (Stages 2 and 3)

Full size image
Fig. 6.
figure 6

Protocol \(\varPi _{FPA}\) (Stages 4 and Recovery)

Full size image

5 Rational Strategies

In this section, we consider the incentives of parties in our protocols. Note that the set of bidders is fixed through the execution, i.e., once the execution has started, even if it is required to re-execute the protocol, no new bid can be submitted, and it is therefore not possible to gain from the leaked information. Moreover, in case there is a cheating party, the protocols refund the honest parties with her deposit.

We now consider the utility of each party from participating in the protocol. The utility function of a generic party \(\mathcal {P} _{i}\) in the first-price auction is \(u^{ FPA }_i(b_1,\dots ,b_n) = v_i - b_i\) if \(b_i > \max _{j\ne i} b_j\) and 0 otherwise, while in the second-price auction is instead \(u^{ SPA }_i(b_1,\dots ,b_n) = v_i- \max _{j\ne i} b_j\) if \(b_i > \max _{j\ne i} b_j\) and 0 otherwise, where \(v_{i}\) represents the \(\mathcal {P} _{i}\)’s private valuation of what is at stake in the auction. It is known that in the first-price auctions the optimal strategy for each rational party depends on their beliefs regarding other party’s valuations, while in the second-price auction the optimal strategy for each party is to bid an amount equal to her valuation regardless of the strategy of other parties [31, 34], i.e., \(b_i=v_i\).

In case a party \(\mathcal {P} _{i}\) is honest, she always gets her deposit \(work\) back. Then, if she is the winner, she gets what is at stake in the auction and pays \(b_{i}\), while if she is not the winner, she gets her entire deposit \(b_{i} + work\) back. Therefore, by following the protocol each rational party has a non-negative utility, i.e., \(u_i(b_1,\dots ,b_n) \ge 0\). However, if a party cheats her deposit \(b_{i} + work\) is distributed among honest parties. Therefore, the utility of a cheating party, regardless of whether her bid is the highest or not, is \( u_i(b_1,\dots ,b_n) = - (b_i +work) < 0\), which is strictly negative. Therefore, cheating is a dominated strategy for each party, i.e., regardless of what other players do it always results in a lower utility.

The above analysis shows that it is not rational for an adversary \(\mathcal {A}\) controlling a single party to deviate from the protocol. Next, we show that it is also the case for an adversary \(\mathcal {A}\) controlling more than one party. Let \(\mathcal {P} _i, \mathcal {P} _j\) be two parties controlled by \(\mathcal {A}\) and let \(v_{\mathcal {A}}\) be the valuation of the adversary for what is at stake in the auction. Without loss of generality let \(b_i > b_j\). If \(\mathcal {A}\) does not deviate from the protocol, then her utility is either 0 (in case neither \(b_i\) nor \(b_j\) is the winning bid) or \(v_{\mathcal {A}}-b_i\) (in case \(b_i\) is the winning bid). Instead, if \(\mathcal {A}\) deviates from the protocol by making \(\mathcal {P} _i\) dropout, in case \(b_j\) is not the second-highest bid, then her utility is \(-(work+b_i)\). If \(b_j\) is the second-highest bid, \(\mathcal {A}\) gets what is at stake in the auction but her utility is \(v_{\mathcal {A}}-(b_i+work+b_j)\). Therefore \(\mathcal {A}\) always prefers to behave honestly.

Note that it is necessary to have the deposit amount at least equal to the bid. Indeed, let d be any deposit amount smaller than \(b_i\). Then the utility of \(\mathcal {A}\) by making \(\mathcal {P} _i\) drop out the protocol is \(v_{\mathcal {A}}-(d+work+b_j)\), while it is \(v_{\mathcal {A}}-b_i\) by behaving honestly. Therefore, in case \(d+work+b_j < b_i\), \(\mathcal {A}\) prefers to deviate from the protocol to increase her utility. A similar argument shows that in the second-price auction, \(\mathcal {A}\) always prefers to act honestly.

6 Complexity Analysis and Comparison to Other Protocols

In this section, we present concrete estimates for the computational and communication complexity of our first and second-price auction protocols, i.e., \(\varPi _{FPA}\) and \(\varPi _{SPA}\), respectively. We show that, in the first-price case, \(\varPi _{FPA}\) is more efficient than the state-of-the-art protocol SEAL [3]. In the second-price case, we show that \(\varPi _{SPA}\) only incurs a small overhead (dominated by re-executing one round) over \(\varPi _{FPA}\). Note that the complexity of Stages 2 and 3 is based on the NIZK constructions available in the full version [20].

Table 1. First-price auction computational complexity comparison in terms of exponentiations performed by a party \(\mathcal {P} _i \in \mathcal {P} \): n is the number of parties, l is the total number of rounds in Stages 2 and 3 (i.e., bit-length of bids), \(\tau \) is the number of rounds in Stage 2.
Full size table
Table 2. First-price auction communication complexity comparison in terms of transmitted bits by a party \(\mathcal {P} _i \in \mathcal {P} \): n is the number of parties, l is the total number of rounds in Stages 2 and 3 (i.e., the bit-length of bids), \(\tau \) is the number of rounds of Stage 2, \(|{{\mathbb G}}|\) and \(|{{\mathbb Z}}_q|\) indicate the bit-length of elements \(g \in {{\mathbb G}}\) and \(z \in {{\mathbb Z}}_q\) respectively, \(\kappa \) id the security parameter, as defined in Sect. 2.
Full size table

The First-Price Case: A concrete estimate of computational complexity is shown in Table 1 and one for communication complexity is shown in Table 2. We estimate these concrete complexities in terms of the number of exponentiations performed by a party \(\mathcal {P} _i\) and of the number of bits transmitted by a party \(\mathcal {P} _i\) in an execution of protocol \(\varPi _{FPA}\), respectively. Moreover, we compare the complexity of our protocol with SEAL [3], which is the current state-of-the-art protocol for first-price sealed-bid auctions. In a similar way to our protocol, SEAL requires all parties to jointly compute the maximum bid bit-by-bit and is subdivided into a Stage 1 devoted to the setup, a Stage 2 identifying the rounds of the protocol before the first veto and a Stage 3 identifying the rounds of the protocol after the first veto. Hence, we highlight the differences in terms of complexity stage by stage. Note that, in order to make the communication complexities of the two protocols comparable, both of them have been expressed in terms of \(|{{\mathbb G}}|\). Finally, FAST has an additional Stage 4 guaranteeing that the payment from the winning party \(\mathcal {P} _w\) to the auctioneer is executed. On the other hand, SEAL does not guarantee this property. In particular, Stage 4 requires 1 exponentiation per party and has a communication complexity equal to \(2(n-1)|{{\mathbb G}}|\).

The Second-Price Case: The computational and communication complexities of the proposed second-price auction are still linear in the number of agents. That is, assuming that at round \(r\), there is a party who is the only one that is vetoing, then the parties have to re-run the \(r^{th}\) round with one less party. More precisely, by following the notation of Table 1 and 2, let \(\tau \) be the number of rounds in Stage 2, then the computational complexity of Stage 1 and Stage 2 is similar to the first-price auction, that is \(nl+l+8\log l+2\) for Stage 1, and \(8\tau + 10n\tau \) for Stage 2. Let r, be the number of rounds until there is only a single party who is veto-ing. Therefore the computational complexity of Stage 3 is \(19r+22nr\) until there is only a single veto. After this, the parties have to run the protocol with one less party, i.e., \(n-1\) parties. Depending on the bid structure of the remaining \(n-1\) parties, the protocol is either in Stage 2 or Stage 3. Let \(\tau '\) denote the number of rounds until the remaining \(n-1\) parties get a veto. Then the computational complexity for these \(\tau '\) rounds would be \(8\tau ' + 10(n-1)\tau '\), and for the remaining \(l-(\tau +\tau '+r)\) it would be \(19\big (l-(\tau +\tau '+r)\big )+22(n-1)\big (l-(\tau +\tau '+r)\big )\). Using the same notation, a similar argument follows for the communication complexity per party in the case of the second-price auction.