# Decentralised private voting

## References to sub-documents
- The slides that capture a subset of this information can be found [here](https://docs.google.com/presentation/d/1M9GKgbd_jAKe2bxgdPGf9vNjbkGtf4iL0O3eX55DYu4/edit#slide=id.g170d5abc957_1_0).
- An analysis of some membership proof based options can be found [here](https://hackmd.io/ThU25dlxQuWOmb3EozEHhA).
- An analysis of some SNARK-based options can be found [here](https://hackmd.io/PkoDFcQyTkan4w9XIWzCDA).
- A brief comparison of some encrypted votes based options can be found [here](https://hackmd.io/9nByzKZNS126Q9dKMO__ew).
- Vocdoni's post on anonymous voting (introducing some helpful vocabulary) can be found [here](https://docs.google.com/document/d/1yMKcG_JOKF0CfAzuXUwQk_2tRDWbrnueemIQp3OscNU/edit#heading=h.4y8zv0zeaxwu).

## What we want to achieve
- Anonymity : A vote cannot be associated with any voter.
- Authenticity : Only eligible voters are allowed to cast a vote, and one vote is counted per voter.
- Individual and universal verifiability (end-to-end verifiability). Each voter can check their vote was counted, and all can check the process was run correctly.
- No trusted authority.

## The solution space

Some ways to split the solution space :
- On-chain / Layer 1 :
1. Commit and reveal
2. Private (linkable) membership proofs (can be SNARK based, ring signature based, blind signature based) + tallyable votes.
These achieve anonymity or “Privacy of voters” – the vote can be in the clear, but we don’t know who it’s coming from.
3. Normal signatures + tallyable encryption of votes.
These have encrypted votes and achieve “Privacy of votes” or 'vote obfuscation' – the voter can be known, but the vote is encrypted, and tallied without being revealed
- Off-chain / Layer 2 : Any of the above, but with some added complexity, or new tradeoffs in trust assumptions for availability

# What can we achieve with each type of solution?

## Commit and reveal

Commit and reveal has a commitment stage, and then afterwards a reveal stage. It achieves fairness, as defined below, and as the votes are revealed in the clear in the second stage, it easily achieves end-to-end verifiability. Every individual with a block explorer is able to check (a) that the people who voted were valid voters, and (b) how each voter voted.

<div class="c-row">
<div class="c-column">

#### Pros:
- Usable today
- Very simple to implement
- Achieves "fairness" of votes
- Easily achieves end-to-end verifiability
- Useful in cases with delegation, or other important-to-verify situations
</div>
<div class="c-column">

#### Cons:
- Doesn’t achieve normal notions of privacy / anonymity
- Reveals which voters voted
- Reveals how each voter voted
</div>
</div>

<br>

## Private (linkable) membership proofs (can be SNARK based, ring signature based, blind signature based) + tallyable votes

The main point with this type of solution is that it achieves voter anonymity though having :
- indistinuighability of voters, and
- the actual votes in the clear.

This means that different types of voting are easily added, without having to make any more decisions relating to cryptography, or re-program any components that are touching on cryptography.

The protocols discussed below are explained through the lens of having a 'one person, one vote' scheme, but it is easy to extend this type of solution to support different voting functionalities. Examples of
different voting models that are easily supported here include arbitrary non-linear voting, and different subgroups having different voting roles.
In the case of different people having different voting roles, anonymity holds within each type of voter -- the votes of voters with different roles *are* distinguishable from one another here.

A limitation of choosing voter anonymity with votes in the clear is that if the goal is to do token-weighted voting (or any other non-standard
weighting of votes), the voters may be able to be identified by their number of tokens, which makes the cryptographic anonymity redundant. This issue has been seen before in both monero and zcash, because the amount of money that was being transfered in transactions used to be in the clear, and so though the sender of the money thought that they had anonymity, the transaction value acted as an identifier.

A thorough walk-through of some options here is discussed in the document [Linkable membership proofs, some options](https://hackmd.io/ThU25dlxQuWOmb3EozEHhA). All of the solutions listed there satisfy the tradeoffs listed in the pros and cons below.

<div class="c-row">
<div class="c-column">

#### Pros:
- Doesn't reveal which voters voted
- Doesn't reveal how specific voters voted
- Usable today
- Can be very fast to generate, including on phones
- Proving time : O(1)
- Verification time : O(1)
- Signature size : O(1)
- End-to-end verifiability built in to the protocol, votes in the clear means verification is trivial
- Protocols are flexible –- to support a different type of voting, you don't need to do any additional cryptography, due to the votes being in the clear

</div>
<div class="c-column">

#### Cons:
- Different voting / token based weighting schemes may introduce privacy concerns
</div>
</div>

## Normal signatures + tallyable encryption of votes

With tallyable encrypted votes, voters themselves are not indistinguishable from one another, but their votes remain private *even after the results of the vote are computed and published*. In this model, voters are not anonymous, but their votes are counted without ever being decrypted, and the results of the votes are released without revealing any information about who voted in which way, except that which is revealed by the output of the vote itself.

Because the cryptography here is in the computation of the votes, this type of protocol supports different voting functionalities in a different way. Each functionality would need to have its own cryptographic protocol designed, implemented (and hopefully audited) before its launch, but due to
the votes remaining encrypted throughout the entire lifetime of the protocol, the weight- or voter-role-based privacy risks highlighted in the 'Private linkable membership proofs' case are no longer present.

This means that in this case, we need only to assess the impact of the results of the votes becoming public. That means that the protocol chosen for counting and releasing the votes has a direct impact on privacy here.

A thorough walk-through of some options here is discussed in the document [Tallyable encryption of votes, some options](https://hackmd.io/9nByzKZNS126Q9dKMO__ew). All of the solutions listed there satisfy the tradeoffs listed in the pros and cons below.

<div class="c-row">
<div class="c-column">

#### Pros:
- Doesn't reveal how specific voters voted
- Usable today
- Can be very fast to generate, including possible on phones
- Proving time : O(1)
- Verification time : O(1)
- Signature size : O(1)
- End-to-end verifiability can be built in to the protocol
- Different voting / token based weighting schemes can be supported without introducing the same privacy concerns as with voter anonymity + votes in the clear.

</div>
<div class="c-column">

#### Cons:
- Reveals which voters voted
- Protocols are generally not 'extendable' or flexible – to support a different type of voting, you need to design and implement an entirely new scheme with the desired properties of your new voting functionality
- Use of cryptography means it’s not trivial to verify
</div>
</div>

## Private (linkable) membership proofs + tallyable encryption of votes

This paradigm combines the two above.
<div class="c-row">
<div class="c-column">

#### Pros:
- Doesn't reveal which voters voted
- Doesn't reveal how specific voters voted
- Usable today
- Eliminates privacy risks of 'private linkable membership proofs', due to weightings / votes being encrypted
- Can have fast proving and verification times
- Can have small proof sizes
- Can be light client friendly
- End-to-end verifiability can be built in to the protocol
- Different voting / token based weighting schemes can be supported without introducing the same privacy concerns as with voter anonymity + votes in the clear.

</div>
<div class="c-column">

#### Cons:
- Protocols are not flexible – to support a different type of voting, you need to design and implement a new scheme from the start
- Use of cryptography means it’s not trivial to verify
- Generally the most complex option
</div>
</div>

# Some security defintions
Summarised from [Roger's document](link_to_doc)
- Eligibility verifiability : Anyone can check that each vote in the election outcome was cast by a registered voter and there is at most one vote per voter.
- Individual verifiability : A voter can check that her own ballot is included in the election’s bulletin board.
- Universal verifiability : Anyone can check that the election outcome corresponds to the ballots published on the bulletin board.
- End-to-end verifiability : E2E == (Individual verifiability + Universal verifiability [ + Eligibility verifiability ])
- Receipt-freeness (RF) : The receipt-freeness property means that a voter cannot produce a proof of his vote to a third party. (Coercion-resistance : voter cannot cooperate with a coercer to produce a vote proof.)
- Fairness: No early results can be obtained which could influence the remaining voters.

<style>
.c-row{
background:#f0f0f0;
}
.c-row:after {
content: "";
display: table;
clear: both;
}
.c-column {
float: left;
width: 50%;
padding: 10px;
}

/* CSS hack to add section numbers to titles,
starting from h2.*/
/* Titles numbers */
.markdown-body h1 {counter-reset: h2}
.markdown-body h2 {counter-reset: h3}
.markdown-body h3 {counter-reset: h4}
.markdown-body h2:before {counter-increment: h2; content: counter(h2) ". "}
.markdown-body h3:before {counter-increment: h3; content: counter(h2) "." counter(h3) ". "}
.markdown-body h2.nocount:before, .markdown-body h3.nocount:before { markdown-body: ""; counter-increment: none }
.markdown-body h1:before, .markdown-body h2:before, .markdown-body h3:before {
color: #737373!important;
}

/* TOC numbers */
.toc ul li ul {
counter-reset: section;
list-style-type: none;
}
.toc ul li ul li::before {
color: #919191!important;
counter-increment: section;
content: counters(section, ".") " ";
}
</style>