Written by Luca Giussani, [e-mail]

Horizen Labs developed an on-chain private voting solution which can be deployed on EVM-compatible blockchains, and is compatible with the widely adopted [OpenZeppelin Governor framework](https://docs.openzeppelin.com/contracts/4.x/api/governance).

The solution migrates the well-known [Helios voting protocol](https://eprint.iacr.org/2016/765.pdf) to on-chain, and adds linear homomorphic encryption of the votes and efficient zk-proofs to guarantee:

* integrity of the voting process
* privacy of the votes
* censorship resistance
* reasonable gas costs

Visit our implementation of the protocol in our [open source repo](https://github.com/HorizenLabs/governor-hidden-voting).

In this blog post, we will build the protocol step-by-step. Through the blog, we'll explain the cryptographic techniques and compatibility with the OpenZeppelin framework.

# Introducing the protocol
If you are already familiar with public key cryptography, linear homomorphic encryption, and zk-proofs, then congratulations, the description of our protocol won’t take much time! Otherwise, fear not, we will explain all of these concepts in detail in the next few sections.

An overview of the protocol:

* Votes are encrypted using a linear homomorphic encryption scheme (El-Gamal instantiated on curve bn254 to be precise).
* Only Yes/No votes are considered, even though it would be feasible to extend the protocol to more general ballot types.
* Our protocol relies on an entity, the tallying authority, who possesses some private information which enables them to perform tallying.

The tallying authority generates a key pair (public key, *pk*; secret key, *sk*), and publishes the encryption key *pk* on-chain, and safely stores the decryption key *sk*. The same key pair can be used for multiple voting events.

In order to cast a vote, a user must encode their vote with a 0 (“No”) or a 1 (“Yes”), encrypt it with *pk*, resulting in cyphertext *c*, and generate a zk-proof of vote well-formedness, which ensures that *c* is indeed the encryption of either a 0 or a 1 with key *pk*. Then the user sends the encrypted vote *c* and the zk-proof to the on-chain smart contract.

Upon receiving a vote, the smart contract performs a number of actions:
1. Checks that the user is eligible and has not already voted (these checks are easy, since the user identity, i.e. their address, is known)
2. Checks the zk-proof of vote well-formedness.
* If the check fails, then the vote is simply discarded.
* If the check passes, the encrypted vote is scaled by the voting weight of the user and is then summed to a variable *t* which holds the encrypted running total. This step takes advantage of the linear homomorphic property of the encryption scheme.
5. When the voting period ends, the tallying authority decrypts the variable *t* using decryption key sk, thus obtaining the total weight cast on the “Yes” option. The weight cast on the “No” option can be easily computed by subtraction.
6. The tallying authority sends the result on-chain, together with a zk-proof of correct decryption, which ensures that the result comes indeed from decrypting *t* using key *sk*.

Now that we've introduced the protocol, we will introduce key concepts behind our protocol and build it step-by-step.

# Asymmetric encryption of votes
Our scheme uses asymmetric encryption to protect the privacy of users votes.

*How asymmetric encryption works*: Alice, who wants to receive encrypted messages, generates an encryption key pair, consisting of a public encryption key *pk*, and a secret decryption key *sk*. As the names imply, she publishes *pk*, and keeps *sk* private. Then, Bob, who wants to send Alice an encrypted message *m*, uses *pk* to encrypt *m*, and sends the resulting ciphertext *c* to Alice. Upon receiving *c*, Alice can finally decrypt it using her secret key *sk*, getting back the original message *m*. The entire process is shown in the diagram below.


A key observation is that, to third parties which do not possess the decryption key *sk*, the ciphertext *c* looks completely random, and doesn’t convey any information about the original message *m*. The only viable way to retrieve the original message *m* from the ciphertext *c* is to use the decryption key *sk* to decrypt it.

Likewise the encryption key *pk* doesn’t convey any meaningful information about the decryption key *sk*. In other words, it’s not feasible to compute *sk* from *pk* (on the other hand it is very easy to compute *pk* from *sk*).

These two facts, combined, make the following possible:

* Alice can confidently publish her encryption key *pk*, knowing that it doesn’t reveal anything about her decryption key *sk*.
* Bob can confidently publish the ciphertext *c*, knowing that it doesn’t reveal anything about the original sensitive message *m* to third parties.

Now that we have recalled how public key encryption works, let’s see how it can be used to put together a very crude first version of private voting protocol. The tallying authority generates a key pair (*pk, sk*), publishes the encryption key *pk* and safely stores *sk*.

Then, users who want to vote encrypt their votes with *pk* and publish the encrypted votes on chain. The tallying authority then collects all the encrypted votes, and, at the end of the voting period, decrypts them with decryption key *sk*, performs the tallying, and publicly announces the result on chain.

While this proposed protocol would protect the privacy of voters from third parties, it exposes some vulnerabilities by fully trusting the tallying authority:

1. Tallying authority would be free to tamper with votes and publish a false result
2. Tallying authority learns all the individual votes in the process
3. Tallying authority could refuse to perform tallying, making it impossible to know the result

In the next few sections we will see how our protocol prevents (for the case 1.) or mitigates (for the case 2. and 3.) these three issues.

# Linear homomorphic encryption
We start from issue 2. We would like that the result of the voting could be computed without the tallying authority learning anything about individual votes. At first this sounds like a contradiction, but cryptography comes to rescue with the technique of homomorphic encryption.

In this section we will see how homomorphic encryption can be used to (publicly) compute the (encrypted) result of the voting event starting from the individual encrypted votes, without ever decrypting them.

Homomorphic encryption is a type of encryption which allows to perform computations on encrypted data, without requiring to decrypt them beforehand. In particular, linear homomorphic encryption allows to perform two kind of operations on encrypted values:
* *Addition*, which allows to sum together two encrypted values.
* *Scalar multiplication*, which allows to multiply an encrypted value by another known, unencrypted value.

Let’s suppose for the sake of simplicity that only “Yes”/“No” votes are allowed. “Yes” votes are encoded with the value 1, and “No” votes are encoded with the value 0. Since votes are encrypted before being cast, nobody can distinguish between the encryption of a “Yes” and a “No” vote, thus guaranteeing the privacy of the votes. However, thanks to the linear homomorphic property of the encryption scheme, it’s possible to add together all the encrypted votes, and obtain the (encrypted) result of the voting (i.e. the total number of “Yes” votes). The following diagram exemplifies the situation with two “Yes” votes and a single “No” vote.


The scheme can also be extended to encompass weighted voting, where different voters can have different voting power, usually according to the amount of tokens they hold. Since voting power is usually public, then it’s possible to scale the encrypted votes by the respective voting power before they are added together. This is exemplified in the diagram below, which generalizes the previous one to the case of two “Yes” votes with voting power 10 and 7 respectively and a single “No” vote with voting power 5.


In this section we have seen that, by using a linear homomorphic encryption scheme, it’s possible to process encrypted votes so that the final (encrypted) result of the voting event can be computed without decrypting the individual votes, thus preserving their privacy.

# Zk-proofs of vote well-formedness
In the previous section there was the tacit assumption that voters are honest, i.e. that they only encrypt 0 or 1 values. However, at the moment nothing prevents a dishonest voter from encrypting a rogue value, e.g. 10. After encryption, this would be indistinguishable from a valid 0 or 1 value, and would allow the dishonest voter to cast a vote for the “Yes” option with 10 times their legitimate voting power. This is clearly unacceptable.

A naive solution to this issue would be to require that the tallying authority decrypt each single vote, check that the decrypted value is indeed 0 or 1, and discard invalid votes. However this solution would defeat the very purpose of the scheme, i.e. that the tallying authority should not be required to decrypt individual votes in order to compute the final result.

Also in this case, cryptography comes to rescue, in the form of zk-proofs. Zk-proofs are cryptographic constructions which allow a party (called the prover) to convince another party (the verifier) that a given statement is true, without disclosing any other detail besides that. The statement can involve both public data (the so called public input, known to both the prover and the verifier) and private data (the witness, known to the prover only).

Just to give a concrete example, a prover could use a zk-proof to convince a verifier that they know the solution to a Sudoku puzzle, without disclosing the solution itself. In this case:

* witness <span style="color:red">w</span> would be the solution of the puzzle
* public input <span style="color:green">y</span> would be the already filled out portion of the Sudoku puzzle

The proven statement would be:
> "I know <span style="color:red">w</span> such that plugging <span style="color:red">w</span> into scheme <span style="color:green">y</span> solves the Sudoku."


In the case we are actually interested in, i.e. proving the well-formedness of a vote, we would have instead that:

* witness is the vote <span style="color:red">*v*</span>
* public input consists of:
* <span style="color:green">*pk*</span>, the public key for encryption
* <span style="color:green">*e*</span>, the encryption of v with public key pk

The proven statement is then:

> I know a value <span style="color:red">*v*</span> such that:
> 1. <span style="color:green">*e*</span> is the encryption of <span style="color:red">*v*</span> with public key <span style="color:green">*pk*</span>, and
> 2. <span style="color:red">*v*</span> is either 0 or 1

This way the resulting zk-proof can be used to convince anyone that an encrypted value is indeed "well-formed", an encryption of a 0 or a 1, and not the encryption of another value. Thanks to the zk property, we can prove well-formedness without revealing the underlying value.

Instead of full-fledged zk-SNARKS, which are slow to verify on EVM-compatible chains, we can use simpler Sigma zk-proofs. This means that these Sigma zk-proofs, with our choice of encryption algorithm (elliptic curve El-Gamal on curve bn254), can be efficiently verified on-chain using EVM precompiled contracts for elliptic curve arithmetics.

So, back to our problem. In order to ensure that only valid votes are taken into account in the final result, each voters, besides encrypting their preference, is also required to generate a zk-proof of vote well-formedness, and post it on chain together with their encrypted vote. The smart contract checks the zk-proof against the appropriate public inputs. If the check passes, then the vote is processed and accumulated with all the previous valid votes, otherwise it’s discarded. This is shown in the diagram below:


# Tallying phase
The description of our protocol is almost complete. There is still one missing piece though. According to the description done so far, we can be sure that the result of the voting is trustlessly computed on chain from the individual encrypted votes, and that all and only the valid votes are processed. However the final result is still encrypted, and it’s not usable for any purpose in this form.

The answer, as you may imagine at this point, is that tallying authority just needs to decrypt the result using their secret decryption key, and post the decrypted result on-chain. This must be accompanied by a zk-proof that ensures that decryption was done correctly, without revealing anything about the secret key. Like the zk-proof of vote well-formedness, also the proof of correct decryption is a simple Sigma proof, and can be efficiently verified on-chain.

If you think about it, this closes the circle around issue 1.: the fact that the encrypted result is transparently computed on-chain from the individual encrypted votes, together with the zk-proofs of vote well-formedness, and of correct decryption, ensure that neither the users nor the tallying authority can cheat in any way. The protocol has strong guarantees concerning the correctness of the result.

The tallying phase, therefore, is technically simple. However it’s also the most delicate part of the entire protocol, because it involves some trust assumptions regarding liveness and vote privacy. More specifically, two issues can arise:

* **The tallying authority could fail to perform its tallying duty**, either because of negligence (e.g. loss of the secret key) or maliciousness (they don’t like the voting result). A possible countermeasure is to require the tallying authority to lock some funds as a collateral, which can be slashed if they fail to perform their duty.
* **The tallying authority could sneakily decrypt each and every vote.** Even though the protocol doesn’t require that individual votes be decrypted in order for the final result to be computed, a dishonest tallying authority has still the ability to sneakily decrypt each and every vote, thus breaking their privacy. A possible countermeasure is to use a m-out-of-n threshold decryption scheme. This allows to appoint n independent tallying authorities, each one having a separate share of decryption key. At least m of them must cooperate to perform decryption. This ensures that, if at least n - m + 1 of them are honest, the privacy of the votes is guaranteed.

# Integration with OpenZeppelin Governor

OpenZeppelin has release a modular implementation of the Governor Bravo on-chain voting protocol, which is one of the most widely adopted solutions for on-chain governance of DAOs.

We have written our solution to (also) be compatible with OpenZeppelin Governor framework, by packaging it as a Governor module.

Below you can find a graphical representation of the lifecycle of a Governor proposal.


To take into account the fact that our solution involves a tallying phase, we have split the `Active` phase into two sub-phases, namely `Voting`, during which users actually cast votes, and `Tallying`, during which vote casting is no longer possible, and the tallying authority can perform the tallying.


If you are interested in the implementation details, you can look at the [smart contracts](https://github.com/HorizenLabs/governor-hidden-voting/tree/main/smart-contracts/contracts/openzeppelin-voting) in our repo!

# Conclusions and future developments
In this post we have broken down the inner workings of our protocol for private on-chain voting. Its on-chain nature, together with the cryptographic techniques employed, guarantee correctness and censorship resistance (votes cannot be forged, dropped, or otherwise tampered with by any party).

However, at the current stage, a certain amount of trust must still be put into the tallying authority for what concerns privacy of votes and availability of the final result. We intend to improve in this regard by introducing a threshold decryption scheme so that multiple independent tallying authorities can be appointed, and no one of them can decrypt individual votes without cooperation from the remaining ones. Moreover, standard cryptoeconomic incentives/deterrents can be put in place to mitigate the possibility that appointed tallying authorities do not perform their duty.

Another interesting aspect of our solution is that it’s compatible with one of the most widely adopted frameworks for on-chain governance, the OpenZeppelin Governor framework. At the moment, a DAO wanting to integrate our solution, would have to update its on-chain governance contract. However we are working on a solution which could allow a “plug-and-play” way to integrate our solution. So stay tuned!

If you are curious about the implementation, you can take a look at our [open source repo](https://github.com/HorizenLabs/governor-hidden-voting). If you would like exploring the possibility to adopt our solution for your DAO or you just have questions, [get in touch ](https://share.hsforms.com/1EhH10K2wSPiRtwnMcuBS4gdjxbg)with our team!