Nova/src/spartan/mod.rs
src/spartan/mod.rsRaw
1//! This module implements RelaxedR1CSSNARKTrait using Spartan that is generic
2//! over the polynomial commitment and evaluation argument (i.e., a PCS)
3mod math;
4pub(crate) mod polynomial;
5pub mod pp;
6mod sumcheck;
7
8use crate::{
9 errors::NovaError,
10 r1cs::{R1CSShape, RelaxedR1CSInstance, RelaxedR1CSWitness},
11 traits::{
12 evaluation::EvaluationEngineTrait, snark::RelaxedR1CSSNARKTrait, Group, TranscriptEngineTrait,
13 },
14 Commitment, CommitmentKey,
15};
16use ff::Field;
17use itertools::concat;
18use polynomial::{EqPolynomial, MultilinearPolynomial, SparsePolynomial};
19use rayon::prelude::*;
20use serde::{Deserialize, Serialize};
21use sumcheck::SumcheckProof;
22
23/// A type that holds a witness to a polynomial evaluation instance
24pub struct PolyEvalWitness<G: Group> {
25 p: Vec<G::Scalar>, // polynomial
26}
27
28impl<G: Group> PolyEvalWitness<G> {
29 fn pad(W: &[PolyEvalWitness<G>]) -> Vec<PolyEvalWitness<G>> {
30 // determine the maximum size
31 if let Some(n) = W.iter().map(|w| w.p.len()).max() {
32 W.iter()
33 .map(|w| {
34 let mut p = w.p.clone();
35 p.resize(n, G::Scalar::zero());
36 PolyEvalWitness { p }
37 })
38 .collect()
39 } else {
40 Vec::new()
41 }
42 }
43
44 fn weighted_sum(W: &[PolyEvalWitness<G>], s: &[G::Scalar]) -> PolyEvalWitness<G> {
45 assert_eq!(W.len(), s.len());
46 let mut p = vec![G::Scalar::zero(); W[0].p.len()];
47 for i in 0..W.len() {
48 for j in 0..W[i].p.len() {
49 p[j] += W[i].p[j] * s[i]
50 }
51 }
52 PolyEvalWitness { p }
53 }
54}
55
56/// A type that holds a polynomial evaluation instance
57pub struct PolyEvalInstance<G: Group> {
58 c: Commitment<G>, // commitment to the polynomial
59 x: Vec<G::Scalar>, // evaluation point
60 e: G::Scalar, // claimed evaluation
61}
62
63impl<G: Group> PolyEvalInstance<G> {
64 fn pad(U: &[PolyEvalInstance<G>]) -> Vec<PolyEvalInstance<G>> {
65 // determine the maximum size
66 if let Some(ell) = U.iter().map(|u| u.x.len()).max() {
67 U.iter()
68 .map(|u| {
69 let mut x = vec![G::Scalar::zero(); ell - u.x.len()];
70 x.extend(u.x.clone());
71 PolyEvalInstance { c: u.c, x, e: u.e }
72 })
73 .collect()
74 } else {
75 Vec::new()
76 }
77 }
78}
79
80/// A type that represents the prover's key
81#[derive(Serialize, Deserialize)]
82#[serde(bound = "")]
83pub struct ProverKey<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
84 pk_ee: EE::ProverKey,
85 S: R1CSShape<G>,
86}
87
88/// A type that represents the verifier's key
89#[derive(Serialize, Deserialize)]
90#[serde(bound = "")]
91pub struct VerifierKey<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
92 vk_ee: EE::VerifierKey,
93 S: R1CSShape<G>,
94}
95
96/// A succinct proof of knowledge of a witness to a relaxed R1CS instance
97/// The proof is produced using Spartan's combination of the sum-check and
98/// the commitment to a vector viewed as a polynomial commitment
99#[derive(Serialize, Deserialize)]
100#[serde(bound = "")]
101pub struct RelaxedR1CSSNARK<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> {
102 sc_proof_outer: SumcheckProof<G>,
103 claims_outer: (G::Scalar, G::Scalar, G::Scalar),
104 eval_E: G::Scalar,
105 sc_proof_inner: SumcheckProof<G>,
106 eval_W: G::Scalar,
107 sc_proof_batch: SumcheckProof<G>,
108 evals_batch: Vec<G::Scalar>,
109 eval_arg: EE::EvaluationArgument,
110}
111
112impl<G: Group, EE: EvaluationEngineTrait<G, CE = G::CE>> RelaxedR1CSSNARKTrait<G>
113 for RelaxedR1CSSNARK<G, EE>
114{
115 type ProverKey = ProverKey<G, EE>;
116 type VerifierKey = VerifierKey<G, EE>;
117
118 fn setup(
119 ck: &CommitmentKey<G>,
120 S: &R1CSShape<G>,
121 ) -> Result<(Self::ProverKey, Self::VerifierKey), NovaError> {
122 let (pk_ee, vk_ee) = EE::setup(ck);
123
124 let S = S.pad();
125
126 let vk = VerifierKey {
127 vk_ee,
128 S: S.clone(),
129 };
130
131 let pk = ProverKey { pk_ee, S };
132
133 Ok((pk, vk))
134 }
135
136 /// produces a succinct proof of satisfiability of a RelaxedR1CS instance
137 fn prove(
138 ck: &CommitmentKey<G>,
139 pk: &Self::ProverKey,
140 U: &RelaxedR1CSInstance<G>,
141 W: &RelaxedR1CSWitness<G>,
142 ) -> Result<Self, NovaError> {
143 let W = W.pad(&pk.S); // pad the witness
144 let mut transcript = G::TE::new(b"RelaxedR1CSSNARK");
145
146 // sanity check that R1CSShape has certain size characteristics
147 assert_eq!(pk.S.num_cons.next_power_of_two(), pk.S.num_cons);
148 assert_eq!(pk.S.num_vars.next_power_of_two(), pk.S.num_vars);
149 assert_eq!(pk.S.num_io.next_power_of_two(), pk.S.num_io);
150 assert!(pk.S.num_io < pk.S.num_vars);
151
152 // append the digest of R1CS matrices and the RelaxedR1CSInstance to the transcript
153 transcript.absorb(b"S", &pk.S);
154 transcript.absorb(b"U", U);
155
156 // compute the full satisfying assignment by concatenating W.W, U.u, and U.X
157 let mut z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
158
159 let (num_rounds_x, num_rounds_y) = (
160 (pk.S.num_cons as f64).log2() as usize,
161 ((pk.S.num_vars as f64).log2() as usize + 1),
162 );
163
164 // outer sum-check
165 let tau = (0..num_rounds_x)
166 .map(|_i| transcript.squeeze(b"t"))
167 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
168
169 let mut poly_tau = MultilinearPolynomial::new(EqPolynomial::new(tau).evals());
170 let (mut poly_Az, mut poly_Bz, poly_Cz, mut poly_uCz_E) = {
171 let (poly_Az, poly_Bz, poly_Cz) = pk.S.multiply_vec(&z)?;
172 let poly_uCz_E = (0..pk.S.num_cons)
173 .map(|i| U.u * poly_Cz[i] + W.E[i])
174 .collect::<Vec<G::Scalar>>();
175 (
176 MultilinearPolynomial::new(poly_Az),
177 MultilinearPolynomial::new(poly_Bz),
178 MultilinearPolynomial::new(poly_Cz),
179 MultilinearPolynomial::new(poly_uCz_E),
180 )
181 };
182
183 let comb_func_outer =
184 |poly_A_comp: &G::Scalar,
185 poly_B_comp: &G::Scalar,
186 poly_C_comp: &G::Scalar,
187 poly_D_comp: &G::Scalar|
188 -> G::Scalar { *poly_A_comp * (*poly_B_comp * *poly_C_comp - *poly_D_comp) };
189 let (sc_proof_outer, r_x, claims_outer) = SumcheckProof::prove_cubic_with_additive_term(
190 &G::Scalar::zero(), // claim is zero
191 num_rounds_x,
192 &mut poly_tau,
193 &mut poly_Az,
194 &mut poly_Bz,
195 &mut poly_uCz_E,
196 comb_func_outer,
197 &mut transcript,
198 )?;
199
200 // claims from the end of sum-check
201 let (claim_Az, claim_Bz): (G::Scalar, G::Scalar) = (claims_outer[1], claims_outer[2]);
202 let claim_Cz = poly_Cz.evaluate(&r_x);
203 let eval_E = MultilinearPolynomial::new(W.E.clone()).evaluate(&r_x);
204 transcript.absorb(
205 b"claims_outer",
206 &[claim_Az, claim_Bz, claim_Cz, eval_E].as_slice(),
207 );
208
209 // inner sum-check
210 let r = transcript.squeeze(b"r")?;
211 let claim_inner_joint = claim_Az + r * claim_Bz + r * r * claim_Cz;
212
213 let poly_ABC = {
214 // compute the initial evaluation table for R(\tau, x)
215 let evals_rx = EqPolynomial::new(r_x.clone()).evals();
216
217 // Bounds "row" variables of (A, B, C) matrices viewed as 2d multilinear polynomials
218 let compute_eval_table_sparse =
219 |S: &R1CSShape<G>, rx: &[G::Scalar]| -> (Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>) {
220 assert_eq!(rx.len(), S.num_cons);
221
222 let inner = |M: &Vec<(usize, usize, G::Scalar)>, M_evals: &mut Vec<G::Scalar>| {
223 for (row, col, val) in M {
224 M_evals[*col] += rx[*row] * val;
225 }
226 };
227
228 let (A_evals, (B_evals, C_evals)) = rayon::join(
229 || {
230 let mut A_evals: Vec<G::Scalar> = vec![G::Scalar::zero(); 2 * S.num_vars];
231 inner(&S.A, &mut A_evals);
232 A_evals
233 },
234 || {
235 rayon::join(
236 || {
237 let mut B_evals: Vec<G::Scalar> = vec![G::Scalar::zero(); 2 * S.num_vars];
238 inner(&S.B, &mut B_evals);
239 B_evals
240 },
241 || {
242 let mut C_evals: Vec<G::Scalar> = vec![G::Scalar::zero(); 2 * S.num_vars];
243 inner(&S.C, &mut C_evals);
244 C_evals
245 },
246 )
247 },
248 );
249
250 (A_evals, B_evals, C_evals)
251 };
252
253 let (evals_A, evals_B, evals_C) = compute_eval_table_sparse(&pk.S, &evals_rx);
254
255 assert_eq!(evals_A.len(), evals_B.len());
256 assert_eq!(evals_A.len(), evals_C.len());
257 (0..evals_A.len())
258 .into_par_iter()
259 .map(|i| evals_A[i] + r * evals_B[i] + r * r * evals_C[i])
260 .collect::<Vec<G::Scalar>>()
261 };
262
263 let poly_z = {
264 z.resize(pk.S.num_vars * 2, G::Scalar::zero());
265 z
266 };
267
268 let comb_func = |poly_A_comp: &G::Scalar, poly_B_comp: &G::Scalar| -> G::Scalar {
269 *poly_A_comp * *poly_B_comp
270 };
271 let (sc_proof_inner, r_y, _claims_inner) = SumcheckProof::prove_quad(
272 &claim_inner_joint,
273 num_rounds_y,
274 &mut MultilinearPolynomial::new(poly_ABC),
275 &mut MultilinearPolynomial::new(poly_z),
276 comb_func,
277 &mut transcript,
278 )?;
279
280 // add additional claims about W and E polynomials to the list from CC
281 let mut w_u_vec = Vec::new();
282 let eval_W = MultilinearPolynomial::evaluate_with(&W.W, &r_y[1..]);
283 w_u_vec.push((
284 PolyEvalWitness { p: W.W.clone() },
285 PolyEvalInstance {
286 c: U.comm_W,
287 x: r_y[1..].to_vec(),
288 e: eval_W,
289 },
290 ));
291
292 w_u_vec.push((
293 PolyEvalWitness { p: W.E },
294 PolyEvalInstance {
295 c: U.comm_E,
296 x: r_x,
297 e: eval_E,
298 },
299 ));
300
301 // We will now reduce a vector of claims of evaluations at different points into claims about them at the same point.
302 // For example, eval_W =? W(r_y[1..]) and eval_W =? E(r_x) into
303 // two claims: eval_W_prime =? W(rz) and eval_E_prime =? E(rz)
304 // We can them combine the two into one: eval_W_prime + gamma * eval_E_prime =? (W + gamma*E)(rz),
305 // where gamma is a public challenge
306 // Since commitments to W and E are homomorphic, the verifier can compute a commitment
307 // to the batched polynomial.
308 assert!(w_u_vec.len() >= 2);
309
310 let (w_vec, u_vec): (Vec<PolyEvalWitness<G>>, Vec<PolyEvalInstance<G>>) =
311 w_u_vec.into_iter().unzip();
312 let w_vec_padded = PolyEvalWitness::pad(&w_vec); // pad the polynomials to be of the same size
313 let u_vec_padded = PolyEvalInstance::pad(&u_vec); // pad the evaluation points
314
315 let powers = |s: &G::Scalar, n: usize| -> Vec<G::Scalar> {
316 assert!(n >= 1);
317 let mut powers = Vec::new();
318 powers.push(G::Scalar::one());
319 for i in 1..n {
320 powers.push(powers[i - 1] * s);
321 }
322 powers
323 };
324
325 // generate a challenge
326 let rho = transcript.squeeze(b"r")?;
327 let num_claims = w_vec_padded.len();
328 let powers_of_rho = powers(&rho, num_claims);
329 let claim_batch_joint = u_vec_padded
330 .iter()
331 .zip(powers_of_rho.iter())
332 .map(|(u, p)| u.e * p)
333 .fold(G::Scalar::zero(), |acc, item| acc + item);
334
335 let mut polys_left: Vec<MultilinearPolynomial<G::Scalar>> = w_vec_padded
336 .iter()
337 .map(|w| MultilinearPolynomial::new(w.p.clone()))
338 .collect();
339 let mut polys_right: Vec<MultilinearPolynomial<G::Scalar>> = u_vec_padded
340 .iter()
341 .map(|u| MultilinearPolynomial::new(EqPolynomial::new(u.x.clone()).evals()))
342 .collect();
343
344 let num_rounds_z = u_vec_padded[0].x.len();
345 let comb_func = |poly_A_comp: &G::Scalar, poly_B_comp: &G::Scalar| -> G::Scalar {
346 *poly_A_comp * *poly_B_comp
347 };
348 let (sc_proof_batch, r_z, claims_batch) = SumcheckProof::prove_quad_batch(
349 &claim_batch_joint,
350 num_rounds_z,
351 &mut polys_left,
352 &mut polys_right,
353 &powers_of_rho,
354 comb_func,
355 &mut transcript,
356 )?;
357
358 let (claims_batch_left, _): (Vec<G::Scalar>, Vec<G::Scalar>) = claims_batch;
359
360 transcript.absorb(b"l", &claims_batch_left.as_slice());
361
362 // we now combine evaluation claims at the same point rz into one
363 let gamma = transcript.squeeze(b"g")?;
364 let powers_of_gamma: Vec<G::Scalar> = powers(&gamma, num_claims);
365 let comm_joint = u_vec_padded
366 .iter()
367 .zip(powers_of_gamma.iter())
368 .map(|(u, g_i)| u.c * *g_i)
369 .fold(Commitment::<G>::default(), |acc, item| acc + item);
370 let poly_joint = PolyEvalWitness::weighted_sum(&w_vec_padded, &powers_of_gamma);
371 let eval_joint = claims_batch_left
372 .iter()
373 .zip(powers_of_gamma.iter())
374 .map(|(e, g_i)| *e * *g_i)
375 .fold(G::Scalar::zero(), |acc, item| acc + item);
376
377 let eval_arg = EE::prove(
378 ck,
379 &pk.pk_ee,
380 &mut transcript,
381 &comm_joint,
382 &poly_joint.p,
383 &r_z,
384 &eval_joint,
385 )?;
386
387 Ok(RelaxedR1CSSNARK {
388 sc_proof_outer,
389 claims_outer: (claim_Az, claim_Bz, claim_Cz),
390 eval_E,
391 sc_proof_inner,
392 eval_W,
393 sc_proof_batch,
394 evals_batch: claims_batch_left,
395 eval_arg,
396 })
397 }
398
399 /// verifies a proof of satisfiability of a RelaxedR1CS instance
400 fn verify(&self, vk: &Self::VerifierKey, U: &RelaxedR1CSInstance<G>) -> Result<(), NovaError> {
401 let mut transcript = G::TE::new(b"RelaxedR1CSSNARK");
402
403 // append the digest of R1CS matrices and the RelaxedR1CSInstance to the transcript
404 transcript.absorb(b"S", &vk.S);
405 transcript.absorb(b"U", U);
406
407 let (num_rounds_x, num_rounds_y) = (
408 (vk.S.num_cons as f64).log2() as usize,
409 ((vk.S.num_vars as f64).log2() as usize + 1),
410 );
411
412 // outer sum-check
413 let tau = (0..num_rounds_x)
414 .map(|_i| transcript.squeeze(b"t"))
415 .collect::<Result<Vec<G::Scalar>, NovaError>>()?;
416
417 let (claim_outer_final, r_x) =
418 self
419 .sc_proof_outer
420 .verify(G::Scalar::zero(), num_rounds_x, 3, &mut transcript)?;
421
422 // verify claim_outer_final
423 let (claim_Az, claim_Bz, claim_Cz) = self.claims_outer;
424 let taus_bound_rx = EqPolynomial::new(tau).evaluate(&r_x);
425 let claim_outer_final_expected =
426 taus_bound_rx * (claim_Az * claim_Bz - U.u * claim_Cz - self.eval_E);
427 if claim_outer_final != claim_outer_final_expected {
428 return Err(NovaError::InvalidSumcheckProof);
429 }
430
431 transcript.absorb(
432 b"claims_outer",
433 &[
434 self.claims_outer.0,
435 self.claims_outer.1,
436 self.claims_outer.2,
437 self.eval_E,
438 ]
439 .as_slice(),
440 );
441
442 // inner sum-check
443 let r = transcript.squeeze(b"r")?;
444 let claim_inner_joint =
445 self.claims_outer.0 + r * self.claims_outer.1 + r * r * self.claims_outer.2;
446
447 let (claim_inner_final, r_y) =
448 self
449 .sc_proof_inner
450 .verify(claim_inner_joint, num_rounds_y, 2, &mut transcript)?;
451
452 // verify claim_inner_final
453 let eval_Z = {
454 let eval_X = {
455 // constant term
456 let mut poly_X = vec![(0, U.u)];
457 //remaining inputs
458 poly_X.extend(
459 (0..U.X.len())
460 .map(|i| (i + 1, U.X[i]))
461 .collect::<Vec<(usize, G::Scalar)>>(),
462 );
463 SparsePolynomial::new((vk.S.num_vars as f64).log2() as usize, poly_X).evaluate(&r_y[1..])
464 };
465 (G::Scalar::one() - r_y[0]) * self.eval_W + r_y[0] * eval_X
466 };
467
468 // compute evaluations of R1CS matrices
469 let multi_evaluate = |M_vec: &[&[(usize, usize, G::Scalar)]],
470 r_x: &[G::Scalar],
471 r_y: &[G::Scalar]|
472 -> Vec<G::Scalar> {
473 let evaluate_with_table =
474 |M: &[(usize, usize, G::Scalar)], T_x: &[G::Scalar], T_y: &[G::Scalar]| -> G::Scalar {
475 (0..M.len())
476 .collect::<Vec<usize>>()
477 .par_iter()
478 .map(|&i| {
479 let (row, col, val) = M[i];
480 T_x[row] * T_y[col] * val
481 })
482 .reduce(G::Scalar::zero, |acc, x| acc + x)
483 };
484
485 let (T_x, T_y) = rayon::join(
486 || EqPolynomial::new(r_x.to_vec()).evals(),
487 || EqPolynomial::new(r_y.to_vec()).evals(),
488 );
489
490 (0..M_vec.len())
491 .collect::<Vec<usize>>()
492 .par_iter()
493 .map(|&i| evaluate_with_table(M_vec[i], &T_x, &T_y))
494 .collect()
495 };
496
497 let evals = multi_evaluate(&[&vk.S.A, &vk.S.B, &vk.S.C], &r_x, &r_y);
498
499 let claim_inner_final_expected = (evals[0] + r * evals[1] + r * r * evals[2]) * eval_Z;
500 if claim_inner_final != claim_inner_final_expected {
501 return Err(NovaError::InvalidSumcheckProof);
502 }
503
504 // add claims about W and E polynomials
505 let u_vec: Vec<PolyEvalInstance<G>> = vec![
506 PolyEvalInstance {
507 c: U.comm_W,
508 x: r_y[1..].to_vec(),
509 e: self.eval_W,
510 },
511 PolyEvalInstance {
512 c: U.comm_E,
513 x: r_x,
514 e: self.eval_E,
515 },
516 ];
517
518 let u_vec_padded = PolyEvalInstance::pad(&u_vec); // pad the evaluation points
519
520 let powers = |s: &G::Scalar, n: usize| -> Vec<G::Scalar> {
521 assert!(n >= 1);
522 let mut powers = Vec::new();
523 powers.push(G::Scalar::one());
524 for i in 1..n {
525 powers.push(powers[i - 1] * s);
526 }
527 powers
528 };
529
530 // generate a challenge
531 let rho = transcript.squeeze(b"r")?;
532 let num_claims = u_vec.len();
533 let powers_of_rho = powers(&rho, num_claims);
534 let claim_batch_joint = u_vec
535 .iter()
536 .zip(powers_of_rho.iter())
537 .map(|(u, p)| u.e * p)
538 .fold(G::Scalar::zero(), |acc, item| acc + item);
539
540 let num_rounds_z = u_vec_padded[0].x.len();
541 let (claim_batch_final, r_z) =
542 self
543 .sc_proof_batch
544 .verify(claim_batch_joint, num_rounds_z, 2, &mut transcript)?;
545
546 let claim_batch_final_expected = {
547 let poly_rz = EqPolynomial::new(r_z.clone());
548 let evals = u_vec_padded
549 .iter()
550 .map(|u| poly_rz.evaluate(&u.x))
551 .collect::<Vec<G::Scalar>>();
552
553 evals
554 .iter()
555 .zip(self.evals_batch.iter())
556 .zip(powers_of_rho.iter())
557 .map(|((e_i, p_i), rho_i)| *e_i * *p_i * rho_i)
558 .fold(G::Scalar::zero(), |acc, item| acc + item)
559 };
560
561 if claim_batch_final != claim_batch_final_expected {
562 return Err(NovaError::InvalidSumcheckProof);
563 }
564
565 transcript.absorb(b"l", &self.evals_batch.as_slice());
566
567 // we now combine evaluation claims at the same point rz into one
568 let gamma = transcript.squeeze(b"g")?;
569 let powers_of_gamma: Vec<G::Scalar> = powers(&gamma, num_claims);
570 let comm_joint = u_vec_padded
571 .iter()
572 .zip(powers_of_gamma.iter())
573 .map(|(u, g_i)| u.c * *g_i)
574 .fold(Commitment::<G>::default(), |acc, item| acc + item);
575 let eval_joint = self
576 .evals_batch
577 .iter()
578 .zip(powers_of_gamma.iter())
579 .map(|(e, g_i)| *e * *g_i)
580 .fold(G::Scalar::zero(), |acc, item| acc + item);
581
582 // verify
583 EE::verify(
584 &vk.vk_ee,
585 &mut transcript,
586 &comm_joint,
587 &r_z,
588 &eval_joint,
589 &self.eval_arg,
590 )?;
591
592 Ok(())
593 }
594}