Anonymised Voting with ZK
Introducing Acropolis: a privacy preserving voting zkApp
Introduction
Voting applications exist as a solve to resolving coordination problems. Within a blockchain setting, a consensus mechanism is itself a form of distributed voting application.
There are a diverse array of voting mechanisms. For example let’s consider a simple majority vote signalled via raising one’s hand in the air. This mechanism exhibits the following properties: simplicity & transparency. Via the principle of informed consent, all voters accept that the advantages of the mechanism outweigh it’s limitations (e.g. a lack of privacy).
However in many cases it is desirable that the voting mechanism supports various forms of information shielding, e.g. anonymous voting. This article explores this use case and presents a zkApp called Acropolis, a technical solution that leverages zero-knowledge (ZK) cryptography.
Why Voting should be Anonymous
Prior to diving into the technical details of the Acropolis anonymous voting protocol, let’s review the benefits of anonymous voting.
- With mathematically verifiable anonymous voting, the overall trust in the voting mechanism increases, leading to more honesty, especially when voting upon sensitive issues.
- By verifying votes mathematically, the likelihood of human error in counting and evaluating is reduced, while the high degree of privacy significantly limits opportunities for manipulation.
Authorization of Voters in the Real World
A key step when conducting any vote is identifying the set of eligible voters. Once identified, the voting mechanism must ensure that only eligible voters are authorised to vote.
Therefore by definition all voting mechanisms rely upon some form of voting authority. Such an authority manages a whitelist of authorised voters — a sensitive information artefact with it’s own security policy.
The whitelist is constructed via some form of KYV (Know Your Voter) mechanism. One example might be the uploading of a passport scan that an ML bot can verify. Another example might be the registration of a cryptographic public key (that maps to an on-chain verified account).
Whilst the identities of voters are thus visible to the voting authority, it is essential that each vote is only known by the voter that cast the vote. To achieve this we can leverage various forms of cryptography.
In version one of the Acropolis protocol, voting secrecy is achieved via a combination of zk proofs and digital signatures. In version two of the Acropolis protocol an optimized Merkle Trie with Nullifiers may offer both enhanced (perfect) privacy and improved performance.
Note: Acropolis does not currently assign weights to votes, but the set of voters could easily be split into subsets of weight assigned voter groups.
Acropolis v1: Protocol
Acropolis (v1) enables anonymous voting through digital signatures over public keys. The cryptographic identity of each user is treated as a secret input to a zero knowledge circuit and never revealed to the public. The only pieces of information that are made publicly available are the signature issued by the authority alongside with the government public key.
A vote is equivalent to a proof that one possesses a cryptographic identity e.g. asymmetric key pair, that verifies one of the signatures published by the authority. External observers other than the issuing authority will not be able to link a cryptographic identity to one of the published signatures, even after the votes have been counted.
Acropolis v1: Open Source Auditing
Acropolis (v1) ships with an auditing toolkit, where users and entities can independently verify the validity of all votes that have occurred for a survey. Documentation on how to use Acropolis alongside said toolkit can be found on the official Github.
Acropolis v1: Issues
1. Having read the above one might conclude that Acropolis (v1) is not perfectly anonymous, since the issuing authority can still link cryptographic identities to asymmetric key pairs.
This observation is indeed correct and enough of a reason for a protocol enhancement proposal. Acropolis (v2) has not been implemented yet, but has the potential to be perfectly anonymous and hide votes even from the issuing authority.
2. Due to expensive Elliptic Curve operations inside the zero knowledge VM, the proof generation can take a significant amount of time even on expensive hardware.
Acropolis v1: Auditing Benchmarks
When generating a Groth16 optimized proof for the first time, which is likely what a voter experiences when running the Client (v1) locally, the process may take roughly 770 seconds on a Macbook Pro M3 64 GB.
While this is a significant amount of time, it may be acceptable in certain scenarios. In cases where this proving time exceeds all expectations and needs, a larger proof may be generated using the Risc0 default prover, which on the same machine takes roughly 2 minutes.
The verification of Groth16 proofs is extremely fast and resource efficient, which will likely enable average users on standard machines to quickly reproduce the survey using the audit utilities provided by Acropolis (v1).
Acropolis v2: Proposal
In order to achieve perfect privacy, the protocol needs to be adjusted significantly. Instead of proving ownership of a cryptographic identity, users may submit the hash of a secret Nullifier that has been combined with their public key, alongside their KYC to the authority.
The circuit must be designed in such a way that the user proves knowledge of a Nullifier and a secret key that corresponds to that exact public key that has been combined with the Nullifer prior to hashing, that links to a specific leaf (hash) in the Tree, without revealing the leaf or the public key.
The proof therefore states that:
“There exists a leaf in the tree that is the composition of the Nullifier and public key that (the composition/hash) was submitted to the Authority by the user (when performing KYC).”
The hash of the Nullifier combined with the public key is included in a Merkle Tree that lives on a blockchain. When voting, a user submits a proof that they know a Nullifier (and possess the corresponding key pair) that is valid for a leaf in the tree, without revealing which leaf exactly they are redeeming. Each submitted Nullifier is stored in the smart contract to ensure that it may only be used once.
Acropolis: Real World Use Cases
Both Acropolis (v1) and (v2) can be utilized to solve real world problems, ranging from community disputes over open source decision making to government elections. We envisage such an application playing a role in the future evolution of the Casper platform.
ZK voting might be the closest we will ever get to a perfectly trusted voting environment, where the privacy of all participants is ensured for the most part and everyone gets to reproduce the entire process locally.
As mentioned earlier there is only one remaining trust assumption for Acropolis (v2) that likely won’t be resolved anytime soon:
The issuing Authority must implement KYC and is responsible for publishing Hashes of Nullifiers.
Acropolis Team
Acropolis was created from scratch during a 3-day Hackathon at ETH-Berlin 2024. Casper R&D Team participants (aka Team Acropolis):
NOTE: Should the team implement v2 then a follow up article will follow.
