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 #![allow(clippy::type_complexity)]
41 pub fn prove(
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: &[CommittedInstance<C>],
49 vec_w: &[Witness<C>],
50 ) -> (
51 CommittedInstance<C>,
52 Witness<C>,
53 Vec<C::ScalarField>,
54 Vec<C::ScalarField>,
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, f_w_i) in f_w.iter().enumerate() {
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, f_ev_i) in f_ev.iter().enumerate() {
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;
155 }
156 let G_X: DensePolynomial<C::ScalarField> =
157 Evaluations::<C::ScalarField>::from_vec_and_domain(G_evals.clone(), EH).interpolate();
158 let Z_X: DensePolynomial<C::ScalarField> = H.vanishing_polynomial().into();
159 // K(X) = (G(X)- F(alpha)*L_0(X)) / Z(X)
160 let L0_e = &L_X[0] * F_alpha; // L0(X)*F(a) will be 0 in the native case
161 let G_L0e = &G_X - &L0_e;
162 // TODO move division by Z_X to the prev loop
163 let (K_X, remainder) = G_L0e.divide_by_vanishing_poly(H).unwrap();
164 assert!(remainder.is_zero()); // sanity check
165
166 transcript.add_vec(&K_X.coeffs);
167
168 let gamma = transcript.get_challenge();
169
170 let e_star =
171 F_alpha * L_X[0].evaluate(&gamma) + Z_X.evaluate(&gamma) * K_X.evaluate(&gamma);
172
173 let mut phi_star: C = instance.phi.0 * L_X[0].evaluate(&gamma);
174 for i in 0..k {
175 phi_star += vec_instances[i].phi.0 * L_X[i + 1].evaluate(&gamma);
176 }
177 let mut w_star: Vec<C::ScalarField> = vec_scalar_mul(&w.w, &L_X[0].evaluate(&gamma));
178 for i in 0..k {
179 w_star = vec_add(
180 &w_star,
181 &vec_scalar_mul(&vec_w[i].w, &L_X[i + 1].evaluate(&gamma)),
182 );
183 }
184 let mut r_w_star: C::ScalarField = w.r_w * L_X[0].evaluate(&gamma);
185 for i in 0..k {
186 r_w_star += vec_w[i].r_w * L_X[i + 1].evaluate(&gamma);
187 }
188
189 (
190 CommittedInstance {
191 betas: betas_star,
192 phi: Commitment(phi_star),
193 e: e_star,
194 },
195 Witness {
196 w: w_star,
197 r_w: r_w_star,
198 },
199 F_X_dense.coeffs,
200 K_X.coeffs,
201 )
202 }
203
204 pub fn verify(
205 transcript: &mut Transcript<C::ScalarField, C>,
206 r1cs: &R1CS<C::ScalarField>,
207 // running instance
208 instance: &CommittedInstance<C>,
209 // incomming instances
210 vec_instances: &[CommittedInstance<C>],
211 // polys from P
212 F_coeffs: Vec<C::ScalarField>,
213 K_coeffs: Vec<C::ScalarField>,
214 ) -> CommittedInstance<C> {
215 let t = instance.betas.len();
216 let n = r1cs.A[0].len();
217
218 let delta = transcript.get_challenge();
219 let deltas = powers_of_beta(delta, t);
220
221 transcript.add_vec(&F_coeffs);
222
223 let alpha = transcript.get_challenge();
224 let alphas = all_powers(alpha, n);
225
226 // F(alpha) = e + \sum_t F_i * alpha^i
227 let mut F_alpha = instance.e;
228 for (i, F_i) in F_coeffs.iter().skip(1).enumerate() {
229 F_alpha += *F_i * alphas[i + 1];
230 }
231
232 let betas_star: Vec<C::ScalarField> = instance
233 .betas
234 .iter()
235 .zip(
236 deltas
237 .iter()
238 .map(|delta_i| alpha * delta_i)
239 .collect::<Vec<C::ScalarField>>(),
240 )
241 .map(|(beta_i, delta_i_alpha)| *beta_i + delta_i_alpha)
242 .collect();
243
244 let k = vec_instances.len();
245 let H = GeneralEvaluationDomain::<C::ScalarField>::new(k + 1).unwrap();
246 let L_X: Vec<DensePolynomial<C::ScalarField>> = lagrange_polys(H);
247 let Z_X: DensePolynomial<C::ScalarField> = H.vanishing_polynomial().into();
248 let K_X: DensePolynomial<C::ScalarField> =
249 DensePolynomial::<C::ScalarField>::from_coefficients_vec(K_coeffs);
250
251 transcript.add_vec(&K_X.coeffs);
252
253 let gamma = transcript.get_challenge();
254
255 let e_star =
256 F_alpha * L_X[0].evaluate(&gamma) + Z_X.evaluate(&gamma) * K_X.evaluate(&gamma);
257
258 let mut phi_star: C = instance.phi.0 * L_X[0].evaluate(&gamma);
259 for i in 0..k {
260 phi_star += vec_instances[i].phi.0 * L_X[i + 1].evaluate(&gamma);
261 }
262
263 // return the folded instance
264 CommittedInstance {
265 betas: betas_star,
266 phi: Commitment(phi_star),
267 e: e_star,
268 }
269 }
270}
271
272// naive impl of pow_i for betas, assuming that betas=(b, b^2, b^4, ..., b^{2^{t-1}})
273fn pow_i<F: PrimeField>(i: usize, betas: &Vec<F>) -> F {
274 // WIP check if makes more sense to do it with ifs instead of arithmetic
275
276 let n = 2_u64.pow(betas.len() as u32);
277 let b = bit_decompose(i as u64, n as usize);
278
279 let mut r: F = F::one();
280 for (j, beta_j) in betas.iter().enumerate() {
281 let mut b_j = F::zero();
282 if b[j] {
283 b_j = F::one();
284 }
285 r *= (F::one() - b_j) + b_j * beta_j;
286 }
287 r
288}
289
290fn pow_i_over_x<F: PrimeField>(i: usize, betas: &Vec<F>, deltas: &Vec<F>) -> SparsePolynomial<F> {
291 assert_eq!(betas.len(), deltas.len());
292
293 let n = 2_u64.pow(betas.len() as u32);
294 let b = bit_decompose(i as u64, n as usize);
295
296 let mut r: SparsePolynomial<F> =
297 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, F::one())]); // start with r(x) = 1
298 for (j, beta_j) in betas.iter().enumerate() {
299 if b[j] {
300 let curr: SparsePolynomial<F> =
301 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, *beta_j), (1, deltas[j])]);
302 r = r.mul(&curr);
303 }
304 }
305 r
306}
307
308// lagrange_polys method from caulk: https://github.com/caulk-crypto/caulk/tree/8210b51fb8a9eef4335505d1695c44ddc7bf8170/src/multi/setup.rs#L300
309fn lagrange_polys<F: PrimeField>(domain_n: GeneralEvaluationDomain<F>) -> Vec<DensePolynomial<F>> {
310 let mut lagrange_polynomials: Vec<DensePolynomial<F>> = Vec::new();
311 for i in 0..domain_n.size() {
312 let evals: Vec<F> = cfg_into_iter!(0..domain_n.size())
313 .map(|k| if k == i { F::one() } else { F::zero() })
314 .collect();
315 lagrange_polynomials.push(Evaluations::from_vec_and_domain(evals, domain_n).interpolate());
316 }
317 lagrange_polynomials
318}
319
320#[derive(Clone, Debug)]
321pub struct R1CS<F: PrimeField> {
322 pub A: Vec<Vec<F>>,
323 pub B: Vec<Vec<F>>,
324 pub C: Vec<Vec<F>>,
325}
326
327// f(w) in R1CS context
328fn eval_f<F: PrimeField>(r1cs: &R1CS<F>, w: &[F]) -> Vec<F> {
329 let AzBz = hadamard(&mat_vec_mul(&r1cs.A, w), &mat_vec_mul(&r1cs.B, w));
330 let Cz = mat_vec_mul(&r1cs.C, w);
331 vec_sub(&AzBz, &Cz)
332}
333
334fn check_instance<C: CurveGroup>(
335 r1cs: &R1CS<C::ScalarField>,
336 instance: &CommittedInstance<C>,
337 w: &Witness<C>,
338) -> bool {
339 assert_eq!(instance.betas.len(), log2(w.w.len()) as usize);
340
341 let f_w = eval_f(r1cs, &w.w); // f(w)
342
343 let mut r = C::ScalarField::zero();
344 for (i, f_w_i) in f_w.iter().enumerate() {
345 r += pow_i(i, &instance.betas) * f_w_i;
346 }
347 if instance.e == r {
348 return true;
349 }
350 false
351}
352
353#[cfg(test)]
354mod tests {
355 use super::*;
356 use crate::pedersen::Pedersen;
357 use crate::transcript::poseidon_test_config;
358 use ark_bls12_381::{Fr, G1Projective};
359 use ark_std::UniformRand;
360
361 pub fn to_F_matrix<F: PrimeField>(M: Vec<Vec<usize>>) -> Vec<Vec<F>> {
362 let mut R: Vec<Vec<F>> = vec![Vec::new(); M.len()];
363 for i in 0..M.len() {
364 R[i] = vec![F::zero(); M[i].len()];
365 for j in 0..M[i].len() {
366 R[i][j] = F::from(M[i][j] as u64);
367 }
368 }
369 R
370 }
371 pub fn to_F_vec<F: PrimeField>(z: Vec<usize>) -> Vec<F> {
372 let mut r: Vec<F> = vec![F::zero(); z.len()];
373 for i in 0..z.len() {
374 r[i] = F::from(z[i] as u64);
375 }
376 r
377 }
378
379 pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
380 // R1CS for: x^3 + x + 5 = y (example from article
381 // https://www.vitalik.ca/general/2016/12/10/qap.html )
382 let A = to_F_matrix::<F>(vec![
383 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
384 vec![0, 0, 0, 1, 0, 0, /**/ 0, 0],
385 vec![0, 1, 0, 0, 1, 0, /**/ 0, 0],
386 vec![5, 0, 0, 0, 0, 1, /**/ 0, 0],
387 //
388 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
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 ]);
393 let B = to_F_matrix::<F>(vec![
394 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
395 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
396 vec![1, 0, 0, 0, 0, 0, /**/ 0, 0],
397 vec![1, 0, 0, 0, 0, 0, /**/ 0, 0],
398 //
399 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
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 ]);
404 let C = to_F_matrix::<F>(vec![
405 vec![0, 0, 0, 1, 0, 0, /**/ 0, 0],
406 vec![0, 0, 0, 0, 1, 0, /**/ 0, 0],
407 vec![0, 0, 0, 0, 0, 1, /**/ 0, 0],
408 vec![0, 0, 1, 0, 0, 0, /**/ 0, 0],
409 //
410 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
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 ]);
415
416 let r1cs = R1CS::<F> { A, B, C };
417 r1cs
418 }
419
420 pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
421 // z = (1, io, w)
422 to_F_vec(vec![
423 1,
424 input,
425 input * input * input + input + 5, // x^3 + x + 5
426 input * input, // x^2
427 input * input * input, // x^2 * x
428 input * input * input + input, // x^3 + x
429 0, // pad to pow of 2
430 0,
431 ])
432 }
433
434 #[test]
435 fn test_pow_i() {
436 let mut rng = ark_std::test_rng();
437 let t = 4;
438 let n = 16;
439 let beta = Fr::rand(&mut rng);
440 let betas = powers_of_beta(beta, t);
441 let not_betas = all_powers(beta, n);
442
443 for i in 0..n {
444 assert_eq!(pow_i(i, &betas), not_betas[i]);
445 }
446 }
447
448 #[test]
449 fn test_pow_i_over_x() {
450 let mut rng = ark_std::test_rng();
451 let t = 3;
452 let n = 8;
453 let beta = Fr::rand(&mut rng);
454 let delta = Fr::rand(&mut rng);
455 let betas = powers_of_beta(beta, t);
456 let deltas = powers_of_beta(delta, t);
457
458 // compute b + X*d, with X=rand
459 let x = Fr::rand(&mut rng);
460 let bxd = vec_add(&betas, &vec_scalar_mul(&deltas, &x));
461
462 // assert that computing pow_over_x of betas,deltas, is equivalent to first computing the
463 // vector [betas+X*deltas] and then computing pow_i over it
464 for i in 0..n {
465 let pow_i1 = pow_i_over_x(i, &betas, &deltas);
466 let pow_i2 = pow_i(i, &bxd);
467 assert_eq!(pow_i1.evaluate(&x), pow_i2);
468 }
469 }
470
471 #[test]
472 fn test_eval_f() {
473 let r1cs = get_test_r1cs::<Fr>();
474 let mut z = get_test_z::<Fr>(3);
475
476 let f_w = eval_f(&r1cs, &z);
477 assert!(is_zero_vec(&f_w));
478
479 z[1] = Fr::from(111);
480 let f_w = eval_f(&r1cs, &z);
481 assert!(!is_zero_vec(&f_w));
482 }
483
484 // k represents the number of instances to be fold, appart from the running instance
485 fn prepare_inputs(
486 k: usize,
487 ) -> (
488 Witness<G1Projective>,
489 CommittedInstance<G1Projective>,
490 Vec<Witness<G1Projective>>,
491 Vec<CommittedInstance<G1Projective>>,
492 ) {
493 let mut rng = ark_std::test_rng();
494 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
495
496 let z = get_test_z::<Fr>(3);
497 let mut zs: Vec<Vec<Fr>> = Vec::new();
498 for i in 0..k {
499 let z_i = get_test_z::<Fr>(i + 4);
500 zs.push(z_i);
501 }
502
503 let n = z.len();
504 let t = log2(n) as usize;
505
506 let beta = Fr::rand(&mut rng);
507 let betas = powers_of_beta(beta, t);
508
509 let witness = Witness::<G1Projective> {
510 w: z.clone(), // WIP
511 r_w: Fr::rand(&mut rng),
512 };
513 let phi = Pedersen::<G1Projective>::commit(&pedersen_params, &witness.w, &witness.r_w);
514 let instance = CommittedInstance::<G1Projective> {
515 phi,
516 betas: betas.clone(),
517 e: Fr::zero(),
518 };
519 // same for the other instances
520 let mut witnesses: Vec<Witness<G1Projective>> = Vec::new();
521 let mut instances: Vec<CommittedInstance<G1Projective>> = Vec::new();
522 for i in 0..k {
523 let witness_i = Witness::<G1Projective> {
524 w: zs[i].clone(), // WIP
525 r_w: Fr::rand(&mut rng),
526 };
527 let phi_i =
528 Pedersen::<G1Projective>::commit(&pedersen_params, &witness_i.w, &witness_i.r_w);
529 let instance_i = CommittedInstance::<G1Projective> {
530 phi: phi_i,
531 betas: betas.clone(),
532 e: Fr::zero(),
533 };
534 witnesses.push(witness_i);
535 instances.push(instance_i);
536 }
537
538 (witness, instance, witnesses, instances)
539 }
540
541 #[test]
542 fn test_fold_native_case() {
543 let k = 6;
544 let (witness, instance, witnesses, instances) = prepare_inputs(k);
545 let r1cs = get_test_r1cs::<Fr>();
546
547 // init Prover & Verifier's transcript
548 let poseidon_config = poseidon_test_config::<Fr>();
549 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
550 let mut transcript_v = Transcript::<Fr, G1Projective>::new(&poseidon_config);
551
552 let (folded_instance, folded_witness, F_coeffs, K_coeffs) = Folding::<G1Projective>::prove(
553 &mut transcript_p,
554 &r1cs,
555 &instance,
556 &witness,
557 &instances,
558 &witnesses,
559 );
560
561 // veriier
562 let folded_instance_v = Folding::<G1Projective>::verify(
563 &mut transcript_v,
564 &r1cs,
565 &instance,
566 &instances,
567 F_coeffs,
568 K_coeffs,
569 );
570
571 // check that prover & verifier folded instances are the same values
572 assert_eq!(folded_instance.phi.0, folded_instance_v.phi.0);
573 assert_eq!(folded_instance.betas, folded_instance_v.betas);
574 assert_eq!(folded_instance.e, folded_instance_v.e);
575 assert!(!folded_instance.e.is_zero());
576
577 // check that the folded instance satisfies the relation
578 assert!(check_instance(&r1cs, &folded_instance, &folded_witness));
579 }
580
581 #[test]
582 fn test_fold_various_iterations() {
583 let r1cs = get_test_r1cs::<Fr>();
584
585 // init Prover & Verifier's transcript
586 let poseidon_config = poseidon_test_config::<Fr>();
587 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
588 let mut transcript_v = Transcript::<Fr, G1Projective>::new(&poseidon_config);
589
590 let (mut running_witness, mut running_instance, _, _) = prepare_inputs(0);
591
592 // fold k instances on each of num_iters iterations
593 let k = 6;
594 let num_iters = 10;
595 for _ in 0..num_iters {
596 // generate the instances to be fold
597 let (_, _, witnesses, instances) = prepare_inputs(k);
598
599 let (folded_instance, folded_witness, F_coeffs, K_coeffs) =
600 Folding::<G1Projective>::prove(
601 &mut transcript_p,
602 &r1cs,
603 &running_instance,
604 &running_witness,
605 &instances,
606 &witnesses,
607 );
608
609 // veriier
610 let folded_instance_v = Folding::<G1Projective>::verify(
611 &mut transcript_v,
612 &r1cs,
613 &running_instance,
614 &instances,
615 F_coeffs,
616 K_coeffs,
617 );
618
619 // check that prover & verifier folded instances are the same values
620 assert_eq!(folded_instance.phi.0, folded_instance_v.phi.0);
621 assert_eq!(folded_instance.betas, folded_instance_v.betas);
622 assert_eq!(folded_instance.e, folded_instance_v.e);
623 assert!(!folded_instance.e.is_zero());
624
625 // check that the folded instance satisfies the relation
626 assert!(check_instance(&r1cs, &folded_instance, &folded_witness));
627
628 running_witness = folded_witness;
629 running_instance = folded_instance;
630 }
631 }
632}