flâneur

The Spartan zkSNARK framework - Alin Tomescu

alinush.github.io · 4,788 words · saved by 1 readers

Spartan1 , 2 is a framework for building zkSNARK schemes using the well-known sumcheck protocol3 , 4 and a sparse multilinear (MLE) polynomial commitment scheme (PCS). Spartan is a SNARK for R1CS satisfiability. Usually, such R1CS SNARKs are built by viewing the R1CS as a QAP. Spartan doesn’t really do that: it works directly with the R1CS matrices. A consequence of this seems to be that its proving time is, at best, Ω ( 𝑛 ) where 𝑛 is the maximum number of non-zero entries in one of the three R1CS matrices. In contrast, SNARKs for QAP like Groth16 tend to have proving times of 𝜔 ( max ( 𝑁 , 𝑚 ) ) where 𝑁 is the number of R1CS constraints (i.e., number of rows in the matrix) and 𝑚 is the number of R1CS variables (i.e., number of columns). For example, Groth16) does: (Universal) setup: Proving: We assume familiarity with: Recall that a vector 𝑉 = [ 𝑉 0 , … 𝑉 𝑛 − 1 ] , where 𝑛 = 2 ℓ , can be represented as a degree-1 multivariate polynomial with ℓ variables, a.k

zero-knowledge proofs (ZKPs) polynomials interpolation rank-1 constraint systems (R1CS) Jun 03, 2025 tl;dr: What a beautiful construction! $ \def\stmt{\mathbf{x}} \def\witn{\mathbf{w}} % \def\td{\mathsf{td}} % \def\zkpSetup{\mathsf{ZKP}.\mathsf{Setup}} \def\zkpProve{\mathsf{ZKP}.\mathsf{Prove}} \def\zkpVerify{\mathsf{ZKP}.\mathsf{Verify}} \def\zkpSim{\mathsf{ZKP}.\mathsf{Sim}} $ $ \def\bin{\{0,1\}} \def\eq{\mathsf{eq}} \def\SC{\mathsf{SumCheck}} \def\MLE#1{\mathsf{MLE}(#1)} \def\i{\boldsymbol{i}} \def\j{\boldsymbol{j}} \def\x{\boldsymbol{x}} \def\X{\boldsymbol{X}} \def\y{\boldsymbol{y}} \def\Y

saved by

related reading