Paper 2025/419

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

Chaya Ganesh, Indian Institute of Science Bangalore
Sikhar Patranabis, IBM Research India
Nitin Singh, IBM Research India
Abstract

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 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 LogSpartan – a new multilinear PIOP for R1CS based on recent techniques for lookup arguments. Compiling this PIOP using SamaritanPCS gives Samaritan – a SNARK in the universal and updatable SRS setting. 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, Samaritan (over the BLS12-381 curve) has a proof size of 6.2KB. We compare 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 Samaritan is independent of the circuit depth. Compared to Gemini (EUROCRYPT 2022), Samaritan achieves 3X 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).

Note: The revised version presents two variants of LogSpartan with different tradeoffs between proof size and prover overhead, and includes a more detailed discussion about the concrete prover efficiency of both versions (and the corresponding realizations of Samaritan). We also cite several relevant related (and concurrent) works.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Zero-knowledge ProofsSNARKsMultilinear Polynomial CommitmentsPolynomial Interactive Oracle Proofs
Contact author(s)
chaya @ iisc ac in
sikhar patranabis @ ibm com
nitisin1 @ in ibm com
History
2025-05-21: last of 3 revisions
2025-03-05: received
See all versions
Short URL
https://ia.cr/2025/419
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/419,
      author = {Chaya Ganesh and Sikhar Patranabis and Nitin Singh},
      title = {Samaritan: Linear-time Prover {SNARK} from New Multilinear Polynomial Commitments},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/419},
      year = {2025},
      url = {https://eprint.iacr.org/2025/419}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.