Elections are the elephants in the room of (un)trusted processes
We highlight some of the tensions in designing a satisfactory electronic voting protocol, without centralized trust, laying the groundwork to present two ZKP-dependent solutions.
As Stratumn’s mission is to free organizations and individuals to trust the processes that surround us, it’s only natural we would investigate adding an election application to the Indigo ecosystem. In this post we’re going to focus on a specific kind of election: boardroom voting with proxies.
Boardroom voting refers to elections that involve a small number of participants (a handful to a few hundred), where strict privacy guarantees are desired and the participants’ voting power is not necessarily equally distributed. Proxy voting allows each participant in the election to delegate some (or all) of their votes to another eligible participant.
While electronic boardroom voting with proxies has obvious convenience and efficiency benefits, making such a system transparent and trustworthy without compromising the privacy of the voters turns out to be quite tricky. We offer a simplified comparison with two popular styles of physical voting to understand the tradeoffs at stake: voice voting (viva voce) and paper ballots. Voice voting entails public disclosure of one’s vote, in front of the voting community and election officials, while secret paper ballots allow participants to select or write-in their choices in a presumably private environment.
In addition to verifiability and anonymity, we are also concerned about franchise: every participant should have the opportunity to vote exactly the number of times they deserve (for invalid participants, that would be 0). Paper ballots suffered (especially in the early days) from vulnerabilities to ballot stuffing, making franchise difficult to guarantee.
Not only do we want to make sure our elections verifiable, anonymous, and franchise-full, but we would also like to avoid having a centrally trusted authority of any kind, so the protocol could be run equally well in a variety of network environments.
To summarize, we would like our boardroom voting protocol to satisfy the following properties:
Verifiability. Anyone with access to the network can verify the correctness of:
– participant registration
– individual votes
– vote tallying
– the election outcome
Anonymity. No vote leaks information about the identity of the voter who cast it.
Franchise. Each participant has a number of votes corresponding to their shares according to a predefined public distribution of shares. A participant may cast a maximum of one vote for each share they control.
And of course, especially important in the boardroom context, the election should permit proxying.
- Proxying. Any participant can delegate any (or all) of their votes to any other participant for a given election.
As we have seen above, these properties are sometimes in tension. The question is, can we have them all in an electronic system in which “trusted” counting or registration authorities are replaced with a decentralized notion of trust?
Reconciling Verifiability and Anonymity
We see two broad approaches to solving this problem: in the first, the identity of the voter (The Who) is obfuscated, while in the second, the voter’s choice (The What) is hidden. We summarize the differences as follows:
||How are votes counted?
||How is franchise enforced?
|Who: Identity of voter (participant X voted for Bob)
||deterministic shadow identities can neither be forged nor traced
|What: Choice of voter (Anton voted for candidate Y)
||random factor cancellation reveals sum of votes
As you might imagine, neither solution is perfect, and each compromises some other desirable properties in order to satisfy our design criteria above. The intricacies of both approaches (Hidden Who and Hidden What), as well as their tradeoffs, will be covered in a future article in this series. For the moment, let it suffice to say that both the shadow identities and random factor cancellation use zero-knowledge proof systems to achieve their obfuscatory goals.
Both approaches also make use of a two-phase protocol, in which all prospective voters must first register before any of them can vote.
Wait, Did Somebody Say Registration? Given the current debate about the inadequacies and pitfalls of voter registration in the physical world, why port this antiquated concept over to our protocol? In physical systems, registration is intended to prevent unauthorized people from voting, and to prevent valid voters from voting multiple times. In many electronic voting protocols (including this one), registration is also fundamental to resolving the inherent tensions in our design criteria. By separating the Registration phase from the Voting phase, we have the power to unlink each participant’s identity from their actual votes, while still allowing counting of the collection of votes as a whole.
The Basic Protocol
Our protocol outline closely follows elections in the physical world:
1) Election Proposal
2) Participant Registration
4) Election Outcome
Phase 1. Election Proposal
Any participant may propose an election by sending a Propose message to the network. The Propose message must specify all of the relevant election details, such as:
- Description/purpose of the election
* Eligible participants’ public keys
* Duration period for Participant Registration and Voting phases
- Victory criteria
– Quorum size (if any)
– Social choice function (majority, plurality, approval, rank-order, etc)
- Protocol-specific cryptographic parameters
In many situations, participants may be concerned how the list of eligible participants is determined. Constraints could be added to a particular implementation of the system such that a Propose message is not considered valid unless its participant list was signed by a specified signature, or came from a certain Proof of Process Network.
Phase 2. Participant Registration
Once a valid Propose message has been sent to the network, the Participant Registration phase is officially open (for the period of time specified in the Propose message) and participants may begin to register.
During the Participant Registration phase any legitimate participant may send a Register message to the network. While the nature of the message depends on the anonymity strategy chosen above (either Hidden Who or Hidden What), in either case the registration message prepares the system to accept another vote, and includes any cryptographic parameters or commitments which the relevant zero-knowledge proof system requires.
The Participant Registration phase also implements the (optional) delegation of voting rights within the current round. It allows participants to designate so-called proxies for the purpose of letting them vote on their behalf. In both cases (Hidden Who and Hidden What), the delegation is achieved via encryption of the secret data (Who or What) with the proxy’s public key, and subsequently broadcasting this encrypted data to the network. Thus, only the designated proxy will be able to decrypt the data and be able to cast the vote, while everybody else will have absolutely no idea to whom the voting right has been delegated.
Once all the participants have registered, or the timeout period (specified in the Election Proposal) has elapsed, voting may begin.
Phase 3. Voting
After someone has signaled the end of the Participant Registration phase, the Voting phase officially begins and any registered participant may send a Vote message to the network. The eligible options and duration of the voting period are detailed in the Propose message at the beginning of the protocol.
The actual Vote message contains the selected option and a proof of its validity. In the case of Hidden Who, the proof is a digital signature created by the shadow identity’s owner, whereas for the Hidden What, a zero-knowledge proof ensuring the validity of the chosen option is used.
Phase 4. Election Outcome
After the Voting phase comes to end, the votes must be tallied and published in a way that is transparent and irrefutable. Any of the participants can (and should) verify the correctness of the election outcome by performing the relevant calculations.
The protocol described above can be run on a variety of network architectures, depending on the organization’s preferences and trust requirements. Some networks require centralized control and intervention, while others will benefit from being uncontrollable by a single authority. Our solution does not rely on a single model, as the Indigo Framework can be used to design a broad range of networks, from contemporary client-server architectures to decentralized and trustless blockchains.
Irrespective of the network type, each of the participants must have the ability to send messages to the system. In the Hidden Who approach, an anonymous channel for posting messages to the network would be required.
At this point, the basic context and mechanics of our election system should be clear, assuming the following claims hold:
Some network exists that allows us to have confidence that these messages are reliable and unaltered.
Some zero-knowledge proof system can be designed to give us anonymity while maintaining franchise enforcement and public verifiability.
Satisfying the first claim is the goal of Stratumn’s Indigo framework. The second claim will be the subject of our next posts, focusing on the internals of the Hidden Who approach (using zkSNARKs) and Hidden What (using a scheme developed by Hao, et al.)
We are excited to be working during an active period of research and implementation of electronic voting protocols on blockchains and other distributed ledgers. Look out for a working demo in the coming months!
Anton Zuenko is an R&D Engineer at Stratumn.
Ankur Shah Delight is a crypto engineer and software architect.