Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs

In this subsection, we introduce Orion, a groundbreaking zero-knowledge argument system that achieves O(N ) prover time of field operations and hash functions, and O(log 2 N ) proof size. Orion stands out for its concretely efficient performance, addressing the high overhead on proof generation time that has limited the efficiency and scalability of existing schemes with succinct proof size. Our implementation of Orion demonstrates remarkable performance, with a prover time of 3.09 seconds and a proof size of 1.5MB for a circuit with 2 20 multiplication gates. Notably, the prover time is the fastest among all existing succinct proof systems, and the proof size is an order of magnitude smaller than a recent scheme proposed by Golovnev et al. in 2021 [GLSTW]. Orion's efficiency improvements can be attributed to two novel techniques. Firstly, we propose a new algorithm for testing whether a random bipartite graph is a lossless expander graph based on the densest subgraph algorithm. This approach allows us to sample lossless expander with overwhelming probability, improving the efficiency and/or security of all existing zero-knowledge argument schemes with linear prover time. The testing algorithm based on the densest subgraph may also be of independent interest for other applications of expander graphs. Secondly, we develop an efficient proof composition scheme called code switching, which reduces the proof size from square root to polylogarithmic in the size of the computation. This scheme is built on the encoding circuit of a linear code and demonstrates that the witness of a second zero-knowledge argument is the same as the message in the linear code. The proof composition introduces only a small overhead on the prover time, further enhancing the performance of Orion. By combining Orion with Libra, a fully optimal prover in terms of complexity can be achieved, significantly advancing the field of zero-knowledge proofs. Distributed Proving The second part of this thesis presents another line of work focused on parallelizing and distributing zero-knowledge proof systems. In this direction, we introduce deVirgo[Xie+22], a novel protocol that builds upon the Libra and Virgo protocols to achieve parallel and distributed proof generation. This approach improves the scalability and efficiency of zero-knowledge proofs, expanding their applicability in various privacy-preserving applications. deVirgo takes advantage of the strengths of both Libra and Virgo. By parallelizing the prover and enabling distributed proof generation, deVirgo tackles the challenges posed by large-scale computations and high prover complexity, which have traditionally limited the practicality of zeroknowledge proof systems. The development of deVirgo represents a significant advancement in the field of zero-knowledge proofs, enhancing their performance and scalability. Another significant protocol is Pianist, a significant protocol built on the Plonk proof system, leverages key features and optimizations such as bi-variate KZG[KZG] commitments and Lagrangebased techniques. These innovations make the distributed proving system more scalable and efficient. The bi-variate KZG commitments with Lagrange-based techniques aim at reducing the size of communication between machines. As a result, Pianist achieves a significantly reduced communication overhead of just several kilobytes. deVirgo In this subsection, we delve into the details of deVirgo, a distributed SNARK protocol designed for data-parallel circuits. Data-parallel circuits, as mentioned earlier, consist of multiple identical sub-circuits with no connections between them. This characteristic allows each sub-circuit to be processed independently, providing an opportunity to accelerate proof generation by handling them in parallel. deVirgo is built upon the Virgo protocol for two main reasons: firstly, Virgo does not require a trusted setup and is plausibly post-quantum secure; secondly, Virgo is among the fastest protocols with succinct verification time and proof size for large-scale problems. deVirgo extends Virgo to handle data-parallel arithmetic circuits, achieving optimal scalability without any overhead on proof size. The protocol is specifically designed to process data-parallel circuits with N copies using N