Hekaton: Horizontally-Scalable zkSNARKs Via Proof Aggregation

Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) allow a prover to convince a verifier of the correct execution of a large computation in private and easily-verifiable manner. These properties make zkSNARKs a powerful tool for adding accountability, scalability, and privacy to numerous systems such as blockchains and verifiable key directories. Unfortunately, existing zkSNARKs are unable to scale to large computations due to time and space complexity requirements for the prover algorithm. As a result, they cannot handle real-world instances of the aforementioned applications. In this work, we introduce HEKATON, a zkSNARK that overcomes these barriers and can efficiently handle arbitrarily large computations. We construct HEKATON via a new "distribute-and-aggregate" framework that breaks up large computations into small chunks, proves these chunks in parallel in a distributed system, and then aggregates the resulting chunk proofs into a single succinct proof. Underlying this framework is a new technique for efficiently handling data that is shared between chunks that we believe could be of independent interest. We implement a distributed prover for HEKATON, and evaluate its performance on a compute cluster. Our experiments show that HEKATON achieves strong horizontal scalability (proving time decreases linearly as we increase the number of nodes in the cluster), and is able to prove large computations quickly: it can prove computations of size 2 35 gates in under an hour, which is much faster than prior work. Finally, we also apply HEKATON to two applications of real-world interest: proofs of batched insertion for a verifiable key directory and proving correctness of RAM computations. In both cases, HEKATON is able to scale to handle realistic workloads with better efficiency than prior work.