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