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