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