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