Nova/src/spartan/sumcheck.rs
src/spartan/sumcheck.rsRaw
1#![allow(clippy::too_many_arguments)]
2#![allow(clippy::type_complexity)]
3use super::polynomial::MultilinearPolynomial;
4use crate::errors::NovaError;
5use crate::traits::{Group, TranscriptEngineTrait, TranscriptReprTrait};
6use core::marker::PhantomData;
7use ff::Field;
8use rayon::prelude::*;
9use serde::{Deserialize, Serialize};
10
11#[derive(Clone, Debug, Serialize, Deserialize)]
12#[serde(bound = "")]
13pub(crate) struct SumcheckProof<G: Group> {
14 compressed_polys: Vec<CompressedUniPoly<G>>,
15}
16
17impl<G: Group> SumcheckProof<G> {
18 pub fn new(compressed_polys: Vec<CompressedUniPoly<G>>) -> Self {
19 Self { compressed_polys }
20 }
21
22 pub fn verify(
23 &self,
24 claim: G::Scalar,
25 num_rounds: usize,
26 degree_bound: usize,
27 transcript: &mut G::TE,
28 ) -> Result<(G::Scalar, Vec<G::Scalar>), NovaError> {
29 let mut e = claim;
30 let mut r: Vec<G::Scalar> = Vec::new();
31
32 // verify that there is a univariate polynomial for each round
33 if self.compressed_polys.len() != num_rounds {
34 return Err(NovaError::InvalidSumcheckProof);
35 }
36
37 for i in 0..self.compressed_polys.len() {
38 let poly = self.compressed_polys[i].decompress(&e);
39
40 // verify degree bound
41 if poly.degree() != degree_bound {
42 return Err(NovaError::InvalidSumcheckProof);
43 }
44
45 // we do not need to check if poly(0) + poly(1) = e, as
46 // decompress() call above already ensures that hods
47 debug_assert_eq!(poly.eval_at_zero() + poly.eval_at_one(), e);
48
49 // append the prover's message to the transcript
50 transcript.absorb(b"p", &poly);
51
52 //derive the verifier's challenge for the next round
53 let r_i = transcript.squeeze(b"c")?;
54
55 r.push(r_i);
56
57 // evaluate the claimed degree-ell polynomial at r_i
58 e = poly.evaluate(&r_i);
59 }
60
61 Ok((e, r))
62 }
63
64 pub fn prove_quad<F>(
65 claim: &G::Scalar,
66 num_rounds: usize,
67 poly_A: &mut MultilinearPolynomial<G::Scalar>,
68 poly_B: &mut MultilinearPolynomial<G::Scalar>,
69 comb_func: F,
70 transcript: &mut G::TE,
71 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
72 where
73 F: Fn(&G::Scalar, &G::Scalar) -> G::Scalar + Sync,
74 {
75 let mut r: Vec<G::Scalar> = Vec::new();
76 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
77 let mut claim_per_round = *claim;
78 for _ in 0..num_rounds {
79 let poly = {
80 let len = poly_A.len() / 2;
81
82 // Make an iterator returning the contributions to the evaluations
83 let (eval_point_0, eval_point_2) = (0..len)
84 .into_par_iter()
85 .map(|i| {
86 // eval 0: bound_func is A(low)
87 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i]);
88
89 // eval 2: bound_func is -A(low) + 2*A(high)
90 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
91 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
92 let eval_point_2 = comb_func(&poly_A_bound_point, &poly_B_bound_point);
93 (eval_point_0, eval_point_2)
94 })
95 .reduce(
96 || (G::Scalar::zero(), G::Scalar::zero()),
97 |a, b| (a.0 + b.0, a.1 + b.1),
98 );
99
100 let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
101 UniPoly::from_evals(&evals)
102 };
103
104 // append the prover's message to the transcript
105 transcript.absorb(b"p", &poly);
106
107 //derive the verifier's challenge for the next round
108 let r_i = transcript.squeeze(b"c")?;
109 r.push(r_i);
110 polys.push(poly.compress());
111
112 // Set up next round
113 claim_per_round = poly.evaluate(&r_i);
114
115 // bound all tables to the verifier's challenege
116 poly_A.bound_poly_var_top(&r_i);
117 poly_B.bound_poly_var_top(&r_i);
118 }
119
120 Ok((
121 SumcheckProof {
122 compressed_polys: polys,
123 },
124 r,
125 vec![poly_A[0], poly_B[0]],
126 ))
127 }
128
129 pub fn prove_quad_batch<F>(
130 claim: &G::Scalar,
131 num_rounds: usize,
132 poly_A_vec: &mut Vec<MultilinearPolynomial<G::Scalar>>,
133 poly_B_vec: &mut Vec<MultilinearPolynomial<G::Scalar>>,
134 coeffs: &[G::Scalar],
135 comb_func: F,
136 transcript: &mut G::TE,
137 ) -> Result<(Self, Vec<G::Scalar>, (Vec<G::Scalar>, Vec<G::Scalar>)), NovaError>
138 where
139 F: Fn(&G::Scalar, &G::Scalar) -> G::Scalar,
140 {
141 let mut e = *claim;
142 let mut r: Vec<G::Scalar> = Vec::new();
143 let mut quad_polys: Vec<CompressedUniPoly<G>> = Vec::new();
144
145 for _j in 0..num_rounds {
146 let mut evals: Vec<(G::Scalar, G::Scalar)> = Vec::new();
147
148 for (poly_A, poly_B) in poly_A_vec.iter().zip(poly_B_vec.iter()) {
149 let mut eval_point_0 = G::Scalar::zero();
150 let mut eval_point_2 = G::Scalar::zero();
151
152 let len = poly_A.len() / 2;
153 for i in 0..len {
154 // eval 0: bound_func is A(low)
155 eval_point_0 += comb_func(&poly_A[i], &poly_B[i]);
156
157 // eval 2: bound_func is -A(low) + 2*A(high)
158 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
159 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
160 eval_point_2 += comb_func(&poly_A_bound_point, &poly_B_bound_point);
161 }
162
163 evals.push((eval_point_0, eval_point_2));
164 }
165
166 let evals_combined_0 = (0..evals.len())
167 .map(|i| evals[i].0 * coeffs[i])
168 .fold(G::Scalar::zero(), |acc, item| acc + item);
169 let evals_combined_2 = (0..evals.len())
170 .map(|i| evals[i].1 * coeffs[i])
171 .fold(G::Scalar::zero(), |acc, item| acc + item);
172
173 let evals = vec![evals_combined_0, e - evals_combined_0, evals_combined_2];
174 let poly = UniPoly::from_evals(&evals);
175
176 // append the prover's message to the transcript
177 transcript.absorb(b"p", &poly);
178
179 // derive the verifier's challenge for the next round
180 let r_i = transcript.squeeze(b"c")?;
181 r.push(r_i);
182
183 // bound all tables to the verifier's challenege
184 for (poly_A, poly_B) in poly_A_vec.iter_mut().zip(poly_B_vec.iter_mut()) {
185 poly_A.bound_poly_var_top(&r_i);
186 poly_B.bound_poly_var_top(&r_i);
187 }
188
189 e = poly.evaluate(&r_i);
190 quad_polys.push(poly.compress());
191 }
192
193 let poly_A_final = (0..poly_A_vec.len()).map(|i| poly_A_vec[i][0]).collect();
194 let poly_B_final = (0..poly_B_vec.len()).map(|i| poly_B_vec[i][0]).collect();
195 let claims_prod = (poly_A_final, poly_B_final);
196
197 Ok((SumcheckProof::new(quad_polys), r, claims_prod))
198 }
199
200 pub fn prove_cubic<F>(
201 claim: &G::Scalar,
202 num_rounds: usize,
203 poly_A: &mut MultilinearPolynomial<G::Scalar>,
204 poly_B: &mut MultilinearPolynomial<G::Scalar>,
205 poly_C: &mut MultilinearPolynomial<G::Scalar>,
206 comb_func: F,
207 transcript: &mut G::TE,
208 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
209 where
210 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar + Sync,
211 {
212 let mut r: Vec<G::Scalar> = Vec::new();
213 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
214 let mut claim_per_round = *claim;
215
216 for _ in 0..num_rounds {
217 let poly = {
218 let len = poly_A.len() / 2;
219
220 // Make an iterator returning the contributions to the evaluations
221 let (eval_point_0, eval_point_2, eval_point_3) = (0..len)
222 .into_par_iter()
223 .map(|i| {
224 // eval 0: bound_func is A(low)
225 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i], &poly_C[i]);
226
227 // eval 2: bound_func is -A(low) + 2*A(high)
228 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
229 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
230 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
231 let eval_point_2 = comb_func(
232 &poly_A_bound_point,
233 &poly_B_bound_point,
234 &poly_C_bound_point,
235 );
236
237 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
238 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
239 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
240 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
241 let eval_point_3 = comb_func(
242 &poly_A_bound_point,
243 &poly_B_bound_point,
244 &poly_C_bound_point,
245 );
246 (eval_point_0, eval_point_2, eval_point_3)
247 })
248 .reduce(
249 || (G::Scalar::zero(), G::Scalar::zero(), G::Scalar::zero()),
250 |a, b| (a.0 + b.0, a.1 + b.1, a.2 + b.2),
251 );
252
253 let evals = vec![
254 eval_point_0,
255 claim_per_round - eval_point_0,
256 eval_point_2,
257 eval_point_3,
258 ];
259 UniPoly::from_evals(&evals)
260 };
261
262 // append the prover's message to the transcript
263 transcript.absorb(b"p", &poly);
264
265 //derive the verifier's challenge for the next round
266 let r_i = transcript.squeeze(b"c")?;
267 r.push(r_i);
268 polys.push(poly.compress());
269
270 // Set up next round
271 claim_per_round = poly.evaluate(&r_i);
272
273 // bound all tables to the verifier's challenege
274 poly_A.bound_poly_var_top(&r_i);
275 poly_B.bound_poly_var_top(&r_i);
276 poly_C.bound_poly_var_top(&r_i);
277 }
278
279 Ok((
280 SumcheckProof {
281 compressed_polys: polys,
282 },
283 r,
284 vec![poly_A[0], poly_B[0], poly_C[0]],
285 ))
286 }
287
288 pub fn prove_cubic_with_additive_term<F>(
289 claim: &G::Scalar,
290 num_rounds: usize,
291 poly_A: &mut MultilinearPolynomial<G::Scalar>,
292 poly_B: &mut MultilinearPolynomial<G::Scalar>,
293 poly_C: &mut MultilinearPolynomial<G::Scalar>,
294 poly_D: &mut MultilinearPolynomial<G::Scalar>,
295 comb_func: F,
296 transcript: &mut G::TE,
297 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
298 where
299 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar + Sync,
300 {
301 let mut r: Vec<G::Scalar> = Vec::new();
302 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
303 let mut claim_per_round = *claim;
304
305 for _ in 0..num_rounds {
306 let poly = {
307 let len = poly_A.len() / 2;
308
309 // Make an iterator returning the contributions to the evaluations
310 let (eval_point_0, eval_point_2, eval_point_3) = (0..len)
311 .into_par_iter()
312 .map(|i| {
313 // eval 0: bound_func is A(low)
314 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
315
316 // eval 2: bound_func is -A(low) + 2*A(high)
317 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
318 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
319 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
320 let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
321 let eval_point_2 = comb_func(
322 &poly_A_bound_point,
323 &poly_B_bound_point,
324 &poly_C_bound_point,
325 &poly_D_bound_point,
326 );
327
328 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
329 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
330 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
331 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
332 let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
333 let eval_point_3 = comb_func(
334 &poly_A_bound_point,
335 &poly_B_bound_point,
336 &poly_C_bound_point,
337 &poly_D_bound_point,
338 );
339 (eval_point_0, eval_point_2, eval_point_3)
340 })
341 .reduce(
342 || (G::Scalar::zero(), G::Scalar::zero(), G::Scalar::zero()),
343 |a, b| (a.0 + b.0, a.1 + b.1, a.2 + b.2),
344 );
345
346 let evals = vec![
347 eval_point_0,
348 claim_per_round - eval_point_0,
349 eval_point_2,
350 eval_point_3,
351 ];
352 UniPoly::from_evals(&evals)
353 };
354
355 // append the prover's message to the transcript
356 transcript.absorb(b"p", &poly);
357
358 //derive the verifier's challenge for the next round
359 let r_i = transcript.squeeze(b"c")?;
360 r.push(r_i);
361 polys.push(poly.compress());
362
363 // Set up next round
364 claim_per_round = poly.evaluate(&r_i);
365
366 // bound all tables to the verifier's challenege
367 poly_A.bound_poly_var_top(&r_i);
368 poly_B.bound_poly_var_top(&r_i);
369 poly_C.bound_poly_var_top(&r_i);
370 poly_D.bound_poly_var_top(&r_i);
371 }
372
373 Ok((
374 SumcheckProof {
375 compressed_polys: polys,
376 },
377 r,
378 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
379 ))
380 }
381}
382
383// ax^2 + bx + c stored as vec![a,b,c]
384// ax^3 + bx^2 + cx + d stored as vec![a,b,c,d]
385#[derive(Debug)]
386pub struct UniPoly<G: Group> {
387 coeffs: Vec<G::Scalar>,
388}
389
390// ax^2 + bx + c stored as vec![a,c]
391// ax^3 + bx^2 + cx + d stored as vec![a,c,d]
392#[derive(Clone, Debug, Serialize, Deserialize)]
393pub struct CompressedUniPoly<G: Group> {
394 coeffs_except_linear_term: Vec<G::Scalar>,
395 _p: PhantomData<G>,
396}
397
398impl<G: Group> UniPoly<G> {
399 pub fn from_evals(evals: &[G::Scalar]) -> Self {
400 // we only support degree-2 or degree-3 univariate polynomials
401 assert!(evals.len() == 3 || evals.len() == 4);
402 let coeffs = if evals.len() == 3 {
403 // ax^2 + bx + c
404 let two_inv = G::Scalar::from(2).invert().unwrap();
405
406 let c = evals[0];
407 let a = two_inv * (evals[2] - evals[1] - evals[1] + c);
408 let b = evals[1] - c - a;
409 vec![c, b, a]
410 } else {
411 // ax^3 + bx^2 + cx + d
412 let two_inv = G::Scalar::from(2).invert().unwrap();
413 let six_inv = G::Scalar::from(6).invert().unwrap();
414
415 let d = evals[0];
416 let a = six_inv
417 * (evals[3] - evals[2] - evals[2] - evals[2] + evals[1] + evals[1] + evals[1] - evals[0]);
418 let b = two_inv
419 * (evals[0] + evals[0] - evals[1] - evals[1] - evals[1] - evals[1] - evals[1]
420 + evals[2]
421 + evals[2]
422 + evals[2]
423 + evals[2]
424 - evals[3]);
425 let c = evals[1] - d - a - b;
426 vec![d, c, b, a]
427 };
428
429 UniPoly { coeffs }
430 }
431
432 pub fn degree(&self) -> usize {
433 self.coeffs.len() - 1
434 }
435
436 pub fn eval_at_zero(&self) -> G::Scalar {
437 self.coeffs[0]
438 }
439
440 pub fn eval_at_one(&self) -> G::Scalar {
441 (0..self.coeffs.len())
442 .into_par_iter()
443 .map(|i| self.coeffs[i])
444 .reduce(G::Scalar::zero, |a, b| a + b)
445 }
446
447 pub fn evaluate(&self, r: &G::Scalar) -> G::Scalar {
448 let mut eval = self.coeffs[0];
449 let mut power = *r;
450 for coeff in self.coeffs.iter().skip(1) {
451 eval += power * coeff;
452 power *= r;
453 }
454 eval
455 }
456
457 pub fn compress(&self) -> CompressedUniPoly<G> {
458 let coeffs_except_linear_term = [&self.coeffs[0..1], &self.coeffs[2..]].concat();
459 assert_eq!(coeffs_except_linear_term.len() + 1, self.coeffs.len());
460 CompressedUniPoly {
461 coeffs_except_linear_term,
462 _p: Default::default(),
463 }
464 }
465}
466
467impl<G: Group> CompressedUniPoly<G> {
468 // we require eval(0) + eval(1) = hint, so we can solve for the linear term as:
469 // linear_term = hint - 2 * constant_term - deg2 term - deg3 term
470 pub fn decompress(&self, hint: &G::Scalar) -> UniPoly<G> {
471 let mut linear_term =
472 *hint - self.coeffs_except_linear_term[0] - self.coeffs_except_linear_term[0];
473 for i in 1..self.coeffs_except_linear_term.len() {
474 linear_term -= self.coeffs_except_linear_term[i];
475 }
476
477 let mut coeffs: Vec<G::Scalar> = Vec::new();
478 coeffs.extend(vec![&self.coeffs_except_linear_term[0]]);
479 coeffs.extend(vec![&linear_term]);
480 coeffs.extend(self.coeffs_except_linear_term[1..].to_vec());
481 assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
482 UniPoly { coeffs }
483 }
484}
485
486impl<G: Group> TranscriptReprTrait<G> for UniPoly<G> {
487 fn to_transcript_bytes(&self) -> Vec<u8> {
488 let coeffs = self.compress().coeffs_except_linear_term;
489 coeffs.as_slice().to_transcript_bytes()
490 }
491}