BLOG - Introducing TIVILEDGE: Next Generation Blockchain Online Voting

Opinion polling (or as it is better known - voting) has a significant role in organisations and societies as a method for making decisions or deciding on the leadership in general.

Let’s consider a series of questions in the following constructed contexts:

1. Four friends share a flat to save on living costs. They need to agree on who takes out trash on Tuesdays;

2. A general meeting of an apartment association needs to decide whether to borrow money to insulate the building to reduce heating costs;

3. The board of a publicly traded company needs to decide whether to pursue a new venture;

4. The electorate of a small European country needs to elect representatives to their national parliament.

The above scenarios all are a type of opinion polling. Opinion polling (or as it is better known - voting) has a significant role in organisations and societies as a method for making decisions or deciding on the leadership in general. And because it is so critical and widespread, there are literally thousands of different ways to do it, with specific methods for particular use cases.

One of such methods involves electronic voting. The term 'electronic voting' itself is rather broad, and its meaning can range from faxing in a filled ballot to using a computer at a remote location where there is no polling station, but only internet access to cast a vote. Advocates for electronic voting propose the method for its accuracy (compared to the deviations when the ballots are hand-tallied), accessibility (by employing different accessibility tools), usability (by enforcing marking rules for the ballots), efficiency (by allowing very fast result tabulation) and many other benefits.

However, there are also a lot of critics of electronic voting. They claim that electronic voting systems are error-prone, hackable, opaque and difficult (or even practically impossible) for a layperson to understand. The truth depends on the individual and thus there is no general consensus on whether electronic voting should become mainstream.

Still, election organizers globally are under great pressure to increase the participation rates, improve the availability and efficiency of election and therefore often turn to electronic voting, or even online voting using the voters’ computer or smartphone.

With thousands of other claimed applications, blockchains are very commonly proposed to fix voting once and for all. The proponents claim that blockchains provide the immutability of the ballots, improve transparency and observability and solve other problems.

This has led to many proposals for using blockchains for electronic voting from both academia and the industry. Broadly speaking, the proposals can be divided into the following categories:

1. Using cryptocurreny payments as a way to cast votes for specific candidates. For example:
– Zhao and Chan [1] defined a scheme using Bitcoin payments.
– Tarasov and Tewari [2] improved the privacy by using Zcash private addresses.

2. Storing ballots as external data on cryptocurrency blockchains.
– Takabatake et al [3] used Zerocoin mixer to protect the privacy of the voters and stored the ballot content in OP_RETURN field of a transaction.

3. Running smart contracts on permissionless blockchains for enforcing voting rules and storing the ballots.
– McCorry, Shahandashti and Hao described the Open Voting Network as an Ethereum smart contract [4].

4. Using smart contracts on permissioned blockchains for storing ballots.
– Yu and others used Hyperledger Fabric to implement a voting protocol [5].

5. Using permissioned blockchains as immutable logs for recording voting events.

– Osgood proposed a system where some information has to be committed to the blockchain for later verification [6].

– Agora Voting recorded the observed election results in Sierra Leone on the blockchain[7]

Whilst many look enthusiastically at blockchain as a solution for secure and transparent electronic voting, many of the proposed solutions have inherent design drawbacks which prevent them from being used in wide-scale binding elections. These issues are eligibility verification, ballot secrecy, consistency verification, transaction rate, cost and trust [8].

Eligibility verification

There are some restrictions on who is eligible to vote if not for all, then for most types of elections. For example, only apartment owners can vote for an apartment association. In a more complex example, only stock owners can vote at a stockholders’ meeting, and their vote must be proportional to their stock size. In political elections, only those that quality to vote through citizenship, age etc. can participate.

In many elections, even the fact that a voter voted (or more importantly, did not vote) is supposed to be secret. In the case of longer election contests, the set of eligible voters can change over time. For example, if the condition for being eligible to vote is being at least 18 years of age, then someone having their 18th birthday during the elections should be able to vote after their birthday, but not before.

In the proposed solutions, it is either assumed that there exists a third party who verifies eligibility of the voters, the voters are already identified (e.g. they have some type of tokens), only the chair setting up the elections can vote or eligibility verification is ignored at all. However, this does not completely model the requirements in practice.

Ballot secrecy

The main selling point of the blockchain is the immutability and transparency of the stored data. This ensures that ballots which are stored are never modified or removed. To achieve any kind of ballot privacy, the ballots must be encrypted before they are stored.

This leads to a problem - if the ballots are encrypted using some method, then there must exist some secret information in order to obtain the tally. This information cannot be stored on the blockchain, as the observers would be able to tally the results prematurely or break the privacy of individual ballots.

In the Open Voting Network protocol, every cast ballot contains just enough information that only after all the ballots have been cast, the result is obtained. However, such a solution is susceptible to denial of service attack, where an individual voter can prevent the opening of the election results.

Additionally, there are indications that practical quantum computing may become available very soon. So, as the data is stored indefinitely on the blockchain, we need to consider the ballot secrecy in the context of quantum computers. As the standardization for post-quantum cryptographic algorithms is still ongoing and current asymmetric encryption schemes are not post-quantum secure, it may therefore be possible to reveal the ballot contents, leaking voters' preferences.

Consistency verification

Storing just the raw ballot data on the blockchain may not be sufficient to ensure the required properties of the ballot. For example, if the ballot contains a single question with a binary choice (e.g. a referendum or first past the post) and the voter submits an encrypted ballot, the receiver can not verify that it contains a binary choice. This may give an advantage to the voter to cast non-valid ballot over casting a paper ballot. This means that in addition to the ballots, the voter should also submit proof of correctness of the ballot.

Even if we have encrypted ballots and zero-knowledge proofs of correctness of the ballot, we still need to resolve the cases where invalid ballots are submitted. The ballot collector should not just discard ballots with invalid proofs as otherwise the voter could claim that their valid ballot was omitted from the tally. With the blockchain storing both valid and invalid ballots, there needs to be a clear process of validating the ballots that are counted in the tally. Thus, there needs to be some kind of decision-making process, which could be handled within a smart contract (or equivalent construction, e.g. chaincode).

Transaction rate and cost

The infrastructure which handles receiving the ballots, must be capable of accepting the cast ballots at a sufficient rate. For example, public permissionless blockchains such as Bitcoin and Ethereum can handle up to 7 and 15 transactions per second, which would amount to 604,800 and 1,296,000 transactions per 24 hours. Even if the whole transactional capacity were to be dedicated to a single election, it may not be sufficient to handle the full capacity of ballots.

Therefore, the ledger technology needs to perform quickly enough to accept the necessary number of ballots. One option would be to use side-chains to store the ballot contents and then occasionally commit to the main chains, but this approach increases the latency between the voter submitting the ballot and being able to verify its correct storage.

Another relevant consideration is the cost of transactions. The current transaction fee on Bitcoin is $1.18, reaching $55.16 in December 2017. Even if the current fees can be estimated, an attacker could possibly flood the mempool and increase the transaction cost.

Trust

The final consideration is the trust. Even though when using a blockchain which ensures Byzantine fault tolerance, a trusted majority is required. Although permissionless blockchains appear decentralized by nature, in practice they are rather centralized. For example, by some estimates, China hosts the three largest mining pools with around 60% of the global hashing power. This implies a possible Chinese state influence in the election which makes hosting elections on permissionless blockchains untenable.

Similar considerations are required when using current permissioned blockchain technologies. Let’s suppose there is a service provider who offers online voting (i.e. Elections-as-a-Service - EaaS) for institutions who can not set up the whole infrastructure themselves due to cost, lack of knowledge, time etc. For cost-efficiency, the provider generally wants to share some of the infrastructure to run many independent elections. From the election owner's point of view, the provider becomes a trusted party as it has to completely trust the infrastructure. This decreases observability and increases cost as the provider needs to be independently audited and certified to be honest.

With the above complications it is highly probable that the current blockchain solutions for electronic voting lack suitability in one way or another to satisfy the key properties of voting. And this is what one of the key use cases of the PRIViLEDGE project seeks to solve. In the next blog post we will describe our initial research and resultant work which addresses some of the complications described above.

- Ivo Kubjas


References:
(1) Zhao Z., Chan TH.H. (2016) How to Vote Privately Using Bitcoin. In: Qing S., Okamoto
E., Kim K., Liu D. (eds) Information and Communications Security. ICICS 2015. Lecture
Notes in Computer Science, vol 9543. Springer, Cham
(2) Tarasov, P. & Tewari, H. (2017). Internet Voting Using Zcash. IACR Cryptology ePrint Archive, 2017, 585.
(3) Takabatake, Yu et al. “An anonymous distributed electronic voting system using Zerocoin.” (2016).
(4) McCorry, P., Shahandashti, S. F., & Hao, F. (2017, April). A smart contract for boardroom voting with maximum voter privacy. In International Conference on Financial Cryptography and Data Security (pp. 357-375). Springer, Cham.
(5) Yu, B., Liu, J. K., Sakzad, A., Nepal, S., Steinfeld, R., Rimba, P., & Au, M. H. (2018, September). Platform-independent secure blockchain-based voting system. In International Conference on Information Security (pp. 369-386). Springer, Cham.
(6) Osgood, R. The Future of Democracy: Blockchain Voting. COMP116: Information Security, 2016. http://www.cs.tufts.edu/comp/116/archive/fall2016/rosgood.pdf
(7) https://medium.com/agorablockchain/984dd07a58ee
(8) Heiberg, S., Kubjas, I., Siim, & Willemson, J. (2018, November). On Trade-offs of Applying Block Chains for Electronic Voting Bulletin Boards. E-Vote-ID 2018.