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