BillionZKVoters

Can large scale voting be performed on-chain? I have a solution. With off-chain ZK voting and a combination of naturally incentivized off-chain ZK counting, we can tally up the results on-chain, all feasible with today's technology. Multiple vote counters (shards) can scale up the speed of counting to an arbitrary factor. All fully decentralized, including counting and inter-component communication.

I use Aztec's Noir and Barretenberg for writing, generating and verifying ZK proofs. The ballots are distributed to each voter in form of Merkle Tree proofs. Voters sign their votes using their wallet (or signing ID card in the near future) and produce proofs and nullifiers by running the Voting Prover. Interested vote counters (for the appropriate side) count their own votes without being able to cheat by producing recursive incremental validity (ZK) proofs of one-time counted votes, assured by proof of single element insertions in Sparse Merkle Trees. The voting population can be split in disjoint shards for scaling of the system. At any time, the current count (or the final one) can be verified on-chain and recorded.

All components are decentralized and duplicate-agnostic and communicate via IPFS PubSub.

In addition I devised and implemented a new ZK Optimized Sparse Merkle Tree in which membership in not only empty, but also single-element (sub)trees can be verified with no hashing instead of performing log((sub)tree size) hashes.