Paper 2025/557

Soloist: Distributed SNARKs for Rank-One Constraint System

Abstract

Distributed SNARKs enable multiple provers to collaboratively generate proofs, enhancing the efficiency and scalability of large-scale computations. The state-of-the-art distributed SNARK for Plonk, Pianist (S\&P '24), achieves constant proof size, constant amortized communication complexity, and constant verifier complexity. However, when proving the Rank-One Constraint System (R1CS), a widely used intermediate representation for SNARKs, Pianist must perform the transformation from R1CS into Plonk before proving, which can introduce a start-up cost of $10\times$ due to the expansion of the statement size. Meanwhile, existing distributed SNARKs for R1CS, e.g., DIZK (USENIX Sec. '18) and Hekaton (CCS '24), fail to match the superior asymptotic complexities of Pianist. We propose $\textsf{Soloist}$, an optimized distributed SNARK for R1CS. $\textsf{Soloist}$ achieves constant proof size, constant amortized communication complexity, and constant verifier complexity, relative to the R1CS size $n$. Utilized with $\ell$ sub-provers, its prover complexity is $O(n/\ell \cdot \log(n/\ell))$. The concrete prover time is~$\ell\times$ as fast as the R1CS-targeted Marlin (Eurocrypt '20). For zkRollups, $\textsf{Soloist}$ can prove more transactions, with $2.5 \times$ smaller memory costs, $2.8\times$ faster preprocessing, and $1.8\times$ faster proving than Pianist. $\textsf{Soloist}$ leverages an improved inner product argument and a new batch bivariate polynomial commitment variant of KZG (Asiacrypt '10). To achieve constant verification, we propose a new preprocessing method with a lookup argument for unprescribed tables, which are usually assumed pre-committed in prior works. Notably, all these schemes are equipped with scalable distributed mechanisms.