Keywords

1 Introduction

Voting plays a significant role in a democratic society. Almost every local authority allots a significant amount of budget on providing a more robust and trustworthy voting system. Cryptographic techniques like homomorphic encryption and Mix-net [7] are usually applied in contemporary electronic voting systems to achieve the voting result verifiability while preserving voters’ secrecy. However, incidents like a security flaw that has erased 197 votes from the computer database in the 2008 United States elections [34] and the compromise of 66,000 electronic votes in the 2015 New South Wales (NSW) state election in Australia [30] raise the public concerns on the security of electronic voting systems. For voting systems based on bulletin (e.g., [1, 9]), one of the major concerns is whether the voting result that is published on the bulletin can be trusted. Blockchain with the growing popularity and remarkable success in cryptocurrency provides a new paradigm to achieve the public verifiability in such electronic voting systems.

Recently a number of blockchain-based electronic voting systems have been developed by exploiting its inherent features. These systems can be classified into three broad categories. (1) Cryptocurrency based voting systems (e.g., [21, 33, 43]). The ballots to a candidate are based on the payment he/she receives from the voters; the problem with such systems are malicious voters may refuse to “pay” the candidates to retain the money. Furthermore, a centralised trusted party, who coordinates the payment between the candidates and voters must exist. (2) Smart contract based voting system [28], which only supports two candidates and the voting is restricted to limited number of participants. Furthermore, it requires all voters to cast their ballots before reaching an agreement on the voting result. (3) Using blockchain as a ballot box to maintain the integrity of the ballots [11, 35].

In summary, the security of these blockchain-based systems highly depends on the specific cryptocurrency protocol they employed. Additionally, these voting systems can only work with a specific blockchain platform, and support a limited number of candidates and voters. Based on our observations and studies, we believe that any blockchain-based voting systems should have the following three features: (1) Platform-independence — this means the changes in the underlying blockchain protocols should not affect the voting schemes. (2) Security framework — the voting system should be implemented with comprehensive security features (the detail of security features are discussed in Sect. 5). The nature of the blockchain allows everyone to obtain the data on it; thus, the comprehensive security features have critical importance to ensure that the ballots are fully secured on the blockchain. (3) Practical — it should be scalable, which means the large amount of ballots casting and tallying can be finished in a reasonable time.

Our Contributions: In this paper, we propose an electronic voting (evoting) system that supports the above identified three features as follows.

  1. 1.

    Our voting system does not depend on a centralised trusted party for ballots tallying and result publishing. Compared with traditional voting systems, which highly depend on a centralised trusted party to tally the ballots and publish the result, our voting system takes the advantage of a blockchain protocol to eliminate the need for a centralised trusted party. The details of the blockchain trustworthiness and voting system trust assumptions are discussed in Sects. 4 and 5, respectively.

  2. 2.

    Our voting system is platform-independent and provides comprehensive security assurances. Existing blockchain-based voting systems highly depend on the underlying cryptocurrency protocols. Receipt-freeness [31] and correctness of the voting result are hard to achieve (we analyse the blockchain-based voting system explicitly in Sect. 2). The security of our voting system is achieved by cryptographic techniques provided by our voting protocol itself, thus, our voting system can be deployed on any blockchain that supports smart contract. To achieve the goal of providing a comprehensive security, we employ Paillier system to enable ballots to be counted without leaking candidature information in the ballots. Proof-of-knowledge is employed to convince the voting system that the ballot casted by a voter is valid without revealing the content of the ballot. Linkable ring signature is employed to ensure that the ballot is from one of the valid voters, while no one can trace the owner of the ballot. The detail of security features that we achieved are discussed in Sect. 5.

  3. 3.

    Our voting system is scalable and applicable. In order to support voting scalability, we propose two optimised short linkable ring signature key accumulation algorithms which are described in our full paper [41] to achieve a reasonable latency in large scale voting. We evaluate our system performance with 1 million voters to show the feasibility of running a large scale voting with the comprehensive security requirements.

The rest of the paper is organised as follows: we discuss the cryptographic techniques applied in voting systems and analyse some typical voting systems in Sect. 2. Cryptographic primitives and our voting protocol are presented in Sects. 3 and 4, respectively. We analyse the correctness and security of our voting system in Sect. 5. In Sect. 6, we deploy our voting system and analyse its performance.

2 Related Work

Secure evoting is considered as one of the most difficult problems in security literature as it involves many security requirements. To satisfy these security requirements, cryptographic techniques are mostly applied in constructing a secure evoting system. In this section, we discuss the existing voting systems based on traditional public bulletin and blockchain technology.

2.1 Public Bulletin Based Voting Systems:

In the following, we outline the key cryptographic techniques used in public bulletin based voting systems and how such techniques address the corresponding security requirements.

  • Homomorphic encryption: Homomorphism feature allows one to operate on ciphertexts without decrypting them [13]. For a voting system, this property allows the encrypted ballots to be counted by any third party without leaking any information in the ballot [10, 14, 18]. Typical cryptosystems applied in a voting system are Paillier encryption [32, 40] and ElGamal encryption [19, 21].

  • Mix-net: Mix-net was proposed in 1981 by Chaum [7]. The main idea of mix-net is to perform a re-encryption over a set of ciphertexts and shuffle the order of those ciphertexts. Mix node only knows the node that it immediately received the message from and the immediate destination to send the shuffled messages to. The voting systems proposed in [1, 17, 20] apply mix-net to shuffle the ballots from different voters, thus the authority cannot relate a ballot to a voter. For the mix-net based voting systems, they need enough amount of mix nodes and ballots to be mixed.

  • Zero-knowledge proof: Zero-knowledge proof is often employed in a voting system [9, 29, 39] to let the prover to prove that the statement is indeed what it claimed without revealing any additional knowledge of the statement itself. In a voting system, the voter should convince the authority that his ballot is valid by proving that the ballot includes only one legitimate candidate without revealing the candidate information.

  • Blind signature and linkable ring signature: Voting systems like [12, 16, 22] employ blind signature [12] to convince the tallying centre that the ballot is from a valid voter while not revealing the owner of the ballot. Simultaneously, the authority who signs the ballot learns nothing about the voter’s selections. In blind signature, both voters and tallying centre must trust the signer. If the signer is compromised, the signature scheme may stop working. Unlike blind signature, linkable ring signature [3,4,5, 8, 23,24,25,26,27, 36, 42] is proposed to avoid the untrusted signer. Instead, it needs a certain number of voters to participate in the signing process. By comparing the linkability tag, the authority can easily tell whether this voter has already voted. When the voter signs on the ballot, he/she needs to include other voters’ public keys to make his/her signature indistinguishable from other voters’ signatures.

2.2 Blockchain-Based Voting Systems

The blockchain-based voting systems can be discussed under three broad categories as follows.

  • Voting systems using cryptocurrency: In [43], authors propose a voting system based on Bitcoin. In their voting system, the ballot does not need to be encrypted/decrypted as they employ the protocol for lottery. Random numbers are used to hide the ballot that are distributed via zero-knowledge proof. Making deposit before voting may keep the voters to comply with the voting protocol while the malicious voters can still forfeit the voting by refusing to vote. However, only supporting “yes/no” voting may restrict the adoption of this voting system.

    In [33], authors proposed a voting system on the Zcash payment protocol [15] without altering the inner working of Zcash protocol. The voter’s anonymity is ensured by the Zcash address schemes. The correctness of the voting is guaranteed by the trusted third-party and the candidates. In this system, the authority, who manages the Zcash and voter status database should be trusted. If the authority is compromised, double-voting or tracing the source of the ballot is possible.

  • Voting systems using smart contract: In [28], the authors claim that their open voting network is the first implementation of a decentralised and self-tallying Internet voting protocol with maximum voter privacy using Blockchain. They employ smart contract as a public bulletin to achieve self-tallying.Footnote 1 However, their voting system can only work with two candidates voting (yes/no voting) and the limitation of 50 voters makes it impractical for a real large scale voting system.

  • Voting systems using blockchain as a ballot box: Tivi and Followmyvote [11, 35] are commercial voting systems which employ the blockchain as a ballot boxFootnote 2. They claim to achieve verifiability and accessibility anytime anywhere, while the voters’ privacy protection in these systems is hard to evaluate.

To summarize, most traditional voting systems need a centralised trusted party to coordinate the whole voting process. In these systems, the centralised trusted party plays a critical role in storing the ballots, counting the ballots, and publishing the voting result. Although the existing blockchain-based voting systems take advantage of blockchain public verifiability, the system security and user privacy of these systems depend on the features provided by the underlying blockchain platform. Our proposed approach not only takes the benefits of a decentralised trust offered by the blockchain technology to remove the need of a centralised trusted party to do the ballots tallying, voting result decoding and publishing, but also considers key security primitives proposed in the literature including traditional evoting systems to build a practical platform independent secure evoting protocol that can be deployed to any blockchain platforms that support smart contract.

3 Cryptographic Primitives

In this section, we describe the cryptography primitives borrowed from traditional voting systems and apply in our evoting system. Note that the syntaxes, correctness conditions, and security models of a linkable ring signature and a public key encryption are given in Appendix A and Appendix B, respectively in our full paper [41].

3.1 Message Encode and Decode

Before the voting starts, we must encode the candidate ID to make it suitable for vote tallying. The encode/decode functions are defined as follows:

  • Candidate encoding: We define \(\zeta := \textsf {Encode}(m) \in \mathbb {Z}\) as the candidate encoding function. For \(\rho \) candidates, each labeled with an ID from \(\mathcal {P}=\{1,2,\ldots , \rho \}\), \(\beta =2^{\rho +1}\) be the basis of encoding operation. We encode the mth candidate as \(\zeta = \beta ^m\) where \(m \in \mathcal {P}\). We choose 2 as the basis of \(\beta \) as the division operation can be replaced by the CPU register right shift instruction to achieve a better performance.

  • Candidate decoding: Let \(k=k_t\beta ^t+\dots +k_n\beta ^n+k_{n-1}\beta ^{n-1}+ \cdots +k_1\beta +k_0\) be the representation of k base \(\beta \), \(k \in \mathbb {Z}\), then we define the right shift k with n positions as \(\textsf {rsh}(k,n) = k_{t}\beta ^{t-n}+k_{t-1}\beta ^{t-n-1}+\cdots +k_{n+1}\beta +k_n\). Let \(\textsf {sum}= s_\rho \beta ^{\rho -1}+s_{\rho -1}\beta ^{\rho -2}+ \cdots +s_{2}\beta +s_1\) be the addition of all the ballots where \(s_j\) is the total number of ballots that the candidate jth acquires. We define \(s_j := \textsf {Decode}(\textsf {sum}, j)\) for \(1\le j \le \rho \) and is computed as \(s_j=\textsf {rsh}(\textsf {sum},\beta ^{j-1}) \bmod \beta \).

3.2 Paillier Encryption System [37]

Paillier Encryption system is employed to enable our voting system to tally the encrypted ballots. In our voting system, we implement the following functions in Paillier system and the detail of these functions are described in Appendix B.1 in the full paper [41].

  • Key Generation: \((\textsf {sk}_{\textsf {Paillier}},\textsf {pk}_{\textsf {Paillier}}) :=\textsf {Gen}_{\textsf {Paillier}}(K_{\textsf {len}})\) is the function to generate the secret key \(\textsf {sk}_{\textsf {Paillier}}\) and the corresponding public key \(\textsf {pk}_{\textsf {Paillier}}\) with the given key length \(K_{\textsf {len}}\). The voting administrator invokes this function to generate the key pair and uploads the public key \(\textsf {pk}_{\textsf {Paillier}}\) to the blockchain.

  • Encryption: \(C_{\textsf {Ballot}} \leftarrow \textsf {Enc}_{\textsf {Paillier}}(\zeta _{\textsf {Ballot}},\textsf {pk}_{\textsf {Paillier}})\) where \(\zeta _{\textsf {Ballot}}\in \mathbb {Z}_n\) is the plaintext ballot to be encrypted. Voters download the \(\textsf {pk}_{\textsf {Paillier}}\) from the blockchain and call this function to encrypt their ballots. This function generates the encrypted ballot \(C_{\textsf {Ballot}}\).

  • Decryption: \(\zeta _{\textsf {Res}}:=\textsf {Dec}_{\textsf {Paillier}}(C_{\textsf {Res}},\textsf {sk}_{\textsf {Paillier}})\) where \(C_{\textsf {Res}}\in \mathbb {Z}_n^*\) is the encrypted voting result; the voting administrator invokes this function to decrypt the voting result.

  • Message Membership Proof of Knowledge [6]: \(\{v_j, e_j, u_j\}_{j \in \mathcal {P}}\) := \(\textsf {PoK}_{\textsf {mem}}(C_{\textsf {Ballot}}, \varUpsilon )\) where \(C_{\textsf {Ballot}}\) is the encrypted ballot, \(\varUpsilon \) is the set of the encoded candidates. When a voter publishes his/her ballot, he/she invokes this function to generate the proof \(\{v_j, e_j, u_j\}_{j \in \mathcal {P}}\) that demonstrates his/her ballot encrypts only one of the encoded candidates in \(\varUpsilon \).

  • Decryption Correctness Proof of Knowledge: \((\zeta _{\textsf {Res}}, r): = \textsf {PoK}(C_{\textsf {Res}}\), \(\textsf {sk}_{\textsf {Paillier}})\), where \(\zeta _{Res}\) is the plaintext and r is the random factor that generate the encrypted voting result \(C_{\textsf {Res}}\). After publishing the voting result, the voting administrator invokes this function to generate a unique value pair \((\zeta _{\textsf {Res}}, r)\) that constructs the \(C_{\textsf {Res}}\) to prove that he/she decrypts the voting result \(C_{\textsf {Res}}\) correctly.

3.3 Linkable Ring Signatures

Linkable ring signature (LRS) can be applied in our system to protect the privacy of the voters. In practice, we apply the short linkable ring signature (\(\textsf {SLRS}\)) [2] which extends all the \(\textsf {SLRS}\) features to make the signature size constant with the growth of voter numbers, it has the following features: (1) every ballot that is accepted by the system is from one of the valid users, (2) the voter can check whether his ballot is counted by the blockchain, (3) the size of the signature is constant to support scalability and (4) double-voting is prevented. In our voting system, we implement the function tuple \((\textsf {Setup}, \textsf {KeyGen}, \textsf {Sign}, \textsf {Verify}, \textsf {Link})\). The details of these functions are explained in Appendix A.2 in the full paper [41].

  • Setup: \(\textsf {param}\leftarrow \textsf {Setup}(\lambda )\) is a function that takes \(\lambda \) as the security parameter and generates system-wide public parameters \(\textsf {param}\) such as the group of quadratic residues modulo a safe prime product N (explained in Appendix A.2 in the full paper [41]) denoted as \(\textsf {QR}(N)\), the length of the key, and a random generator \(\tilde{g}\in \textsf {QR}(N)\).

  • Key Generation: \((\textsf {sk}_i,\textsf {pk}_i)\leftarrow \textsf {KeyGen}(\textsf {param})\) is a function to generate a key pair for each voter i.

  • Signature: \(\sigma \) \(\leftarrow \textsf {Sign}({\mathcal {Y}},\textsf {sk},\textsf {msg})\) is a function to generate the signature \(\sigma \) using all voters’ public keys \(\mathcal {Y}=\{y_1,y_2,\ldots ,y_b\}\), the message \(\textsf {msg}\) to be signed, and the voter’s secret key \(\textsf {sk}\). Voters should invoke this function to sign on his/her encrypted ballot.

  • Verification: \(\textsf {accept}/\textsf {reject} \leftarrow \textsf {Verify}(\sigma ,\mathcal {Y},\textsf {msg})\); our voting system invokes this function to test the validity of every ballot. Based on the input of the encrypted ballot itself, the voter’s signature and all the voters’ public keys, the blockchain accepts or rejects this ballot to be put on the chain.

  • Linkability: \(\textsf {Link}(\sigma _1, \sigma _2) \rightarrow \textsf {linked}/ \textsf {unlinked}\). When a voter casts his/her vote, our voting system invokes this function to check whether this voter has already casted his vote. If this function returns linked, our voting system rejects this ballot; otherwise, the ballot is recorded on the chain.

4 The Voting Protocol

In this section, we first provide an overview of the whole voting protocol and then discuss each step in details. The whole voting process can be divided into 11 steps as shown in Fig. 1(a). Except smart contract administrator, three entities are involved: voters, smart contract, and voting administrator.

The voting system consists of one front-end smart contract and several validation nodes as shown in Fig. 1(b). The role of a validation node is to replicate the execution of the smart contract codes to ensure its correct execution. For a practical voting, the validation nodes could be held by different entities/stakeholders, thus all ballots on the blockchain have been verified by different entities/stakeholders. As all the entities/stakeholders have the agreement on the data stored on the blockchain, the blockchain built on the servers owned by different entities can be regarded as trustworthy.

Fig. 1.
figure 1

The general voting protocol and how entities are connected.

Full size image

4.1 Entities in the Voting Process

Four entities should be involved in our voting system shown in Fig. 1(a), and details are explained as follows:

  • smart contract administrator: he/she has the ability to access the smart contract platform to deploy/terminate smart contract. In Hyperledger fabric, this account is authorised by the membership service and a permission is granted to deploy/terminate the Smart contract. In our voting system, we need at least one smart contract administrator to deploy the voting smart contract.

  • voting administrator: The role of voting administrator is to organize the vote by setting up the voting parameters and triggering the tallying and result publishing phase. Although there are underlying mechanisms in hyperledger to authenticate users, we use \(\textsf {SLRS}\) to prevent administrator from linking the ballots with the users.

  • smart contract: The role of smart contract include (1) store the encrypted ballots. (2) verify the validity of the ballots. (3) count the encrypted ballot. (4) verify the correctness of the voting result. (5) publish the voting result and provide the platform for the voters to verify the voting process.

  • voters: Voters are the people who have the rights to cast their vote. They need to register into the voting system before they cast their vote.

4.2 Voting System Set Up

During the system set up, the voting administrator uploads the following three parameters to the blockchain:

  • The public key of the Paillier system \(\textsf {pk}_{\textsf {Paillier}}\).

  • A set of encryptions of zero denoted as T, generated by the administrator’s Paillier public key \(\textsf {pk}_{\textsf {Paillier}}\). For voting with 1 million voters, we suggest the set should contain enough elements to make the randomised pool large enough and the detail of T is discussed in receipt-freeness analysisFootnote 3.

  • The \(\textsf {SLRS}\) scheme parameters, \(\textsf {param}\).

4.3 Voter Registration

Bob must register this voting system with his identity. The registration information could be: (1) email address with a desired password, or (2) the identity number with a desired password, or (3) an invitation URL sent by the administrator with a desired password. After Bob passes the identity check conducted by the smart contract, he can login with the desired password to download the \(\textsf {SLRS}\) \({\textsf {param}}\) and the administrator’s Paillier public key \(\textsf {pk}_{\textsf {Paillier}}\), then generates the \(\textsf {SLRS}\) key pair \((\textsf {sk}_i, \textsf {pk}_i)\) by calling \(\textsf {KeyGen}({\textsf {param}})\); Bob then uploads the public key \(pk_i\) to the smart contract (Bob’s secret key is kept off-chain by himself). If the smart contract accepts his \(\textsf {SLRS}\) public key, the smart contract puts his public key \(\textsf {pk}_i\) on the blockchain to complete his registration phase.

4.4 Vote Casting Phase

During this phase, Bob casts his vote as follows: (1) Bob chooses one of the candidates \(m \in \mathcal {P}\) and encodes it as \(\zeta := \textsf {Encode}(m)\). (2) Bob invokes the Paillier encryption function \(C \leftarrow \textsf {Enc}_{\textsf {Paillier}}(\zeta ,\textsf {pk}_{\textsf {Paillier}})\). (3) Bob needs to prove that C is an encryption of an element in \(\{\zeta _1,\ldots ,\zeta _\rho \}\) (set of all encoded candidates) by calling \(\{v_j,e_j,u_j\}_{j \in \mathcal {P}} := \textsf {PoK}_{\textsf {mem}}(C, \varUpsilon )\); hence he sends \(\pi =\{C,\{v_j,e_j,u_j\}_{j \in \mathcal {P}}\}\) to the smart contract.Footnote 4 (4) Upon receiving \(\{v_j,e_j,u_j\}_{j \in \mathcal {P}}\), the smart contract verifies the validation of the encrypted ballot C. We denote \(\phi \) as a mapping of this transaction’s session id to T domain. If C is valid, the smart contract takes an encryption of zero at \(\phi \)th position. Let \(\epsilon \) be the addition of \(T[\phi ]\) and C. The smart contract signs on \(\epsilon \) denoted as s and sends \((\epsilon , s)\) back to Bob. (5) If Bob accepts s, he invokes \((v,\tilde{y}, \sigma ') := \textsf {Sign}(\epsilon ,(\textsf {pk},\textsf {sk}),\mathcal {Y})\) to generate the \(\textsf {Sign}_\text {bob}\) on \(\epsilon \) and sends \((\epsilon , \textsf {Sign}_\text {bob})\) to the smart contract. (6) If the smart contract detects that \(\textsf {Sign}_\text {bob}\) has already been recorded on the blockchain or cached in the memory, it rejects Bob’s vote; otherwise, \((\epsilon , \textsf {Sign}_\text {bob})\) is put on the blockchain.

4.5 Ballots Tallying and Result Publishing

Due to the Paillier system’s homomorphic feature, counting the vote is as simple as fetching the encrypted ballots from the blockchain and adding them together. The result publishing mechanism is described in the following steps: (1) Let \(E_{\textsf {sum}}\) be the sum of all the encrypted votes and \(\textsf {Sign}_{s}\) be the signature signed by the smart contract on \(E_{\textsf {sum}}\). The smart contract sends \((E_{\textsf {sum}},\textsf {Sign}_{s})\) to the administrator. (2) The administrator invokes \(\textsf {sum}:= \textsf {Dec}_{\textsf {Paillier}}(E_\textsf {sum},\textsf {sk}_{\textsf {Paillier}})\) to compute plaintext \(\textsf {sum}\), which encodes the ballots of each candidate. The administrator also invokes \((\textsf {sum},r) := \textsf {PoK}(E_\textsf {sum},\textsf {sk}_{\textsf {Paillier}})\) to calculate the random r that constructs this \(E_\textsf {sum}\), and sends \((\textsf {sum},r)\) to the smart contract. (3) The smart contract verifies the correctness of \((\textsf {sum},r)\) by checking if \(E_{\textsf {sum}}\overset{?}{=}g^{\textsf {sum}}r^n\) (g is one of the elements of \(\textsf {pk}_{\textsf {Paillier}}\)). (4) If the smart contract accepts the \(\textsf {sum}\), it iteratively invokes \(m := \textsf {Decode}(\textsf {sum},i)\) to compute the ballots for each candidate i. Let \(\varPi \) be the dictionary holding the voting result of all candidates. The smart contract finally puts \(\varPi \) on the blockchain.

4.6 Ballot Verifying

After tallying ballots and before the voting administrator decrypts the tallying result, the public can verify ballots on the blockchain to make sure the validity of the voting process. We define two roles for people who can verify the voting. The first one is those who have the right to access the data on the blockchain while they do not have the right to vote. The second one is those who have both rights to vote and access the data on the blockchain. The public verifiability to those who have first role is as follows (1) Checking the number of ballots that were counted and the number of people registered for this voting. (2) Checking the correctness of the tallying result by downloading and adding all the encrypted ballots to match with the tallying result published on the blockchain. Compared to those who have the first role, people assigned to the second role can also verify that his/her ballot is recorded on the blockchain by checking whether there exists one ballot that is signed with his/her signature; This ensure his/her vote is recorded and counted.

In practice, we suggest enhancing the trustworthiness of the blockchain by allowing different political parties/stakeholders host their own validation nodes. The data on the blockchain is verified by different entities/stakeholders, and it is unlikely that these entities/stakeholders collude with each other to publish a false voting result.

5 Correctness and Security Analysis

5.1 Correctness Analysis

The correctness of our voting system is guaranteed by the public verifiability provided by the smart contract and the proof of knowledge provided by the cryptographic schemes. More than that, the smart contract ensures the consistency of a transaction execution. Any inconsistencies generate an error which results in the rejection of the transaction. This means the voting participants can be assured that every transaction on the blockchain is verified and accepted by all participating nodes. This prevents compromised nodes from putting an invalid data on the blockchain unless the adversary can take control of a proportion of the nodes in the whole blockchain networkFootnote 5.

5.2 Security Features of Our Voting System

  • Privacy: The ballots on the public ledger are encrypted and only the voting administrator who initiates the voting can decrypt the ballots. This ensures that the tallying center can count the ballots without knowing the content of the ballots.

  • Anonymity: The voters, candidates, or smart contract cannot tell the public key of the signer with a probability larger than 1/b, where b is the number of the voters. This can be guaranteed by the anonymity property of the linkable ring signature (LRS) scheme. Details are explained in Appendix A.2 in the full paper [41].

  • Double-voting-avoided: In our voting system, we take the advantage of linkability provided by the short ring signature scheme. This means it is infeasible for a voter to generate two signatures such that they are determined to be unlinked. Our system can detect whether the signatures are from the same voter. Hence, a voter can only sign on one ballot and cast his/her ballot only once. This can be guaranteed by the linkable property of the LRS scheme. Details are explained in Appendix A.2 in the full paper [41].

  • Slanderability-avoided: A voter cannot generate a signature which is determined to be linked with another signature not generated by him/her. In other words, an adversary cannot fake other voters’ signature. This can be guaranteed by the non-slanderability property of the LRS scheme. Details are explained in Appendix A.2 in the full paper [41].

  • Receipt-freeness: Even if an adversary obtains a voter’s secret key, the adversary cannot prove that this voter voted for a specific candidate. This is guaranteed by the addition of encryption of zero which provides additional randomness to the ciphertext which is unknown to the voter. Thus, even if the voter’s secret key is disclosed, no one can prove his casted ballot. For our voting system, the security level of the receipt-freeness is affected by the size of the encryption of zero pool, as the voters can collude with each other to reconstruct the encryption of zero pool. One solution is increase the size of zero pool thus more voters is required to reconstruct the pool. Another solution is applying coin flipping protocol on all validation node to work out a consistent randomness encryption of zero for each valid ballot. We have taken the first approach in this paper with 4096 encryptions of zeros.

  • Public verifiability: Anyone who has the relevant rights to access the blockchain can verify that all the ballots are counted correctly; moreover, voters can also verify whether their ballots have been recorded.

  • Correctness: Proof-of-knowledge ensures the correctness of the voting process. Voting participants need to prove the correctness of the interactions with the blockchain. Even if some blockchain nodes are compromised, others can still verify whether the proof is correct.

  • Vote-and-Go: Compared with the voting system proposed in [31], our voting system does not need the voter to trigger the tallying phase. Moreover, in our system, voters can also cast their vote and quit before the voting ends, unlike [28] which needs all voters to finish voting before tallying the ballots.

5.3 Security and Coercion-Resistance Analysis

To address the security and coercion-resistance, we make the following assumptions:

  • The trustworthiness of the blockchain platform is achieved by allowing different stakeholders/entities to host the blockchain validation nodes.

  • Voters cast their ballots in a secure terminal, which means it is assumed that no one stand behind a voter or uses digital devices to record the voting process. We do not take the physical voting environment security into our consideration.

  • The possibility of an attacker to create a blockchain and apply a social engineering technique to launch a phishing attack is beyond our research scope.

  • The administrator should not reveal the Paillier system secret key and the encryption of zeros to anyone.

  • Voters should cast their ballots by themselves. No one else can cast the ballot with a voter’s identification except the voter himself.

We demonstrate the robustness of our system under two typical attacks below.

Man-in-the-Middle Attacks: Our voting system has strong resistance to this attack. First, as the voters and the smart contract both sign their messages and the voting data is encrypted, it is impossible for an adversary to forge the signature or alter the data on any parties involved in the transactions. Second, the public keys used for signature verification are all published on the blockchain, preventing the adversary from cheating any parties by replacing the original public key with the adversary’s public key. The encryption of the ballot also eliminates the possibility of the ballot leakage.

Denial-of-Service (DoS) Attacks: DoS attack is feasible to launch since the network service is provided in a relatively centralised way. In addition, the servers have relatively limited processing ability for a large number of requests. Distributing the service on different nodes is one of the solutions to DoS attack as it is almost impossible for the adversary to compromise all the servers.

Coercion-Resistance Analysis: Coercion-Resistance means it is infeasible for the adversary to determine whether a coerced voter complies with the demand. Our voting system security features discussed in Sect. 5.2 make it impossible to launch the Ballots-buyer attack and Double voting attack. Additionally, our voting system is free from randomization attack.

For the Ballots-buyer attack, an attacker coerces a voter by requiring that he submits a randomly composed ballot. Under such circumstances, both the attacker and the voter have no idea about which candidate this voter casts the ballot for. The purpose of this attack is to nullify the ballots. For our system, it is impossible to launch this attack as the voter should prove that the ciphertext is one out of \(\rho \) encrypted candidates by calling \(\{v_j,e_j,u_j\}_{j \in \mathcal {P}} :=\) \(\textsf {PoK}_{\textsf {mem}}(\textsf {Enc}_{\textsf {Paillier}}(\zeta ,\textsf {pk}), \varUpsilon )\). Since \(\varUpsilon \) is held by the smart contract, any ballot that is not the encryption of any element in \(\varUpsilon \) is rejected and the voter is notified that this transaction is failed.

6 System Deployment and Experiments

6.1 System Deployment

Our voting system can be deployed in any blockchain platforms with smart contract capability and achieve the same level of security. There might be some other reasons to choose a particular platform such as voting latency and flexibility requirements. Different consensus protocols have significant impact on the blockchain network latency and node scalability [38]. If the ballots’ confirmation latency is not a major issue for the voting system, the PoW-based blockchain system could be a good option to achieve maximum node scalability. Otherwise, a BFT-based blockchain platform is a better solution. In our scenario, we employ the BFT-based blockchain platform Hyperledger Fabric and deploy our voting system in a practical scenario.

6.2 Experiments and Performance Evaluation

We deploy our system in docker containers running on a desktop with 4 cores i5-6500 CPU and 8 GB DDR3 memory. We conduct 1 million voters voting process on the blockchain that consists of 4 validation nodes and 1 PBFT leader node. Each of the validation nodes runs in one dedicated container; thus, we run five docker containers to build our testing blockchain system. We set a voter’s public key as 1024 and 2048 bits respectively and the Paillier key pairs as 1024 bits. The deployment pattern is shown in Fig. 1(b). We summarize the time spent on our employed cryptographic processes for 1 million voters’ voting in Table 1.

Table 1. Time consumed on each step.
Full size table
Fig. 2.
figure 2

The diagram of Algorithm 1.

Full size image

Voting Parameters Setting Up Time (Administrator Side): To initialise the voting, the administrator is responsible for uploading the voting parameters as discussed in Sect. 3. Let \(t_\text {cal}\) be the time taken to generate T, and \(t_\text {upload}\) be the time spent on uploading T to the blockchain. With 1024 bits key length, the pool size is 1 MB. According to our test, \(t_\text {upload}\) is <1 s and \(T_\text {cal}\) is about 14 s. In conclusion, under 100 MB bandwidth network, on the smart contract side, the majority of the time is spent on bottom half key accumulation, and on the administrator side, the most time-consuming phase is generating and uploading T (the pool of encryption of zeros).

SLRS Parameter Setting Up Time: Compared with LRS, SLRS enables the size of the signature constant no matter how many signers are involved in this signature. This feature is critical important for a large scale voting (i.e. the number of voters \(>100,000\) 1024-bits keys) as the signature should be constant to be suitable for storing on the blockchain. Compared with LRS, SLRS needs an extra step that accumulates all the signers’ public keys. Let \(y_i\) be the public key of ith voter and \(\psi \) be the SLRS public parameter for all voters. We define the key accumulation operation for all the voters’ \(\textsf {SLRS}\) public keys for the ith voter as \(w_i=\psi ^{y_1y_2 \dots y_{i-1}y_{i+1}y_{i+2}\dots y_b}\). In order to make the time spent on key accumulation acceptable, we divide the key accumulation into two halves. The bottom half is run on smart contract and the top half is run by each voter.

Fig. 3.
figure 3

\(\textsf {SLRS}\) public key accumulation and searching a block on a given blockchain in 1 million voters’ voting

Full size image

Bottom Half Time Consumption (Smart Contract Side): For the bottom half (the bottom half algorithm is shown in our full paper [41]), on the smart contract, we divide the voter \(\textsf {SLRS}\) public keys into m groups and pre-calculate the accumulation of all the public keys except the keys in the given group i and denote this key accumulation as \(\textsf {ws}_i\). A diagram that shows how bottom half algorithm works is also given in Fig. 2. We only discuss a case in which the number of the voters is larger than 500; otherwise, the voters can generate the key accumulation themselves within a reasonable computation time. We denote G as the group that contains the voters’ \(\textsf {SLRS}\) public key \(\textsf {pk}\) and f the public key accumulation function. We invoke an array operation function append to add an element into the array. We distribute the voters’ \(\textsf {SLRS}\) public keys into u groups and each group has \(\textsf {Num}\) of keys (except the last group). We denote the array \(\textsf {WS}\) to store all \(\textsf {ws}\), and \(\textsf {gkeys}\) to store the voters’ \(\textsf {SLRS}\) public keys groups. The most time-consuming part is the multiplication of public keys for each group. In our implementation, we calculate the \(\textsf {WS}\) using four threads to save time.

We evaluate the performance for 1 million voters’ voting and the result is shown in Fig. 3(a). We find that the time spent on calculating \(\textsf {WS}\) decreases with the growth of the voter numbers in one group. For example, for 1024 bits length and 2048 bit length key accumulation, it decreases from 34 s and 171 s for the group that contains 3000 voters to 13 s and 35 s for the group that contains 8, 000 voters, respectively. This is due to (1) the time spent on running the exponential computation loop in bottom half algorithm that dominates the time spent for the whole algorithm (2). For the 1 million voters’ public key accumulation, we decrease the number of groups by increasing the number of the voters in a group to decrease the time spent on the loop in bottom half execution.

Top Half Time Consumption (Voter Side Key Accumulation): For the top half execution (The top half algorithm is shown in our full paper [41]), the voter downloads the array \(\textsf {WS}\) and the key group that his key belongs to in \(\textsf {gkeys}\) from the blockchain. The time spent on downloading these parameters is acceptable because of two reasons (1) the key size and the element size in \(\textsf {WS}\) are constant. (2) The number of groups is relatively small. For instance, if we have 1 million voters and we group 5000 voters in one group, and set the public key size as 1024 bits and N as 1024 bits, then the size of all the public keys in this group, denoted as \(\mathcal {Y'}\), is approximately 624 KB. The size of an element in \(\textsf {WS}\) is restricted by SLRS parameter N; thus with the parameters above, \(\textsf {WS}\) is 256 KB. Therefore, the total size of \(\mathcal {Y'}\) and \(\textsf {WS}\) is about 880 KB. The voter only needs to do one exponential operation, regardless of the voting scale. From Fig. 3(b), it can be seen that with the key size of 1024 bits, it increase from 8.48 ms for the group that contains 3000 voters to 16.35 ms for the group that contains 8000 voters. The increase of time spent for the key accumulation on the voter’s side can be explained as the increase of time spent in top half execution, as it dominates the total time spent for the voter side key accumulation.

For 1 million voter’s voting, we could set the number of voters in one group smaller to reduce the time spent on the voter side for key accumulation. For the key length of 1024 bits, we recommend to set each group contains about 7000 voters so that it takes 14 s and 15.48 ms on the smart contract side and the voter side key accumulation, respectively.

Based on the above experiments, it is clear that both the increases of the block size and chain length increase the time spent on searching one given block in the blockchain. For 1 million voters’ voting system, the blockchain that consists of smaller blocks has better search performance. However, the drawback of the smaller block size is that it increases the number of searching operations (e.g., if we put all ballots in one block, users only searches once to get them; whereas if we allocate all of them in 10 blocks, users have to search 10 times to get them). Based on the experiment results shown in Fig. 3(c) and (d), in practice, we recommend to set each block contains 640 ballots to achieve both a reasonable search time latency and the average number of search operations.

7 Conclusion

To solve the problems that the current blockchain voting system cannot provide the comprehensive security features, and most of them are platform dependent, we have proposed a blockchain-based voting system that the voters’ privacy and voting correctness are guaranteed by homomorphic encryption, linkable ring signature, and PoKs between the voter and blockchain. We analyse the correctness and the security of our voting system. The experimental results show that our voting system achieves a reasonable performance even in a large scale voting.