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