Soloist: Distributed SNARK for R1CS with Constant Proof Size

Succinct non-interactive arguments of knowledge (SNARK) is a powerful cryptographic primitive with diverse real-world applications. The rank-one constraint system (R1CS), an intermediate representation of SNARK, has been widely used for proving arithmetic circuits.

Distributed SNARKs allow multiple provers to jointly generate proofs for improving prover efficiency. However, state-of-the-art distributed SNARKs for R1CS, i.e., DIZK (USENIX Sec. '18) and Hekaton (CCS '24), fail to simultaneously achieve scalable prover efficiency and constant proof sizes. In this paper we propose Soloist, a distributed SNARK for R1CS with constant proof size, amortized communication and verification. For a size-O(n) R1CS, its prover complexity is $O(n/\ell · \log(n/\ell))$ given $\ell$ sub-provers. Experiments show that the concrete prover time of Soloist is $\ell$× as fast as the non-distributed R1CS-targeted Marlin (Eurocrypt '20) given $\ell$ sub-provers. Compared with Hekaton, Soloist features a 100× smaller communication overhead, and has a 7× faster prover time when proving general circuits. For R1CS-friendly zkRollups, Soloist outperforms the Plonk-targeted Pianist (S&P '24) with a 2.5× smaller memory cost, a 2.8× faster preprocessing, and a 1.8× faster prover when proving general circuits.

To build Soloist, we design a distributed polynomial oracle proof (PIOP) for R1CS. Its core techniques include an improved (and distributed) inner product PIOP, and a distributed preprocessing PIOP via lookup tables. To instantiate the PIOPs, we propose a (distributed) batch scheme for bivariate KZG, which enables opening multiple points on multiple polynomials with a proof size irrelevant to polynomial size or point number.