Aragon Nest Proposal: Secret voting infrastructure using Ring/Threshold signatures

[izqui]

Aragon Nest Proposal: Secret voting infrastructure using Ring/Threshold signatures

Abstract

The first Metropolis release, Byzantium, introduced a series of precompiled
contracts that made some elliptic curve arithmetic operations available to be
used in smart contracts within reasonable gas costs.

These operations allow for great things such as verifying zkSNARKs proofs,
as well a way to implementing ring signatures on chain.

Ring signatures are a cryptographic construct that allow a number of keyholders
of a particular ring, to sign a message authenticating themselves as part of the group,
in a way that it is impossible to determine who in the group signed a particular message, but
also detecting if one particular member tries to submit more than one signed messages.

This technology could be used to implement secret voting on-chain with a flow similar
to this:

• A sign up period, in which all token holders of a particular token can get a
  key that they can use to vote. This is specially useful for settings in which
  voting is not stake based and every holder has the same voting rights or small
  multiples.

• A voting period, in which key holders can sign their vote and submit it to
  the blockchain in a way that it is almost impossible to identify the voter. A
  Ring Voting smart contract will validate the signature and count the vote if valid.

Deliverables

A smart contract implementation (plus off-chain tooling) to achieve:

1. An initial assessment of what is kept on-chain vs off-chain in regards to reasonable gas costs
2. Key generation process that based on an onchain oracle feedback
   (ask: can this user get a key?) generates a key.
3. A smart contract that validates messages coming from key holders and forwards
   valid messages to a proposal tallying smart contract.
4. Off-chain infrastructure for users to keep their generated key and sign their
   vote message.

Bonus:

5. Make Aragon app using this technology that can be used as an aragonOS forwarder.
6. Best practices and tooling for ensuring vote anonymity.
7. Standardize Ring Voting through Ethereum EIP/ERC process

As this project will require a significant research effort which will probably result in
not yet know facts, these deliverables can be modified for reasonable causes.

Prior art

• https://github.com/stonecoldpat/anonymousvoting

Grant size

TBD

Application requirements

• Diagram with all the components
• Document detailing the architecture and possible libraries and tools to be used
• Details of the team members, alongside with their implication
• Estimated average burn rate for completing the deliverables
• Legal structure to be adopted, if any
• Willingness to open source work under a copyleft license, such as GPLv3.
• Comment on the state of prior art and how the new proposal is superior.

Development timeline

We intend to make an Aragon app for secret voting using this tech in the first half of 2018.

[eccentricexit]

Important notes

For future readers interested in blockchain voting systems or otherwise any voting system using electronics: Any high stake voting system such as a nation election MUST be accompanied by a software independent audit trail to have any value. Specially if that voting system involves having devices connected to the internet.

---

I have been researching trustless voting systems as well and had a proposal that uses similar techniques to provide anonymity to this but is focused on large scale voting systems.

Please read this and tell me if it you think I should create a new issue. Suggestions are also welcome.

---

Vīsus : High Throughput Decentralized Voting System

Abstract

Many of the current on-chain voting systems provide elegant solutions with features that traditional (client-server) e-voting couldn't deliver. However, most of them are either too expensive or too slow to implement on public chains when high throughput is required. Consortium chains can provide such scalability but require users to trust that authorities won't fork the chain. This restricts trustless voting systems to be used on the main chain by small groups and prevents usage in large scale voting systems such as the ones used to elect presidents and state representatives.

By leveraging security of the Ethereum mainnet and performance of a tindermint child chain it is possible to offload high throughput requirements from the main chain while retaining guarantee that tokens can be withdrawn to the main chain even if the child chain completely halts. By submitting merkle roots of every 2^n blocks we can trade finality to further decrease the cost of maintaining the child chain.

Proof-of-Concept Deliverables

1. A token to be deposited to and from the child chain for staking and voting.
2. A smart contract to store and manage:
   • Merkle roots of block sequences;
   • Authorities allowed to submit merkle roots of sequence of finalized blocks;
   • deposit(), exit() and challengeExit() functions.
3. A child chain client to:
   • Collect public keys TXOs from the child chain for ring signatures;
   • Calculate stealth addresses for voting;
   • Calculate key images.
   • Submit transactions
   • Transaction discovery and tallying.

Note: PoC will be UTXO based to simplify proof verification on the parent chain.

Procedure

1. Election authority buys tokens on a regular exchange.
2. Election authority deposits them on the child chain along with candidate's addresses
3. Election authority transfers tokens to voters on the child chain.
4. Voter ring-signs a transaction transferring their vote to a calculated candidate stealth address. The transaction also includes the voter key image.
5. Election authority sunsets the election on the child chain and publishes candidates' view keys.
6. Voters may tally the election results themselves

**Note: The tokens stay on the candidates' wallets forever, are considered spent and cannot be withdrawn to the parent chain again. The tokens received by block producers are newly minted tokens from coinbase transactions.

Incentivization

Block producers, validators and stakers will receive tokens proportional to the number of tokens processed in a block such that blocks with 0 transactions provide no reward.
In short, the system is a transfer of funds from users/election authorities to the stakers/validators/block producers that maintain the blockchain.

Example:
An election where 30.165.500 votes* will be cast in an 8 hour period requires ~1050tx/s
Using a 5 second blocktime rewards 5235 tokens to be distributed among stakers per block.

• Population of Chongqing - The Largest city in the world by population.

Challenges

For these plans we must keep in mind that a voting system has requirements that most plasma chains don't need to deal with:

• A voting system is an all-or-nothing game: In a currency related plasma chain, interaction is mostly centered around 2 parties where one side wants to be sure that the other didn't trick him. However in a voting system, your voice being included in the results is not enough: It is important that everyone else is heard correctly.

• Authorization and account handling: The voting system must be protected against sybil attacks and only allow one vote per participant. Furthermore, there must be a mechanism to do account recovery that doesn't require (or allow) a central authority. Luckily, we have uPort being developed. Integrating uPort into visus creates a bridge between traditional institutions and the blockchain to allow for KYC authorization. Authorization is done by sending an authorization message signed with a government authority private key.

If voters loose their private keys they can recover them using uPort's social recovery.

[burdges]

There is an interesting related discussion started by @evainfeld at ZcashFoundation/GrantProposals-2018Q2#22 (comment)

[mariapao]

Hi @burdges I'll check it out. Thanks for the info :)

[burdges]

I think most threshold classic signature schemes do not do what you want here:

It's true they provide a measure of anonymity, but the anonymity set is tiny due to the communications cost to set them up. Also, threshold signatures do not provide anonymity from everyone, since someone must actually do the Lagrange interpolation.

You want a threshold signatures when (1) your participant set is tiny, and either (2a) you need to hide that a signature is threshold from non-participants or else (2b) you have higher bureaucratic cost for adding a new signature scheme than developer or protocol costs for managing the setup, i.e. you are bitcoin.

There should be deterministic ring signatures with which you can use simpler vote counting schemes, but actually there is a rich field around voting counting and better schemes exist.

[mariapao]

Hi @mattdf what's you take on the above?

[mariapao]

Hi @mtsalenc you didn't submit the request for funding and I don't know why I didn't receive the notification regarding your comment. Are you still interested in applying for this proposal?

[eccentricexit]

@mariapao There is a problem with that proposal: child chains used for high stake voting systems MUST have high liveliness guarantees or would otherwise require significant coordination mid-voting session in case of an attack, so a plasma chain might not be the best solution for this kind of application.

Right now I am looking into swarm's mutable resource updates as a solution, so I won't apply for this proposal.

Thanks for the response 👍 🍪

[Jake-Gillberg]

Hey y'all! It's been a dream of mine to get a workable version of Civitas (a coercion resistant remote voting system) up and running and integrated with Ethereum.

From my (non-expert, limited) research it seems to be the best-in-class method for running secure electronic elections for small-size groups (paper reports 39 seconds per voter is required to tabulate results).

Is this something that other people would be excited to see and work on?

[LouisGrx]

As this issue hasn't received any love since more than 6 months, I will close it. Feel free to open a new issue/ping me if you have any questions.