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