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