Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs

Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs

Speakers: Tianyi Liu; Tiancheng Xie; Jiaheng Zhang; Dawn Song; Yupeng Zhang

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=-I7aoP7GXKw

Overview

The presented work, "Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs," introduces a novel framework for significantly enhancing the scalability and efficiency of zero-knowledge proof (ZKP) generation, particularly for applications like ZK-Rollups and ZK-EVMs on blockchains. Given by Tianyi Liu and his co-authors Tiancheng Xie, Jiaheng Zhang, Dawn Song, and Yupeng Zhang, this research addresses a critical bottleneck in the widespread adoption of ZKP technologies: the substantial computational and memory costs associated with generating proofs for large-scale arithmetic circuits.

Pianist proposes a fully distributed ZKP protocol that maintains the desirable properties of existing efficient schemes like Plonk – namely, quasi-linear proving computation, constant proof size, and constant verification time – while drastically reducing the communication overhead between nodes in a distributed proving system. By achieving constant communication complexity between worker and master nodes, Pianist offers a practical solution for offloading computationally intensive proof generation to a cluster of machines, making ZKP-powered blockchain scaling solutions more accessible and economically viable. This work is pivotal for the future of privacy-preserving and scalable decentralized applications.

Background

▶ Watch: Introduction to ZKP, ZK-Rollups, and ZK-EVM (0:00)

Zero-knowledge proofs (ZKPs) are cryptographic protocols that enable a prover to convince a verifier of the truth of a statement without revealing any information beyond the statement's validity. Essential properties of ZKPs include completeness (a correct statement always yields an accepted proof), soundness (an incorrect statement is rejected, except for a negligible probability), and optionally zero-knowledge (the prover's private input remains confidential) and succinctness (verification time and proof size are sublinear to the input size). The latter two properties are crucial for efficiency and privacy in real-world applications.

One of the most impactful applications of succinct ZKPs is in blockchain scalability, specifically through ZK-Rollups and ZK-EVMs. In a traditional blockchain, every node must execute all transactions in a block to synchronize its state. This process becomes a bottleneck as transaction throughput increases. ZK-Rollups address this by having a powerful machine (the prover) compute the result of a batch of transactions and generate a succinct ZKP for their correctness. Instead of re-executing all transactions, other users (verifiers) can simply verify this compact proof, drastically improving throughput. ZK-EVMs extend this concept to smart contracts, allowing for more complex functionalities beyond simple token transfers.

The underlying computational model for many ZKP schemes is an arithmetic circuit, which represents computations as a series of additions and multiplications over finite fields. General-purpose ZKP schemes, such as Plonk, are designed to generate proofs for arbitrary arithmetic circuits. Plonk, in particular, is widely used in industry due to its efficiency, offering quasi-linear proving time relative to circuit size, and constant proof size and verification time. However, as the complexity and size of these arithmetic circuits grow, even Plonk's efficiency can be insufficient. A single machine often cannot afford the long proof generation times and substantial memory costs required for very large circuits. This limitation has spurred research into distributed ZKP systems.

Prior efforts in distributed succinct ZKP protocols include Dixie, which is based on the Groth16 scheme and the R1CS arithmetic system. Dixie, however, suffers from complex witness reduction and requires linear communication between nodes. Another notable work is ZKBridge, which leverages the GKR protocol and Virgo polynomial commitment, but similarly incurs linear communication costs. The challenge in designing an efficient distributed ZKP system lies in maintaining the cryptographic guarantees and efficiency of single-prover schemes while distributing the computational burden without introducing prohibitive communication overhead, especially for polynomial operations like the Number Theoretic Transform (NTT), which often require extensive data transpositions across machines.

Key Findings

▶ Watch: Pianist's key contribution: constant communication distributed ZKP (4:00)

Pianist's core contribution is the development of a novel, fully distributed zero-knowledge proof protocol that significantly enhances the scalability of ZKP generation, particularly for general arithmetic circuits. The key findings and contributions can be summarized as follows:

1. Distributed Plonk Variant: Pianist introduces a distributed protocol based on a variant of the widely-used Plonk scheme. This allows it to leverage the inherent efficiency of Plonk (quasi-linear proving computations, constant proof size, and verification time) while distributing the workload across multiple machines.
2. Constant Communication Complexity: A major breakthrough is achieving constant communication between the master node and each worker node. Unlike prior distributed ZKP schemes that often require linear communication, Pianist's design drastically reduces network overhead, making it highly efficient for large-scale deployments. This is accomplished by a clever modification of the Plonk protocol that avoids the need for a distributed Number Theoretic Transform (NTT) across all machines.
3. Balanced Proving Cost Distribution: The protocol ensures that the proving cost is balanced and distributed evenly throughout the cluster, preventing bottlenecks at individual nodes and maximizing parallelization benefits.
4. Generalizability to Arbitrary Circuits: While the talk simplifies the explanation using data-parallel circuits, the underlying scheme is generalized to support arbitrary arithmetic circuits, making it broadly applicable to diverse ZKP use cases. This generalization involves a distributed proof of a Runge-Grand product argument.
5. Enhanced Robustness: Pianist incorporates features to improve the robustness of the distributed system. Specifically, the master node can detect incorrect proof pieces generated by faulty worker nodes. Crucially, it can then generate a correct proof for the faulty parts without requiring the re-execution of computations by other correct nodes, thus minimizing wasted effort and improving fault tolerance.
6. Empirical Validation: Practical implementation based on the gnark library demonstrates that as the number of nodes increases, both proving time and memory usage are reduced proportionately. This confirms the theoretical benefits and shows that Pianist introduces minimal overhead in a distributed setting, even with a small number of nodes.

In essence, Pianist provides a practical, efficient, and robust solution for generating zero-knowledge proofs in a distributed manner, removing a significant barrier to the widespread adoption of ZKP technologies for blockchain scalability and privacy-preserving computations.

Technical Deep Dive

▶ Watch: Brief overview of the Plonk protocol internals (5:00)

Pianist's technical innovation lies in its clever adaptation of the Plonk protocol to a distributed setting, specifically by circumventing the communication-intensive aspects of traditional distributed polynomial operations.

At its core, Plonk represents an arithmetic circuit as a single table that captures all mix operations (additions and multiplications) along with "switch" columns that determine which operations are active. This tabular representation is then converted into a series of vector identities. These vector identities are subsequently transformed into a polynomial equation by interpolating each vector onto the powers of a root of unity. The crucial step is to prove that this polynomial equation can be divided by $X^N - 1$, where $N$ is the size of the circuit, implying the identity holds. This divisibility is proven by demonstrating the existence of a quotient polynomial $H(X)$. Finally, by applying the Schwartz-Zippel Lemma, the verifier can check the polynomial identity by evaluating it at a single random point, which is efficiently handled.

The complete Plonk protocol, in its Interactive Oracle Proof (IOP) form, involves the prover providing "oracles" (commitments to polynomials) to the verifier, computing the witness polynomial $H(X)$, and sending its oracle. These oracles allow the verifier to query evaluations and verify the polynomial identity. In practice, these oracles are instantiated using a Polynomial Commitment Scheme (PCS), with KZG (Kate-Zaverucha-Goldberg) being the popular choice in Plonk due to its constant-sized proofs. A significant computational bottleneck in Plonk, especially for large circuits, is the computation of polynomials like $H(X)$, which often relies on the Number Theoretic Transform (NTT) algorithm for efficient polynomial multiplications and additions. NTT, in a distributed context, typically requires frequent data transpositions across machines, leading to linear communication costs.

Pianist's distributed framework combines a distributed IOP protocol with a distributed PCS protocol. While the KZG PCS scheme is relatively straightforward to distribute, the primary challenge addressed by Pianist is the distributed IOP, specifically avoiding the high communication cost associated with distributed NTT. Instead of attempting to distribute the NTT algorithm directly, Pianist bypasses it by modifying the Plonk protocol itself.

The core idea is to partition the arithmetic circuit into $M$ parts, where $M$ is the number of machines (worker nodes) in the proving cluster. Each machine initially holds its own local polynomials corresponding to its part of the circuit. Pianist then applies a transformation that converts the initial vector identity, where vectors are distributed across machines, into a "bit constraint." This is further converted into a "berserk polynomial identity" by interpolating each vector of polynomials on the powers of another root of unity. Similar to Plonk, the Schwartz-Zippel Lemma is applied to check this identity on evaluations at a random point $\beta \alpha$.

The distributed proving process unfolds as follows:

1. Initial Polynomial Holding: Each worker node in the cluster holds its own segment of the polynomials that collectively represent the entire circuit, as per the partitioned structure.
2. First Evaluation Phase: The verifier sends a random challenge point, $\alpha$, to the prover cluster. Each worker node then locally evaluates its respective polynomials at this point $\alpha$.
3. Master Node Aggregation: Each worker node sends its computed evaluations (not the full polynomials) to a designated master node. The master node, using these aggregated evaluations, constructs a new polynomial identity. This identity is derived from the evaluations, effectively collapsing the distributed work into a single identity at the master. Crucially, the master node computes a new witness polynomial, $H_{\alpha}(Y)$, from these aggregated evaluations.
4. Second Evaluation and Proof Generation: The verifier sends another random challenge point. The prover cluster (implicitly coordinated by the master) evaluates the newly constructed polynomial identity at this second random point. The master node commits to $H_{\alpha}(Y)$ and then generates all necessary evaluations and the PCS opening proof (using the distributed KZG scheme) to the verifier.

By having worker nodes only send evaluations to the master node, rather than transposing large intermediate polynomial data for NTT computations, Pianist achieves its constant communication goal. The master node then performs a reduced set of computations on these aggregated evaluations to construct the final proof components.

Furthermore, Pianist generalizes this scheme to arbitrary arithmetic circuits by incorporating a distributed proof for a Runge-Grand product argument. This ensures broad applicability beyond simple data-parallel structures. Robustness is also enhanced: if a worker node submits incorrect evaluations, the master node can identify the erroneous proof pieces and generate correct proofs for those specific parts without requiring other correct nodes to re-run their computations, significantly improving the fault tolerance of the system.

Demo / Proof of Concept

▶ Watch: Pianist's core idea: avoiding distributed NTT for efficiency (8:00)

The efficacy of the Pianist protocol was validated through a practical implementation and experimental evaluation. The researchers implemented their distributed ZKP scheme based on the existing Plonk implementation found in the popular gnark library. The gnark library is a well-regarded open-source framework for building ZKP circuits and proving systems in Go.

The empirical evaluation focused on demonstrating the core benefits of the distributed approach: reduced proving time and memory usage. The experiments showed that when the size of the arithmetic circuit was fixed, both the proving time and memory usage were reduced proportionately as the number of nodes in the proving cluster increased. This linear scaling behavior is a strong indicator of the protocol's efficiency and its ability to effectively distribute the computational load.

Crucially, the results indicated that this proportional reduction holds true even when the number of nodes is relatively small. This suggests that Pianist introduces minimal overhead in a distributed setting, making it beneficial even for smaller clusters rather than only for massive deployments. The demonstration confirms that the theoretical advantages of constant communication and balanced computation distribution translate into tangible performance improvements in practice, making ZKP generation for large circuits significantly more feasible and resource-efficient. The availability of the implementation via a QR code (mentioned in the talk) further encourages independent verification and adoption.

Defensive Implications

▶ Watch: Step-by-step illustration of Pianist's distributed proving process (10:00)

While Pianist primarily focuses on improving the efficiency and scalability of zero-knowledge proof generation, its implications for defenders are significant in an indirect but fundamental way. By making the generation of complex ZKPs more feasible and affordable, Pianist directly contributes to the wider adoption and practical deployment of ZKP-based privacy-preserving and scaling solutions, which are inherently defensive technologies.

1. Enabling Scalable Security: The primary defensive implication is that Pianist enables the practical deployment of highly scalable and secure systems like ZK-Rollups and ZK-EVMs. These technologies are crucial for the long-term security and decentralization of blockchains, as they allow networks to handle vastly more transactions without compromising security or requiring users to run high-powered nodes. By reducing the cost and time of proof generation, Pianist lowers the barrier to entry for ZKP service providers, fostering a more robust ecosystem.
2. Enhanced Privacy-Preserving Applications: ZKPs are a cornerstone of many privacy-preserving protocols, allowing users to prove compliance with rules or ownership of assets without revealing sensitive underlying data. Pianist's ability to handle larger and more complex circuits in a distributed manner means that more sophisticated privacy-preserving applications, previously deemed too computationally intensive, can now be developed and deployed. This includes private transactions, confidential smart contracts, and verifiable computation in sensitive environments.
3. Resilience Against Prover Centralization: One potential risk in ZKP systems is the centralization of proof generation if only a few powerful entities can afford the hardware and compute resources. By making distributed proving efficient and affordable, Pianist helps to mitigate this risk, promoting a more decentralized and resilient proving landscape. Multiple smaller entities can collectively generate proofs, reducing reliance on single points of failure or control.
4. Faster Incident Response and Auditing: In scenarios requiring verifiable computation for auditing or incident response, the ability to rapidly generate proofs for large datasets or complex system states can be invaluable. Pianist could enable faster generation of forensic proofs or compliance attestations, aiding defenders in understanding and responding to security incidents more efficiently.
5. Robustness and Fault Tolerance: The robustness enhancements in Pianist, allowing the master node to detect and correct faulty proof pieces without re-running entire computations, improve the reliability of ZKP systems. This fault tolerance is a defensive characteristic, ensuring that the integrity of the proof system is maintained even if individual worker nodes fail or act maliciously, thereby strengthening the overall security guarantees of ZKP-based applications.

In essence, Pianist strengthens the foundation upon which many future secure and private systems will be built. Defenders can leverage the newfound efficiency to implement ZKP solutions that were previously impractical, thereby enhancing the security, scalability, and privacy posture of a wide range of applications.

Key Takeaways

• Pianist introduces a fully distributed ZKP protocol that makes ZK-Rollups and ZK-EVMs more scalable and practical by efficiently distributing proof generation.
• It achieves constant communication complexity between master and worker nodes, a significant improvement over prior distributed ZKP schemes which typically incur linear communication costs.
• The protocol is based on a variant of Plonk, retaining its desirable properties of quasi-linear proving computation, constant proof size, and constant verification time, but now distributed.
• Pianist avoids the communication bottleneck of distributed NTT by modifying the Plonk protocol's structure, allowing worker nodes to send only evaluations to the master node, rather than large intermediate polynomial data.
• The system is robust and fault-tolerant, enabling the master node to detect and correct erroneous proof pieces from worker nodes without requiring a full re-computation from other correct nodes.
• Empirical results confirm proportional reductions in proving time and memory usage with an increasing number of nodes, demonstrating practical efficiency and minimal overhead even with small clusters.

About the Speaker(s)

The talk "Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs" was presented by Tianyi Liu, who is listed as the primary presenter. The work is a joint effort with Tiancheng Xie, Jiaheng Zhang, Dawn Song, and Yupeng Zhang. The transcript mentions "our advices" in the introduction, implying that Dawn Song and Yupeng Zhang are likely advisors or senior researchers guiding the project. While specific titles and affiliations for all speakers are not detailed in the transcript, Dawn Song is a highly recognized figure in the cybersecurity and blockchain space, known for her work at UC Berkeley and her contributions to blockchain security and privacy. The collaborative nature of the research suggests a strong academic background, likely from a leading institution given the IEEE S&P conference context.