What a lovely hat

Paper 2024/1273

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

Abstract

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 HyperPianist^K and HyperPianist^D respectively. Both systems have linear prover complexity and logarithmic communication cost; furthermore, HyperPianist^D requires 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 HyperPianist^K and HyperPianist^D achieve a speedup of 66.8\times and 44.9\times over HyperPlonk with 32 distributed machines. Compared to Pianist, HyperPianistK can be 3.2\times and 5.0\times as fast and HyperPianistD can be 2.7\times and 4.1\times as fast, on vanilla gates and custom gates respectively.