# Publicly VerifiableM + 1st-Price Auction Fit for IoT with Minimum Storage

Authors: Po-Chu Hsu; Atsuko Miyaji
Journal: Security and Communication Networks
 (2021)

---

## Abstract

In anM+1st-price auction, all bidders submit their bids simultaneously, and the M highest bidders purchase M identical goods at the M+1st bidding price. Previous research is constructed based on trusted managers such as a trusted third party (TTP), trusted mix servers, and honest managers. All of the previous auctions are not fit for edge-assisted IoT since they need TTP. In this paper, we formalize a notion of commutative bi-homomorphic multiparty encryption and achieve no-TTP M+1-st auction based on blockchain with public verifiability. Our M+1st auction guarantees financial fairness, robustness, and correctness without TTP and is secure under a malicious model for the first time. Our M+1st auction can be executed over a distributed network and is thus fit for edge-assisted IoT. Furthermore, our formalized commutative bi-homomorphic multiparty encryption can be used in various applications for edge-assisted IoT, which needs to protect privacy and correctness.


---

## Body

## 1. Introduction

Since the introduction of Ethereum [1], a smart contract has become a robust decentralized execution environment for many applications. A variety of applications have been built on Ethereum. For example, cryptocurrency wallets, decentralized markets, and games are just a few examples. In this paper, we study secure auctions as an example of smart contracts.Vickrey auction is also called second-price auction. In a second-price auction, the bidder who placed the highest bid only needs to pay the second-highest bidding price for the goods. Except for the identity of the highest bidder and the second-highest price, all other information is kept a secret. A 2nd-price auction is a type of sealed-bid auction. In a sealed-bid auction, bidders submit written bids without knowing other bidders’ bids.M+1st-price auction is an extension of second-price auction. In M+1st-price auction, there are M identical goods. The bidders who placed top M bids only need to pay the M+1st bidding price for the goods. Ideally, all information except the M+1st price and the bidders who placed the M highest bids are kept as a secret. Figure 1 shows an example of M+1st auction for M=2 goods. The top two bidders B4 and B2 can buy the goods by $500. Except the boxed information, all other information is kept as a secret. Table 1 shows the public and secret information in a M+1st-price auction.Figure 1
All but boxed information should be secret (example ofM+1st auction for M=2).Table 1
Public and secret information inM+1st-price auction.
Other biddersTopM+1st bidderTopM winning biddersIdentitySecretSecretPublicPriceSecretPublicSecretThere are many applications using IoT devices such as smart agriculture [2], smart grid [3], and raw materials [4], all of which will use price decision procedures. In the price decision procedures, the second-price auction is said to be a method that reflects market prices and is used in various situations. The M+1st auction is the second-price auction that deals with M products. This is why M+1st auctions are exactly one of the important applications since they can use M products at once.To achieve a secureM + 1st auction, there are two main issues: correctness and public verifiability. Usually, correctness and public verifiability are realized by using trusted third party (TTP) as an auctioneer and mix and match [5]. Abe and Suzuki [6] introduced one of the first auction protocols based on homomorphic encryption. The bidding price is a bounded range. Bidders can only choose one bid from this pricing list. Many related research studies [7, 8] have a similar design such that the time or communication complexity is related to the length of the bidding price list P. To solve this problem, Mitsunaga et al. [9] proposed a scheme that uses a binary format to represent bidding vectors. This improvement reduced the time complexity to logP. In this research, instead of further improving complexity, we focus on removing the trusted parties, such as manager and mix servers. Based on Abe and Suzuki’s scheme [6], we removed TTP by letting bidders collaboratively act as managers and mix servers. This strategy can also be used in follow-up research studies [7–9]. In our preliminary version of [10], we construct a verifiable M+1st-price auction without manager. In the journal version, we implement the smart contract and reduce the computation cost by using elliptic curve cryptography.Auctioneer in a sealed-bid auction is usually a trusted person since he can see the secret information. To construct a scheme that no party, such as manager, bidder, smart contract, and trusted third party (TTP), knows secret information, a typical method is to divide a function of manager into two independent parties as in [7]. In their scheme, no single managers or bidders know this secret information. However, this scheme is based on the pth root problem, which causes high time complexity and requires massive memory usage by public parameters and bid values.Mix and match [5] is widely used in auction protocols such as bit-slice-based auction [9, 11, 12] as well as [6] to verify if each encrypted bit is either E0 or E1. Mix and match can be divided into mix phase and match phase. The mix phase is based on mix net [13, 14] to shuffle a set of encrypted messages. The match phase is usually based on zero-knowledge proofs to prove that the encrypted message is in the shuffled set. Mix net not only relied on TTP but also increased communication costs. In summary, previous schemes need TTP.


### 1.1. Our Contribution

We proposed a secureM+1st auction, which satisfies the following features:(1)
Multiparty encryption: our multiparty encryption is asynchronous.The order of decryption does not depend on the order of encryption, which makes the decryption asynchronous for the decryptors. So, decryptors do not need to wait for each other.(2)
Publicly verifiableM+1st auction: our M+1st auction does not use mix and match in bid verification phase and does not use TTP in the whole protocol.(a)
No mix and match protocol in bid verification: our protocol does not rely on mix and match unlike [6, 9, 11, 12]. Our new approach can also be used on bit-slice-based auction protocols [9, 11, 12] and all other auction protocols, which is based on encrypted bits.(b)
No TTP: in the M+1st-price decision phase, we modify mix and match by letting bidders act as mix servers, and thus no trusted mix server is used. Our M+1st-price auction is secure under a malicious model that guarantees financial fairness, robustness, and correctness without any other party such as manager and TTP. We remark that our scheme can be operated without TTP, and thus any bidder can start auction freely by using their IoT devices. Our decentralized auction exactly fits for IoT environment.This paper is organized as follows. We introduce the related studies on smart contract auction protocols in Section2 and explain cryptographic backgrounds in Section 3. We propose an efficient and secure M + 1st-price auction protocol in Section 4 and compare our work with the related works in Section 6. Finally, we conclude our work in Section 7.


## 1.1. Our Contribution

We proposed a secureM+1st auction, which satisfies the following features:(1)
Multiparty encryption: our multiparty encryption is asynchronous.The order of decryption does not depend on the order of encryption, which makes the decryption asynchronous for the decryptors. So, decryptors do not need to wait for each other.(2)
Publicly verifiableM+1st auction: our M+1st auction does not use mix and match in bid verification phase and does not use TTP in the whole protocol.(a)
No mix and match protocol in bid verification: our protocol does not rely on mix and match unlike [6, 9, 11, 12]. Our new approach can also be used on bit-slice-based auction protocols [9, 11, 12] and all other auction protocols, which is based on encrypted bits.(b)
No TTP: in the M+1st-price decision phase, we modify mix and match by letting bidders act as mix servers, and thus no trusted mix server is used. Our M+1st-price auction is secure under a malicious model that guarantees financial fairness, robustness, and correctness without any other party such as manager and TTP. We remark that our scheme can be operated without TTP, and thus any bidder can start auction freely by using their IoT devices. Our decentralized auction exactly fits for IoT environment.This paper is organized as follows. We introduce the related studies on smart contract auction protocols in Section2 and explain cryptographic backgrounds in Section 3. We propose an efficient and secure M + 1st-price auction protocol in Section 4 and compare our work with the related works in Section 6. Finally, we conclude our work in Section 7.


## 2. Related Work

This section reviews previous auction protocols which use a smart contract.


### 2.1. Overview of Auction

We define necessary features for auction protocol(i)
Bid binding: bidders cannot change their bidding price after the bid submission phase is closed.(ii)
Bid secrecy: all bidding prices except theM+1st-price should be kept secret.(iii)
Bidder anonymity: except for the winning bidder, the identity of other bidders, including the bidder who placed theM+1st-price, is kept secret.(iv)
Manager-based secrecy and anonymity: except those explained above, all secrets are also disclosed to the manager.(v)
Posterior secrecy and anonymity: all secrets can be a secret even after the auction.(vi)
Robustness: malicious behaviors in each phase can be found immediately. Timeouts are set to make sure the auction ends within a determined time.(vii)
Public verifiability: all procedures can be publicly verified.(viii)
Correctness: the auction has correctly proceeded as defined in the auction protocol.(ix)
Financial fairness: malicious parties need to compensate other parties. Usually, all parties need to deposit some Ether in the smart contract as a stake.


### 2.2. Hawk

Hawk executes smart contracts while keeping secrets [15] when a bidder and a manager exchange data in the following way. (1) When the protocol starts, the bidders and the manager deposit some Ether to the smart contract as a stake. (2) Zero-knowledge proof (zk-SNARK) is attached with all messages sent by the manager and bidders. (3) Smart contract verifies the zero-knowledge proof and the time limit in each phase. In the Hawk protocol, since the bid amount of all bidders is leaked to the manager by design, it is necessary to assume that the manager does not leak any information inappropriately or collude with any party. In other words, the manager has to be a trusted third party. The Hawk protocol achieves bid binding, bid secrecy, bidder anonymity, manager-based secrecy and anonymity, posterior secrecy and anonymity, robustness, correctness, public verifiability, and financial fairness.


### 2.3. Verifiable Sealed-Bid Auction Protocol

Another verifiable sealed-bid auction protocol [8] was proposed by using a smart contract and Pedersen commitment scheme [16]. In this protocol, there are bidders and managers, just as in Hawk. The manager and a bidder pay a deposit to the smart contract, and the bidder simultaneously sends a bid commitment to the smart contract. Next, the bidder encrypts the value by the manager’s public key and opens the commitment to the smart contract. The manager determines the winning bid and winner, sends the commitment of the winning bid to the smart contract, and proves to the smart contract that the winning bid is higher than any other bid. This scheme achieves bid binding, bid secrecy, manager-based secrecy, posterior secrecy, robustness, correctness, and financial fairness.


### 2.4. Other Related Works

Wu et al. proposed a smart contract-enabled collusion-resistant e-auction [17], which is well organized and provides many experimental data. However, bidder anonymity is revealed when commitments have been opened. Blockchain-based smart contract for bidding system [18] has the same problem as [17] although they used a blockchain called MinerGate. It also reveals secrets at the end of the auction. Galal also proposed a full privacy-preserving Vickrey auction on top of Ethereum [19], whose design is similar to Hawk. All bidders encrypt their bids by managers of public key. The manager uses Intel SGX to decrypt each bids and determine a winner. Thus, it only satisfies manager-based secrecy and anonymity.


## 2.1. Overview of Auction

We define necessary features for auction protocol(i)
Bid binding: bidders cannot change their bidding price after the bid submission phase is closed.(ii)
Bid secrecy: all bidding prices except theM+1st-price should be kept secret.(iii)
Bidder anonymity: except for the winning bidder, the identity of other bidders, including the bidder who placed theM+1st-price, is kept secret.(iv)
Manager-based secrecy and anonymity: except those explained above, all secrets are also disclosed to the manager.(v)
Posterior secrecy and anonymity: all secrets can be a secret even after the auction.(vi)
Robustness: malicious behaviors in each phase can be found immediately. Timeouts are set to make sure the auction ends within a determined time.(vii)
Public verifiability: all procedures can be publicly verified.(viii)
Correctness: the auction has correctly proceeded as defined in the auction protocol.(ix)
Financial fairness: malicious parties need to compensate other parties. Usually, all parties need to deposit some Ether in the smart contract as a stake.


## 2.2. Hawk

Hawk executes smart contracts while keeping secrets [15] when a bidder and a manager exchange data in the following way. (1) When the protocol starts, the bidders and the manager deposit some Ether to the smart contract as a stake. (2) Zero-knowledge proof (zk-SNARK) is attached with all messages sent by the manager and bidders. (3) Smart contract verifies the zero-knowledge proof and the time limit in each phase. In the Hawk protocol, since the bid amount of all bidders is leaked to the manager by design, it is necessary to assume that the manager does not leak any information inappropriately or collude with any party. In other words, the manager has to be a trusted third party. The Hawk protocol achieves bid binding, bid secrecy, bidder anonymity, manager-based secrecy and anonymity, posterior secrecy and anonymity, robustness, correctness, public verifiability, and financial fairness.


## 2.3. Verifiable Sealed-Bid Auction Protocol

Another verifiable sealed-bid auction protocol [8] was proposed by using a smart contract and Pedersen commitment scheme [16]. In this protocol, there are bidders and managers, just as in Hawk. The manager and a bidder pay a deposit to the smart contract, and the bidder simultaneously sends a bid commitment to the smart contract. Next, the bidder encrypts the value by the manager’s public key and opens the commitment to the smart contract. The manager determines the winning bid and winner, sends the commitment of the winning bid to the smart contract, and proves to the smart contract that the winning bid is higher than any other bid. This scheme achieves bid binding, bid secrecy, manager-based secrecy, posterior secrecy, robustness, correctness, and financial fairness.


## 2.4. Other Related Works

Wu et al. proposed a smart contract-enabled collusion-resistant e-auction [17], which is well organized and provides many experimental data. However, bidder anonymity is revealed when commitments have been opened. Blockchain-based smart contract for bidding system [18] has the same problem as [17] although they used a blockchain called MinerGate. It also reveals secrets at the end of the auction. Galal also proposed a full privacy-preserving Vickrey auction on top of Ethereum [19], whose design is similar to Hawk. All bidders encrypt their bids by managers of public key. The manager uses Intel SGX to decrypt each bids and determine a winner. Thus, it only satisfies manager-based secrecy and anonymity.


## 3. Preliminaries

Definition 1 (DDH assumption).
Lettbe a security parameter. A decisional Diffie–Hellman (DDH) parameter generatorIGis a probabilistic polynomial time (PPT) algorithm that takes an input1kand outputs the description of a finite fieldFpand a basepointg∈Fpwith the prime orderq. We say thatIGsatisfies the DDH assumption ifϵ=p1−p2is negligible (inK) for all PPT algorithmsA, wherep1=PRFp,g⟵IG1K;y1=gx1,y2=gx2⟵Fp:AFp,g,y1,y2,gx1x2=0andp2=PrFp,g⟵IG1K;y1=gx1,y2=gx2,z⟵Fp:AFp,g,y1,y2,z=0.Definition 2 (ElGamal encryption [20]).
Letp and q be large primes. Let g denote a prime subgroup of ℤp∗ generated by g whose order is q. Given a message m∈ℤp∗, we define ElGamal [20] encryption as Encym=gr,m⋅yr, where y is the public key and r∈ℤq∗. Given a ciphertext c=gr,m⋅yr, decryption is defined as Decxc=m, where x is the private key.Theorem 1 (plaintext equivalence proof of ElGamal ciphertext).
Given an ElGamal ciphertextgr,myr and a plaintext m′, the encryptor can prove the value of m=m′ without revealing r. This type of proof is based on the proof of equality of two discrete logarithms. i.e., gr and myr/m′ share the same discrete logarithm r.Theorem 2 (proof of knowledge of a discrete logarithm).
Giveng∈ℤp and x∈ℤq∗, the knowledge of gx’s discrete logarithm x can be proved without revealing x.Theorem 3 (proof of equality of two discrete logarithms).
Giveng1,g2∈ℤp and x1,x2∈ℤq∗, the proof of g1x1 and g2x2 has same discrete logarithm x1=x2 that can be proved without revealing x1 and x2. This type of proof is a variation of the proof of knowledge of a discrete logarithm (Theorem 2).Protocol 1 (mix and match).
Mix and match [5] is a technique used to examine whether the decryption of a ciphertext Decc belongs to a set of plaintexts. It is based on mix net, which can perform verifiable secret shuffle. The mix server only knows their own permutation, and they do not know the plaintext. MixMatchc,S:Input: ciphertextc and a set of plaintexts S=m1,m2,…,mn.Output: true ifDecc∈S. Otherwise, output false.(1)
Constructn ciphertext by C=c/Em1,…,c/Emn=C1,…,Cn.(2)
For each mix server(a)
CalculateC′=C1r1,…,Cnrn where ri is a secret random value.(b)
Generate a random permutationpm.(c)
Shuffle these ciphertexts:ShuffleC′,pm=C″,π.(d)
SendC″ to next mix server and publish π.(3)
Use a publicly verifiable way to decrypt the outputC″ of the last mix server.(4)
If there exists one plaintext 1, then output true. Otherwise, output false.Protocol 2 (verifiable secret shuffle).
Verifiable secret shuffle is a technique for mix and match, which is designed to use multiple mix servers (TTP) to secretly shuffle ciphertexts.ShuffleC,pm=C′,π:Input:n ciphertexts C=Encm1,…,Encmn.Output: shuffled ciphertextsC′=Encmpm1,…,Encmpmn and the proof π, where pm⋅ is a secret permutation.Protocol 3 (bit-slice).
Bit-slice is a common technique used in many auction protocols. Assume that the maximum bidding price is 8 dollars. If bidder wants to buy the goods by 6 dollars, the bidder can compose a bidding vectorV by E0 and E1. Figure 2 gives an example of a bit-slice bidding vector. The bidding vector can also be presented by a binary format [9, 12] to reduce its size. Figure 3 gives an example of a binary format bidding vector.Algorithm 1 (binary search).
Binary search [21] is an algorithm used to search an ordered list; it can reduce the time complexity to OlogN, where N is the number of elements; BiSearchA,cmp=i:Input: given an ordered listA of N elements and a compare function cmp.Output: the indexj of the target element Aj. If there is no element that satisfies the condition, output the largest i where cmpi=−1.Figure 2
Example of bit-slice bidding vector.Figure 3
Example of bit-slice bidding vector in binary format.


## 4. Our Scheme

Mix servers in mix and match perform verifiable secret shuffle. However, the mix servers can leak the secret permutation to the bidder or the manager. In an auction, let bidder act as mix server that can still be secure because each bidder can only know their permutation. As bidders are counterparties, they have no incentives to leak their secret permutation to others. The design of this protocol is simple, and no additional parties such as manager and TTP are needed.A notion of commutative encryption is extended to multiparty encryption, which is fit for encryption schemes in smart contract protocol. During decryption, each secret key holder can send their decryption message to the smart contract concurrently. Without this, if the ciphertext is not decrypted before timeout, the responsibility of failure is hard to define. The last honest decryptor might be punished simply because the previous decryptor takes too much time. Also, transaction settlement takes time. It can be time costly for decryptors to decrypt things one by one.


### 4.1. Multiparty Encryption

A concept of commutative encryption was introduced in [22]. However, to better fit the asynchronous nature of smart contract protocol, we re-formalize it as multiparty encryption here. Without losing generality, we use n=2 case to explain.Definition 3 (multiparty encryption).
Let the public and private key pairs of the public key cryptosystem of the party bey1,x1 and y2,x2, respectively. The ciphertext of plaintext using the public key yi is Encyim, and the decryption is DecyiEncyim. When public key cryptosystem satisfies the following, the public key cryptosystem is called a multiparty encryption cryptosystem.(i)
Full Encryption. We define the encryption using the public keyy2for the ciphertext encrypted with public keyy1for a plaintextmthrough the following operation.(1)Ency1⋅y2m=Ency2Ency1m.(ii)
Partial Decryption. We define the decryption performed by each party for the ciphertextEncy1⋅y2mencrypted with the public keysy1,y2for the plaintextmthrough the following operation.(2)Decy1Ency1⋅y2m=Ency2m,Decy2Ency1⋅y2m=Ency1m.(iii)
Full Decryption. We define the decryption performed by both parties for the ciphertextEncy1⋅y2mencrypted with the public keysy1,y2for the plaintextmthrough the following operation.(3)Decy1Decy2Ency1⋅y2m=m.Definition 4 (commutative).
For a given encryptionEncy1⋅y2m, if(4)Decy1Decy2Ency1⋅y2m=Decy2Decy1Ency1⋅y2m=m,is satisfied, then the encryption is a commutative.Definition 5 (bi-homomorphic).
When a encryption satisfies the following properties, we say that the encryption is bi-homomorphic.(i)
Ency1⋅y2m⋅Ency1m˜=Ency1⋅y2m⋅m˜(ii)
Ency1⋅y2m⋅Ency2m˜=Ency1⋅y2m⋅m˜(iii)
Ency1⋅y2m⋅Ency1⋅y2m˜=Ency1⋅y2m⋅m˜(iv)
Ency1⋅y2mω=Ency1⋅y2mω
The multiparty encryption based on the ElGamal encryption is defined as follows, which will be proved to be bi-homomorphism.(i)
Full Encryption. The encryption using the public keys y2 and y1 is as follows.(5)Ency1⋅y2m=u1,u2,c,where,u1=gr1,u2=gr2andc=m⋅y1r1y2r2.(ii)
Partial Decryption. The partial decryption for a ciphertext Ency1⋅y2m by each party y1 or y2 is as follows.(6)Decy1Ency1⋅y2m=u2,c⋅u1−x1=u2,my2r2=Ency2m,Decy2Ency1⋅y2m=u1,c⋅u2−x2=u1,my1r1=Ency1m.(iii)
Full Decryption. The decryption performed by both parties for the ElGamal ciphertext Ency1⋅y2m encrypted with the public keys y1 and y2 for the plaintext m is defined as follows.(7)Decy1Decy2Ency1⋅y2m=Decy1Ency1m=m.
Thus, the multiparty ElGamal encryption scheme satisfies partial decryption, full decryption, and commutative encryption. We also show that the multiparty ElGamal encryption satisfies the commutative encryption with bi-homomorphism as follows.Theorem 4.
The multiparty ElGamal encryption satisfies the commutative encryption with bi-homomorphism.Proof.
For two given ciphertextsEncy1⋅y2m=u1,u2,c and Ency1m˜=u1˜,c˜ with u1=gr1,u2=gr2,u1˜=gr1˜,c=m⋅y1r1y2r2,c˜=m˜⋅y1r1˜, the multiplication of the ciphertexts is as follows.(8)Ency1⋅y2m⋅Ency1m˜=u1,u2,c⋅u1˜,c˜=u1u1˜,u2,cc˜=Ency1⋅y2m⋅m˜.
For two given ciphertextsEncy1⋅y2m=u1,u2,c and Ency2m˜=u2˜,c˜with u1=gr1,u2=gr2,u2˜=gr2˜,c=m⋅y1r1y2r2,c˜=m˜⋅y2r2˜, the multiplication of the ciphertexts is as follows.(9)Ency1⋅y2m⋅Ency2m˜=u1,u2,c⋅u2˜,c˜=u1,u2u2˜,cc˜=Ency1⋅y2m⋅m˜.
For two given ciphertextsEncy1⋅y2m=u1,u2,c and Ency1⋅y2m˜=u1˜,u2˜,c˜ with u1=gr1,u2=gr2,c=m⋅y1r1y2r2,u1˜=gr1˜,u2˜=gr2˜,c˜=m˜⋅y1r1˜y2r2˜, the multiplication of the ciphertexts is as follows.(10)Ency1⋅y2m⋅Ency1⋅y2m˜=u1,u2,c⋅u1˜,u2˜,c˜=u1u1˜,u2u2˜,cc˜=Ency1⋅y2m⋅m˜.
For a given ciphertextEncy1⋅y2m=u1,u2,c with u1=gr1,u2=gr2,c=m⋅y1r1y2r2, the exponentiation of the ciphertext is as follows.(11)Ency1⋅y2mω=u1ω,u2ω,cω=gr1ω,gr2ω,mω⋅y1r1ωy2r2ω=Ency1⋅y2mω.
By using Theorem1, we can make the verifiable partial decryption as follows.Theorem 5 (verifiable partial decryption).
A decryptor (party 2) can prove that a decrypted ciphertextEncy1=u1,c1 is a partial decryption of Ency1⋅y2m=u1,u2,c without revealing x2 by showing a same discrete logarithm proof that y2=gx2 and u2−x2=u2−1x2 has same discrete log x2.(12)SPKα:c/c1≡y2α∧u2≡gαm.


### 4.2. Our Auction Protocol

Our protocol consists of a seller, who sellsM goods at a fixed set of prices 1,…,P, and bidders, who bid a price for the goods. The top M bidders can buy the goods by the M+1st price. Remark that no other party except the seller of bidders is required in our protocol.Our protocol consists of 7 phases as follows.(1)
Smart contract deployment: the seller sets necessary parameters and initialization.(2)
Bidder initialization: bidders who are interested in the auction submit their stake and join the auction.(3)
Submission of bids by bidders: bidders decide their bid and submit it to the smart contract.(4)
Bid verification: verify all bidders’ bid.(5)
M+1st-price decision: find out the M+1st bidding price.(6)
Winner decision: find out the highest M bidders who are winners of the auction.(7)
Payment: the winning bidders pay the seller the M+1st price to buy the goods.The protocol is described in detail as follows.


#### 4.2.1. Smart Contract Deployment

The seller decides the following parameter and deploys the smart contractSC to start the auction.(i)
Cryptographic parameters: large primep, a basepoint g with prime order q, and an auction base z⟵ℤp/0,1.(ii)
Seller initialization:(1)
Bidding price listp1,…,pP.(2)
Timeouts for each phaseT1,…,T6: if a bidder failed to submit valid messages to smart contract within the timeout, the bidder will be treated as a malicious bidder and be financially penalized.(3)
Stake requirementd: bidders are required to submit d amount of Ether as stake to join the auction.


#### 4.2.2. Phase 1: Bidder Initialization

Bidders submityi,πi1 to SC within time T1 as follows. We assume that there are more than M+1 bidders.(i)
Each bidderBi,i∈1,…,B computes the following and submits it to SC:(1)
Compute a public keyyi=gxi for the ElGamal encryption, where xi⟵ℤq is a randomly chosen secret key.(2)
Compute a proofπi1 of yi=gxi as a conventional way of a proof of knowledge of yi’s discrete logarithm xi described in Section 3 and d amount of Ether as stake.(ii)
After this phase ends, an aggregated public keyY=∏i=1Byi can be calculated by SC.


#### 4.2.3. Phase 2: Submission of Bids by Bidders

All bidders submitVi,Vi′,πi2 to SC within time T2 as follows: see Figure 4 for Vi and Vi′. Bidders B2 and B3 win the auction and pay pjM+1=p2 for the goods.(i)
Bi,i∈1,…,B, computes the below and submits it to SC:(1)
Bidding vectorVi=Vi1,…,ViP.(2)
Shuffled bidding vectorVi′=Vi,pm1,…,Vi,pmP.(3)
A proof of secure shuffleπi2.(13)Vij=Z1,ifj=bi,Z0,ifj≠bi..Figure 4
Example ofM=2 with 3 bidders and 5 bidding prices.A bidderBi first chooses a bidding point bi∈1,…,P corresponding to bidding price pbi, constructs a bidding vector Vi, and shuffles Vi to Vi′, while making a proof of the secure shuffle:(14)πi2,Vi′=shuffleVi,pmi,where pmi is a secret permutation generated by Bi. This Vi′ is used for the verification of Vi. In phase 3, we can decrypt Vi′ to verify Vi without leaking Vi.(i)
SC calculates the following array ai for Bi and c for bidding price after receiving all Vi,pmi (see Figure 4 for ai and c).(1)
Compute arrayai=ai1,…,aiP for each bidder Bi:(15)aij=∏k=jPVik=Z∑k=jPtik1≤j≤p.For anyj, a value of aij is equal to Z1 if bi≥j, where bi is Bi’s bidding point. Otherwise, aij=Z0. The time complexity is OP, by computing aij=aij+1⋅Vij.(2)
Compute arrayc=c1,…,cP for each bidding price p1,…,pP:(16)cj=∏i=1Baij=Z∑i=1B∑j=1Ptij1≤j≤p.The value ofcj is the number of bidders whose bid bi is larger than or equal to j.


#### 4.2.4. Phase 3: Bid Verification

A bidder can only bid on one price. So, correct bidding vectorsVi consists of P−1 times of Z0 and one Z1. Since bidder Bi also submitted Vi′, a shuffled Vi, we can simply decrypt Vi′ to verify if it consists of P−1 times of Z0 and one Z1 within time T3. The decryption will not leak any secret since the shuffled bidding vector Vi′ does not contain any secret.(i)
SC verifies all bidder Bi’s bid Vi:(1)
Decrypt the shuffled bidding vectorVi′:(17)mi1,…,miP=DecVi1′,…,DecViP′.(2)
Verify if there is exactlyP−1 times of z0 and one z1 in mi1,…,miP.


#### 4.2.5. Phase 4:M+1st-Price Decision

By using mix and match,SC and all Bi determine the M+1st price within T4. In array c=c1,…,cP, the value of cj is the number of bidders Bi whose bid bi is larger than or equal to bidding point j. Thus, we can use mix and match to find out the bidding point j where Deccj∉z0,z1,…,zM, but Deccj+1∈z0,z1,…,zM. This j is the M+1st price’s bidding point. Since the c array is a decrementing array, binary search can speed up the search. We use jM+1st as a symbol to this j.(i)
By all bidders’ help,SC finds the bidding point j that MixMatchcj,z0,z1,…,zM=False but MixMatchcj+1,z0,z1,…,zM=True. Assume cmp is the compare function of binary search (Algorithm 1). BiSearch will return the j where cmpcj=−1 but cmpcj+1=1. This j is the M+1st price.(18)jM+1st=BiSearchc,cmp,cmpcj=1,ifMixMatchcj,z0,z1,…,zM=True,−1,otherwise..


#### 4.2.6. Phase 5: Winner Decision

In this phase, by decrypting all bidders’ai,jM+1st+1 within time T5, the winners can be easily found. In this phase, bid secrecy holds because the bid bi can be any number between jM+1st+1 and P.(i)
By all bidders’ help,SC decrypts ai,jM+1st+1 for all i∈1,…,B.(19)δi=DECai,jM+1st+1=z∑k=jPtik.BidderBi with δi=z1 wins the auction.


#### 4.2.7. Phase 6: Payment

The bidders who win the auction senddpjM+1st amount of Ether (in Wei) to the seller through SC.(i)
All winning biddersBi send dpjM+1st amount of Ether (in Wei) to SC.(ii)
SC sends dpjM+1stM amount of Ether (in Wei) to the seller and refunds the stakes to all bidders.


### 4.3. Features and Security

In this section, we discuss the features and security of our protocol.(i)
Bid binding: according to our implementation, the functions in SC will not allow bidders to change their bidding point after the bid submission phase is closed.(ii)
Bid secrecy: the bidding vectors V1,…,VB are encrypted by all bidders’ public keys Y=y1⋯yB. Without all bidders’ collaboration, the bid is kept a secret. Even though V′ is decrypted, it is a permutation of V. Thus, decrypting V′ will not leak any secret. The secrecy of top M bids is protected in phase 5. If ai,jM+1st+1 is an encrypted z1, all bids from ai,jM+1st+1 to aiP can contain z1.Unless all bidders collude, the bid secrecy will be satisfied in the mix and match used in Phase 4. In the mix part, ciphertexts are re-randomized and secretly shuffled by all bidders. Without all bidders colluding, the permutation of shuffled ciphertexts cannot be identified. In the match part, the shuffled ciphertexts can be decrypted by only all bidders’ collaboration.(iii)
Bidder anonymity: since c1,…,cP are products of ciphertexts generated by all bidders, i.e., cj=∏i=1Baij. The proof of Deccj=zM will not leak aij,i=1,…,B. Thus, the identity of the M+1st bidder is still a secret.(iv)
Posterior secrecy and anonymity: the bidding points bi,i=1,…,B and bidding vectors Vi,i=1,…,B are still secrets even after the auction. Thus, posterior secrecy and anonymity still hold.(v)
Robustness: since all messages sent to the smart contract are attached with a proof, malicious behaviors in each phase can be found immediately. The timeouts T1,…,T6 are also set for each phase to ensure that the auction ends within a determined time. Therefore, this protocol provides robustness even in malicious models.(vi)
Public verifiability: all messages sent to SC are attached with a publicly verifiable non-interactive proof, which can be verified by smart contract immediately. Therefore, the correctness of the protocol is publicly verifiable.(1)
Phase 1: Bidder Initialization. A public key yi=gxi is submitted by each bidder Bi to SC, i=1,…,B. The proof of knowledge of xi is publicly verifiable. Thus, the correctness of the public key is publicly verifiable.(2)
Phase 2: Submission of Bids by Bidders. A secure shuffled bidding vector Vi′ is submitted by each bidder Bi to SC, i=1,…,B. The proof that Vi′ is a secure shuffle of Vi is publicly verifiable.(3)
Phase 3: Bid Verification. Let Vi′=Vi1′,…,ViP′=ui1,vi1,…,uiP,viP. BP decryption messages uijxi;i=1,…,B;j=1,…,P are submitted by each bidder Bi. The proof of the same discrete logarithm that uijxi and public key yi=gxi have the same discrete logarithm xi is publicly verifiable. If Vi′ is valid, then Vi is a valid bidding vector. Thus, the verification on bidding vectors Vi,i=1,…,B is publicly verifiable.(4)
Phase 4:M+1st-Bid Decision. A verifiable mix and match [5] is performed in this phase. The validity of the M+1st bidding point j where MixMatchcj,z0,z1,…,zM=False but MixMatchcj+1,z0,z1,…,zM=True is publicly verifiable. Thus, the M+1st bidding price is publicly verifiable.(5)
Phase 5: Winner Decision. Let aij=uij,vij. B decryption messages ui,jM+1st+1xi;i=1,…,B are submitted by each bidder Bi. Therefore, the decryption on ai,jM+1st+1 is verifiable. The decision of winners is publicly verifiable.(vii)
Correctness:(1)
Phase 1: Bidder Initialization. All public keys yi=gxi,i=1,…,B are publicly verified. Thus, the correctness holds.(2)
Phase 2: Submission of Bids by Bidders. All secure shuffled bidding vectors Vi′,i=1,…,B are publicly verified. Vi′ is a secure shuffle of Vi. The correctness holds.(3)
Phase 3: Bid Verification. A correct bidding vector Vi should contain P−1 amount of Z0 and one Z1. Since Vi′ is a secure shuffle of Vi, Vi is correct if and only if Vi′ also contains P−1 amount of Z0 and one Z1. Thus, the correctness holds.(4)
Phase 4:M+1st-Bid Decision. The bidding point jM+1st is correct since MixMatchcjM+1st,z0,z1,…,zM=False, but MixMatchcjM+1st+1,z0,z1,…,zM=True. There are less than M bidders’ bids that are larger than or equal to jM+1st+1, but there are more than M bidders’ bids that are larger than or equal to jM+1st+1. Thus, jM+1st is the M+1st bidding point. The correctness holds.(5)
Phase 5: Winner Decision. If ai,jM+1st+1=Z1, then the bidder Bi’s bidding point bi is larger than or equal to jM+1st+1. Thus, this bidder is a winning bidder. The correctness holds.(viii)
Financial fairness: all bidders deposit d amount Ether (in Wei) in the smart contract as a stake in phase 1. In the failure condition part, malicious bidders will compensate other bidders by their stake.


## 4.1. Multiparty Encryption

A concept of commutative encryption was introduced in [22]. However, to better fit the asynchronous nature of smart contract protocol, we re-formalize it as multiparty encryption here. Without losing generality, we use n=2 case to explain.Definition 3 (multiparty encryption).
Let the public and private key pairs of the public key cryptosystem of the party bey1,x1 and y2,x2, respectively. The ciphertext of plaintext using the public key yi is Encyim, and the decryption is DecyiEncyim. When public key cryptosystem satisfies the following, the public key cryptosystem is called a multiparty encryption cryptosystem.(i)
Full Encryption. We define the encryption using the public keyy2for the ciphertext encrypted with public keyy1for a plaintextmthrough the following operation.(1)Ency1⋅y2m=Ency2Ency1m.(ii)
Partial Decryption. We define the decryption performed by each party for the ciphertextEncy1⋅y2mencrypted with the public keysy1,y2for the plaintextmthrough the following operation.(2)Decy1Ency1⋅y2m=Ency2m,Decy2Ency1⋅y2m=Ency1m.(iii)
Full Decryption. We define the decryption performed by both parties for the ciphertextEncy1⋅y2mencrypted with the public keysy1,y2for the plaintextmthrough the following operation.(3)Decy1Decy2Ency1⋅y2m=m.Definition 4 (commutative).
For a given encryptionEncy1⋅y2m, if(4)Decy1Decy2Ency1⋅y2m=Decy2Decy1Ency1⋅y2m=m,is satisfied, then the encryption is a commutative.Definition 5 (bi-homomorphic).
When a encryption satisfies the following properties, we say that the encryption is bi-homomorphic.(i)
Ency1⋅y2m⋅Ency1m˜=Ency1⋅y2m⋅m˜(ii)
Ency1⋅y2m⋅Ency2m˜=Ency1⋅y2m⋅m˜(iii)
Ency1⋅y2m⋅Ency1⋅y2m˜=Ency1⋅y2m⋅m˜(iv)
Ency1⋅y2mω=Ency1⋅y2mω
The multiparty encryption based on the ElGamal encryption is defined as follows, which will be proved to be bi-homomorphism.(i)
Full Encryption. The encryption using the public keys y2 and y1 is as follows.(5)Ency1⋅y2m=u1,u2,c,where,u1=gr1,u2=gr2andc=m⋅y1r1y2r2.(ii)
Partial Decryption. The partial decryption for a ciphertext Ency1⋅y2m by each party y1 or y2 is as follows.(6)Decy1Ency1⋅y2m=u2,c⋅u1−x1=u2,my2r2=Ency2m,Decy2Ency1⋅y2m=u1,c⋅u2−x2=u1,my1r1=Ency1m.(iii)
Full Decryption. The decryption performed by both parties for the ElGamal ciphertext Ency1⋅y2m encrypted with the public keys y1 and y2 for the plaintext m is defined as follows.(7)Decy1Decy2Ency1⋅y2m=Decy1Ency1m=m.
Thus, the multiparty ElGamal encryption scheme satisfies partial decryption, full decryption, and commutative encryption. We also show that the multiparty ElGamal encryption satisfies the commutative encryption with bi-homomorphism as follows.Theorem 4.
The multiparty ElGamal encryption satisfies the commutative encryption with bi-homomorphism.Proof.
For two given ciphertextsEncy1⋅y2m=u1,u2,c and Ency1m˜=u1˜,c˜ with u1=gr1,u2=gr2,u1˜=gr1˜,c=m⋅y1r1y2r2,c˜=m˜⋅y1r1˜, the multiplication of the ciphertexts is as follows.(8)Ency1⋅y2m⋅Ency1m˜=u1,u2,c⋅u1˜,c˜=u1u1˜,u2,cc˜=Ency1⋅y2m⋅m˜.
For two given ciphertextsEncy1⋅y2m=u1,u2,c and Ency2m˜=u2˜,c˜with u1=gr1,u2=gr2,u2˜=gr2˜,c=m⋅y1r1y2r2,c˜=m˜⋅y2r2˜, the multiplication of the ciphertexts is as follows.(9)Ency1⋅y2m⋅Ency2m˜=u1,u2,c⋅u2˜,c˜=u1,u2u2˜,cc˜=Ency1⋅y2m⋅m˜.
For two given ciphertextsEncy1⋅y2m=u1,u2,c and Ency1⋅y2m˜=u1˜,u2˜,c˜ with u1=gr1,u2=gr2,c=m⋅y1r1y2r2,u1˜=gr1˜,u2˜=gr2˜,c˜=m˜⋅y1r1˜y2r2˜, the multiplication of the ciphertexts is as follows.(10)Ency1⋅y2m⋅Ency1⋅y2m˜=u1,u2,c⋅u1˜,u2˜,c˜=u1u1˜,u2u2˜,cc˜=Ency1⋅y2m⋅m˜.
For a given ciphertextEncy1⋅y2m=u1,u2,c with u1=gr1,u2=gr2,c=m⋅y1r1y2r2, the exponentiation of the ciphertext is as follows.(11)Ency1⋅y2mω=u1ω,u2ω,cω=gr1ω,gr2ω,mω⋅y1r1ωy2r2ω=Ency1⋅y2mω.
By using Theorem1, we can make the verifiable partial decryption as follows.Theorem 5 (verifiable partial decryption).
A decryptor (party 2) can prove that a decrypted ciphertextEncy1=u1,c1 is a partial decryption of Ency1⋅y2m=u1,u2,c without revealing x2 by showing a same discrete logarithm proof that y2=gx2 and u2−x2=u2−1x2 has same discrete log x2.(12)SPKα:c/c1≡y2α∧u2≡gαm.


## 4.2. Our Auction Protocol

Our protocol consists of a seller, who sellsM goods at a fixed set of prices 1,…,P, and bidders, who bid a price for the goods. The top M bidders can buy the goods by the M+1st price. Remark that no other party except the seller of bidders is required in our protocol.Our protocol consists of 7 phases as follows.(1)
Smart contract deployment: the seller sets necessary parameters and initialization.(2)
Bidder initialization: bidders who are interested in the auction submit their stake and join the auction.(3)
Submission of bids by bidders: bidders decide their bid and submit it to the smart contract.(4)
Bid verification: verify all bidders’ bid.(5)
M+1st-price decision: find out the M+1st bidding price.(6)
Winner decision: find out the highest M bidders who are winners of the auction.(7)
Payment: the winning bidders pay the seller the M+1st price to buy the goods.The protocol is described in detail as follows.


### 4.2.1. Smart Contract Deployment

The seller decides the following parameter and deploys the smart contractSC to start the auction.(i)
Cryptographic parameters: large primep, a basepoint g with prime order q, and an auction base z⟵ℤp/0,1.(ii)
Seller initialization:(1)
Bidding price listp1,…,pP.(2)
Timeouts for each phaseT1,…,T6: if a bidder failed to submit valid messages to smart contract within the timeout, the bidder will be treated as a malicious bidder and be financially penalized.(3)
Stake requirementd: bidders are required to submit d amount of Ether as stake to join the auction.


### 4.2.2. Phase 1: Bidder Initialization

Bidders submityi,πi1 to SC within time T1 as follows. We assume that there are more than M+1 bidders.(i)
Each bidderBi,i∈1,…,B computes the following and submits it to SC:(1)
Compute a public keyyi=gxi for the ElGamal encryption, where xi⟵ℤq is a randomly chosen secret key.(2)
Compute a proofπi1 of yi=gxi as a conventional way of a proof of knowledge of yi’s discrete logarithm xi described in Section 3 and d amount of Ether as stake.(ii)
After this phase ends, an aggregated public keyY=∏i=1Byi can be calculated by SC.


### 4.2.3. Phase 2: Submission of Bids by Bidders

All bidders submitVi,Vi′,πi2 to SC within time T2 as follows: see Figure 4 for Vi and Vi′. Bidders B2 and B3 win the auction and pay pjM+1=p2 for the goods.(i)
Bi,i∈1,…,B, computes the below and submits it to SC:(1)
Bidding vectorVi=Vi1,…,ViP.(2)
Shuffled bidding vectorVi′=Vi,pm1,…,Vi,pmP.(3)
A proof of secure shuffleπi2.(13)Vij=Z1,ifj=bi,Z0,ifj≠bi..Figure 4
Example ofM=2 with 3 bidders and 5 bidding prices.A bidderBi first chooses a bidding point bi∈1,…,P corresponding to bidding price pbi, constructs a bidding vector Vi, and shuffles Vi to Vi′, while making a proof of the secure shuffle:(14)πi2,Vi′=shuffleVi,pmi,where pmi is a secret permutation generated by Bi. This Vi′ is used for the verification of Vi. In phase 3, we can decrypt Vi′ to verify Vi without leaking Vi.(i)
SC calculates the following array ai for Bi and c for bidding price after receiving all Vi,pmi (see Figure 4 for ai and c).(1)
Compute arrayai=ai1,…,aiP for each bidder Bi:(15)aij=∏k=jPVik=Z∑k=jPtik1≤j≤p.For anyj, a value of aij is equal to Z1 if bi≥j, where bi is Bi’s bidding point. Otherwise, aij=Z0. The time complexity is OP, by computing aij=aij+1⋅Vij.(2)
Compute arrayc=c1,…,cP for each bidding price p1,…,pP:(16)cj=∏i=1Baij=Z∑i=1B∑j=1Ptij1≤j≤p.The value ofcj is the number of bidders whose bid bi is larger than or equal to j.


### 4.2.4. Phase 3: Bid Verification

A bidder can only bid on one price. So, correct bidding vectorsVi consists of P−1 times of Z0 and one Z1. Since bidder Bi also submitted Vi′, a shuffled Vi, we can simply decrypt Vi′ to verify if it consists of P−1 times of Z0 and one Z1 within time T3. The decryption will not leak any secret since the shuffled bidding vector Vi′ does not contain any secret.(i)
SC verifies all bidder Bi’s bid Vi:(1)
Decrypt the shuffled bidding vectorVi′:(17)mi1,…,miP=DecVi1′,…,DecViP′.(2)
Verify if there is exactlyP−1 times of z0 and one z1 in mi1,…,miP.


### 4.2.5. Phase 4:M+1st-Price Decision

By using mix and match,SC and all Bi determine the M+1st price within T4. In array c=c1,…,cP, the value of cj is the number of bidders Bi whose bid bi is larger than or equal to bidding point j. Thus, we can use mix and match to find out the bidding point j where Deccj∉z0,z1,…,zM, but Deccj+1∈z0,z1,…,zM. This j is the M+1st price’s bidding point. Since the c array is a decrementing array, binary search can speed up the search. We use jM+1st as a symbol to this j.(i)
By all bidders’ help,SC finds the bidding point j that MixMatchcj,z0,z1,…,zM=False but MixMatchcj+1,z0,z1,…,zM=True. Assume cmp is the compare function of binary search (Algorithm 1). BiSearch will return the j where cmpcj=−1 but cmpcj+1=1. This j is the M+1st price.(18)jM+1st=BiSearchc,cmp,cmpcj=1,ifMixMatchcj,z0,z1,…,zM=True,−1,otherwise..


### 4.2.6. Phase 5: Winner Decision

In this phase, by decrypting all bidders’ai,jM+1st+1 within time T5, the winners can be easily found. In this phase, bid secrecy holds because the bid bi can be any number between jM+1st+1 and P.(i)
By all bidders’ help,SC decrypts ai,jM+1st+1 for all i∈1,…,B.(19)δi=DECai,jM+1st+1=z∑k=jPtik.BidderBi with δi=z1 wins the auction.


### 4.2.7. Phase 6: Payment

The bidders who win the auction senddpjM+1st amount of Ether (in Wei) to the seller through SC.(i)
All winning biddersBi send dpjM+1st amount of Ether (in Wei) to SC.(ii)
SC sends dpjM+1stM amount of Ether (in Wei) to the seller and refunds the stakes to all bidders.


## 4.2.1. Smart Contract Deployment

The seller decides the following parameter and deploys the smart contractSC to start the auction.(i)
Cryptographic parameters: large primep, a basepoint g with prime order q, and an auction base z⟵ℤp/0,1.(ii)
Seller initialization:(1)
Bidding price listp1,…,pP.(2)
Timeouts for each phaseT1,…,T6: if a bidder failed to submit valid messages to smart contract within the timeout, the bidder will be treated as a malicious bidder and be financially penalized.(3)
Stake requirementd: bidders are required to submit d amount of Ether as stake to join the auction.


## 4.2.2. Phase 1: Bidder Initialization

Bidders submityi,πi1 to SC within time T1 as follows. We assume that there are more than M+1 bidders.(i)
Each bidderBi,i∈1,…,B computes the following and submits it to SC:(1)
Compute a public keyyi=gxi for the ElGamal encryption, where xi⟵ℤq is a randomly chosen secret key.(2)
Compute a proofπi1 of yi=gxi as a conventional way of a proof of knowledge of yi’s discrete logarithm xi described in Section 3 and d amount of Ether as stake.(ii)
After this phase ends, an aggregated public keyY=∏i=1Byi can be calculated by SC.


## 4.2.3. Phase 2: Submission of Bids by Bidders

All bidders submitVi,Vi′,πi2 to SC within time T2 as follows: see Figure 4 for Vi and Vi′. Bidders B2 and B3 win the auction and pay pjM+1=p2 for the goods.(i)
Bi,i∈1,…,B, computes the below and submits it to SC:(1)
Bidding vectorVi=Vi1,…,ViP.(2)
Shuffled bidding vectorVi′=Vi,pm1,…,Vi,pmP.(3)
A proof of secure shuffleπi2.(13)Vij=Z1,ifj=bi,Z0,ifj≠bi..Figure 4
Example ofM=2 with 3 bidders and 5 bidding prices.A bidderBi first chooses a bidding point bi∈1,…,P corresponding to bidding price pbi, constructs a bidding vector Vi, and shuffles Vi to Vi′, while making a proof of the secure shuffle:(14)πi2,Vi′=shuffleVi,pmi,where pmi is a secret permutation generated by Bi. This Vi′ is used for the verification of Vi. In phase 3, we can decrypt Vi′ to verify Vi without leaking Vi.(i)
SC calculates the following array ai for Bi and c for bidding price after receiving all Vi,pmi (see Figure 4 for ai and c).(1)
Compute arrayai=ai1,…,aiP for each bidder Bi:(15)aij=∏k=jPVik=Z∑k=jPtik1≤j≤p.For anyj, a value of aij is equal to Z1 if bi≥j, where bi is Bi’s bidding point. Otherwise, aij=Z0. The time complexity is OP, by computing aij=aij+1⋅Vij.(2)
Compute arrayc=c1,…,cP for each bidding price p1,…,pP:(16)cj=∏i=1Baij=Z∑i=1B∑j=1Ptij1≤j≤p.The value ofcj is the number of bidders whose bid bi is larger than or equal to j.


## 4.2.4. Phase 3: Bid Verification

A bidder can only bid on one price. So, correct bidding vectorsVi consists of P−1 times of Z0 and one Z1. Since bidder Bi also submitted Vi′, a shuffled Vi, we can simply decrypt Vi′ to verify if it consists of P−1 times of Z0 and one Z1 within time T3. The decryption will not leak any secret since the shuffled bidding vector Vi′ does not contain any secret.(i)
SC verifies all bidder Bi’s bid Vi:(1)
Decrypt the shuffled bidding vectorVi′:(17)mi1,…,miP=DecVi1′,…,DecViP′.(2)
Verify if there is exactlyP−1 times of z0 and one z1 in mi1,…,miP.


## 4.2.5. Phase 4:M+1st-Price Decision

By using mix and match,SC and all Bi determine the M+1st price within T4. In array c=c1,…,cP, the value of cj is the number of bidders Bi whose bid bi is larger than or equal to bidding point j. Thus, we can use mix and match to find out the bidding point j where Deccj∉z0,z1,…,zM, but Deccj+1∈z0,z1,…,zM. This j is the M+1st price’s bidding point. Since the c array is a decrementing array, binary search can speed up the search. We use jM+1st as a symbol to this j.(i)
By all bidders’ help,SC finds the bidding point j that MixMatchcj,z0,z1,…,zM=False but MixMatchcj+1,z0,z1,…,zM=True. Assume cmp is the compare function of binary search (Algorithm 1). BiSearch will return the j where cmpcj=−1 but cmpcj+1=1. This j is the M+1st price.(18)jM+1st=BiSearchc,cmp,cmpcj=1,ifMixMatchcj,z0,z1,…,zM=True,−1,otherwise..


## 4.2.6. Phase 5: Winner Decision

In this phase, by decrypting all bidders’ai,jM+1st+1 within time T5, the winners can be easily found. In this phase, bid secrecy holds because the bid bi can be any number between jM+1st+1 and P.(i)
By all bidders’ help,SC decrypts ai,jM+1st+1 for all i∈1,…,B.(19)δi=DECai,jM+1st+1=z∑k=jPtik.BidderBi with δi=z1 wins the auction.


## 4.2.7. Phase 6: Payment

The bidders who win the auction senddpjM+1st amount of Ether (in Wei) to the seller through SC.(i)
All winning biddersBi send dpjM+1st amount of Ether (in Wei) to SC.(ii)
SC sends dpjM+1stM amount of Ether (in Wei) to the seller and refunds the stakes to all bidders.


## 4.3. Features and Security

In this section, we discuss the features and security of our protocol.(i)
Bid binding: according to our implementation, the functions in SC will not allow bidders to change their bidding point after the bid submission phase is closed.(ii)
Bid secrecy: the bidding vectors V1,…,VB are encrypted by all bidders’ public keys Y=y1⋯yB. Without all bidders’ collaboration, the bid is kept a secret. Even though V′ is decrypted, it is a permutation of V. Thus, decrypting V′ will not leak any secret. The secrecy of top M bids is protected in phase 5. If ai,jM+1st+1 is an encrypted z1, all bids from ai,jM+1st+1 to aiP can contain z1.Unless all bidders collude, the bid secrecy will be satisfied in the mix and match used in Phase 4. In the mix part, ciphertexts are re-randomized and secretly shuffled by all bidders. Without all bidders colluding, the permutation of shuffled ciphertexts cannot be identified. In the match part, the shuffled ciphertexts can be decrypted by only all bidders’ collaboration.(iii)
Bidder anonymity: since c1,…,cP are products of ciphertexts generated by all bidders, i.e., cj=∏i=1Baij. The proof of Deccj=zM will not leak aij,i=1,…,B. Thus, the identity of the M+1st bidder is still a secret.(iv)
Posterior secrecy and anonymity: the bidding points bi,i=1,…,B and bidding vectors Vi,i=1,…,B are still secrets even after the auction. Thus, posterior secrecy and anonymity still hold.(v)
Robustness: since all messages sent to the smart contract are attached with a proof, malicious behaviors in each phase can be found immediately. The timeouts T1,…,T6 are also set for each phase to ensure that the auction ends within a determined time. Therefore, this protocol provides robustness even in malicious models.(vi)
Public verifiability: all messages sent to SC are attached with a publicly verifiable non-interactive proof, which can be verified by smart contract immediately. Therefore, the correctness of the protocol is publicly verifiable.(1)
Phase 1: Bidder Initialization. A public key yi=gxi is submitted by each bidder Bi to SC, i=1,…,B. The proof of knowledge of xi is publicly verifiable. Thus, the correctness of the public key is publicly verifiable.(2)
Phase 2: Submission of Bids by Bidders. A secure shuffled bidding vector Vi′ is submitted by each bidder Bi to SC, i=1,…,B. The proof that Vi′ is a secure shuffle of Vi is publicly verifiable.(3)
Phase 3: Bid Verification. Let Vi′=Vi1′,…,ViP′=ui1,vi1,…,uiP,viP. BP decryption messages uijxi;i=1,…,B;j=1,…,P are submitted by each bidder Bi. The proof of the same discrete logarithm that uijxi and public key yi=gxi have the same discrete logarithm xi is publicly verifiable. If Vi′ is valid, then Vi is a valid bidding vector. Thus, the verification on bidding vectors Vi,i=1,…,B is publicly verifiable.(4)
Phase 4:M+1st-Bid Decision. A verifiable mix and match [5] is performed in this phase. The validity of the M+1st bidding point j where MixMatchcj,z0,z1,…,zM=False but MixMatchcj+1,z0,z1,…,zM=True is publicly verifiable. Thus, the M+1st bidding price is publicly verifiable.(5)
Phase 5: Winner Decision. Let aij=uij,vij. B decryption messages ui,jM+1st+1xi;i=1,…,B are submitted by each bidder Bi. Therefore, the decryption on ai,jM+1st+1 is verifiable. The decision of winners is publicly verifiable.(vii)
Correctness:(1)
Phase 1: Bidder Initialization. All public keys yi=gxi,i=1,…,B are publicly verified. Thus, the correctness holds.(2)
Phase 2: Submission of Bids by Bidders. All secure shuffled bidding vectors Vi′,i=1,…,B are publicly verified. Vi′ is a secure shuffle of Vi. The correctness holds.(3)
Phase 3: Bid Verification. A correct bidding vector Vi should contain P−1 amount of Z0 and one Z1. Since Vi′ is a secure shuffle of Vi, Vi is correct if and only if Vi′ also contains P−1 amount of Z0 and one Z1. Thus, the correctness holds.(4)
Phase 4:M+1st-Bid Decision. The bidding point jM+1st is correct since MixMatchcjM+1st,z0,z1,…,zM=False, but MixMatchcjM+1st+1,z0,z1,…,zM=True. There are less than M bidders’ bids that are larger than or equal to jM+1st+1, but there are more than M bidders’ bids that are larger than or equal to jM+1st+1. Thus, jM+1st is the M+1st bidding point. The correctness holds.(5)
Phase 5: Winner Decision. If ai,jM+1st+1=Z1, then the bidder Bi’s bidding point bi is larger than or equal to jM+1st+1. Thus, this bidder is a winning bidder. The correctness holds.(viii)
Financial fairness: all bidders deposit d amount Ether (in Wei) in the smart contract as a stake in phase 1. In the failure condition part, malicious bidders will compensate other bidders by their stake.


## 5. Implementation and Optimization

In this section, we introduce our implementation, optimization, and benchmarks. This protocol consists of smart contract (https://github.com/tonypottera24/m-1st_auction_dlp_sol) and web3 clients (https://github.com/tonypottera24/m-1st_auction_dlp_py). The smart contract is implemented by Solidity 0.7.x with experimental ABIEncoderV2. We also used the “solidity-BigNumber” library (https://github.com/zcoinofficial/solidity-BigNumber) for big number computation. In the client part, we use Python library web3.py (https://github.com/ethereum/web3.py) for better big number support. In terms of the simulation environment, we use Ganache (https://www.trufflesuite.com/ganache), a testnet built by Truffle, to execute and estimate the gas usage.The computational costs of discrete logarithm problem (DLP) based algorithms are usually significantly affected by the key size. Figure5 shows the gas usage by using 1024-, 2048-, and 3072-bit DLP and ECC P256. A common way to solve this problem is to use elliptic curve cryptography (ECC). Our ECC contract used the “elliptic-curve-solidity” (https://github.com/witnet/elliptic-curve-solidity) library, which is well tested and provides common NIST series curves such as secp256r1 (P256). As an Ethereum virtual machine always uses 256-bit integers, the gas consumption should not have significant differences between P192, P224, and P256. The ECC P256 version can save 69% gas on average compared with 3072-bit DLP. Table 2 shows implementation results of AS [6] and our scheme. Without using full mix and match and applying some optimization (see Section 6), we can reduce 33% gas on a 3-bidder and 6-bidding price setting.Figure 5
Gas usage of 1024-, 2048-, and 3072-bit DLP and 256-bit ECC (B2P4: 2 bidders and 4 bidding prices; B4P6: 4 bidders and 6 bidding prices).Table 2
Comparison of AS [6] gas usage (106) and our scheme (ECC 256: 3 bidders and 6 bidding prices).
AS [6]This schemeManagerBidderBidder(1) Initialization1—1−0%(2) Submission of bids by bidders553−40%(3) Bid verification520—350−33%(4)M+1st-price decision79—52−34%(5) Winner decision9—8−11%(6) Payment442−50%Overall6189416−33%


## 6. Comparison

In this section, we compared the performance of our scheme with those of the AS [6], OM [7], GY [8], and MMO [9], as shown in Table 3; compared with other schemes, we do not need a trusted manager. The only role in our scheme is bidder. This design matches the ultimate goal of smart contract protocol, decentralized and trustless. As one of our main contributions in the bid verification phase, we use verifiable shuffle, i.e., the mix part, instead of the whole mix and match protocol as other related works do.Table 3
Comparison of related works and our scheme (TM: trusted manager).
Trusted managerBid verificationPosterior secrecy and anonymityPublic verifiabilityRobustnessFinancial fairnessAS [6]YesMix and matchTM basedNoTM basedNoOM [7]YesMix and matchTM basedNoTM basedNoMMO [9]YesMix and matchTM basedInteractiveTM basedNoGY [8]YesCommitmentTM basedNoTM basedYesOur schemeNoVerifiable shuffleYesYesYesYesDetailed comparisons of phases 1 and 3 are as follows:(1)
Phase 1: Bidder Initialization. In previous research [6, 9, 11, 12], the bids are encrypted only by managers’ public key. The bid secrecy, bidder anonymity, and many other properties all relied on the trusted manager. On the other hand, in our scheme, the ciphertexts are encrypted by all bidders’ public keys. Without all bidders’ collaboration, no one can break the bid secrecy and bidder anonymity.(2)
Phase 3: Bid Verification. A valid bidding vector Vi=Vi1,…,ViP should contain exactly P−1 amounts of Z0 and one Z1. In previous research [6, 9, 11, 12], bidding vector verification contains two parts: (1) Vi1∈Z0,Z1; (2) ∑j=1PVij=Z1. The first part is accomplished by mix and match [5]. This requires T (trusted) mix servers to perform mix (secure shuffle [23–25]) and match (zk equality proof). The second part is accomplished by asking trusted manager to decrypt ∑j=1PVij.In our scheme, we only use the match part (secure shuffle) of the mix and match protocol to prove these two parts simultaneously. By all bidders’ collaboration, we decryptVi′ (a publicly verifiable shuffle of Vi). SC can verify if there is exactly P−1 amounts of Z0 and one Z1 in Vi′ without leaking any secret.Table4 compares our protocol with previous protocols. In previous research, trusted managers need to use mix and match on M values to verify P ciphertexts in bidding vector Vi for all B bidders. Therefore, the time complexity of manager is OBPM [6–8]. The time complexity and storage complexity on SC are proportional to the number of trusted manager T, i.e., OTBPM overall. By removing the manager and letting bidders act as managers, the time complexity of our bidder is as good as the time complexity of the manager in previous research. On the other hand, as one of our contributions, we applied optimization to reduce the storage complexity from OB2PM to OBPM. In previous research, the multiparty ElGamal ciphertext is in a format of gr1,…,grT,gmy1r1⋯yTrT. However, it is meaningless to use different randomness r1,…,rT since the ciphertexts are created by the same bidder. Only gr,gmy1⋯yTr is enough.Table 4
Comparison of the complexity with related works (B: the number of bidders, P: the number of bidding prices, M: number of goods, and T: the number of trusted managers and trusted mix servers).
Time per managerTime per bidderTimeSCStorageSCAS [6]OBPMOPOTBPMOTBPMOM [7]OBPMOPOTBPMOTBPMMMO [9]OBlogPMOlogPMOTBlogPMOTBlogPMGY [8]OBPMOPOTBPMOTBPMOur scheme—OBPMOB2PMOBPM


## 7. Conclusion

We propose an efficient and secureM+1st-price auction protocol without a trusted manager under a malicious model. Out protocol satisfies anonymity, robustness, correctness, public verifiability, and financial fairness.



---

*Source: 1615117-2021-11-30.xml*