ElectAnon: A Blockchain-based, Anonymous, Robust and Scalable Ranked-Choice Voting Protocol
In recent years, especially after the Covid-19 outbreak, the importance of remote systems, such as internet voting, has increased dramatically. The development of blockchain technology and its benefits like decentralization, security and transparency have encouraged election systems to use blockchains as well. Analysis on existing solutions and paradigms reveals that anonymity, robustness and scalability are common problems in blockchain-based election systems. In most of the previous works, anonymity could not be achieved successfully because election authorities can know the real identities of voters. Robustness was also not assured as their protocols are disruptable in the voting process. In addition, high transaction costs for vote casting make existing systems unscalable. In this thesis, we propose ElectAnon; a blockchain-based, ranked-choice election protocol with a focus on anonymity, robustness and scalability. ElectAnon achieves full anonymity by enabling voters to anonymously prove their eligibility to vote by using zero-knowledge proofs in conjunction with merkle trees. Robustness is realized by completely removing the direct control of the authorities in the voting process via using a timed-transition state machine in addition to the utilization of a self-tallying election scheme. Scalability is ensured by treating each ranked-choice ballot as a permutation list, which is then encoded into a single integer that can be efficiently stored. Moreover, ElectAnon incorporates different optimization techniques like using batch inputs and offloading complex computations with zero-knowledge proofs to improve the scalability. The proposed protocol also includes a candidate proposal system to provide an end-to-end election solution, which was not included in the previous works. We also propose and discuss possible extensions like Multiple Elections, Assisted Merkle Tree and The Merkle Forest for our protocol. Multiple Elections extension provides a mechanism to use the same set of voters for multiple elections with our protocol. The Merkle Forest extension provides a different way to minimizes the trust assumption on election authorities with zero knowledge proofs in exchange for a decrease in scalability. The Assisted Merkle Tree extension offers just the opposite tradeoff by increasing scalability in the favor of requiring an external assistance from authorities in merkle tree construction.
ElectAnon is implemented by using Ethereum smart contracts and a zero-knowledge gadget, Semaphore. Two different sophisticated tallying methods, Borda Count and Tideman, are included in our implementation and analysis. We conducted tests within Ethereum local test network to obtain performance metrics such as elapsed times, file sizes and gas consumptions. Results show that ElectAnon is capable of running feasibly with up to 100,000 voters. It also reduces the gas consumption up to 89\% compared to previous works.
