Paper 2025/419
Samaritan: Linear-time Prover SNARK from New Multilinear Polynomial Commitments
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. SamaritanPCS is a drop-in replacement for the popular PST scheme, and improves upon PST in all relevant parameters.
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 BLS12-381 curve) has a proof size of 6.7KB.
We compare Samaritan with other linear-time prover SNARKs in the updatable setting. We asymptotically improve on the
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-03-05: approved
- 2025-03-05: received
- See all versions
- Short URL
- https://ia.cr/2025/419
- License
-
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} }