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