A Zcash-based voting system

[evainfeld]

The Zcash blockchain is particularly well suited to support online voting. Blockchain in general mitigates many of the security concerns often raised when it comes to using digital technology in elections.

A standard blockchain, of the type we might see in Bitcoin, would be the perfect system for an open election – one in which everyone simply declares publically who they wish to vote for. One might do that by distributing a token to each voter and having them send it to their chosen candidate. An election like this would be extremely difficult to forge, since each voter could verify if their vote was correctly counted. However, there are many more properties we would like to see in an election. For example, we would like the vote to be anonymous. These properties can be achieved with ZK-Snarks.

We would like to build a voting system based on this technology that is straightforward to use by voters. We have a distributed social movement interested in using this system to elect its governing structures as a proof of concept.

How do we build it?

We are hoping to set up a separate blockchain based on the Zcash code, with minor modifications. We would have separate voter addresses and candidate addresses, both types shielded. The functionality would be limited to voter addresses receiving the initial voting token, then sending it to a candidate address of their choice in a shielded transaction. (Splitting a token between several candidate addresses may be acceptable, otherwise transactions with less than a full token can be considered invalid and discarded on the receiving side.) This is all possible thanks to the fact that ZK-Snarks use separate sending and receiving keys. After the election, an election committee opens the candidate addresses, perhaps with distributed keys, and proves how many votes each candidate received by publishing the contents of these addresses. Anyone can verify that votes are valid. Voters can verify that their votes were counted correctly.

The interface may be build as a command line wrapper, or based on existing open source wallets. We are envisioning a simple GUI in which a voter gives credentials to register an address and receive a token, and when the time comes chooses a name out of a list of candidates and sends the vote. Perhaps the most ambitious aspect of this project, is that we would like to have a working interface in all leading operating systems. The time in between registering and voting can be used to additionally verify the identity of the voter.

Some of the changes to the blockchain functionality should be as follows. The voter addresses could receive the initial voting token and then be stripped of the receiving key (perhaps the initial token can be sent in an unshielded way.) The candidate addresses would have no sending key. There would be no memo field and no transaction fee. Fixed number of tokens will be created and distributed to the eligible voters, no additional tokens can be created by miners.

Team: currently, myself and Anna Olchowik (software engineer at RowAnalytics)

[autotunafish]

I remember reading these a while back, maybe could be of use

https://scss.tcd.ie/publications/theses/diss/2017/TCD-SCSS-DISSERTATION-2017-015.pdf https://www.nsd.ru/en/press/pubs/index.php?id36=633655

[evainfeld]

Thank you, looks interesting. I'm familiar with the voting one - as far as I remember it suggested using the actual ZCash blockchain rather than forking its own and introduced complicated ways of getting around the problems that come out of that. Our way is simpler. :)

[b-g-goodell]

While I like the idea in general (especially for open source governance), there are public key infrastructure issues to overcome. A project like this inherits all problems with voter registration, for example.

Can you elaborate on the scope of your project? If the goal is a simple but private e-voting scheme, using snarks seems like overkill: verification time won't be very important like in currency use-cases, so why use something like snarks to establish voter anonymity instead of something like ring signatures? Can you elaborate on why you want to use tokens to vote instead of signatures? ( https://scholar.google.com/scholar?hl=en&as_sdt=0,5&q=e-voting+and+digital+signature#d=gs_qabs&p=&u=%23p%3DNV7BbatwU1cJ )

[evainfeld]

I agree that registration is the weakest point when it comes to security - that is why we are envisioning additional time between registration and voting, to verify the voters by other means.

Let's operate under a use case of leadership election of a body with some direct political power, where voters are geographically separated and paper ballot voting is not feasible.

I don't think snarks are overkill - with the coming efficiency updates it shouldn't be much of a usability hurdle. Tokens allow for better security and a potential for more elaborate voting schemes in the future. Also, don't ring signatures require stable anonymity sets that in this case simply wouldn't be feasible to hold between registration and voting?

[tromer]

Let me share some general notes on blockchain-voting by voting expert Josh Benaloh (private communication, released with permission):

Blockchains provide an unexpectedly effective answer to a long-standing problem in computer science -- how to form a consistent public ledger in a dynamic and fully distributed environment in which there is no leader and participants may join and leave at any time. In fact, the blockchain process effectively selects a "random" leader at each step to move things forward, so this seems at first to be a natural fit for elections -- citizens post their preferences onto a blockchain (privacy is usually an afterthought which is dealt with in some often underspecified fashion) and everyone can see and agree upon the outcome of the election. However ...

Elections (especially public elections) already have central authorities to play the leadership role. There must be some entity to set the election (what will be voted on, when will the vote take place, who is allowed to vote, etc.). Once we have a central authority, that authority can also be tasked with publishing a public ledger of events. Note that (as with blockchains) there need be no special trust in a central authority as these tasks are all publicly observable. So to begin with, by simply posting something on a web page, an election office can do in a single step what blockchains do with a cumbersome protocol involving huge amounts of computation.

But it's not just a matter of efficiency, there's also accountability. Blockchains are inherently unaccountable. Blockchain miners are individually free to include or reject any transactions they desire -- this is considered a feature. So if I am the public leader of a referendum to enact a large tax on blockchain miners, what miner in going to accept and post my vote? No miner has done anything wrong by refusing to accept my vote, so there's no accountability.

There's also no certainty. Blockchains ultimately resolve disputes with a "longest chain wins" rule. Miners may have inconsistent views of the contents of blockchains, but the incentives are structured so that the less widely held views eventually fade away -- usually. At the conclusion of an election, my view may be that your vote was not posted in time, while your view may include your vote beating the deadline. Which view prevails is determined by actions which take place subsequently, and prevalence is never absolute but only something that becomes more and more accepted over time. This lack of certainty is not a desirable property in elections.

Yet another deterrent to the use of blockchains with public elections is that any group with a majority of mining power can cause a blockchain to eventually produce any view that it wants. So blockchain elections effectively turn rule by majority of voters into rule by majority of miners.

There are other incompatibilities [in particular: avoiding coercion, whether by forcing voters to irrevocably vote in a specific way, forcing voters to reveal their true vote, or chain-voting attacks --ET].

What's your perspective on these points?

[evainfeld]

I think this is precisely why we need to use ZCash rather than any type of blockchain.

Normally, you choose either public election - verifiable but as pointed out above simply publishing a list of votes would be more efficient. That option does not have voter secrecy. If you anonymized it it's not verifiable. With ZCash you get the verifiability of a public election as well as voter secrecy.

As for coercion, that may require an extra layer of magic, perhaps having the voter assign custom pseudonyms to candidates. Solving coercion is the reason we're getting rid of the memo field. As for chain voting, that's why we would like to strip the wallets off the receiving key.

PS I seem unable to set labels myself - I Wonder if you could add the ux one as well? What we would like to Focus on is an implementation rather than reaserch. ;) thank you!

[olchowik]

"At the conclusion of an election, my view may be that your vote was not posted in time, while your view may include your vote beating the deadline."

The best way to end a voting is an open question. There is no way to reliably know the time the transaction was created and every transaction created before the deadline should be included in the blockchain. The simplest way to do it is to wait. Let’s assume everyone procrastinates and votes just before the deadline. We can calculate the time needed to include every transaction on a blockchain and check the results after that time. There are many issues with this approach. It allows people to cheat and vote “after” deadline, this could be minimized by not allowing nodes to accept transactions after some deadline, but nodes can cheat. On the other hand if someone is eligible to vote and is late is it undesirable to count this vote? It might take a lot of time depending on the size of the voting group and the speed of the blockchain. Assume that the zcash blockchain speed in case of all shielded transactions is 6,7 transactions/second it is not possible to do it on a country scale, but it will work reasonably in a political organisation that we would like to test the blockchain voting on (estimated time 6 min).

[tromer]

The Zcash Foundation Grant Review committee has reviewed your pre-proposal, including the above discussion, to evaluate its potential and competitiveness relative to other proposals. Every pre-proposal was evaluated by at least 3 (and typically more than 4) committee members .

The committee's opinion is that your pre-proposal is a promising candidate funding in this round, and the committee therefore invites you to submit a full proposal. Please submit a full proposal by June 15th, following the detailed structure described in the Call for Proposals. We encourage you to submit a draft as early as possible, to allow for community feedback.

[evainfeld]

Here is the full proposal, we really appreciate the chance to submit this and thank you for the time and advice.

Best Regards,

Ewa Infeld, Anna Olchowik, Bartosz Owczarek

Z-Cash Voting.pdf

[evainfeld]

I would like to add a disclaimer. Election security experts are correct in being extremely wary of any project of this kind. We do not plan to make any claims that cannot be supported, and plan to pick our use cases very carefully.

However, all existing voting systems have significant flaws and our project, in time, has the potential for improving on them, at least for particular use cases. This should not be underestimated.

[tromer]

@nealmcb, what's your take on this grant proposal, in light of your comments on blockchain-based voting?

[nealmcb]

Thanks for pointing this proposal out, @tromer. I'll repeat my comments here, for convenience, and since this seems like a more appropriate place.

Note that this proposal amounts to internet voting, but does not address the host of associated issues like malware on the voter's computer, usability in the face of lost private keys and other voter authentication and authorization issues, denial of service attacks, coercion, and auditability and transparency around all those other requirements.

In addition, using a distributed blockchain system introduces new problems of accountability, complexity, and bias, as touched on here: Blockchains are Great for Audits, but not Elections

Remember that for deeply entrenched reasons, voting systems are run by thousands of often inexperienced and non-technical local or state administrators. But allowing them to be controlled instead by third-party experts introduces yet more dangers to democracy.

For these reasons and more, election integrity experts agree that the low-tech but highly transparent approach of voting on paper remains the best way to preserve democracy. In addition, it is critical to require Evidence-Based Elections, which include doing risk-limiting audits.

See also If I can shop and bank online, why can’t I vote online?

A much fuller exposition of the enormous and unsolved challenges of secure internet voting is at E2E-VIV Project | U.S. Vote Foundation

---

I hear this proposed as a convenient election mechanism for small organizations which don't feel like targets for concerted attacks. But any suggestion that this is a "pilot" or "proof of concept" for elections of significant consequence is dangerous, since it allows attackers to just bide their time until people predictably claim (with little firm basis, since attacks can be so well hidden) that their system hasn't been hacked in all the pilot elections.

The comments by renowned crypto expert Josh Benaloh above (https://github.com/ZcashFoundation/GrantProposals-2018Q2/issues/22#issuecomment-392825397) are also spot-on.

[evainfeld]

Hi Neal, thank you very much for your comments.

You are absolutely right about the issues you list. All of those issues are also true when it comes to cryptocurrencies.

Therefore, I would like to propose the following heuristic: let us, in the short term, limit ourselves to use cases such that the benefit of hacking such election would be lower for all attackers than hacking the money out of the ZCash blockchain.

If we stick to that, and use cases where a paper ballot vote is not feasible, this approach is arguably an improvement on existing online voting systems.

However, and perhaps separately from the short or medium-term consequences of this project, I would like to challenge the paper ballot orthodoxy in two ways. First, the ease with which a state-wide paper ballot election can be rigged is often underestimated in western democracies and by western researchers. Second, the fact that this system has both voter secrecy and verifiability really is a big step, and worth exploring. The verifiability in particular is a feature that boosts security and which the paper ballot does not have. Yes - it is, in its current form, still very much vulnerable to the same attacks a cryptocurrency system is. But this is a profound discussion that is worth opening.

The article you cite is applicable to a blockchain in which the miners can see the details of the transactions, but in ZCash the problem it argues - of miners censoring certain kinds of votes - disappears.

[nealmcb]

Thanks for your comments, @evainfeld.

I think the challenges of having governments (including tiny non-tech-savvy jurisdictions) roll out elections to all voters is quite different from having well-funded IT shops provide a new option for commercial transactions. And requiring non-tech-savvy jurisdictions to trust their elections to third parties while having no clue for the daunting details is even worse.

Of course voters wouldn't be required to vote online, but it does increase the attack surface, and if everyone is authorized to vote online, a single hacker may well be able to swing an arbitrary fraction of the vote and steal any contest.

Furthermore, issues of authentication against official voter lists, usability, coercion, public transparency and public verifiability by the general public are very different for elections vs commercial transactions.

I.e. attacks on zcash voting can take many forms that don't also enable attacks on zcash commercial transactions.

Note that many attacks, including censorship, don't require seeing the details of the transactions.

Suppose (for ease of motivation) that there is a vote on whether to tax crypto-currencies, and that many miners 1) don't want the tax and 2) know that a certain locality or ISP has lots of supporters of the tax. They could in many cases find clever ways to selectively censor votes from the relevant IP addresses, leading to a net bias in the results.

I'd love some references on what you see as the ease of rigging paper ballot elections in modern elections with multi-partisan election officials. Every attack I've heard of requires cooperation of many people, so wholesale attacks are hard. Wholesale attacks on online elections may well turn out to be trivially executed by a savvy individual, and after an exploit is published, by a clueless script-kiddie.

[tromer]

@evainfeld It sounds to me that you're proposing to essentially use the Sander Ta-Shma protocol, using a blockchain as a public broadcast channel.

Why use a blockchain at all? If users have receipts for their votes (which they can present in case the final tally did not include their vote), then there's no need for an immutable blockchain -- one large commitment at the end will suffice. Conversely, if users don't have receipts, then they can just be excluded from the blockchain.

So it seems to be that you'd need some kind of Helios-like receipt system, perhaps combined with Sander Ta-Shma. That doesn't sound trivial.

Also, eliminating the memo field does not prevent coercion. For example, users can be forced to send a particular vote while the attacker is watching (or operating) their computer. Again, Helios shows example of mitigation strategies (letting users cast a new vote which replaces their old one). How would you address this?

[bjowczarek]

I have a felling that we are still talking about different things. When organizing a paper ballot you are always dependent on some type of central voting commission. This creates two risks: ⁃ people do not believe government (or organization) leaders and expect that they’re going to defraud elections. This may influence tensions and further arguments regardlles results were falsified or not. Giving people chance to verify they votes limits this possibility and gives higher trust to voting results. ⁃ Many leaders around the world have such power that they don’t need to care about covering an election fraud. Legitimate multi-party oversight is a very Western thing. Of course, when such things happen it’s too late to change the election method. However, it makes sense to create a method in which such fraud would be harder, so that the international community can put the right pressures.

I agree with you both @tromer @nealmcb , that there are scenarios when voters could be forced to do something, but it’s exactly the same with paper ballots. And technology could mitigate the risk that somebody is monitoring what you do by just staying behind your back. Doubtlessly, our POC will be vulnerable to many attacks and will require much further work, but current paper ballot elections are also possible to fraud by a sufficiently powerful individual. IT and computers support all votes calculations and result preparation. Data, even before announcement, are stored in databases. No one can guarantee that they were never manipulated. In my opinion risk that somebody unnoticedly compromises blockchain elections is not an issue that doesn’t exist in paper ballot.

[nealmcb]

Thank you @bjowczarek for describing some of the concerns motivating this work! I haven't said it well, so let me hasten to say that I'm delighted to see creative ideas brought to the table. I've just been trying to point out a variety of ways in which blockchains hurt rather than help in this surprisingly complex realm.

Here is the broader landscape, as I see it. A lot is going on thanks to the work of a wide variety of activists, good-government groups and election officials over the last decade and more. that hasn't gotten as much recognition as I think it deserves. I'm not claiming that we have all the solutions for making elections perfectly trustable! But having good options on the table should help us see where future work should be focused.

Let me distinguish two flavors of assessing political preferences:

• Government-run elections: may involve referrenda proposed by citizens through some process, but involves centralized decision making to define the contests, language for referrenda, registration of voters etc. See below for a variety of approaches to give the public confidence in the outcomes.

• Random Sample Voting (RSV): independent but verifiable assessment of public opinion: any organization can take public registration data or their own public list of appropriate voters and do a publicly verifiable random sample, send ballots to the sampled voters, combine that with end-to-end open audit (E2E) techniques and decoy ballots to deal with integrity and vote-buying concerns, etc. (Disclaimer - I'm involved with this....) I think this can address the trust issues you note in an even more robust fashion, but it is a yet more radical change with a variety of other challenges facing it.

The paper Evidence-Based Elections goes a long way to laying out a guiding philosophy for running public elections in a truly trustworthy way.

When people vote in properly run physical polling places (the classic "Australian ballot") the risk of coercion is dramatically reduced.

Paper ballots and risk-limiting audits (RLAs) are designed to establish the "software independence" of the election and thus mitigate most of the risks with computerized tabulation of ballots. We've pioneered state-wide RLAs in Colorado last year, and when there are individual cast-vote records (CVRs) which can be matched with the original voter-ferified paper ballots, ballot-level comparison RLAs are a very efficient new best practice.

We've also put together a Public RLA Oversight Protocol to help establish clarity on what evidence should be shared so the public does indeed have the kind of evidence it needs to be confident that the outcomes are supported by the ballots.

Beyond that, mechanisms already exist for establishing much deeper trust in the outcomes, e.g. via E2E approaches. One example is Scantegrity, used in Takoma Park municipal elections twice. Another is STAR-Vote, backed by Travis County and a set of crypto and auditing experts (disclaimer - I was involved with both of those). Other good proposals also exist. They don't need blockchains, as explained in the materials by Josh Benaloh and Joe Kiniry referenced here and elsewhere.

But I certianly agree that there are places where the authorities can't be trusted even for the most basic of election safeguards. That is of course a rather challenging environment to work in, and I think RSV might be one worthy approach to pursue.

[evainfeld]

We would like to recap and extend some of the incredibly productive discussions that we had at ZCon0 about this project. In accordance with ZCon rules, the statements made face-to-face rather than from the stage or on the web will not be attributed.

We are very happy that using Zcash for voting has been proposed before by @arielgabizon (https://github.com/zcash/zips/issues/102). This proposal assumes using the actual Zcash blockchain and building a universal token on top of it. Our proposal is less universal but simpler to build, and each has advantages when it comes to election properties. The merits of choosing the more universal route are worth discussing, and we are certainly open to collaboration. We are weighing the pros and cons of both approaches.

If we’re opening up the candidate addresses at the end, do we really need a blockchain? There are advantages to a distributed infrastructure. It is more resistant to DoS attacks and it is often cheaper - it can rely on less powerful machines rather than a few powerful ones. In fact, Helios may be considering introducing a distributed version: https://escholarship.org/uc/item/7xs630v9. Moreover, a blockchain gives us the option of distributing tokens in a public way and then making sure no new tokens are generated so that the voting authority cannot pad the votes.

Comparison with the Sander Ta-Shma protocol (https://www.cs.tau.ac.il/~amnon/Papers/ST.crypto99.pdf) - indeed, the version of this protocol that features zero-knowledge arguments (chapter 6) does have a similar flavor to our proposal. What the paper refers to as a bank has a similar role to our voting authority. Since Zcash has implemented zk-SNArKs, we can now build a system like this.

Currently, Helios uses homomorphic encryption to count the votes without decrypting them. However, the central server does have the keys to decrypt the votes and see who cast them if necessary. (https://heliosvoting.org/privacy) Moreover, it cannot be verified by outside observers whether the calculation was correct. In the system we are proposing, the central authority releases the viewing keys for the candidate addresses at the end, and so we can verify whether the calculation was correct. The release of those keys would be necessary for the result to be valid. An advantage of Helios is that one can correct one’s vote and so it is partially resistant to coercion - although one can still be coerced not to vote at all, since the information who voted is published at the end. (https://escholarship.org/uc/item/7xs630v9) Our system is currently not coercion-resistant. In his ZCon0 talk, Matthew Green said that "having trusted parties sucks. You can't get off the ground if you have to trust somebody." - this is a philosophy we try to emulate with this system.

[stefanoquintarelli]

I am deeply interested in understanding how you are going to avoid

• the possibility of vote-selling (eg. the possibility for someone to verify her vote in front of someone who is going to pay for her vote)

while preserving

• the anonimity of the vote -the possibility of a person being sure of her vote
• the possibility of verification without trusting in someone else. (otherwise, you could just ask "has my vote been correctly recorded ? " - "yes")

[evainfeld]

Hi Stefan, as I wrote above - this design is not currently coercion-resistant.

[sonyamann]

We regret to inform you that your submission was not selected by the Grant Review Committee, and hence the Zcash Foundation will not be funding this proposal. Thank you very much for your thoughtful contribution!

Please consider subscribing to the Zcash Foundation newsletter so that you will be notified of future funding opportunities.

The Grant Review Committee’s comments:

This proposal suggests to use a fork of the Zcash blockchain as a voting protocol, using the observation that voting can be implemented by sending tokens (issued to voters) to designated addresses (corresponding to candidates/outcomes). One may then expect the security and privacy properties of Zcash would translate into security of the voting scheme. Blockchain-based voting would be well aligned with the Foundation's mission, as it facilitates democratic, decentralized governance mechanisms.

Such blockchain-based voting is a a known concept (a folkloke among experts, and described in this preprint: https://eprint.iacr.org/2017/585), which has severe problems. Voting systems raise many additional considerations, such as resisting coercion, and the need for end-to-end verification of what is actually recorded on the blockchain. Several renown voting experts have weighed on this (including within the proposal's disucssion on GitHub) with highly critical opinions, that are not adequately addressed by the proposal.

Consequentially, the committee does not recommend funding this proposal.

We encourage the proposers to open a conversation with voting experts who have studied the requisite properties and similar systems, to see how the limitations can be resolved or suitable applications identified.