ZkDemocracy: the Easiest Solution for Zero-knowledge Proof-based Anonymous Voting

Our current systems, which are based on representative democracy, face many problems. In fact, they are dysfunctional in the sense that they do not fulfill the fundamental goal of democracy, which is to ensure that the will of the majority prevails.

The following diagram is familiar to everyone:

By strategically selecting electoral districts, it can happen that a party wins even though only a minority of voters supported it. But this is just one of many problems. Participating in politics requires a lot of money, which makes the political system vulnerable to financial influence. The systems we believe to be democratic actually serve private interests and corporations, not the voters (see State Capture).

The solution would be for people to participate in decision-making in a much more direct way, through direct democracy or liquid democracy. Of course, in reality, it is not feasible to organize paper-based referendums on every issue, as such voting is extremely resource-intensive. But is it not possible to solve this digitally, at a low cost, while ensuring the anonymity and security of paper-based voting? I began searching for an answer to this question about two years ago. This is how I came across coin mixers and zero-knowledge-proof technology.

The essence of coin mixers is to make blockchain transactions untraceable. Such a mixer works like a large pool. Users deposit their coins on one side and withdraw them on the other. The key is that we don’t know who withdraws which coin on the other side while ensuring that everyone can only withdraw the same amount they deposited. This is exactly the kind of system needed for anonymous voting. Everyone receives a ballot on which they can cast their vote. We don’t know who cast which vote, but we can be certain that each person casts only one vote.

So, I delved into the source code of one of the most popular coin mixers, Tornado Cash, to understand how it works. An article was written about this as well. Once I fully understood the functionality, I separated the core features and created a library called zk-merkle-tree, which anyone can use to conduct anonymous voting. A proof of concept voting application was also developed, which allows anyone to build their own system. The system is blockchain-based, which makes it secure, but at the same time, it also makes it very difficult to use. If we build on an existing blockchain, transaction costs such as smart contract deployment and similar issues arise, while operating our own blockchain is an even bigger challenge. I wanted a solution that is blockchain-free and easy to set up in a few minutes. That's how zkDemocracy was born.

zkDemocracy is a traditional NodeJS and MySQL-based system that can be set up in just a few minutes. It can operate in standalone mode, where zkDemocracy serves as the complete backend layer, or as a service integrated into a larger system.

The first question that arises with such a system is: how can blockchain-level security be ensured over a MySQL database?

The blockchain is ideal because it is an append-only solution where modifications are not possible, which helps filter out most types of fraud. In reality, the only way to cheat is for someone to vote on behalf of others, or for someone to vote who is not authorized to do so. These possibilities can be prevented with proper voter identification. If this is ensured, fraud becomes theoretically impossible. Therefore, if we can establish such an append-only system on top of MySQL, we can provide the same level of security that blockchain offers.

zkDemocracy's solution to the problem is that each row inserted into the database tables is associated with a 'checkpoint hash.' This is a keccak256 hash, which is composed of the data from the fields and the previous row's checkpoint hash. Similar to a blockchain, the checkpoint hashes are chained, so if anything is changed in the database, the checkpoint hash of every row after the modified one will change as well.

When someone registers as a voter or casts a vote, the system provides a digitally signed, certified receipt confirming that the transaction was completed. This receipt also contains the checkpoint hash. Since both the list of members and the list of votes are fully public after the voting, anyone can check whether any changes have occurred, and if so, they can use the digitally signed receipt provided by the server to prove it.

The current list of registered voters and the most recent checkpoint hash can be retrieved from the system at any time, making any fraud instantly provable. Additionally, there is the option to write the checkpoint hash to the blockchain at regular intervals (for example, every 10 minutes), further ensuring that the database cannot be altered after the hash has been written to the blockchain. This solution provides full blockchain-level security, as any attempt to tamper with the data would require modifying the hash on the blockchain as well.

It is clear that with the above solution, the same level of security provided by the blockchain can be achieved while using familiar technologies (such as MySQL clusters) to operate the system.

I used the Semaphore library for generating and verifying zero-knowledge proofs. It works similarly to zk-merkle-tree but has been audited and has a larger developer base.

zkDemocracy has two fundamental elements: group and voting. A group is a set of voters, such as voters from a specific electoral district, company shareholders, etc. Similarly, voting represents a voting event, which could be a presidential election, a referendum, corporate decision-making, and so on. Multiple groups can participate in a single voting event; for example, in a referendum, all electoral districts participate in the vote, and the results are aggregated. Likewise, a group can participate in multiple voting events. So, if the groups for the electoral districts are established, multiple referendums can be held with these groups. In other words, groups and votings have an n-m relationship.

Let’s now take a look at how a referendum would work when built on the zkDemocracy system.

The first step is to identify the people eligible to vote. In a paper-based voting system, this is done by providing each electoral district with a list of eligible voters for that district. When someone shows up to vote, their name is crossed off the list, ensuring that they can only vote once.

In digital or online voting, this process is much simpler. If the state provides some form of digital identification, the verification can be fully automated. The voter submits a unique commitment, which is recorded with their name in the database. This is one-half of the zero-knowledge proof. The list of voters and commitments is public, protected by a checkpoint hash, and a digitally signed, certified list can be requested at any time. Therefore, if the identification system is secure, fraud at this stage becomes theoretically impossible.

If a digital identification document is not provided, manual identification is required. This can be done in person or even through a video conferencing system (though online identification has its risks due to advanced deep fake technology). Identification can be carried out by one person, but it's more secure if done by multiple randomly selected individuals. Additional security is provided if a video recording of the identification is made and stored for a limited time. During this period, an independent organization can conduct random checks on the recordings to further minimize the chance of fraud. This identification system is as secure as, or even more secure than, the one used in current paper-based voting.

Once registration is successfully completed, the process becomes very simple, as the voter can participate in as many votes as they wish. Due to the checkpoint hash and the publicly accessible voter list, it is ensured that only eligible individuals can vote. The entire database for each voting event is also public and protected by a checkpoint hash. Anyone can verify, using zero-knowledge proofs, whether a given vote comes from a valid voter, and each voter can check at any time whether their own vote is correctly recorded in the database. Voters can easily prove any fraud using the digitally signed receipt provided by the system.

It is clear that with the zkDemocracy system, it is possible to ensure that databases are public and accessible to everyone and that the consistency of the database is provable, while at the same time maintaining voter anonymity.

The system is available on GitHub at the following URL: https://github.com/TheBojda/zkdemocracy

I am also planning to write another article specifically for developers. In the meantime, detailed developer documentation and sample code for using the system can be found on GitHub.

My goal with this development is to prove that the technological conditions are in place to improve our democratic systems. It is up to us how we are able to use these opportunities...