We study linear-time prover SNARKs and make the following contributions: We provide a framework for transforming a univariate polynomial commitment scheme into a multilinear polynomial commitment scheme. Our transformation is generic, can be instantiated with any univariate scheme and improves on prior transformations like Gemini (EUROCRYPT 2022) and Virgo (S&P 2020) in all relevant parameters: proof size, verification complexity, and prover complexity. Instantiating the above framework with the KZG univariate polynomial commitment scheme, we get \(\textsf {SamaritanPCS}\) – the first multilinear polynomial commitment scheme with constant proof size and linear-time prover. The proof size is just 368 bytes, which is the smallest among all multilinear polynomial commitment schemes. Our scheme also has excellent batching properties, wherein proving k evaluations over the hypercube of size n incurs \(O(n+k\sqrt{n})\) cryptographic work, resulting in substantially amortized prover work over several evaluations. We construct \(\textsf {LogSpartan}\) – a new multilinear PIOP for R1CS based on recent techniques for lookup arguments. Compiling this PIOP using \(\textsf {SamaritanPCS}\) gives \(\textsf {Samaritan}\) – a SNARK in the universal and updatable SRS setting. \(\textsf {Samaritan}\) has linear-time prover, logarithmic verification and logarithmic proof size. Concretely, its proof size is one of the smallest among other known linear-time prover SNARKs without relying on concretely expensive proof recursion techniques. For an R1CS instance with 1 million constraints, \(\textsf {Samaritan}\) (over the BLS12-381 curve) has a proof size of 6.2 KB. We compare \(\textsf {Samaritan}\) with other linear-time prover SNARKs in the updatable setting. We asymptotically improve on the \(\log ^2 n\) proof size of Spartan. Unlike Libra (CRYPTO 2019), the argument size of \(\textsf {Samaritan}\) is independent of the circuit depth. Compared to Gemini (EUROCRYPT 2022), \(\textsf {Samaritan}\) achieves 3 \(\times \) smaller argument size at 1 million constraints. We are competitive with the very recently proposed MicroSpartan (S&P 2025) and linear-time SNARKs for the Plonkish constraint system such as HyperPlonk (EUROCRYPT 2023).

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

Samaritan: Linear-Time Prover SNARK from New Multilinear Polynomial Commitments

  • Chaya Ganesh,
  • Sikhar Patranabis,
  • Nitin Singh

摘要

We study linear-time prover SNARKs and make the following contributions: We provide a framework for transforming a univariate polynomial commitment scheme into a multilinear polynomial commitment scheme. Our transformation is generic, can be instantiated with any univariate scheme and improves on prior transformations like Gemini (EUROCRYPT 2022) and Virgo (S&P 2020) in all relevant parameters: proof size, verification complexity, and prover complexity. Instantiating the above framework with the KZG univariate polynomial commitment scheme, we get \(\textsf {SamaritanPCS}\) – the first multilinear polynomial commitment scheme with constant proof size and linear-time prover. The proof size is just 368 bytes, which is the smallest among all multilinear polynomial commitment schemes. Our scheme also has excellent batching properties, wherein proving k evaluations over the hypercube of size n incurs \(O(n+k\sqrt{n})\) cryptographic work, resulting in substantially amortized prover work over several evaluations. We construct \(\textsf {LogSpartan}\) – a new multilinear PIOP for R1CS based on recent techniques for lookup arguments. Compiling this PIOP using \(\textsf {SamaritanPCS}\) gives \(\textsf {Samaritan}\) – a SNARK in the universal and updatable SRS setting. \(\textsf {Samaritan}\) has linear-time prover, logarithmic verification and logarithmic proof size. Concretely, its proof size is one of the smallest among other known linear-time prover SNARKs without relying on concretely expensive proof recursion techniques. For an R1CS instance with 1 million constraints, \(\textsf {Samaritan}\) (over the BLS12-381 curve) has a proof size of 6.2 KB. We compare \(\textsf {Samaritan}\) with other linear-time prover SNARKs in the updatable setting. We asymptotically improve on the \(\log ^2 n\) proof size of Spartan. Unlike Libra (CRYPTO 2019), the argument size of \(\textsf {Samaritan}\) is independent of the circuit depth. Compared to Gemini (EUROCRYPT 2022), \(\textsf {Samaritan}\) achieves 3 \(\times \) smaller argument size at 1 million constraints. We are competitive with the very recently proposed MicroSpartan (S&P 2025) and linear-time SNARKs for the Plonkish constraint system such as HyperPlonk (EUROCRYPT 2023).