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