Paper 2024/1273

HyperPianist: Pianist with Linear-Time Prover via Fully Distributed HyperPlonk

Abstract

Zero-knowledge proofs allow one party to prove the truth of a statement without disclosing any extra information. Recent years have seen great improvements in zero-knowledge proofs. Among them, zero-knowledge SNARKs are notable for their compact and efficiently-verifiable proofs but face challenges with high prover costs for large-scale applications. To accelerate proof generation, Pianist (Liu et al., S&P 2024) proposes to distribute the proof generation process across multiple machines, and achieves a significant reduction in overall prover time. However, Pianist inherits the quasi-linear computational complexity from its underlying SNARK proof system Plonk, limiting its scalability and efficiency with large circuits. In this paper, we introduce HyperPianist, a fully distributed proof system with linear-time prover complexity and logarithmic communication cost among distributed machines. Starting from deVirgo (Xie et al., CCS 2022), we study their distributed multivariate SumCheck protocol and achieve logarithmic communication cost by using an additively homomorphic multivariate polynomial commitment scheme in the distributed setting. Given the distributed SumCheck protocol, we then adapt HyperPlonk (Chen et al., EuroptCrypt 2023), a proof system based on multivariate polynomials, to the distributed setting without extra overhead for witness re-distribution. In addition, we propose a more efficient construction of lookup arguments based on Lasso (Setty et al., Eurocrypt 2024), and adapt it to the distributed setting to enhance HyperPianist and obtain HyperPianist+.