Implementing a decentralized anonymous voting system

Using smart contracts and zero-knowledge proofs

Recently, there’s been a lot of interest in zero-knowledge (zk) proofs in the crypto space (see Mina, Zcash, Deco). The main reason is they provide a way to introduce anonymity to transparency-based decentralized systems. We’re going to look at one “simple” application of zk-proofs — a smart contract allowing for anonymous voting.

The voting implementation is on this repo, with more specific info about the usage in its readme.

Zero-knowledge proofs

General idea

Intuitively, zk-proofs allow us to prove possession of a solution without revealing it. For example, we can prove that we have a solution to a sudoku puzzle, without revealing any information about the said solution.

The main idea of how zk-proofs work is they abuse the fact that knowing a solution to a problem gives you superpowers you do not have otherwise.

Let’s see how we can prove we have a solution to a sudoku puzzle, with an interaction between a prover (us) and a verifier (some skeptical party). We’re going to simplify things and assume no field is required to hold a specific number (so, we’re proving we know how to fill an empty sudoku puzzle).

• First we randomly shuffle the numbers from 1 to 9 in our solution.
• Then we cryptographically seal the shuffled solution and send that to the verifier. Formally, the sealing is done via some one-way function.
• The verifier picks two random fields that have to be in the same 3x3 square or on the same line. He sends us his field choices.
• We send the two keys that unlock the two chosen fields of our sealed solution to the verifier.
• Verifier unlocks his chosen two fields and requires that they contain different numbers.

Ok, so let’s mention that our hidden solution might be wrong in two different places than the ones chosen by the verifier. In that case, our wrong solution isn’t noticed. This is solved by repeating the above interaction (a lot of times), which arbitrarily reduces the probability of the verifier not noticing us not knowing a solution.

Next, why doesn’t the verifier learn anything about our solution? Let’s think about what he sees. He only ever sees two different numbers, which is what he already expects from a correctly solved sudoku puzzle. He cannot construct a full solution from those partial solution views through multiple interactions, as we each time randomly shuffle the numbers 1,2,…,9. Two different numbers thus carry absolutely no information about our solution, as they are random.

Snarks

We are going to look at a specific sort of zk-proofs — zk-snarks, which stands for zero-knowledge succinct non-interactive argument of knowledge. Let’s explain all the words separately

• succinct: proofs are short in size and fast to compute,
• non-interactive: the verification of proof requires no interaction between the prover and verifier,
• argument of knowledge: producing such proofs force the prover to know specific values.

There are numerous models for zk-snark construction, the two most famous being Groth16 and Plonk. Both produce proofs that depend on a given function/program F and prove statements of the form

for a given public values a and b I know secret values x and y, such that F(a, x) = (b, y).

So, for example, you could make a function that takes as public input a sudoku puzzle, as private input its missing values and outputs a public value — 1 if the input is a correct solution and 0 otherwise (note that in this case there is no private output y).

Another more common example is that we have a hiding function H. Then we can prove we know a secret hidden value x such that for a given public y it produces H(x) = y. This doesn’t have to be the end though as x can be used in further proving. This notion of proving things about hidden values is the basis for many (most?) zk-snark applications.

One limitation of the functions describing the problems is that they have to be expressed as arithmetic circuits.

Arithmetic circuits

Because models for zk-snark construction are very mathematical in nature, the problems also have to be described mathematically. Arithmetic circuits describe a problem through enforcing arithmetic (+ and •) connections between defined memory slots (you can imagine them as nodes in a graph). So, each slot has to be either

• a sum of two other slots,
• a product of two other slots.

Luckily we don’t have to construct raw arithmetic circuits but can describe them via a programming language circom. Check the docs here if you want to learn more about circuit construction via circom. Here I’ll just give a simple example on how to construct a circuit that proves for a polynomial

p(x) = x⁴ + x³ + x² + 3x + 2

and a given element y the knowledge of input x such that p(x) = y.

Circuit of a proof of knowledge of preimage of polynomial p(x)

Practical proof construction

This section is for people who want to learn how to concretely construct zk-snarks via a couple of programming tools. Note that once you create your circom circuit, the procedure to construct a zk-snark is algorithmic.

Using circom’s cli app you can compile your circom circuit description to get a file with the extension .r1cs and another with the extension .wasm, using

circom <file>.circom --wasm --r1cs

The proof construction is done via the javascript app snarkjs. First, you download a one-time trusted .ptau setup file from the table here (the exact file depends on the circuit size — for our app I used power-16) and generate a file with an extension .zkey with

snarkjs plonk setup <file>.r1cs <file>.ptau <file>.zkey

Now you can produce the proof from typescript or javascript as

const snarkjs = require("snarkjs")
const proof = snarkjs.plonk.fullprove(<input>, <wasm>, <zkey>)

where the <parameters> are paths to the files with given extensions.

We can also use snarkjs to create a smart contract that verifies a given proof. This is how we achieve decentralized verification that we can trust. To generate the contract, use

snarkjs zkesv <file>.zkey <contract_name>.sol

Now we also have to take care of smart contract parameter construction. This can again be done from typescript as

const parameters = await snarkjs.plonk
    .exportSolidityCallData(<proof>, <public_values>)
    .slice(0, callargs.indexOf(","))

Theoretic voting implementation

Here we’ll describe how our anonymous voting works. There will be three stages:

• registering an election: define eligible voter addresses,
• registering tickets: voters send their tickets to the smart contract,
• spending tickets: voters spend their tickets by proving their ownership to the smart contract in a zero-knowledge way.

Specifically, first, we as a voter pick a secret value, our voting option, and define our ticket as H(secret, option), where H is some function that hides the input. Those are formally known as one-way hash functions and in our case, we use Poseidon, as it’s snark-friendly.

Then comes the zero-knowledge proving. We send (from any address) to the contract our voting option, a special serial number, and a zk-snark that says.

• we know a ticket in an array of all tickets,
• for that ticket we know a secret value, such that the ticket is of the form H(secret, option) for the given option,
• the given serial number is of the form H(secret, ticket).

This zk-snark doesn’t reveal the ticket or the secret value. You’re probably wondering what is the purpose of the serial number. As the system doesn’t see the spent ticket it needs a mechanism to prevent it being double spent. So, it requires the serial number to be a unique ticket identifier, but one that doesn’t reveal any information about the ticket itself.

And that’s it. The contract basically stores the tickets when they are registered and checks that every voter has registered at most one ticket. When it comes to spending tickets, it stores the serial numbers and prevents them from being used again. It, of course, also keeps track of the voting results.

The complete implementation with a cli app is here. It’s a bit more complicated as the contract has to store election ids and keep track of the voting period, during which the tickets can be spent. Also, proving a zero-knowledge inclusion of a ticket inside a list of tickets requires a Merkle tree implementation.

ZCash

Our implementation was actually a simplified idea of how ZCash implements an anonymous decentralized cryptocurrency. Spending a ticket means destroying a coin that was used to make new coins that are sent to other addresses. Those new coins are encrypted in such a way that recipients can decrypt them, and zero-knowledge proof is used to prove that their encryption doesn’t inflate the destroyed coin’s value.