ZK Labs: Scalable & Private Voting through Bilinear Pairings

[mattdf]

ZK Labs: Scalable & Private Voting through Bilinear Pairings

Abstract

The work shall produce a scheme for off-chain signature generation with efficient on-chain verification. The scheme should scale well with the number of participants (sublinearly, super-sublinearly, or logarithmically), and the steps beyond key registration and final verification should be done off-chain.

The goal is to support on-chain ring signing that can handle a member set with size of at least in the multiple thousands. Primary use cases would be voting and authentication, ideally with the option of verifiable anonymity.

Currently, no ring signature implementation can scale to anything beyond 10-15 participants per ring, per block. We hope the R&D undertaken through this grant will serve as a foundation to overcome these limitations.

The end product should be a set of libraries supporting the on-chain and off-chain processes, and a proof of concept implementation for scalable on-chain voting that leverages the Aragon platform. A diagram of the interplay of the components in the final delivery can be seen here.

In terms of prior art, there is an implementation[1] of Linkable Ring Signatures[2] and there is a RingCT Token[3] implemented, however they are not specific to voting and are not tailored to scalability in the 100s to 1000s of participants due to heavy on-chain computation. The work undertaken will hopefully provide a foundation for scalable ring signatures for many different applications.

• [1] - https://github.com/mattdf/RingCrypto/
• [2] - https://eprint.iacr.org/2012/577.pdf
• [3] - https://github.com/solidblu1992/RingCTToken

Roadmap / Deliverables

Below is a breakdown of work, with ordered dependencies. As parts of the work require specific skillets, not all of the team will be working at the same time - e.g. the implementation phase is dependent on the outcome of the research phase.

Q2-Q3 - Research Phase

Month 1

• Research possible paths (accumulators, bilinear sigs, threshold sigs).
• Find most feasible/efficient scheme.

Month 2-3

• Write report with findings (performance and scalability difference between approaches)
• Formalize final algorithm/approach into a paper
• Peer review scheme

Q3-Q4 - Smart Contracts / Infrastructure Phase

Month 3-4

• Prototype/implement chosen scheme in Solidity (on-chain component)
• Write userland tools for signature generation, testing

Month 4-5

• Write supporting libraries, server/relay tools in Python/Go/Haskell (off-chain/infrastrucure components)
• Write test integration into Aragon app
• Document APIs and write final specification

Month 5-6

• Formal audit/review of complete implementation

Funding / Burndown

Cost is $145k in development and support costs, working capital to be supplied in ETH.
60k allocated to research phase, and 85k allocated to implementation phase.

Success reward: Up to $50k in ANT, given out when final public release is ready.

Team Name

ZK Labs Research

Team Members

Matthew Di Ferrante - Ethereum Foundation Security, Founder of ZK Labs.

• LinkedIn: https://www.linkedin.com/in/matthewdiferrante
• Github: https://github.com/mattdf
• Twitter: https://twitter.com/matthewdif
• Commitment: full time

Dean Eigenmann - Founder of Harbour Project, Dev/Auditor at ZK Labs.

• LinkedIn: https://www.linkedin.com/in/deaneigenmann/
• Github: https://github.com/decanus
• Commitment: part time smart contracts/infrastructure

Jake Goh - Ethereum Foundation Researcher.

• LinkedIn: https://www.linkedin.com/in/jake-si-yuan-goh-25a56682/
• Github: https://github.com/jakegsy
• Commitment: full time smart contracts/infrastructure, part time research

Rebekah Mercer - PhD Cryptography Student at Aarhus University.

• LinkedIn: https://www.linkedin.com/in/rebekah-mercer/
• Github: https://github.com/bekahoxoo
• Commitment: full time research phase, part time implementation

Legal Structure

ZK Labs GmbH (Swiss GmbH, Zug domicile)

Code License

All code written by the team will be GPLv3. If the team needs to leverage or modify existing libraries, the modifications shall be under a copyleft license if possible.

[mariapao]

Hi @mattdf thanks for submitting your proposal!

As this proposal is related to this initial proposal that is already approved, what we can do is convert this proposal into a request for funding (RFF), moving to the second phase of the application. This is the guide for submitting the RFF. The only things that you have to add are:

1. More information about the team (commitment of each member and social profiles[github][linked] [twitter]). You have a template here

2. A more detailed roadmap. We would like to see a timeline for the deliverables. You have a template here.

3. PoC or research paper. I know part of the work is research but can you provide us with a sort of initial document/diagram with the components, architecture and tools that you have in mind for the project?

4. A comment on the state of prior art and how the new proposal is better.

All the above referred points will help us with the assessment of the merits of the project to be approved. Let me know if you any help with the above.

[mariapao]

Hi @mattdf thanks a lot for adding everything we needed :)

Could you convert this into a PR following these instructions (point #3)? We just need to keep the process consistent ;)

[sirpy]

Are you familiar with DEDIS implementation for ring signatures?
https://github.com/dedis/kyber/blob/master/sign/anon/sig.go

[LouisGrx]

This proposal hasn't received any love in the past 6 months. I will close it.