sonobe/src/folding/protogalaxy/folding.rs
src/folding/protogalaxy/folding.rsRaw
1/// Implements the scheme described in [ProtoGalaxy](https://eprint.iacr.org/2023/1106.pdf)
2use ark_crypto_primitives::sponge::Absorb;
3use ark_ec::{CurveGroup, Group};
4use ark_ff::PrimeField;
5use ark_poly::{
6 univariate::{DensePolynomial, SparsePolynomial},
7 DenseUVPolynomial, EvaluationDomain, Evaluations, GeneralEvaluationDomain, Polynomial,
8};
9use ark_std::log2;
10use ark_std::{cfg_into_iter, Zero};
11use rayon::iter::{IntoParallelIterator, ParallelIterator};
12use std::marker::PhantomData;
13use std::ops::Add;
14
15use super::traits::ProtoGalaxyTranscript;
16use super::utils::{all_powers, betas_star, exponential_powers};
17use super::ProtoGalaxyError;
18use super::{CommittedInstance, Witness};
19
20use crate::ccs::r1cs::R1CS;
21use crate::transcript::Transcript;
22use crate::utils::{bit::bit_decompose, vec::*};
23use crate::Error;
24
25#[derive(Clone, Debug)]
26/// Implements the protocol described in section 4 of
27/// [ProtoGalaxy](https://eprint.iacr.org/2023/1106.pdf)
28pub struct Folding<C: CurveGroup> {
29 _phantom: PhantomData<C>,
30}
31impl<C: CurveGroup> Folding<C>
32where
33 <C as Group>::ScalarField: Absorb,
34 <C as CurveGroup>::BaseField: Absorb,
35{
36 #![allow(clippy::type_complexity)]
37 /// implements the non-interactive Prover from the folding scheme described in section 4
38 pub fn prove(
39 transcript: &mut (impl Transcript<C> + ProtoGalaxyTranscript<C>),
40 r1cs: &R1CS<C::ScalarField>,
41 // running instance
42 instance: &CommittedInstance<C>,
43 w: &Witness<C::ScalarField>,
44 // incomming instances
45 vec_instances: &[CommittedInstance<C>],
46 vec_w: &[Witness<C::ScalarField>],
47 ) -> Result<
48 (
49 CommittedInstance<C>,
50 Witness<C::ScalarField>,
51 Vec<C::ScalarField>, // F_X coeffs
52 Vec<C::ScalarField>, // K_X coeffs
53 ),
54 Error,
55 > {
56 if vec_instances.len() != vec_w.len() {
57 return Err(Error::NotSameLength(
58 "vec_instances.len()".to_string(),
59 vec_instances.len(),
60 "vec_w.len()".to_string(),
61 vec_w.len(),
62 ));
63 }
64 let d = 2; // for the moment hardcoded to 2 since it only supports R1CS
65 let k = vec_instances.len();
66 let t = instance.betas.len();
67 let n = r1cs.A.n_cols;
68 if w.w.len() != n {
69 return Err(Error::NotSameLength(
70 "w.w.len()".to_string(),
71 w.w.len(),
72 "n".to_string(),
73 n,
74 ));
75 }
76 if log2(n) as usize != t {
77 return Err(Error::NotEqual);
78 }
79 if !(k + 1).is_power_of_two() {
80 return Err(Error::ProtoGalaxy(ProtoGalaxyError::WrongNumInstances(k)));
81 }
82
83 // absorb the committed instances
84 transcript.absorb_committed_instance(instance)?;
85 for ci in vec_instances.iter() {
86 transcript.absorb_committed_instance(ci)?;
87 }
88
89 let delta = transcript.get_challenge();
90 let deltas = exponential_powers(delta, t);
91
92 let f_w = eval_f(r1cs, &w.w)?;
93
94 // F(X)
95 let mut F_X: SparsePolynomial<C::ScalarField> = SparsePolynomial::zero();
96 for (i, f_w_i) in f_w.iter().enumerate() {
97 let lhs = pow_i_over_x::<C::ScalarField>(i, &instance.betas, &deltas)?;
98 let curr = &lhs * *f_w_i;
99 F_X = F_X.add(curr);
100 }
101
102 let F_X_dense = DensePolynomial::from(F_X.clone());
103 transcript.absorb_vec(&F_X_dense.coeffs);
104
105 let alpha = transcript.get_challenge();
106
107 // eval F(alpha)
108 let F_alpha = F_X.evaluate(&alpha);
109
110 // betas*
111 let betas_star = betas_star(&instance.betas, &deltas, alpha);
112
113 // sanity check: check that the new randomized instance (the original instance but with
114 // 'refreshed' randomness) satisfies the relation.
115 #[cfg(test)]
116 tests::check_instance(
117 r1cs,
118 &CommittedInstance {
119 phi: instance.phi,
120 betas: betas_star.clone(),
121 e: F_alpha,
122 },
123 w,
124 )?;
125
126 let ws: Vec<Vec<C::ScalarField>> = std::iter::once(w.w.clone())
127 .chain(
128 vec_w
129 .iter()
130 .map(|wj| {
131 if wj.w.len() != n {
132 return Err(Error::NotSameLength(
133 "wj.w.len()".to_string(),
134 wj.w.len(),
135 "n".to_string(),
136 n,
137 ));
138 }
139 Ok(wj.w.clone())
140 })
141 .collect::<Result<Vec<Vec<C::ScalarField>>, Error>>()?,
142 )
143 .collect::<Vec<Vec<C::ScalarField>>>();
144
145 let H =
146 GeneralEvaluationDomain::<C::ScalarField>::new(k + 1).ok_or(Error::NewDomainFail)?;
147 let G_domain = GeneralEvaluationDomain::<C::ScalarField>::new((d * k) + 1)
148 .ok_or(Error::NewDomainFail)?;
149 let L_X: Vec<DensePolynomial<C::ScalarField>> = lagrange_polys(H);
150
151 // K(X) computation in a naive way, next iterations will compute K(X) as described in Claim
152 // 4.5 of the paper.
153 let mut G_evals: Vec<C::ScalarField> = vec![C::ScalarField::zero(); G_domain.size()];
154 for (hi, h) in G_domain.elements().enumerate() {
155 // each iteration evaluates G(h)
156 // inner = L_0(x) * w + \sum_k L_i(x) * w_j
157 let mut inner: Vec<C::ScalarField> = vec![C::ScalarField::zero(); ws[0].len()];
158 for (i, w) in ws.iter().enumerate() {
159 // Li_w_h = (Li(X)*wj)(h) = Li(h) * wj
160 let mut Liw_h: Vec<C::ScalarField> = vec![C::ScalarField::zero(); w.len()];
161 for (j, wj) in w.iter().enumerate() {
162 Liw_h[j] = (&L_X[i] * *wj).evaluate(&h);
163 }
164
165 for j in 0..inner.len() {
166 inner[j] += Liw_h[j];
167 }
168 }
169 let f_ev = eval_f(r1cs, &inner)?;
170
171 let mut Gsum = C::ScalarField::zero();
172 for (i, f_ev_i) in f_ev.iter().enumerate() {
173 let pow_i_betas = pow_i(i, &betas_star);
174 let curr = pow_i_betas * f_ev_i;
175 Gsum += curr;
176 }
177 G_evals[hi] = Gsum;
178 }
179 let G_X: DensePolynomial<C::ScalarField> =
180 Evaluations::<C::ScalarField>::from_vec_and_domain(G_evals, G_domain).interpolate();
181 let Z_X: DensePolynomial<C::ScalarField> = H.vanishing_polynomial().into();
182 // K(X) = (G(X) - F(alpha)*L_0(X)) / Z(X)
183 // Notice that L0(X)*F(a) will be 0 in the native case (the instance of the first folding
184 // iteration case).
185 let L0_e = &L_X[0] * F_alpha;
186 let G_L0e = &G_X - &L0_e;
187 // Pending optimization: move division by Z_X to the prev loop
188 let (K_X, remainder) = G_L0e.divide_by_vanishing_poly(H).ok_or(Error::ProtoGalaxy(
189 ProtoGalaxyError::CouldNotDivideByVanishing,
190 ))?;
191 if !remainder.is_zero() {
192 return Err(Error::ProtoGalaxy(ProtoGalaxyError::RemainderNotZero));
193 }
194
195 transcript.absorb_vec(&K_X.coeffs);
196
197 let gamma = transcript.get_challenge();
198
199 let e_star =
200 F_alpha * L_X[0].evaluate(&gamma) + Z_X.evaluate(&gamma) * K_X.evaluate(&gamma);
201
202 let mut phi_star: C = instance.phi * L_X[0].evaluate(&gamma);
203 for i in 0..k {
204 phi_star += vec_instances[i].phi * L_X[i + 1].evaluate(&gamma);
205 }
206 let mut w_star: Vec<C::ScalarField> = vec_scalar_mul(&w.w, &L_X[0].evaluate(&gamma));
207 let mut r_w_star: C::ScalarField = w.r_w * L_X[0].evaluate(&gamma);
208 for i in 0..k {
209 let L_X_at_i1 = L_X[i + 1].evaluate(&gamma);
210 w_star = vec_add(&w_star, &vec_scalar_mul(&vec_w[i].w, &L_X_at_i1))?;
211 r_w_star += vec_w[i].r_w * L_X_at_i1;
212 }
213
214 Ok((
215 CommittedInstance {
216 betas: betas_star,
217 phi: phi_star,
218 e: e_star,
219 },
220 Witness {
221 w: w_star,
222 r_w: r_w_star,
223 },
224 F_X_dense.coeffs,
225 K_X.coeffs,
226 ))
227 }
228
229 /// implements the non-interactive Verifier from the folding scheme described in section 4
230 pub fn verify(
231 transcript: &mut (impl Transcript<C> + ProtoGalaxyTranscript<C>),
232 r1cs: &R1CS<C::ScalarField>,
233 // running instance
234 instance: &CommittedInstance<C>,
235 // incomming instances
236 vec_instances: &[CommittedInstance<C>],
237 // polys from P
238 F_coeffs: Vec<C::ScalarField>,
239 K_coeffs: Vec<C::ScalarField>,
240 ) -> Result<CommittedInstance<C>, Error> {
241 let t = instance.betas.len();
242 let n = r1cs.A.n_cols;
243
244 // absorb the committed instances
245 transcript.absorb_committed_instance(instance)?;
246 for ci in vec_instances.iter() {
247 transcript.absorb_committed_instance(ci)?;
248 }
249
250 let delta = transcript.get_challenge();
251 let deltas = exponential_powers(delta, t);
252
253 transcript.absorb_vec(&F_coeffs);
254
255 let alpha = transcript.get_challenge();
256 let alphas = all_powers(alpha, n);
257
258 // F(alpha) = e + \sum_t F_i * alpha^i
259 let mut F_alpha = instance.e;
260 for (i, F_i) in F_coeffs.iter().skip(1).enumerate() {
261 F_alpha += *F_i * alphas[i + 1];
262 }
263
264 let betas_star = betas_star(&instance.betas, &deltas, alpha);
265
266 let k = vec_instances.len();
267 let H =
268 GeneralEvaluationDomain::<C::ScalarField>::new(k + 1).ok_or(Error::NewDomainFail)?;
269 let L_X: Vec<DensePolynomial<C::ScalarField>> = lagrange_polys(H);
270 let Z_X: DensePolynomial<C::ScalarField> = H.vanishing_polynomial().into();
271 let K_X: DensePolynomial<C::ScalarField> =
272 DensePolynomial::<C::ScalarField>::from_coefficients_vec(K_coeffs);
273
274 transcript.absorb_vec(&K_X.coeffs);
275
276 let gamma = transcript.get_challenge();
277
278 let e_star =
279 F_alpha * L_X[0].evaluate(&gamma) + Z_X.evaluate(&gamma) * K_X.evaluate(&gamma);
280
281 let mut phi_star: C = instance.phi * L_X[0].evaluate(&gamma);
282 for i in 0..k {
283 phi_star += vec_instances[i].phi * L_X[i + 1].evaluate(&gamma);
284 }
285
286 // return the folded instance
287 Ok(CommittedInstance {
288 betas: betas_star,
289 phi: phi_star,
290 e: e_star,
291 })
292 }
293}
294
295// naive impl of pow_i for betas, assuming that betas=(b, b^2, b^4, ..., b^{2^{t-1}})
296fn pow_i<F: PrimeField>(i: usize, betas: &Vec<F>) -> F {
297 // WIP check if makes more sense to do it with ifs instead of arithmetic
298
299 let n = 2_u64.pow(betas.len() as u32);
300 let b = bit_decompose(i as u64, n as usize);
301
302 let mut r: F = F::one();
303 for (j, beta_j) in betas.iter().enumerate() {
304 let mut b_j = F::zero();
305 if b[j] {
306 b_j = F::one();
307 }
308 r *= (F::one() - b_j) + b_j * beta_j;
309 }
310 r
311}
312
313// Pending optimization: instead of this approach use Claim 4.4 from the paper.
314fn pow_i_over_x<F: PrimeField>(
315 i: usize,
316 betas: &Vec<F>,
317 deltas: &Vec<F>,
318) -> Result<SparsePolynomial<F>, Error> {
319 if betas.len() != deltas.len() {
320 return Err(Error::NotSameLength(
321 "betas.len()".to_string(),
322 betas.len(),
323 "deltas.len()".to_string(),
324 deltas.len(),
325 ));
326 }
327
328 let n = 2_u64.pow(betas.len() as u32);
329 let b = bit_decompose(i as u64, n as usize);
330
331 let mut r: SparsePolynomial<F> =
332 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, F::one())]); // start with r(x) = 1
333 for (j, beta_j) in betas.iter().enumerate() {
334 if b[j] {
335 let curr: SparsePolynomial<F> =
336 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, *beta_j), (1, deltas[j])]);
337 r = r.mul(&curr);
338 }
339 }
340 Ok(r)
341}
342
343// lagrange_polys method from caulk: https://github.com/caulk-crypto/caulk/tree/8210b51fb8a9eef4335505d1695c44ddc7bf8170/src/multi/setup.rs#L300
344fn lagrange_polys<F: PrimeField>(domain_n: GeneralEvaluationDomain<F>) -> Vec<DensePolynomial<F>> {
345 let mut lagrange_polynomials: Vec<DensePolynomial<F>> = Vec::new();
346 for i in 0..domain_n.size() {
347 let evals: Vec<F> = cfg_into_iter!(0..domain_n.size())
348 .map(|k| if k == i { F::one() } else { F::zero() })
349 .collect();
350 lagrange_polynomials.push(Evaluations::from_vec_and_domain(evals, domain_n).interpolate());
351 }
352 lagrange_polynomials
353}
354
355// f(w) in R1CS context. For the moment we use R1CS, in the future we will abstract this with a
356// trait
357fn eval_f<F: PrimeField>(r1cs: &R1CS<F>, w: &[F]) -> Result<Vec<F>, Error> {
358 let Az = mat_vec_mul_sparse(&r1cs.A, w)?;
359 let Bz = mat_vec_mul_sparse(&r1cs.B, w)?;
360 let Cz = mat_vec_mul_sparse(&r1cs.C, w)?;
361 let AzBz = hadamard(&Az, &Bz)?;
362 vec_sub(&AzBz, &Cz)
363}
364
365#[cfg(test)]
366mod tests {
367 use super::*;
368 use ark_pallas::{Fr, Projective};
369 use ark_std::UniformRand;
370
371 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
372 use crate::commitment::{pedersen::Pedersen, CommitmentProver};
373 use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
374
375 pub(crate) fn check_instance<C: CurveGroup>(
376 r1cs: &R1CS<C::ScalarField>,
377 instance: &CommittedInstance<C>,
378 w: &Witness<C::ScalarField>,
379 ) -> Result<(), Error> {
380 if instance.betas.len() != log2(w.w.len()) as usize {
381 return Err(Error::NotSameLength(
382 "instance.betas.len()".to_string(),
383 instance.betas.len(),
384 "log2(w.w.len())".to_string(),
385 log2(w.w.len()) as usize,
386 ));
387 }
388
389 let f_w = eval_f(r1cs, &w.w)?; // f(w)
390
391 let mut r = C::ScalarField::zero();
392 for (i, f_w_i) in f_w.iter().enumerate() {
393 r += pow_i(i, &instance.betas) * f_w_i;
394 }
395 if instance.e == r {
396 return Ok(());
397 }
398 Err(Error::NotSatisfied)
399 }
400
401 #[test]
402 fn test_pow_i() {
403 let mut rng = ark_std::test_rng();
404 let t = 4;
405 let n = 16;
406 let beta = Fr::rand(&mut rng);
407 let betas = exponential_powers(beta, t);
408 let not_betas = all_powers(beta, n);
409
410 #[allow(clippy::needless_range_loop)]
411 for i in 0..n {
412 assert_eq!(pow_i(i, &betas), not_betas[i]);
413 }
414 }
415
416 #[test]
417 fn test_pow_i_over_x() {
418 let mut rng = ark_std::test_rng();
419 let t = 3;
420 let n = 8;
421 let beta = Fr::rand(&mut rng);
422 let delta = Fr::rand(&mut rng);
423 let betas = exponential_powers(beta, t);
424 let deltas = exponential_powers(delta, t);
425
426 // compute b + X*d, with X=rand
427 let x = Fr::rand(&mut rng);
428 let bxd = vec_add(&betas, &vec_scalar_mul(&deltas, &x)).unwrap();
429
430 // assert that computing pow_over_x of betas,deltas, is equivalent to first computing the
431 // vector [betas+X*deltas] and then computing pow_i over it
432 for i in 0..n {
433 let pow_i1 = pow_i_over_x(i, &betas, &deltas).unwrap();
434 let pow_i2 = pow_i(i, &bxd);
435 assert_eq!(pow_i1.evaluate(&x), pow_i2);
436 }
437 }
438
439 #[test]
440 fn test_eval_f() {
441 let r1cs = get_test_r1cs::<Fr>();
442 let mut z = get_test_z::<Fr>(3);
443
444 let f_w = eval_f(&r1cs, &z).unwrap();
445 assert!(is_zero_vec(&f_w));
446
447 z[1] = Fr::from(111);
448 let f_w = eval_f(&r1cs, &z).unwrap();
449 assert!(!is_zero_vec(&f_w));
450 }
451
452 // k represents the number of instances to be fold, appart from the running instance
453 #[allow(clippy::type_complexity)]
454 fn prepare_inputs(
455 k: usize,
456 ) -> (
457 Witness<Fr>,
458 CommittedInstance<Projective>,
459 Vec<Witness<Fr>>,
460 Vec<CommittedInstance<Projective>>,
461 ) {
462 let mut rng = ark_std::test_rng();
463 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
464
465 let z = get_test_z::<Fr>(3);
466 let mut zs: Vec<Vec<Fr>> = Vec::new();
467 for i in 0..k {
468 let z_i = get_test_z::<Fr>(i + 4);
469 zs.push(z_i);
470 }
471
472 let n = z.len();
473 let t = log2(n) as usize;
474
475 let beta = Fr::rand(&mut rng);
476 let betas = exponential_powers(beta, t);
477
478 let witness = Witness::<Fr> {
479 w: z.clone(),
480 r_w: Fr::rand(&mut rng),
481 };
482 let phi =
483 Pedersen::<Projective>::commit(&pedersen_params, &witness.w, &witness.r_w).unwrap();
484 let instance = CommittedInstance::<Projective> {
485 phi,
486 betas: betas.clone(),
487 e: Fr::zero(),
488 };
489 // same for the other instances
490 let mut witnesses: Vec<Witness<Fr>> = Vec::new();
491 let mut instances: Vec<CommittedInstance<Projective>> = Vec::new();
492 #[allow(clippy::needless_range_loop)]
493 for i in 0..k {
494 let witness_i = Witness::<Fr> {
495 w: zs[i].clone(),
496 r_w: Fr::rand(&mut rng),
497 };
498 let phi_i =
499 Pedersen::<Projective>::commit(&pedersen_params, &witness_i.w, &witness_i.r_w)
500 .unwrap();
501 let instance_i = CommittedInstance::<Projective> {
502 phi: phi_i,
503 betas: betas.clone(),
504 e: Fr::zero(),
505 };
506 witnesses.push(witness_i);
507 instances.push(instance_i);
508 }
509
510 (witness, instance, witnesses, instances)
511 }
512
513 #[test]
514 fn test_fold_native_case() {
515 let k = 7;
516 let (witness, instance, witnesses, instances) = prepare_inputs(k);
517 let r1cs = get_test_r1cs::<Fr>();
518
519 // init Prover & Verifier's transcript
520 let poseidon_config = poseidon_test_config::<Fr>();
521 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
522 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
523
524 let (folded_instance, folded_witness, F_coeffs, K_coeffs) = Folding::<Projective>::prove(
525 &mut transcript_p,
526 &r1cs,
527 &instance,
528 &witness,
529 &instances,
530 &witnesses,
531 )
532 .unwrap();
533
534 // veriier
535 let folded_instance_v = Folding::<Projective>::verify(
536 &mut transcript_v,
537 &r1cs,
538 &instance,
539 &instances,
540 F_coeffs,
541 K_coeffs,
542 )
543 .unwrap();
544
545 // check that prover & verifier folded instances are the same values
546 assert_eq!(folded_instance.phi, folded_instance_v.phi);
547 assert_eq!(folded_instance.betas, folded_instance_v.betas);
548 assert_eq!(folded_instance.e, folded_instance_v.e);
549 assert!(!folded_instance.e.is_zero());
550
551 // check that the folded instance satisfies the relation
552 check_instance(&r1cs, &folded_instance, &folded_witness).unwrap();
553 }
554
555 #[test]
556 fn test_fold_various_iterations() {
557 let r1cs = get_test_r1cs::<Fr>();
558
559 // init Prover & Verifier's transcript
560 let poseidon_config = poseidon_test_config::<Fr>();
561 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
562 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
563
564 let (mut running_witness, mut running_instance, _, _) = prepare_inputs(0);
565
566 // fold k instances on each of num_iters iterations
567 let k = 7;
568 let num_iters = 10;
569 for _ in 0..num_iters {
570 // generate the instances to be fold
571 let (_, _, witnesses, instances) = prepare_inputs(k);
572
573 let (folded_instance, folded_witness, F_coeffs, K_coeffs) =
574 Folding::<Projective>::prove(
575 &mut transcript_p,
576 &r1cs,
577 &running_instance,
578 &running_witness,
579 &instances,
580 &witnesses,
581 )
582 .unwrap();
583
584 // veriier
585 let folded_instance_v = Folding::<Projective>::verify(
586 &mut transcript_v,
587 &r1cs,
588 &running_instance,
589 &instances,
590 F_coeffs,
591 K_coeffs,
592 )
593 .unwrap();
594
595 // check that prover & verifier folded instances are the same values
596 assert_eq!(folded_instance.phi, folded_instance_v.phi);
597 assert_eq!(folded_instance.betas, folded_instance_v.betas);
598 assert_eq!(folded_instance.e, folded_instance_v.e);
599 assert!(!folded_instance.e.is_zero());
600
601 // check that the folded instance satisfies the relation
602 check_instance(&r1cs, &folded_instance, &folded_witness).unwrap();
603
604 running_witness = folded_witness;
605 running_instance = folded_instance;
606 }
607 }
608}