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. 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), SamaritanPCS 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).

Note: The revised version incorporates comments and suggestions from anonymous reviewers of Asiacrypt 2025, whom we thank for their constructive feedback.