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