KZH-Fold: Accountable Voting from Sublinear Accumulation
Hossein Hafezi
VideoAbstract:
Accumulation schemes are powerful primitives that enable distributed and incremental verifiable computation with less overhead than recursive SNARKs. However, existing schemes with constant-size accumulation verifiers, suffer from linear-sized accumulators and deciders, leading to linear-sized proofs that are unsuitable in distributed settings. Motivated by the need for bandwidth-efficient accountable voting protocols. Our contributions are as follows:
1- We introduce KZH, a novel polynomial commitment scheme (PCS), and KZH-fold, the first sublinear accumulation scheme where the verifier only does 3 group scalar multiplications and O(n^{1/2}) accumulator size and decider time. Our scheme generalizes to achieve accumulator and decider complexity of k . n^{1/k} with verifier complexity k.
2) Using the BCLMS compiler, we build Homa-star, an IVC (PCD) scheme for R1CS, based on PCS accumulation, in which instantiated KZH-fold results in a sublinear proof and decider. 3) We present Homa-galaxy and Homa-universe, our approach for non-uniform IVC and non-uniform PCD respectively, they can be built via any PCS accumulation scheme, e.g. KZH-fold. Homa-universe is the first approach to non-uniform PCD that, unlike the previous works, i.e. SuperNova and Protostar, the prover's computation and communication at each step, grows sublinearly with the combined circuit size of all instructions.
4) Leveraging these advancements, we demonstrate the power of KZH-fold by implementing an accountable voting scheme using a novel signature aggregation protocol supporting millions of participants, significantly reducing communication overhead and verifier time compared to BLS-based aggregation.
5) We implemented and benchmarked our protocols, Homa-star initiated with KZH-fold achieves a 2000x reduction in communication and a 50x improvement in decider time over Nova when proving 2000 Poseidon hashes, at the cost of 3x the prover time.
Bio:
Hossein is a first-year PhD student at NYU, working with Joseph Bonneau and Benedikt Bünz. His research focuses on both the theory and practical applications of SNARKs, with a particular interest in developing SNARKs for real-world use cases.