2024 305 Pianist Scalable zkRollups via Fully Distributed Zero Knowledge Proofs Tianyi Liu

### Overview In this talk, the speaker presents Pianist, a scalable, fully distributed zero-knowledge proof (ZKP) protocol designed for arbitrary arithmetic circuits, with applications targeting zkRollups and zkEVM on blockchains. While general-purpose schemes like Plonk provide quasi-linear proving time and constant proof size and verification time, scaling them on a single machine encounters severe bottlenecks in proof generation time and memory cost. Pianist addresses this challenge by distributing proof generation across a cluster while maintaining the asymptotic complexity of Plonk and requiring only constant communication between the master node and each worker node.

### Key Topics - **Zero-Knowledge Proofs & zkRollups**: Leveraging succinct zero-knowledge proofs (such as Plonk) so untrusted parties can verify execution correctness without re-executing transactions, scaling blockchain systems. - **Limitations of Prior Distributed ZKPs**: Earlier distributed systems such as DIZK (based on Groth16 and R1CS) and Z-Bridge (based on GKR and Virgo polynomial commitments) suffer from complex witness reductions or require linear communication. - **Plonk Bottlenecks in Distributed Settings**: Distributed execution of the Number Theoretic Transform (NTT) to compute witness polynomials normally requires inter-machine vector transpositions across butterfly networks, incurring linear communication overhead. - **Pianist Architecture**: Bypassing cross-machine NTTs by partitioning circuits and using bivariate polynomial identities and distributed polynomial commitment schemes (PCS) like KZG.

### Technical Details - **Bypassing Distributed NTT**: Rather than executing global butterfly transforms across machines, Pianist partitions the circuit into $M$ parts across $M$ machines and establishes an independent argument for each. Each vector holding distributed polynomials across machines is interpolated over powers of a root of unity to form a bivariate polynomial identity, which is verified on random challenge points via the Schwartz-Zippel lemma. - **Interactive Protocol Execution**: Each worker node maintains its own polynomials and evaluates them at a challenge point $\alpha$ received from the verifier. Evaluations are transmitted to the master node, which constructs a new polynomial identity and commits to a witness ($H_y(\alpha, Y)$). The prover cluster then evaluates this on an additional random evaluation point from the verifier and produces a bivariate KZG opening proof. - **Arbitrary Circuit Generalization & Robustness**: Pianist extends beyond data-parallel circuits to arbitrary arithmetic circuits by implementing a distributed grand product argument. Additionally, the master node can identify faulty proof fragments from worker nodes in data-parallel setups and generate proofs for correct slices without rerunning the entire cluster. - **Implementation & Benchmarks**: Implemented on top of the Plonk codebase in the gnark library, Pianist demonstrates that proving time and memory usage scale down proportionally as cluster size grows, maintaining low overhead even with small numbers of worker nodes.

### Takeaways Pianist offers a fully distributed ZKP protocol for general arithmetic circuits that preserves the constant proof size, constant verification time, and quasi-linear proving computation of Plonk while requiring only $O(1)$ constant communication between the master and worker nodes, effectively removing distributed communication bottlenecks in zkRollup scaling.