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 // check if G_k(0) + G_k(1) = e
42 if poly.eval_at_zero() + poly.eval_at_one() != e {
43 return Err(NovaError::InvalidSumcheckProof);
44 }
45
46 // append the prover's message to the transcript
47 poly.append_to_transcript(b"poly", transcript);
48
49 //derive the verifier's challenge for the next round
50 let r_i = G::Scalar::challenge(b"challenge_nextround", transcript)?;
51
52 r.push(r_i);
53
54 // evaluate the claimed degree-ell polynomial at r_i
55 e = poly.evaluate(&r_i);
56 }
57
58 Ok((e, r))
59 }
60
61 pub fn prove_quad<F>(
62 claim: &G::Scalar,
63 num_rounds: usize,
64 poly_A: &mut MultilinearPolynomial<G::Scalar>,
65 poly_B: &mut MultilinearPolynomial<G::Scalar>,
66 comb_func: F,
67 transcript: &mut G::TE,
68 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
69 where
70 F: Fn(&G::Scalar, &G::Scalar) -> G::Scalar + Sync,
71 {
72 let mut r: Vec<G::Scalar> = Vec::new();
73 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
74 let mut claim_per_round = *claim;
75 for _ in 0..num_rounds {
76 let poly = {
77 let len = poly_A.len() / 2;
78
79 // Make an iterator returning the contributions to the evaluations
80 let (eval_point_0, eval_point_2) = (0..len)
81 .into_par_iter()
82 .map(|i| {
83 // eval 0: bound_func is A(low)
84 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i]);
85
86 // eval 2: bound_func is -A(low) + 2*A(high)
87 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
88 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
89 let eval_point_2 = comb_func(&poly_A_bound_point, &poly_B_bound_point);
90 (eval_point_0, eval_point_2)
91 })
92 .reduce(
93 || (G::Scalar::zero(), G::Scalar::zero()),
94 |a, b| (a.0 + b.0, a.1 + b.1),
95 );
96
97 let evals = vec![eval_point_0, claim_per_round - eval_point_0, eval_point_2];
98 UniPoly::from_evals(&evals)
99 };
100
101 // append the prover's message to the transcript
102 poly.append_to_transcript(b"poly", transcript);
103
104 //derive the verifier's challenge for the next round
105 let r_i = G::Scalar::challenge(b"challenge_nextround", transcript)?;
106 r.push(r_i);
107 polys.push(poly.compress());
108
109 // Set up next round
110 claim_per_round = poly.evaluate(&r_i);
111
112 // bound all tables to the verifier's challenege
113 poly_A.bound_poly_var_top(&r_i);
114 poly_B.bound_poly_var_top(&r_i);
115 }
116
117 Ok((
118 SumcheckProof {
119 compressed_polys: polys,
120 },
121 r,
122 vec![poly_A[0], poly_B[0]],
123 ))
124 }
125
126 pub fn prove_cubic_with_additive_term<F>(
127 claim: &G::Scalar,
128 num_rounds: usize,
129 poly_A: &mut MultilinearPolynomial<G::Scalar>,
130 poly_B: &mut MultilinearPolynomial<G::Scalar>,
131 poly_C: &mut MultilinearPolynomial<G::Scalar>,
132 poly_D: &mut MultilinearPolynomial<G::Scalar>,
133 comb_func: F,
134 transcript: &mut G::TE,
135 ) -> Result<(Self, Vec<G::Scalar>, Vec<G::Scalar>), NovaError>
136 where
137 F: Fn(&G::Scalar, &G::Scalar, &G::Scalar, &G::Scalar) -> G::Scalar + Sync,
138 {
139 let mut r: Vec<G::Scalar> = Vec::new();
140 let mut polys: Vec<CompressedUniPoly<G>> = Vec::new();
141 let mut claim_per_round = *claim;
142
143 for _ in 0..num_rounds {
144 let poly = {
145 let len = poly_A.len() / 2;
146
147 // Make an iterator returning the contributions to the evaluations
148 let (eval_point_0, eval_point_2, eval_point_3) = (0..len)
149 .into_par_iter()
150 .map(|i| {
151 // eval 0: bound_func is A(low)
152 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
153
154 // eval 2: bound_func is -A(low) + 2*A(high)
155 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
156 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
157 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
158 let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
159 let eval_point_2 = comb_func(
160 &poly_A_bound_point,
161 &poly_B_bound_point,
162 &poly_C_bound_point,
163 &poly_D_bound_point,
164 );
165
166 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
167 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
168 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
169 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
170 let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
171 let eval_point_3 = comb_func(
172 &poly_A_bound_point,
173 &poly_B_bound_point,
174 &poly_C_bound_point,
175 &poly_D_bound_point,
176 );
177 (eval_point_0, eval_point_2, eval_point_3)
178 })
179 .reduce(
180 || (G::Scalar::zero(), G::Scalar::zero(), G::Scalar::zero()),
181 |a, b| (a.0 + b.0, a.1 + b.1, a.2 + b.2),
182 );
183
184 let evals = vec![
185 eval_point_0,
186 claim_per_round - eval_point_0,
187 eval_point_2,
188 eval_point_3,
189 ];
190 UniPoly::from_evals(&evals)
191 };
192
193 // append the prover's message to the transcript
194 poly.append_to_transcript(b"poly", transcript);
195
196 //derive the verifier's challenge for the next round
197 let r_i = G::Scalar::challenge(b"challenge_nextround", transcript)?;
198 r.push(r_i);
199 polys.push(poly.compress());
200
201 // Set up next round
202 claim_per_round = poly.evaluate(&r_i);
203
204 // bound all tables to the verifier's challenege
205 poly_A.bound_poly_var_top(&r_i);
206 poly_B.bound_poly_var_top(&r_i);
207 poly_C.bound_poly_var_top(&r_i);
208 poly_D.bound_poly_var_top(&r_i);
209 }
210
211 Ok((
212 SumcheckProof {
213 compressed_polys: polys,
214 },
215 r,
216 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
217 ))
218 }
219}
220
221// ax^2 + bx + c stored as vec![a,b,c]
222// ax^3 + bx^2 + cx + d stored as vec![a,b,c,d]
223#[derive(Debug)]
224pub struct UniPoly<G: Group> {
225 coeffs: Vec<G::Scalar>,
226}
227
228// ax^2 + bx + c stored as vec![a,c]
229// ax^3 + bx^2 + cx + d stored as vec![a,c,d]
230#[derive(Debug, Serialize, Deserialize)]
231pub struct CompressedUniPoly<G: Group> {
232 coeffs_except_linear_term: Vec<G::Scalar>,
233 _p: PhantomData<G>,
234}
235
236impl<G: Group> UniPoly<G> {
237 pub fn from_evals(evals: &[G::Scalar]) -> Self {
238 // we only support degree-2 or degree-3 univariate polynomials
239 assert!(evals.len() == 3 || evals.len() == 4);
240 let coeffs = if evals.len() == 3 {
241 // ax^2 + bx + c
242 let two_inv = G::Scalar::from(2).invert().unwrap();
243
244 let c = evals[0];
245 let a = two_inv * (evals[2] - evals[1] - evals[1] + c);
246 let b = evals[1] - c - a;
247 vec![c, b, a]
248 } else {
249 // ax^3 + bx^2 + cx + d
250 let two_inv = G::Scalar::from(2).invert().unwrap();
251 let six_inv = G::Scalar::from(6).invert().unwrap();
252
253 let d = evals[0];
254 let a = six_inv
255 * (evals[3] - evals[2] - evals[2] - evals[2] + evals[1] + evals[1] + evals[1] - evals[0]);
256 let b = two_inv
257 * (evals[0] + evals[0] - evals[1] - evals[1] - evals[1] - evals[1] - evals[1]
258 + evals[2]
259 + evals[2]
260 + evals[2]
261 + evals[2]
262 - evals[3]);
263 let c = evals[1] - d - a - b;
264 vec![d, c, b, a]
265 };
266
267 UniPoly { coeffs }
268 }
269
270 pub fn degree(&self) -> usize {
271 self.coeffs.len() - 1
272 }
273
274 pub fn eval_at_zero(&self) -> G::Scalar {
275 self.coeffs[0]
276 }
277
278 pub fn eval_at_one(&self) -> G::Scalar {
279 (0..self.coeffs.len())
280 .into_par_iter()
281 .map(|i| self.coeffs[i])
282 .reduce(G::Scalar::zero, |a, b| a + b)
283 }
284
285 pub fn evaluate(&self, r: &G::Scalar) -> G::Scalar {
286 let mut eval = self.coeffs[0];
287 let mut power = *r;
288 for coeff in self.coeffs.iter().skip(1) {
289 eval += power * coeff;
290 power *= r;
291 }
292 eval
293 }
294
295 pub fn compress(&self) -> CompressedUniPoly<G> {
296 let coeffs_except_linear_term = [&self.coeffs[0..1], &self.coeffs[2..]].concat();
297 assert_eq!(coeffs_except_linear_term.len() + 1, self.coeffs.len());
298 CompressedUniPoly {
299 coeffs_except_linear_term,
300 _p: Default::default(),
301 }
302 }
303}
304
305impl<G: Group> CompressedUniPoly<G> {
306 // we require eval(0) + eval(1) = hint, so we can solve for the linear term as:
307 // linear_term = hint - 2 * constant_term - deg2 term - deg3 term
308 pub fn decompress(&self, hint: &G::Scalar) -> UniPoly<G> {
309 let mut linear_term =
310 *hint - self.coeffs_except_linear_term[0] - self.coeffs_except_linear_term[0];
311 for i in 1..self.coeffs_except_linear_term.len() {
312 linear_term -= self.coeffs_except_linear_term[i];
313 }
314
315 let mut coeffs: Vec<G::Scalar> = Vec::new();
316 coeffs.extend(vec![&self.coeffs_except_linear_term[0]]);
317 coeffs.extend(vec![&linear_term]);
318 coeffs.extend(self.coeffs_except_linear_term[1..].to_vec());
319 assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
320 UniPoly { coeffs }
321 }
322}
323
324impl<G: Group> AppendToTranscriptTrait<G> for UniPoly<G> {
325 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut G::TE) {
326 <[G::Scalar] as AppendToTranscriptTrait<G>>::append_to_transcript(
327 &self.coeffs,
328 label,
329 transcript,
330 );
331 }
332}