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, existing distributed SNARKs for R1CS, i.e., DIZK (USENIX Sec. ’18) and Hekaton (CCS ’24), fail to simultaneously achieve constant proof size and scalable prover efficiency. In this paper, we propose \(\textsf{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 \cdot \log (n/\ell ))\) given \(\ell \) sub-provers. Experiments show that the concrete prover time of \(\textsf{Soloist}\) is  \(\sim \!\ell \times \) as fast as the non-distributed R1CS-targeted Marlin (Eurocrypt ’20) given \(\ell \) sub-provers. Compared with Hekaton, \(\textsf{Soloist}\) features a \(100{\times }\) smaller communication overhead, and has a \(7{\times }\) faster prover time when proving general circuits. For R1CS-friendly zkRollups, \(\textsf{Soloist}\) outperforms the state-of-the-art Plonk-targeted Pianist (S&P ’24) with a \(2.5{\times }\) smaller memory cost, a \(2.8{\times }\) faster preprocessing, and a \(1.8{\times }\) faster prover. To build \(\textsf{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 build 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Soloist: Distributed SNARK for R1CS with Constant Proof Size

  • Weihan Li,
  • Zongyang Zhang,
  • Yun Li,
  • Pengfei Zhu,
  • Cheng Hong,
  • Jianwei Liu

摘要

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, existing distributed SNARKs for R1CS, i.e., DIZK (USENIX Sec. ’18) and Hekaton (CCS ’24), fail to simultaneously achieve constant proof size and scalable prover efficiency. In this paper, we propose \(\textsf{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 \cdot \log (n/\ell ))\) given \(\ell \) sub-provers. Experiments show that the concrete prover time of \(\textsf{Soloist}\) is  \(\sim \!\ell \times \) as fast as the non-distributed R1CS-targeted Marlin (Eurocrypt ’20) given \(\ell \) sub-provers. Compared with Hekaton, \(\textsf{Soloist}\) features a \(100{\times }\) smaller communication overhead, and has a \(7{\times }\) faster prover time when proving general circuits. For R1CS-friendly zkRollups, \(\textsf{Soloist}\) outperforms the state-of-the-art Plonk-targeted Pianist (S&P ’24) with a \(2.5{\times }\) smaller memory cost, a \(2.8{\times }\) faster preprocessing, and a \(1.8{\times }\) faster prover. To build \(\textsf{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 build 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.