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