Nova/src/spartan_with_ipa_pc/sumcheck.rs
src/spartan_with_ipa_pc/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 merlin::Transcript;
9use rayon::prelude::*;
10
11#[derive(Debug)]
12pub struct SumcheckProof<G: Group> {
13 compressed_polys: Vec<CompressedUniPoly<G>>,
14}
15
16impl<G: Group> SumcheckProof<G> {
17 pub fn verify(
18 &self,
19 claim: G::Scalar,
20 num_rounds: usize,
21 degree_bound: usize,
22 transcript: &mut Transcript,
23 ) -> Result<(G::Scalar, Vec<G::Scalar>), NovaError> {
24 let mut e = claim;
25 let mut r: Vec<G::Scalar> = Vec::new();
26
27 // verify that there is a univariate polynomial for each round
28 if self.compressed_polys.len() != num_rounds {
29 return Err(NovaError::InvalidSumcheckProof);
30 }
31
32 for i in 0..self.compressed_polys.len() {
33 let poly = self.compressed_polys[i].decompress(&e);
34
35 // verify degree bound
36 if poly.degree() != degree_bound {
37 return Err(NovaError::InvalidSumcheckProof);
38 }
39
40 // check if G_k(0) + G_k(1) = e
41 if poly.eval_at_zero() + poly.eval_at_one() != e {
42 return Err(NovaError::InvalidSumcheckProof);
43 }
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_nextround", 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 Transcript,
67 ) -> (Self, Vec<G::Scalar>, Vec<G::Scalar>)
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_nextround", 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 (
117 SumcheckProof {
118 compressed_polys: polys,
119 },
120 r,
121 vec![poly_A[0], poly_B[0]],
122 )
123 }
124
125 pub fn prove_cubic_with_additive_term<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 Transcript,
134 ) -> (Self, Vec<G::Scalar>, Vec<G::Scalar>)
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
142 for _ in 0..num_rounds {
143 let poly = {
144 let len = poly_A.len() / 2;
145
146 // Make an iterator returning the contributions to the evaluations
147 let (eval_point_0, eval_point_2, eval_point_3) = (0..len)
148 .into_par_iter()
149 .map(|i| {
150 // eval 0: bound_func is A(low)
151 let eval_point_0 = comb_func(&poly_A[i], &poly_B[i], &poly_C[i], &poly_D[i]);
152
153 // eval 2: bound_func is -A(low) + 2*A(high)
154 let poly_A_bound_point = poly_A[len + i] + poly_A[len + i] - poly_A[i];
155 let poly_B_bound_point = poly_B[len + i] + poly_B[len + i] - poly_B[i];
156 let poly_C_bound_point = poly_C[len + i] + poly_C[len + i] - poly_C[i];
157 let poly_D_bound_point = poly_D[len + i] + poly_D[len + i] - poly_D[i];
158 let eval_point_2 = comb_func(
159 &poly_A_bound_point,
160 &poly_B_bound_point,
161 &poly_C_bound_point,
162 &poly_D_bound_point,
163 );
164
165 // eval 3: bound_func is -2A(low) + 3A(high); computed incrementally with bound_func applied to eval(2)
166 let poly_A_bound_point = poly_A_bound_point + poly_A[len + i] - poly_A[i];
167 let poly_B_bound_point = poly_B_bound_point + poly_B[len + i] - poly_B[i];
168 let poly_C_bound_point = poly_C_bound_point + poly_C[len + i] - poly_C[i];
169 let poly_D_bound_point = poly_D_bound_point + poly_D[len + i] - poly_D[i];
170 let eval_point_3 = comb_func(
171 &poly_A_bound_point,
172 &poly_B_bound_point,
173 &poly_C_bound_point,
174 &poly_D_bound_point,
175 );
176 (eval_point_0, eval_point_2, eval_point_3)
177 })
178 .reduce(
179 || (G::Scalar::zero(), G::Scalar::zero(), G::Scalar::zero()),
180 |a, b| (a.0 + b.0, a.1 + b.1, a.2 + b.2),
181 );
182
183 let evals = vec![
184 eval_point_0,
185 claim_per_round - eval_point_0,
186 eval_point_2,
187 eval_point_3,
188 ];
189 UniPoly::from_evals(&evals)
190 };
191
192 // append the prover's message to the transcript
193 poly.append_to_transcript(b"poly", transcript);
194
195 //derive the verifier's challenge for the next round
196 let r_i = G::Scalar::challenge(b"challenge_nextround", transcript);
197 r.push(r_i);
198 polys.push(poly.compress());
199
200 // Set up next round
201 claim_per_round = poly.evaluate(&r_i);
202
203 // bound all tables to the verifier's challenege
204 poly_A.bound_poly_var_top(&r_i);
205 poly_B.bound_poly_var_top(&r_i);
206 poly_C.bound_poly_var_top(&r_i);
207 poly_D.bound_poly_var_top(&r_i);
208 }
209
210 (
211 SumcheckProof {
212 compressed_polys: polys,
213 },
214 r,
215 vec![poly_A[0], poly_B[0], poly_C[0], poly_D[0]],
216 )
217 }
218}
219
220// ax^2 + bx + c stored as vec![a,b,c]
221// ax^3 + bx^2 + cx + d stored as vec![a,b,c,d]
222#[derive(Debug)]
223pub struct UniPoly<G: Group> {
224 coeffs: Vec<G::Scalar>,
225}
226
227// ax^2 + bx + c stored as vec![a,c]
228// ax^3 + bx^2 + cx + d stored as vec![a,c,d]
229#[derive(Debug)]
230pub struct CompressedUniPoly<G: Group> {
231 coeffs_except_linear_term: Vec<G::Scalar>,
232 _p: PhantomData<G>,
233}
234
235impl<G: Group> UniPoly<G> {
236 pub fn from_evals(evals: &[G::Scalar]) -> Self {
237 // we only support degree-2 or degree-3 univariate polynomials
238 assert!(evals.len() == 3 || evals.len() == 4);
239 let coeffs = if evals.len() == 3 {
240 // ax^2 + bx + c
241 let two_inv = G::Scalar::from(2).invert().unwrap();
242
243 let c = evals[0];
244 let a = two_inv * (evals[2] - evals[1] - evals[1] + c);
245 let b = evals[1] - c - a;
246 vec![c, b, a]
247 } else {
248 // ax^3 + bx^2 + cx + d
249 let two_inv = G::Scalar::from(2).invert().unwrap();
250 let six_inv = G::Scalar::from(6).invert().unwrap();
251
252 let d = evals[0];
253 let a = six_inv
254 * (evals[3] - evals[2] - evals[2] - evals[2] + evals[1] + evals[1] + evals[1] - evals[0]);
255 let b = two_inv
256 * (evals[0] + evals[0] - evals[1] - evals[1] - evals[1] - evals[1] - evals[1]
257 + evals[2]
258 + evals[2]
259 + evals[2]
260 + evals[2]
261 - evals[3]);
262 let c = evals[1] - d - a - b;
263 vec![d, c, b, a]
264 };
265
266 UniPoly { coeffs }
267 }
268
269 pub fn degree(&self) -> usize {
270 self.coeffs.len() - 1
271 }
272
273 pub fn eval_at_zero(&self) -> G::Scalar {
274 self.coeffs[0]
275 }
276
277 pub fn eval_at_one(&self) -> G::Scalar {
278 (0..self.coeffs.len())
279 .into_par_iter()
280 .map(|i| self.coeffs[i])
281 .reduce(G::Scalar::zero, |a, b| a + b)
282 }
283
284 pub fn evaluate(&self, r: &G::Scalar) -> G::Scalar {
285 let mut eval = self.coeffs[0];
286 let mut power = *r;
287 for coeff in self.coeffs.iter().skip(1) {
288 eval += power * coeff;
289 power *= r;
290 }
291 eval
292 }
293
294 pub fn compress(&self) -> CompressedUniPoly<G> {
295 let coeffs_except_linear_term = [&self.coeffs[0..1], &self.coeffs[2..]].concat();
296 assert_eq!(coeffs_except_linear_term.len() + 1, self.coeffs.len());
297 CompressedUniPoly {
298 coeffs_except_linear_term,
299 _p: Default::default(),
300 }
301 }
302}
303
304impl<G: Group> CompressedUniPoly<G> {
305 // we require eval(0) + eval(1) = hint, so we can solve for the linear term as:
306 // linear_term = hint - 2 * constant_term - deg2 term - deg3 term
307 pub fn decompress(&self, hint: &G::Scalar) -> UniPoly<G> {
308 let mut linear_term =
309 *hint - self.coeffs_except_linear_term[0] - self.coeffs_except_linear_term[0];
310 for i in 1..self.coeffs_except_linear_term.len() {
311 linear_term -= self.coeffs_except_linear_term[i];
312 }
313
314 let mut coeffs: Vec<G::Scalar> = Vec::new();
315 coeffs.extend(vec![&self.coeffs_except_linear_term[0]]);
316 coeffs.extend(vec![&linear_term]);
317 coeffs.extend(self.coeffs_except_linear_term[1..].to_vec());
318 assert_eq!(self.coeffs_except_linear_term.len() + 1, coeffs.len());
319 UniPoly { coeffs }
320 }
321}
322
323impl<G: Group> AppendToTranscriptTrait for UniPoly<G> {
324 fn append_to_transcript(&self, label: &'static [u8], transcript: &mut Transcript) {
325 transcript.append_message(label, b"UniPoly_begin");
326 for i in 0..self.coeffs.len() {
327 self.coeffs[i].append_to_transcript(b"coeff", transcript);
328 }
329 transcript.append_message(label, b"UniPoly_end");
330 }
331}