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