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