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