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