HyperPianist: Pianist with Linear-Time Prover and Logarithmic Communication Cost

Recent years have seen great improvements in zero-knowledge proofs (ZKPs). Among them, zero-knowledge SNARKs are notable for their compact and efficiently-verifiable proofs, but suffer from high prover costs. Wu et al. (Usenix Security 2018) proposed to distribute the proving task across multiple machines, and achieved significant improvements in proving time. However, existing distributed ZKP systems still have quasi-linear prover cost, and may incur a communication cost that is linear in circuit size. In this paper, we introduce HyperPianist. Inspired by the state-of-the-art distributed ZKP system Pianist (Liu et al., S&P 2024) and the multivariate proof system HyperPlonk (Chen et al., EUROCRYPT 2023), we design a distributed multivariate polynomial interactive oracle proof (PIOP) system with a linear-time prover cost and logarithmic communication cost. Unlike Pianist, HyperPianist incurs no extra overhead in prover time or communication when applied to general (non-data-parallel) circuits. To instantiate the PIOP system, we adapt two additively-homomorphic multivariate polynomial commitment schemes, multivariate KZG (Papamanthou et al., TCC 2013) and Dory (Lee et al., TCC 2021), into the distributed setting, and get HyperPianistK and HyperPianistDrespectively. Both systems have linear prover complexity and logarithmic communication cost; furthermore, HyperPianistDrequires no trusted setup. We also propose HyperPianist+, incorporating an optimized lookup argument based on Lasso (Setty et al., EUROCRYPT 2024) with lower prover cost. Experiments demonstrate HyperPianistK and HyperPianistDachieve speedups of 63.1x and 40.2x over HyperPlonk with 32 distributed machines. Compared to Pianist, HyperPianistK can be 2.9x and 4.6x as fast and HyperPianistDcan be 2.4x and 3.8x as fast, on vanilla gates and custom gates respectively. With layered circuits, HyperPianistK is up to 5.9x as fast on custom gates, and HyperPianistDachieves a 4.7x speedup.