sonobe/src/folding/hypernova/nimfs.rs
src/folding/hypernova/nimfs.rsRaw
1use ark_ec::CurveGroup;
2use ark_ff::{Field, PrimeField};
3use ark_std::{One, Zero};
4
5use espresso_subroutines::PolyIOP;
6use espresso_transcript::IOPTranscript;
7
8use super::cccs::{Witness, CCCS};
9use super::lcccs::LCCCS;
10use super::utils::{compute_c_from_sigmas_and_thetas, compute_g, compute_sigmas_and_thetas};
11use crate::ccs::CCS;
12use crate::utils::hypercube::BooleanHypercube;
13use crate::utils::sum_check::structs::IOPProof as SumCheckProof;
14use crate::utils::sum_check::{verifier::interpolate_uni_poly, SumCheck};
15use crate::utils::virtual_polynomial::VPAuxInfo;
16use crate::Error;
17
18use std::marker::PhantomData;
19
20/// Proof defines a multifolding proof
21#[derive(Debug)]
22pub struct Proof<C: CurveGroup> {
23 pub sc_proof: SumCheckProof<C::ScalarField>,
24 pub sigmas_thetas: SigmasThetas<C::ScalarField>,
25}
26
27#[derive(Debug)]
28pub struct SigmasThetas<F: PrimeField>(pub Vec<Vec<F>>, pub Vec<Vec<F>>);
29
30#[derive(Debug)]
31/// Implements the Non-Interactive Multi Folding Scheme described in section 5 of
32/// [HyperNova](https://eprint.iacr.org/2023/573.pdf)
33pub struct NIMFS<C: CurveGroup> {
34 pub _c: PhantomData<C>,
35}
36
37impl<C: CurveGroup> NIMFS<C> {
38 pub fn fold(
39 lcccs: &[LCCCS<C>],
40 cccs: &[CCCS<C>],
41 sigmas_thetas: &SigmasThetas<C::ScalarField>,
42 r_x_prime: Vec<C::ScalarField>,
43 rho: C::ScalarField,
44 ) -> LCCCS<C> {
45 let (sigmas, thetas) = (sigmas_thetas.0.clone(), sigmas_thetas.1.clone());
46 let mut C_folded = C::zero();
47 let mut u_folded = C::ScalarField::zero();
48 let mut x_folded: Vec<C::ScalarField> = vec![C::ScalarField::zero(); lcccs[0].x.len()];
49 let mut v_folded: Vec<C::ScalarField> = vec![C::ScalarField::zero(); sigmas[0].len()];
50
51 for i in 0..(lcccs.len() + cccs.len()) {
52 let rho_i = rho.pow([i as u64]);
53
54 let c: C;
55 let u: C::ScalarField;
56 let x: Vec<C::ScalarField>;
57 let v: Vec<C::ScalarField>;
58 if i < lcccs.len() {
59 c = lcccs[i].C;
60 u = lcccs[i].u;
61 x = lcccs[i].x.clone();
62 v = sigmas[i].clone();
63 } else {
64 c = cccs[i - lcccs.len()].C;
65 u = C::ScalarField::one();
66 x = cccs[i - lcccs.len()].x.clone();
67 v = thetas[i - lcccs.len()].clone();
68 }
69
70 C_folded += c.mul(rho_i);
71 u_folded += rho_i * u;
72 x_folded = x_folded
73 .iter()
74 .zip(
75 x.iter()
76 .map(|x_i| *x_i * rho_i)
77 .collect::<Vec<C::ScalarField>>(),
78 )
79 .map(|(a_i, b_i)| *a_i + b_i)
80 .collect();
81
82 v_folded = v_folded
83 .iter()
84 .zip(
85 v.iter()
86 .map(|x_i| *x_i * rho_i)
87 .collect::<Vec<C::ScalarField>>(),
88 )
89 .map(|(a_i, b_i)| *a_i + b_i)
90 .collect();
91 }
92
93 LCCCS::<C> {
94 C: C_folded,
95 u: u_folded,
96 x: x_folded,
97 r_x: r_x_prime,
98 v: v_folded,
99 }
100 }
101
102 pub fn fold_witness(
103 w_lcccs: &[Witness<C::ScalarField>],
104 w_cccs: &[Witness<C::ScalarField>],
105 rho: C::ScalarField,
106 ) -> Witness<C::ScalarField> {
107 let mut w_folded: Vec<C::ScalarField> = vec![C::ScalarField::zero(); w_lcccs[0].w.len()];
108 let mut r_w_folded = C::ScalarField::zero();
109
110 for i in 0..(w_lcccs.len() + w_cccs.len()) {
111 let rho_i = rho.pow([i as u64]);
112 let w: Vec<C::ScalarField>;
113 let r_w: C::ScalarField;
114
115 if i < w_lcccs.len() {
116 w = w_lcccs[i].w.clone();
117 r_w = w_lcccs[i].r_w;
118 } else {
119 w = w_cccs[i - w_lcccs.len()].w.clone();
120 r_w = w_cccs[i - w_lcccs.len()].r_w;
121 }
122
123 w_folded = w_folded
124 .iter()
125 .zip(
126 w.iter()
127 .map(|x_i| *x_i * rho_i)
128 .collect::<Vec<C::ScalarField>>(),
129 )
130 .map(|(a_i, b_i)| *a_i + b_i)
131 .collect();
132
133 r_w_folded += rho_i * r_w;
134 }
135 Witness {
136 w: w_folded,
137 r_w: r_w_folded,
138 }
139 }
140
141 /// Performs the multifolding prover. Given μ LCCCS instances and ν CCS instances, fold them
142 /// into a single LCCCS instance. Since this is the prover, also fold their witness.
143 /// Returns the final folded LCCCS, the folded witness, and the multifolding proof, which
144 /// contains the sumcheck proof and the helper sumcheck claim sigmas and thetas.
145 #[allow(clippy::type_complexity)]
146 pub fn prove(
147 transcript: &mut IOPTranscript<C::ScalarField>,
148 ccs: &CCS<C>,
149 running_instances: &[LCCCS<C>],
150 new_instances: &[CCCS<C>],
151 w_lcccs: &[Witness<C::ScalarField>],
152 w_cccs: &[Witness<C::ScalarField>],
153 ) -> Result<(Proof<C>, LCCCS<C>, Witness<C::ScalarField>), Error> {
154 // TODO appends to transcript
155
156 if running_instances.is_empty() {
157 return Err(Error::Empty);
158 }
159 if new_instances.is_empty() {
160 return Err(Error::Empty);
161 }
162
163 // construct the LCCCS z vector from the relaxation factor, public IO and witness
164 // XXX this deserves its own function in LCCCS
165 let mut z_lcccs = Vec::new();
166 for (i, running_instance) in running_instances.iter().enumerate() {
167 let z_1: Vec<C::ScalarField> = [
168 vec![running_instance.u],
169 running_instance.x.clone(),
170 w_lcccs[i].w.to_vec(),
171 ]
172 .concat();
173 z_lcccs.push(z_1);
174 }
175 // construct the CCCS z vector from the public IO and witness
176 let mut z_cccs = Vec::new();
177 for (i, new_instance) in new_instances.iter().enumerate() {
178 let z_2: Vec<C::ScalarField> = [
179 vec![C::ScalarField::one()],
180 new_instance.x.clone(),
181 w_cccs[i].w.to_vec(),
182 ]
183 .concat();
184 z_cccs.push(z_2);
185 }
186
187 // Step 1: Get some challenges
188 let gamma: C::ScalarField = transcript.get_and_append_challenge(b"gamma").unwrap();
189 let beta: Vec<C::ScalarField> = transcript
190 .get_and_append_challenge_vectors(b"beta", ccs.s)
191 .unwrap();
192
193 // Compute g(x)
194 let g = compute_g(ccs, running_instances, &z_lcccs, &z_cccs, gamma, &beta);
195
196 // Step 3: Run the sumcheck prover
197 let sumcheck_proof =
198 <PolyIOP<C::ScalarField> as SumCheck<C::ScalarField>>::prove(&g, transcript).unwrap(); // XXX unwrap
199
200 // Note: The following two "sanity checks" are done for this prototype, in a final version
201 // they should be removed.
202 //
203 // Sanity check 1: evaluate g(x) over x \in {0,1} (the boolean hypercube), and check that
204 // its sum is equal to the extracted_sum from the SumCheck.
205 //////////////////////////////////////////////////////////////////////
206 let mut g_over_bhc = C::ScalarField::zero();
207 for x in BooleanHypercube::new(ccs.s) {
208 g_over_bhc += g.evaluate(&x).unwrap();
209 }
210
211 // note: this is the sum of g(x) over the whole boolean hypercube
212 let extracted_sum =
213 <PolyIOP<C::ScalarField> as SumCheck<C::ScalarField>>::extract_sum(&sumcheck_proof);
214 if extracted_sum != g_over_bhc {
215 return Err(Error::NotEqual);
216 }
217 // Sanity check 2: expect \sum v_j * gamma^j to be equal to the sum of g(x) over the
218 // boolean hypercube (and also equal to the extracted_sum from the SumCheck).
219 let mut sum_v_j_gamma = C::ScalarField::zero();
220 for (i, running_instance) in running_instances.iter().enumerate() {
221 for j in 0..running_instance.v.len() {
222 let gamma_j = gamma.pow([(i * ccs.t + j) as u64]);
223 sum_v_j_gamma += running_instance.v[j] * gamma_j;
224 }
225 }
226 if g_over_bhc != sum_v_j_gamma {
227 return Err(Error::NotEqual);
228 }
229 if extracted_sum != sum_v_j_gamma {
230 return Err(Error::NotEqual);
231 }
232 //////////////////////////////////////////////////////////////////////
233
234 // Step 2: dig into the sumcheck and extract r_x_prime
235 let r_x_prime = sumcheck_proof.point.clone();
236
237 // Step 4: compute sigmas and thetas
238 let sigmas_thetas = compute_sigmas_and_thetas(ccs, &z_lcccs, &z_cccs, &r_x_prime);
239
240 // Step 6: Get the folding challenge
241 let rho: C::ScalarField = transcript.get_and_append_challenge(b"rho").unwrap();
242
243 // Step 7: Create the folded instance
244 let folded_lcccs = Self::fold(
245 running_instances,
246 new_instances,
247 &sigmas_thetas,
248 r_x_prime,
249 rho,
250 );
251
252 // Step 8: Fold the witnesses
253 let folded_witness = Self::fold_witness(w_lcccs, w_cccs, rho);
254
255 Ok((
256 Proof::<C> {
257 sc_proof: sumcheck_proof,
258 sigmas_thetas,
259 },
260 folded_lcccs,
261 folded_witness,
262 ))
263 }
264
265 /// Performs the multifolding verifier. Given μ LCCCS instances and ν CCS instances, fold them
266 /// into a single LCCCS instance.
267 /// Returns the folded LCCCS instance.
268 pub fn verify(
269 transcript: &mut IOPTranscript<C::ScalarField>,
270 ccs: &CCS<C>,
271 running_instances: &[LCCCS<C>],
272 new_instances: &[CCCS<C>],
273 proof: Proof<C>,
274 ) -> Result<LCCCS<C>, Error> {
275 // TODO appends to transcript
276
277 if running_instances.is_empty() {
278 return Err(Error::Empty);
279 }
280 if new_instances.is_empty() {
281 return Err(Error::Empty);
282 }
283
284 // Step 1: Get some challenges
285 let gamma: C::ScalarField = transcript.get_and_append_challenge(b"gamma").unwrap();
286 let beta: Vec<C::ScalarField> = transcript
287 .get_and_append_challenge_vectors(b"beta", ccs.s)
288 .unwrap();
289
290 let vp_aux_info = VPAuxInfo::<C::ScalarField> {
291 max_degree: ccs.d + 1,
292 num_variables: ccs.s,
293 phantom: PhantomData::<C::ScalarField>,
294 };
295
296 // Step 3: Start verifying the sumcheck
297 // First, compute the expected sumcheck sum: \sum gamma^j v_j
298 let mut sum_v_j_gamma = C::ScalarField::zero();
299 for (i, running_instance) in running_instances.iter().enumerate() {
300 for j in 0..running_instance.v.len() {
301 let gamma_j = gamma.pow([(i * ccs.t + j) as u64]);
302 sum_v_j_gamma += running_instance.v[j] * gamma_j;
303 }
304 }
305
306 // Verify the interactive part of the sumcheck
307 let sumcheck_subclaim = <PolyIOP<C::ScalarField> as SumCheck<C::ScalarField>>::verify(
308 sum_v_j_gamma,
309 &proof.sc_proof,
310 &vp_aux_info,
311 transcript,
312 )
313 .unwrap();
314
315 // Step 2: Dig into the sumcheck claim and extract the randomness used
316 let r_x_prime = sumcheck_subclaim.point.clone();
317
318 // Step 5: Finish verifying sumcheck (verify the claim c)
319 let c = compute_c_from_sigmas_and_thetas(
320 ccs,
321 &proof.sigmas_thetas,
322 gamma,
323 &beta,
324 &running_instances
325 .iter()
326 .map(|lcccs| lcccs.r_x.clone())
327 .collect(),
328 &r_x_prime,
329 );
330 // check that the g(r_x') from the sumcheck proof is equal to the computed c from sigmas&thetas
331 if c != sumcheck_subclaim.expected_evaluation {
332 return Err(Error::NotEqual);
333 }
334
335 // Sanity check: we can also compute g(r_x') from the proof last evaluation value, and
336 // should be equal to the previously obtained values.
337 let g_on_rxprime_from_sumcheck_last_eval = interpolate_uni_poly::<C::ScalarField>(
338 &proof.sc_proof.proofs.last().unwrap().evaluations,
339 *r_x_prime.last().unwrap(),
340 )
341 .unwrap();
342 if g_on_rxprime_from_sumcheck_last_eval != c {
343 return Err(Error::NotEqual);
344 }
345 if g_on_rxprime_from_sumcheck_last_eval != sumcheck_subclaim.expected_evaluation {
346 return Err(Error::NotEqual);
347 }
348
349 // Step 6: Get the folding challenge
350 let rho: C::ScalarField = transcript.get_and_append_challenge(b"rho").unwrap();
351
352 // Step 7: Compute the folded instance
353 Ok(Self::fold(
354 running_instances,
355 new_instances,
356 &proof.sigmas_thetas,
357 r_x_prime,
358 rho,
359 ))
360 }
361}
362
363#[cfg(test)]
364pub mod tests {
365 use super::*;
366 use crate::ccs::tests::{get_test_ccs, get_test_z};
367 use ark_std::test_rng;
368 use ark_std::UniformRand;
369
370 use crate::pedersen::Pedersen;
371 use ark_pallas::{Fr, Projective};
372
373 #[test]
374 fn test_fold() {
375 let ccs = get_test_ccs();
376 let z1 = get_test_z::<Fr>(3);
377 let z2 = get_test_z::<Fr>(4);
378 ccs.check_relation(&z1).unwrap();
379 ccs.check_relation(&z2).unwrap();
380
381 let mut rng = test_rng();
382 let r_x_prime: Vec<Fr> = (0..ccs.s).map(|_| Fr::rand(&mut rng)).collect();
383
384 let sigmas_thetas =
385 compute_sigmas_and_thetas(&ccs, &[z1.clone()], &[z2.clone()], &r_x_prime);
386
387 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, ccs.n - ccs.l - 1);
388
389 let (lcccs, w1) = ccs.to_lcccs(&mut rng, &pedersen_params, &z1).unwrap();
390 let (cccs, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z2).unwrap();
391
392 lcccs.check_relation(&pedersen_params, &ccs, &w1).unwrap();
393 cccs.check_relation(&pedersen_params, &ccs, &w2).unwrap();
394
395 let mut rng = test_rng();
396 let rho = Fr::rand(&mut rng);
397
398 let folded = NIMFS::<Projective>::fold(&[lcccs], &[cccs], &sigmas_thetas, r_x_prime, rho);
399
400 let w_folded = NIMFS::<Projective>::fold_witness(&[w1], &[w2], rho);
401
402 // check lcccs relation
403 folded
404 .check_relation(&pedersen_params, &ccs, &w_folded)
405 .unwrap();
406 }
407
408 /// Perform multifolding of an LCCCS instance with a CCCS instance (as described in the paper)
409 #[test]
410 pub fn test_basic_multifolding() {
411 let mut rng = test_rng();
412
413 // Create a basic CCS circuit
414 let ccs = get_test_ccs::<Projective>();
415 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
416
417 // Generate a satisfying witness
418 let z_1 = get_test_z(3);
419 // Generate another satisfying witness
420 let z_2 = get_test_z(4);
421
422 // Create the LCCCS instance out of z_1
423 let (running_instance, w1) = ccs.to_lcccs(&mut rng, &pedersen_params, &z_1).unwrap();
424 // Create the CCCS instance out of z_2
425 let (new_instance, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z_2).unwrap();
426
427 // Prover's transcript
428 let mut transcript_p = IOPTranscript::<Fr>::new(b"multifolding");
429 transcript_p.append_message(b"init", b"init").unwrap();
430
431 // Run the prover side of the multifolding
432 let (proof, folded_lcccs, folded_witness) = NIMFS::<Projective>::prove(
433 &mut transcript_p,
434 &ccs,
435 &[running_instance.clone()],
436 &[new_instance.clone()],
437 &[w1],
438 &[w2],
439 )
440 .unwrap();
441
442 // Verifier's transcript
443 let mut transcript_v = IOPTranscript::<Fr>::new(b"multifolding");
444 transcript_v.append_message(b"init", b"init").unwrap();
445
446 // Run the verifier side of the multifolding
447 let folded_lcccs_v = NIMFS::<Projective>::verify(
448 &mut transcript_v,
449 &ccs,
450 &[running_instance.clone()],
451 &[new_instance.clone()],
452 proof,
453 )
454 .unwrap();
455 assert_eq!(folded_lcccs, folded_lcccs_v);
456
457 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
458 folded_lcccs
459 .check_relation(&pedersen_params, &ccs, &folded_witness)
460 .unwrap();
461 }
462
463 /// Perform multiple steps of multifolding of an LCCCS instance with a CCCS instance
464 #[test]
465 pub fn test_multifolding_two_instances_multiple_steps() {
466 let mut rng = test_rng();
467
468 let ccs = get_test_ccs::<Projective>();
469
470 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
471
472 // LCCCS witness
473 let z_1 = get_test_z(2);
474 let (mut running_instance, mut w1) =
475 ccs.to_lcccs(&mut rng, &pedersen_params, &z_1).unwrap();
476
477 let mut transcript_p = IOPTranscript::<Fr>::new(b"multifolding");
478 let mut transcript_v = IOPTranscript::<Fr>::new(b"multifolding");
479 transcript_p.append_message(b"init", b"init").unwrap();
480 transcript_v.append_message(b"init", b"init").unwrap();
481
482 let n: usize = 10;
483 for i in 3..n {
484 println!("\niteration: i {}", i); // DBG
485
486 // CCS witness
487 let z_2 = get_test_z(i);
488 println!("z_2 {:?}", z_2); // DBG
489
490 let (new_instance, w2) = ccs.to_cccs(&mut rng, &pedersen_params, &z_2).unwrap();
491
492 // run the prover side of the multifolding
493 let (proof, folded_lcccs, folded_witness) = NIMFS::<Projective>::prove(
494 &mut transcript_p,
495 &ccs,
496 &[running_instance.clone()],
497 &[new_instance.clone()],
498 &[w1],
499 &[w2],
500 )
501 .unwrap();
502
503 // run the verifier side of the multifolding
504 let folded_lcccs_v = NIMFS::<Projective>::verify(
505 &mut transcript_v,
506 &ccs,
507 &[running_instance.clone()],
508 &[new_instance.clone()],
509 proof,
510 )
511 .unwrap();
512
513 assert_eq!(folded_lcccs, folded_lcccs_v);
514
515 // check that the folded instance with the folded witness holds the LCCCS relation
516 println!("check_relation {}", i);
517 folded_lcccs
518 .check_relation(&pedersen_params, &ccs, &folded_witness)
519 .unwrap();
520
521 running_instance = folded_lcccs;
522 w1 = folded_witness;
523 }
524 }
525
526 /// Test that generates mu>1 and nu>1 instances, and folds them in a single multifolding step.
527 #[test]
528 pub fn test_multifolding_mu_nu_instances() {
529 let mut rng = test_rng();
530
531 // Create a basic CCS circuit
532 let ccs = get_test_ccs::<Projective>();
533 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
534
535 let mu = 10;
536 let nu = 15;
537
538 // Generate a mu LCCCS & nu CCCS satisfying witness
539 let mut z_lcccs = Vec::new();
540 for i in 0..mu {
541 let z = get_test_z(i + 3);
542 z_lcccs.push(z);
543 }
544 let mut z_cccs = Vec::new();
545 for i in 0..nu {
546 let z = get_test_z(nu + i + 3);
547 z_cccs.push(z);
548 }
549
550 // Create the LCCCS instances out of z_lcccs
551 let mut lcccs_instances = Vec::new();
552 let mut w_lcccs = Vec::new();
553 for z_i in z_lcccs.iter() {
554 let (running_instance, w) = ccs.to_lcccs(&mut rng, &pedersen_params, z_i).unwrap();
555 lcccs_instances.push(running_instance);
556 w_lcccs.push(w);
557 }
558 // Create the CCCS instance out of z_cccs
559 let mut cccs_instances = Vec::new();
560 let mut w_cccs = Vec::new();
561 for z_i in z_cccs.iter() {
562 let (new_instance, w) = ccs.to_cccs(&mut rng, &pedersen_params, z_i).unwrap();
563 cccs_instances.push(new_instance);
564 w_cccs.push(w);
565 }
566
567 // Prover's transcript
568 let mut transcript_p = IOPTranscript::<Fr>::new(b"multifolding");
569 transcript_p.append_message(b"init", b"init").unwrap();
570
571 // Run the prover side of the multifolding
572 let (proof, folded_lcccs, folded_witness) = NIMFS::<Projective>::prove(
573 &mut transcript_p,
574 &ccs,
575 &lcccs_instances,
576 &cccs_instances,
577 &w_lcccs,
578 &w_cccs,
579 )
580 .unwrap();
581
582 // Verifier's transcript
583 let mut transcript_v = IOPTranscript::<Fr>::new(b"multifolding");
584 transcript_v.append_message(b"init", b"init").unwrap();
585
586 // Run the verifier side of the multifolding
587 let folded_lcccs_v = NIMFS::<Projective>::verify(
588 &mut transcript_v,
589 &ccs,
590 &lcccs_instances,
591 &cccs_instances,
592 proof,
593 )
594 .unwrap();
595 assert_eq!(folded_lcccs, folded_lcccs_v);
596
597 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
598 folded_lcccs
599 .check_relation(&pedersen_params, &ccs, &folded_witness)
600 .unwrap();
601 }
602
603 /// Test that generates mu>1 and nu>1 instances, and folds them in a single multifolding step
604 /// and repeats the process doing multiple steps.
605 #[test]
606 pub fn test_multifolding_mu_nu_instances_multiple_steps() {
607 let mut rng = test_rng();
608
609 // Create a basic CCS circuit
610 let ccs = get_test_ccs::<Projective>();
611 let pedersen_params = Pedersen::new_params(&mut rng, ccs.n - ccs.l - 1);
612
613 // Prover's transcript
614 let mut transcript_p = IOPTranscript::<Fr>::new(b"multifolding");
615 transcript_p.append_message(b"init", b"init").unwrap();
616
617 // Verifier's transcript
618 let mut transcript_v = IOPTranscript::<Fr>::new(b"multifolding");
619 transcript_v.append_message(b"init", b"init").unwrap();
620
621 let n_steps = 3;
622
623 // number of LCCCS & CCCS instances in each multifolding step
624 let mu = 10;
625 let nu = 15;
626
627 // Generate a mu LCCCS & nu CCCS satisfying witness, for each step
628 for step in 0..n_steps {
629 let mut z_lcccs = Vec::new();
630 for i in 0..mu {
631 let z = get_test_z(step + i + 3);
632 z_lcccs.push(z);
633 }
634 let mut z_cccs = Vec::new();
635 for i in 0..nu {
636 let z = get_test_z(nu + i + 3);
637 z_cccs.push(z);
638 }
639
640 // Create the LCCCS instances out of z_lcccs
641 let mut lcccs_instances = Vec::new();
642 let mut w_lcccs = Vec::new();
643 for z_i in z_lcccs.iter() {
644 let (running_instance, w) = ccs.to_lcccs(&mut rng, &pedersen_params, z_i).unwrap();
645 lcccs_instances.push(running_instance);
646 w_lcccs.push(w);
647 }
648 // Create the CCCS instance out of z_cccs
649 let mut cccs_instances = Vec::new();
650 let mut w_cccs = Vec::new();
651 for z_i in z_cccs.iter() {
652 let (new_instance, w) = ccs.to_cccs(&mut rng, &pedersen_params, z_i).unwrap();
653 cccs_instances.push(new_instance);
654 w_cccs.push(w);
655 }
656
657 // Run the prover side of the multifolding
658 let (proof, folded_lcccs, folded_witness) = NIMFS::<Projective>::prove(
659 &mut transcript_p,
660 &ccs,
661 &lcccs_instances,
662 &cccs_instances,
663 &w_lcccs,
664 &w_cccs,
665 )
666 .unwrap();
667
668 // Run the verifier side of the multifolding
669 let folded_lcccs_v = NIMFS::<Projective>::verify(
670 &mut transcript_v,
671 &ccs,
672 &lcccs_instances,
673 &cccs_instances,
674 proof,
675 )
676 .unwrap();
677 assert_eq!(folded_lcccs, folded_lcccs_v);
678
679 // Check that the folded LCCCS instance is a valid instance with respect to the folded witness
680 folded_lcccs
681 .check_relation(&pedersen_params, &ccs, &folded_witness)
682 .unwrap();
683 }
684 }
685}