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 holds
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 #[inline]
65 fn compute_eval_points<F>(
66 poly_A: &MultilinearPolynomial<G::Scalar>,
67 poly_B: &MultilinearPolynomial<G::Scalar>,
68 comb_func: &F,
69 ) -> (G::Scalar, G::Scalar)
70 where
71 F: Fn(&G::Scalar, &G::Scalar) -> G::Scalar + Sync,
72 {
73 let len = poly_A.len() / 2;
74 (0..len)
75 .into_par_iter()
76 .map(|i| {
77 // eval 0: bound_func is A(low)
78 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i]);
79
80 // eval 2: bound_func is -A(low) + 2*A(high)
81 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
82 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
83 let eval_point_2 = comb_func(&poly_A_bound_point, &poly_B_bound_point);
84 (eval_point_0, eval_point_2)
85 })
86 .reduce(
87 || (G::Scalar::ZERO, G::Scalar::ZERO),
88 |a, b| (a.0 + b.0, a.1 + b.1),
89 )
90 }
91
92 pub fn prove_quad<F>(
93 claim: &G::Scalar,
94 num_rounds: usize,
95 poly_A: &mut MultilinearPolynomial<G::Scalar>,
96 poly_B: &mut MultilinearPolynomial<G::Scalar>,
97 comb_func: F,
98 transcript: &mut G::TE,
99 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
100 where
101 F: Fn(&G::Scalar, &G::Scalar) -> G::Scalar + Sync,
102 {
103 let mut r: Vec<G::Scalar> = Vec::new();
104 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
105 let mut claim_per_round = *claim;
106 for _ in 0..num_rounds {
107 let poly = {
108 let (eval_point_0, eval_point_2) = Self::compute_eval_points(poly_A, poly_B, &comb_func);
109
110 let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
111 UniPoly::from_evals(&evals)
112 };
113
114 // append the prover's message to the transcript
115 transcript.absorb(b"p", &poly);
116
117 //derive the verifier's challenge for the next round
118 let r_i = transcript.squeeze(b"c")?;
119 r.push(r_i);
120 polys.push(poly.compress());
121
122 // Set up next round
123 claim_per_round = poly.evaluate(&r_i);
124
125 // bound all tables to the verifier's challenege
126 poly_A.bound_poly_var_top(&r_i);
127 poly_B.bound_poly_var_top(&r_i);
128 }
129
130 Ok((
131 SumcheckProof {
132 compressed_polys: polys,
133 },
134 r,
135 vec![poly_A[0], poly_B[0]],
136 ))
137 }
138
139 pub fn prove_quad_batch<F>(
140 claim: &G::Scalar,
141 num_rounds: usize,
142 poly_A_vec: &mut Vec<MultilinearPolynomial<G::Scalar>>,
143 poly_B_vec: &mut Vec<MultilinearPolynomial<G::Scalar>>,
144 coeffs: &[G::Scalar],
145 comb_func: F,
146 transcript: &mut G::TE,
147 ) -> Result<(Self, Vec<G::Scalar>, (Vec<G::Scalar>, Vec<G::Scalar>)), NovaError>
148 where
149 F: Fn(&G::Scalar, &G::Scalar) -> G::Scalar + Sync,
150 {
151 let mut e = *claim;
152 let mut r: Vec<G::Scalar> = Vec::new();
153 let mut quad_polys: Vec<CompressedUniPoly<G>> = Vec::new();
154
155 for _j in 0..num_rounds {
156 let mut evals: Vec<(G::Scalar, G::Scalar)> = Vec::new();
157
158 for (poly_A, poly_B) in poly_A_vec.iter().zip(poly_B_vec.iter()) {
159 let (eval_point_0, eval_point_2) = Self::compute_eval_points(poly_A, poly_B, &comb_func);
160 evals.push((eval_point_0, eval_point_2));
161 }
162
163 let evals_combined_0 = (0..evals.len()).map(|i| evals[i].0 * coeffs[i]).sum();
164 let evals_combined_2 = (0..evals.len()).map(|i| evals[i].1 * coeffs[i]).sum();
165
166 let evals = vec![evals_combined_0, e - evals_combined_0, evals_combined_2];
167 let poly = UniPoly::from_evals(&evals);
168
169 // append the prover's message to the transcript
170 transcript.absorb(b"p", &poly);
171
172 // derive the verifier's challenge for the next round
173 let r_i = transcript.squeeze(b"c")?;
174 r.push(r_i);
175
176 // bound all tables to the verifier's challenege
177 for (poly_A, poly_B) in poly_A_vec.iter_mut().zip(poly_B_vec.iter_mut()) {
178 poly_A.bound_poly_var_top(&r_i);
179 poly_B.bound_poly_var_top(&r_i);
180 }
181
182 e = poly.evaluate(&r_i);
183 quad_polys.push(poly.compress());
184 }
185
186 let poly_A_final = (0..poly_A_vec.len()).map(|i| poly_A_vec[i][0]).collect();
187 let poly_B_final = (0..poly_B_vec.len()).map(|i| poly_B_vec[i][0]).collect();
188 let claims_prod = (poly_A_final, poly_B_final);
189
190 Ok((SumcheckProof::new(quad_polys), r, claims_prod))
191 }
192
193 pub fn prove_cubic_with_additive_term<F>(
194 claim: &G::Scalar,
195 num_rounds: usize,
196 poly_A: &mut MultilinearPolynomial<G::Scalar>,
197 poly_B: &mut MultilinearPolynomial<G::Scalar>,
198 poly_C: &mut MultilinearPolynomial<G::Scalar>,
199 poly_D: &mut MultilinearPolynomial<G::Scalar>,
200 comb_func: F,
201 transcript: &mut G::TE,
202 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
203 where
204 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar + Sync,
205 {
206 let mut r: Vec<G::Scalar> = Vec::new();
207 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
208 let mut claim_per_round = *claim;
209
210 for _ in 0..num_rounds {
211 let poly = {
212 let len = poly_A.len() / 2;
213
214 // Make an iterator returning the contributions to the evaluations
215 let (eval_point_0, eval_point_2, eval_point_3) = (0..len)
216 .into_par_iter()
217 .map(|i| {
218 // eval 0: bound_func is A(low)
219 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
220
221 // eval 2: bound_func is -A(low) + 2*A(high)
222 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
223 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
224 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
225 let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
226 let eval_point_2 = comb_func(
227 &poly_A_bound_point,
228 &poly_B_bound_point,
229 &poly_C_bound_point,
230 &poly_D_bound_point,
231 );
232
233 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
234 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
235 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
236 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
237 let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
238 let eval_point_3 = comb_func(
239 &poly_A_bound_point,
240 &poly_B_bound_point,
241 &poly_C_bound_point,
242 &poly_D_bound_point,
243 );
244 (eval_point_0, eval_point_2, eval_point_3)
245 })
246 .reduce(
247 || (G::Scalar::ZERO, G::Scalar::ZERO, G::Scalar::ZERO),
248 |a, b| (a.0 + b.0, a.1 + b.1, a.2 + b.2),
249 );
250
251 let evals = vec![
252 eval_point_0,
253 claim_per_round - eval_point_0,
254 eval_point_2,
255 eval_point_3,
256 ];
257 UniPoly::from_evals(&evals)
258 };
259
260 // append the prover's message to the transcript
261 transcript.absorb(b"p", &poly);
262
263 //derive the verifier's challenge for the next round
264 let r_i = transcript.squeeze(b"c")?;
265 r.push(r_i);
266 polys.push(poly.compress());
267
268 // Set up next round
269 claim_per_round = poly.evaluate(&r_i);
270
271 // bound all tables to the verifier's challenege
272 poly_A.bound_poly_var_top(&r_i);
273 poly_B.bound_poly_var_top(&r_i);
274 poly_C.bound_poly_var_top(&r_i);
275 poly_D.bound_poly_var_top(&r_i);
276 }
277
278 Ok((
279 SumcheckProof {
280 compressed_polys: polys,
281 },
282 r,
283 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
284 ))
285 }
286}
287
288// ax^2 + bx + c stored as vec![a,b,c]
289// ax^3 + bx^2 + cx + d stored as vec![a,b,c,d]
290#[derive(Debug)]
291pub struct UniPoly<G: Group> {
292 coeffs: Vec<G::Scalar>,
293}
294
295// ax^2 + bx + c stored as vec![a,c]
296// ax^3 + bx^2 + cx + d stored as vec![a,c,d]
297#[derive(Clone, Debug, Serialize, Deserialize)]
298pub struct CompressedUniPoly<G: Group> {
299 coeffs_except_linear_term: Vec<G::Scalar>,
300 _p: PhantomData<G>,
301}
302
303impl<G: Group> UniPoly<G> {
304 pub fn from_evals(evals: &[G::Scalar]) -> Self {
305 // we only support degree-2 or degree-3 univariate polynomials
306 assert!(evals.len() == 3 || evals.len() == 4);
307 let coeffs = if evals.len() == 3 {
308 // ax^2 + bx + c
309 let two_inv = G::Scalar::from(2).invert().unwrap();
310
311 let c = evals[0];
312 let a = two_inv * (evals[2] - evals[1] - evals[1] + c);
313 let b = evals[1] - c - a;
314 vec![c, b, a]
315 } else {
316 // ax^3 + bx^2 + cx + d
317 let two_inv = G::Scalar::from(2).invert().unwrap();
318 let six_inv = G::Scalar::from(6).invert().unwrap();
319
320 let d = evals[0];
321 let a = six_inv
322 * (evals[3] - evals[2] - evals[2] - evals[2] + evals[1] + evals[1] + evals[1] - evals[0]);
323 let b = two_inv
324 * (evals[0] + evals[0] - evals[1] - evals[1] - evals[1] - evals[1] - evals[1]
325 + evals[2]
326 + evals[2]
327 + evals[2]
328 + evals[2]
329 - evals[3]);
330 let c = evals[1] - d - a - b;
331 vec![d, c, b, a]
332 };
333
334 UniPoly { coeffs }
335 }
336
337 pub fn degree(&self) -> usize {
338 self.coeffs.len() - 1
339 }
340
341 pub fn eval_at_zero(&self) -> G::Scalar {
342 self.coeffs[0]
343 }
344
345 pub fn eval_at_one(&self) -> G::Scalar {
346 (0..self.coeffs.len())
347 .into_par_iter()
348 .map(|i| self.coeffs[i])
349 .reduce(|| G::Scalar::ZERO, |a, b| a + b)
350 }
351
352 pub fn evaluate(&self, r: &G::Scalar) -> G::Scalar {
353 let mut eval = self.coeffs[0];
354 let mut power = *r;
355 for coeff in self.coeffs.iter().skip(1) {
356 eval += power * coeff;
357 power *= r;
358 }
359 eval
360 }
361
362 pub fn compress(&self) -> CompressedUniPoly<G> {
363 let coeffs_except_linear_term = [&self.coeffs[0..1], &self.coeffs[2..]].concat();
364 assert_eq!(coeffs_except_linear_term.len() + 1, self.coeffs.len());
365 CompressedUniPoly {
366 coeffs_except_linear_term,
367 _p: Default::default(),
368 }
369 }
370}
371
372impl<G: Group> CompressedUniPoly<G> {
373 // we require eval(0) + eval(1) = hint, so we can solve for the linear term as:
374 // linear_term = hint - 2 * constant_term - deg2 term - deg3 term
375 pub fn decompress(&self, hint: &G::Scalar) -> UniPoly<G> {
376 let mut linear_term =
377 *hint - self.coeffs_except_linear_term[0] - self.coeffs_except_linear_term[0];
378 for i in 1..self.coeffs_except_linear_term.len() {
379 linear_term -= self.coeffs_except_linear_term[i];
380 }
381
382 let mut coeffs: Vec<G::Scalar> = Vec::new();
383 coeffs.push(self.coeffs_except_linear_term[0]);
384 coeffs.push(linear_term);
385 coeffs.extend(&self.coeffs_except_linear_term[1..]);
386 assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
387 UniPoly { coeffs }
388 }
389}
390
391impl<G: Group> TranscriptReprTrait<G> for UniPoly<G> {
392 fn to_transcript_bytes(&self) -> Vec<u8> {
393 let coeffs = self.compress().coeffs_except_linear_term;
394 coeffs.as_slice().to_transcript_bytes()
395 }
396}