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