nova-study/src/hypernova/sumcheck.rs
src/hypernova/sumcheck.rsRaw
1// this file contains a sum-check protocol initial implementation, not used by the rest of the repo
2// but implemented as an exercise and it will probably be used in the future.
3
4use ark_ec::CurveGroup;
5use ark_ff::{BigInteger, PrimeField};
6use ark_poly::{
7 multivariate::{SparsePolynomial, SparseTerm, Term},
8 DenseMVPolynomial, DenseUVPolynomial, Polynomial,
9};
10use ark_std::log2;
11use ark_std::marker::PhantomData;
12
13use ark_crypto_primitives::sponge::{poseidon::PoseidonConfig, Absorb};
14
15use crate::transcript::Transcript;
16
17pub struct Point<F: PrimeField> {
18 _f: PhantomData<F>,
19}
20impl<F: PrimeField> Point<F> {
21 pub fn point_normal(n_elems: usize, iter_num: usize) -> Vec<F> {
22 let p = Self::point(vec![], false, n_elems, iter_num);
23 let mut r = vec![F::zero(); n_elems];
24 for i in 0..n_elems {
25 r[i] = p[i].unwrap();
26 }
27 r
28 }
29 pub fn point_complete(challenges: Vec<F>, n_elems: usize, iter_num: usize) -> Vec<F> {
30 let p = Self::point(challenges, false, n_elems, iter_num);
31 let mut r = vec![F::zero(); n_elems];
32 for i in 0..n_elems {
33 r[i] = p[i].unwrap();
34 }
35 r
36 }
37 fn point(challenges: Vec<F>, none: bool, n_elems: usize, iter_num: usize) -> Vec<Option<F>> {
38 let mut n_vars = n_elems - challenges.len();
39 assert!(n_vars >= log2(iter_num + 1) as usize);
40
41 if none {
42 // WIP
43 if n_vars == 0 {
44 panic!("err"); // or return directly challenges vector
45 }
46 n_vars -= 1;
47 }
48 let none_pos = if none {
49 challenges.len() + 1
50 } else {
51 challenges.len()
52 };
53 let mut p: Vec<Option<F>> = vec![None; n_elems];
54 for i in 0..challenges.len() {
55 p[i] = Some(challenges[i]);
56 }
57 for i in 0..n_vars {
58 let k = F::from(iter_num as u64).into_bigint().to_bytes_le();
59 let bit = k[i / 8] & (1 << (i % 8));
60 if bit == 0 {
61 p[none_pos + i] = Some(F::zero());
62 } else {
63 p[none_pos + i] = Some(F::one());
64 }
65 }
66 p
67 }
68}
69
70pub struct SumCheck<
71 F: PrimeField + Absorb,
72 C: CurveGroup,
73 UV: DenseUVPolynomial<F>,
74 MV: DenseMVPolynomial<F>,
75> {
76 _f: PhantomData<F>,
77 _c: PhantomData<C>,
78 _uv: PhantomData<UV>,
79 _mv: PhantomData<MV>,
80}
81
82impl<
83 F: PrimeField + Absorb,
84 C: CurveGroup,
85 UV: Polynomial<F> + DenseUVPolynomial<F>,
86 MV: Polynomial<F> + DenseMVPolynomial<F>,
87 > SumCheck<F, C, UV, MV>
88where
89 <C as CurveGroup>::BaseField: Absorb,
90{
91 fn partial_evaluate(g: &MV, point: &[Option<F>]) -> UV {
92 assert!(point.len() >= g.num_vars(), "Invalid evaluation domain");
93 // TODO: add check: there can only be 1 'None' value in point
94 if g.is_zero() {
95 return UV::from_coefficients_vec(vec![F::zero()]);
96 }
97
98 // note: this can be parallelized with cfg_into_iter
99 let mut univ_terms: Vec<(F, SparseTerm)> = vec![];
100 for (coef, term) in g.terms().iter() {
101 // partial_evaluate each term
102 let mut new_coef = F::one();
103 let mut new_term = Vec::new();
104 for (var, power) in term.iter() {
105 match point[*var] {
106 Some(v) => {
107 if v.is_zero() {
108 new_coef = F::zero();
109 new_term = vec![];
110 break;
111 } else {
112 new_coef *= v.pow([(*power) as u64]);
113 }
114 }
115 _ => {
116 new_term.push((*var, *power));
117 }
118 };
119 }
120 let new_term = SparseTerm::new(new_term);
121 let new_coef = new_coef * coef;
122 univ_terms.push((new_coef, new_term));
123 }
124 let mv_poly: SparsePolynomial<F, SparseTerm> =
125 DenseMVPolynomial::<F>::from_coefficients_vec(g.num_vars(), univ_terms.clone());
126
127 let mut univ_coeffs: Vec<F> = vec![F::zero(); mv_poly.degree() + 1];
128 for (coef, term) in univ_terms {
129 if term.is_empty() {
130 univ_coeffs[0] += coef;
131 continue;
132 }
133 for (_, power) in term.iter() {
134 univ_coeffs[*power] += coef;
135 }
136 }
137 UV::from_coefficients_vec(univ_coeffs)
138 }
139
140 pub fn prove(poseidon_config: &PoseidonConfig<F>, g: MV) -> (F, Vec<UV>, F)
141 where
142 <MV as Polynomial<F>>::Point: From<Vec<F>>,
143 {
144 // init transcript
145 let mut transcript = Transcript::<F, C>::new(poseidon_config);
146
147 let v = g.num_vars();
148
149 // compute T
150 let mut T = F::zero();
151 for i in 0..(2_u64.pow(v as u32) as usize) {
152 let p = Point::<F>::point_complete(vec![], v, i);
153
154 T += g.evaluate(&p.into());
155 }
156 transcript.add(&T);
157
158 let mut ss: Vec<UV> = Vec::new();
159 let mut r: Vec<F> = vec![];
160 for i in 0..v {
161 let r_i = transcript.get_challenge();
162 r.push(r_i);
163
164 let var_slots = v - 1 - i;
165 let n_points = 2_u64.pow(var_slots as u32) as usize;
166
167 let mut s_i = UV::zero();
168 for j in 0..n_points {
169 let point = Point::<F>::point(r[..i].to_vec(), true, v, j);
170 s_i = s_i + Self::partial_evaluate(&g, &point);
171 }
172 transcript.add_vec(s_i.coeffs());
173 ss.push(s_i);
174 }
175
176 let last_g_eval = g.evaluate(&r.into());
177 // ss: intermediate univariate polynomials
178 (T, ss, last_g_eval)
179 }
180
181 pub fn verify(poseidon_config: &PoseidonConfig<F>, proof: (F, Vec<UV>, F)) -> bool {
182 // init transcript
183 let mut transcript = Transcript::<F, C>::new(poseidon_config);
184 transcript.add(&proof.0);
185
186 let (c, ss, last_g_eval) = proof;
187
188 let mut r: Vec<F> = vec![];
189 for (i, s) in ss.iter().enumerate() {
190 // TODO check degree
191 if i == 0 {
192 if c != s.evaluate(&F::zero()) + s.evaluate(&F::one()) {
193 return false;
194 }
195 let r_i = transcript.get_challenge();
196 r.push(r_i);
197 transcript.add_vec(s.coeffs());
198 continue;
199 }
200
201 let r_i = transcript.get_challenge();
202 r.push(r_i);
203 if ss[i - 1].evaluate(&r[i - 1]) != s.evaluate(&F::zero()) + s.evaluate(&F::one()) {
204 return false;
205 }
206 transcript.add_vec(s.coeffs());
207 }
208 // last round
209 if ss[ss.len() - 1].evaluate(&r[r.len() - 1]) != last_g_eval {
210 return false;
211 }
212
213 true
214 }
215}
216
217#[cfg(test)]
218mod tests {
219 use super::*;
220 use crate::transcript::poseidon_test_config;
221 use ark_mnt4_298::{Fr, G1Projective}; // scalar field
222 use ark_poly::{
223 multivariate::{SparsePolynomial, SparseTerm, Term},
224 univariate::DensePolynomial,
225 DenseMVPolynomial, DenseUVPolynomial,
226 };
227 use ark_std::{rand::Rng, UniformRand};
228
229 #[test]
230 fn test_new_point() {
231 let f4 = Fr::from(4_u32);
232 let f1 = Fr::from(1);
233 let f0 = Fr::from(0);
234 type SC = SumCheck<Fr, G1Projective, DensePolynomial<Fr>, SparsePolynomial<Fr, SparseTerm>>;
235 type P = Point<Fr>;
236
237 let p = P::point(vec![Fr::from(4_u32)], true, 5, 0);
238 assert_eq!(vec![Some(f4), None, Some(f0), Some(f0), Some(f0),], p);
239
240 let p = P::point(vec![Fr::from(4_u32)], true, 5, 1);
241 assert_eq!(vec![Some(f4), None, Some(f1), Some(f0), Some(f0),], p);
242
243 let p = P::point(vec![Fr::from(4_u32)], true, 5, 2);
244 assert_eq!(vec![Some(f4), None, Some(f0), Some(f1), Some(f0),], p);
245
246 let p = P::point(vec![Fr::from(4_u32)], true, 5, 3);
247 assert_eq!(vec![Some(f4), None, Some(f1), Some(f1), Some(f0),], p);
248
249 let p = P::point(vec![Fr::from(4_u32)], true, 5, 4);
250 assert_eq!(vec![Some(f4), None, Some(f0), Some(f0), Some(f1),], p);
251
252 // without None
253 let p = P::point(vec![], false, 4, 0);
254 assert_eq!(vec![Some(f0), Some(f0), Some(f0), Some(f0),], p);
255
256 let p = P::point(vec![Fr::from(4_u32)], false, 5, 0);
257 assert_eq!(vec![Some(f4), Some(f0), Some(f0), Some(f0), Some(f0),], p);
258
259 let p = P::point(vec![Fr::from(4_u32)], false, 5, 1);
260 assert_eq!(vec![Some(f4), Some(f1), Some(f0), Some(f0), Some(f0),], p);
261
262 let p = P::point(vec![Fr::from(4_u32)], false, 5, 3);
263 assert_eq!(vec![Some(f4), Some(f1), Some(f1), Some(f0), Some(f0),], p);
264
265 let p = P::point(vec![Fr::from(4_u32)], false, 5, 4);
266 assert_eq!(vec![Some(f4), Some(f0), Some(f0), Some(f1), Some(f0),], p);
267
268 let p = P::point(vec![Fr::from(4_u32)], false, 5, 10);
269 assert_eq!(vec![Some(f4), Some(f0), Some(f1), Some(f0), Some(f1),], p);
270
271 let p = P::point(vec![Fr::from(4_u32)], false, 5, 15);
272 assert_eq!(vec![Some(f4), Some(f1), Some(f1), Some(f1), Some(f1),], p);
273
274 // let p = P::point(vec![Fr::from(4_u32)], false, 4, 16); // TODO expect error
275 }
276
277 #[test]
278 fn test_partial_evaluate() {
279 // g(X_0, X_1, X_2) = 2 X_0^3 + X_0 X_2 + X_1 X_2
280 let terms = vec![
281 (Fr::from(2u32), SparseTerm::new(vec![(0_usize, 3)])),
282 (
283 Fr::from(1u32),
284 SparseTerm::new(vec![(0_usize, 1), (2_usize, 1)]),
285 ),
286 (
287 Fr::from(1u32),
288 SparseTerm::new(vec![(1_usize, 1), (2_usize, 1)]),
289 ),
290 ];
291 let p = SparsePolynomial::from_coefficients_slice(3, &terms);
292
293 type SC = SumCheck<Fr, G1Projective, DensePolynomial<Fr>, SparsePolynomial<Fr, SparseTerm>>;
294
295 let e0 = SC::partial_evaluate(&p, &[Some(Fr::from(2_u32)), None, Some(Fr::from(0_u32))]);
296 assert_eq!(e0.coeffs(), vec![Fr::from(16_u32)]);
297 let e1 = SC::partial_evaluate(&p, &[Some(Fr::from(2_u32)), None, Some(Fr::from(1_u32))]);
298 assert_eq!(e1.coeffs(), vec![Fr::from(18_u32), Fr::from(1)]);
299
300 assert_eq!((e0 + e1).coeffs(), vec![Fr::from(34_u32), Fr::from(1)]);
301 }
302
303 #[test]
304 fn test_flow_hardcoded_values() {
305 // g(X_0, X_1, X_2) = 2 X_0^3 + X_0 X_2 + X_1 X_2
306 let terms = vec![
307 (Fr::from(2u32), SparseTerm::new(vec![(0_usize, 3)])),
308 (
309 Fr::from(1u32),
310 SparseTerm::new(vec![(0_usize, 1), (2_usize, 1)]),
311 ),
312 (
313 Fr::from(1u32),
314 SparseTerm::new(vec![(1_usize, 1), (2_usize, 1)]),
315 ),
316 ];
317 let p = SparsePolynomial::from_coefficients_slice(3, &terms);
318 // println!("p {:?}", p);
319
320 let poseidon_config = poseidon_test_config::<Fr>();
321 type SC = SumCheck<Fr, G1Projective, DensePolynomial<Fr>, SparsePolynomial<Fr, SparseTerm>>;
322
323 let proof = SC::prove(&poseidon_config, p);
324 assert_eq!(proof.0, Fr::from(12_u32));
325 // println!("proof {:?}", proof);
326
327 let v = SC::verify(&poseidon_config, proof);
328 assert!(v);
329 }
330
331 fn rand_poly<R: Rng>(l: usize, d: usize, rng: &mut R) -> SparsePolynomial<Fr, SparseTerm> {
332 // This method is from the arkworks/algebra/poly/multivariate test:
333 // https://github.com/arkworks-rs/algebra/blob/bc991d44c5e579025b7ed56df3d30267a7b9acac/poly/src/polynomial/multivariate/sparse.rs#L303
334 let mut random_terms = Vec::new();
335 let num_terms = rng.gen_range(1..1000);
336 // For each term, randomly select up to `l` variables with degree
337 // in [1,d] and random coefficient
338 random_terms.push((Fr::rand(rng), SparseTerm::new(vec![])));
339 for _ in 1..num_terms {
340 let term = (0..l)
341 .map(|i| {
342 if rng.gen_bool(0.5) {
343 Some((i, rng.gen_range(1..(d + 1))))
344 } else {
345 None
346 }
347 })
348 .flatten()
349 .collect();
350 let coeff = Fr::rand(rng);
351 random_terms.push((coeff, SparseTerm::new(term)));
352 }
353 SparsePolynomial::from_coefficients_slice(l, &random_terms)
354 }
355
356 #[test]
357 fn test_flow_rng() {
358 let mut rng = ark_std::test_rng();
359 // let p = SparsePolynomial::<Fr, SparseTerm>::rand(3, 3, &mut rng);
360 let p = rand_poly(3, 3, &mut rng);
361 // println!("p {:?}", p);
362
363 let poseidon_config = poseidon_test_config::<Fr>();
364 type SC = SumCheck<Fr, G1Projective, DensePolynomial<Fr>, SparsePolynomial<Fr, SparseTerm>>;
365
366 let proof = SC::prove(&poseidon_config, p);
367 // println!("proof.s len {:?}", proof.1.len());
368
369 let v = SC::verify(&poseidon_config, proof);
370 assert!(v);
371 }
372}