sonobe/folding-schemes/src/folding/nova/nifs.rs
folding-schemes/src/folding/nova/nifs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_std::Zero;
4use std::marker::PhantomData;
5
6use super::{CommittedInstance, Witness};
7use crate::arith::r1cs::R1CS;
8use crate::commitment::CommitmentScheme;
9use crate::transcript::Transcript;
10use crate::utils::vec::{hadamard, mat_vec_mul, vec_add, vec_scalar_mul, vec_sub};
11use crate::Error;
12
13/// Implements the Non-Interactive Folding Scheme described in section 4 of
14/// [Nova](https://eprint.iacr.org/2021/370.pdf)
15/// `H` specifies whether the NIFS will use a blinding factor
16pub struct NIFS<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool = false> {
17 _c: PhantomData<C>,
18 _cp: PhantomData<CS>,
19}
20
21impl<C: CurveGroup, CS: CommitmentScheme<C, H>, const H: bool> NIFS<C, CS, H>
22where
23 <C as Group>::ScalarField: Absorb,
24{
25 // compute_T: compute cross-terms T
26 pub fn compute_T(
27 r1cs: &R1CS<C::ScalarField>,
28 u1: C::ScalarField,
29 u2: C::ScalarField,
30 z1: &[C::ScalarField],
31 z2: &[C::ScalarField],
32 ) -> Result<Vec<C::ScalarField>, Error> {
33 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
34
35 // this is parallelizable (for the future)
36 let Az1 = mat_vec_mul(&A, z1)?;
37 let Bz1 = mat_vec_mul(&B, z1)?;
38 let Cz1 = mat_vec_mul(&C, z1)?;
39 let Az2 = mat_vec_mul(&A, z2)?;
40 let Bz2 = mat_vec_mul(&B, z2)?;
41 let Cz2 = mat_vec_mul(&C, z2)?;
42
43 let Az1_Bz2 = hadamard(&Az1, &Bz2)?;
44 let Az2_Bz1 = hadamard(&Az2, &Bz1)?;
45 let u1Cz2 = vec_scalar_mul(&Cz2, &u1);
46 let u2Cz1 = vec_scalar_mul(&Cz1, &u2);
47
48 vec_sub(&vec_sub(&vec_add(&Az1_Bz2, &Az2_Bz1)?, &u1Cz2)?, &u2Cz1)
49 }
50
51 pub fn fold_witness(
52 r: C::ScalarField,
53 w1: &Witness<C>,
54 w2: &Witness<C>,
55 T: &[C::ScalarField],
56 rT: C::ScalarField,
57 ) -> Result<Witness<C>, Error> {
58 let r2 = r * r;
59 let E: Vec<C::ScalarField> = vec_add(
60 &vec_add(&w1.E, &vec_scalar_mul(T, &r))?,
61 &vec_scalar_mul(&w2.E, &r2),
62 )?;
63 let rE = w1.rE + r * rT + r2 * w2.rE;
64 let W: Vec<C::ScalarField> = w1.W.iter().zip(&w2.W).map(|(a, b)| *a + (r * b)).collect();
65
66 let rW = w1.rW + r * w2.rW;
67 Ok(Witness::<C> { E, rE, W, rW })
68 }
69
70 pub fn fold_committed_instance(
71 r: C::ScalarField,
72 ci1: &CommittedInstance<C>, // U_i
73 ci2: &CommittedInstance<C>, // u_i
74 cmT: &C,
75 ) -> CommittedInstance<C> {
76 let r2 = r * r;
77 let cmE = ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2);
78 let u = ci1.u + r * ci2.u;
79 let cmW = ci1.cmW + ci2.cmW.mul(r);
80 let x = ci1
81 .x
82 .iter()
83 .zip(&ci2.x)
84 .map(|(a, b)| *a + (r * b))
85 .collect::<Vec<C::ScalarField>>();
86
87 CommittedInstance::<C> { cmE, u, cmW, x }
88 }
89
90 /// NIFS.P is the consecutive combination of compute_cmT with fold_instances
91
92 /// compute_cmT is part of the NIFS.P logic
93 pub fn compute_cmT(
94 cs_prover_params: &CS::ProverParams,
95 r1cs: &R1CS<C::ScalarField>,
96 w1: &Witness<C>,
97 ci1: &CommittedInstance<C>,
98 w2: &Witness<C>,
99 ci2: &CommittedInstance<C>,
100 ) -> Result<(Vec<C::ScalarField>, C), Error> {
101 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
102 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
103
104 // compute cross terms
105 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
106 // use r_T=0 since we don't need hiding property for cm(T)
107 let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
108 Ok((T, cmT))
109 }
110 pub fn compute_cyclefold_cmT(
111 cs_prover_params: &CS::ProverParams,
112 r1cs: &R1CS<C::ScalarField>, // R1CS over C2.Fr=C1.Fq (here C=C2)
113 w1: &Witness<C>,
114 ci1: &CommittedInstance<C>,
115 w2: &Witness<C>,
116 ci2: &CommittedInstance<C>,
117 ) -> Result<(Vec<C::ScalarField>, C), Error>
118 where
119 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
120 {
121 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
122 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
123
124 // compute cross terms
125 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
126 // use r_T=0 since we don't need hiding property for cm(T)
127 let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
128 Ok((T, cmT))
129 }
130
131 /// fold_instances is part of the NIFS.P logic described in
132 /// [Nova](https://eprint.iacr.org/2021/370.pdf)'s section 4. It returns the folded Committed
133 /// Instances and the Witness.
134 pub fn fold_instances(
135 r: C::ScalarField,
136 w1: &Witness<C>,
137 ci1: &CommittedInstance<C>,
138 w2: &Witness<C>,
139 ci2: &CommittedInstance<C>,
140 T: &[C::ScalarField],
141 cmT: C,
142 ) -> Result<(Witness<C>, CommittedInstance<C>), Error> {
143 // fold witness
144 // use r_T=0 since we don't need hiding property for cm(T)
145 let w3 = NIFS::<C, CS, H>::fold_witness(r, w1, w2, T, C::ScalarField::zero())?;
146
147 // fold committed instances
148 let ci3 = NIFS::<C, CS, H>::fold_committed_instance(r, ci1, ci2, &cmT);
149
150 Ok((w3, ci3))
151 }
152
153 /// verify implements NIFS.V logic described in [Nova](https://eprint.iacr.org/2021/370.pdf)'s
154 /// section 4. It returns the folded Committed Instance
155 pub fn verify(
156 // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
157 r: C::ScalarField,
158 ci1: &CommittedInstance<C>,
159 ci2: &CommittedInstance<C>,
160 cmT: &C,
161 ) -> CommittedInstance<C> {
162 NIFS::<C, CS, H>::fold_committed_instance(r, ci1, ci2, cmT)
163 }
164
165 /// Verify committed folded instance (ci) relations. Notice that this method does not open the
166 /// commitments, but just checks that the given committed instances (ci1, ci2) when folded
167 /// result in the folded committed instance (ci3) values.
168 pub fn verify_folded_instance(
169 r: C::ScalarField,
170 ci1: &CommittedInstance<C>,
171 ci2: &CommittedInstance<C>,
172 ci3: &CommittedInstance<C>,
173 cmT: &C,
174 ) -> Result<(), Error> {
175 let expected = Self::fold_committed_instance(r, ci1, ci2, cmT);
176 if ci3.cmE != expected.cmE
177 || ci3.u != expected.u
178 || ci3.cmW != expected.cmW
179 || ci3.x != expected.x
180 {
181 return Err(Error::NotSatisfied);
182 }
183 Ok(())
184 }
185
186 pub fn prove_commitments(
187 tr: &mut impl Transcript<C::ScalarField>,
188 cs_prover_params: &CS::ProverParams,
189 w: &Witness<C>,
190 ci: &CommittedInstance<C>,
191 T: Vec<C::ScalarField>,
192 cmT: &C,
193 ) -> Result<[CS::Proof; 3], Error> {
194 let cmE_proof = CS::prove(cs_prover_params, tr, &ci.cmE, &w.E, &w.rE, None)?;
195 let cmW_proof = CS::prove(cs_prover_params, tr, &ci.cmW, &w.W, &w.rW, None)?;
196 let cmT_proof = CS::prove(cs_prover_params, tr, cmT, &T, &C::ScalarField::zero(), None)?; // cm(T) is committed with rT=0
197 Ok([cmE_proof, cmW_proof, cmT_proof])
198 }
199}
200
201#[cfg(test)]
202pub mod tests {
203 use super::*;
204 use ark_crypto_primitives::sponge::{
205 poseidon::{PoseidonConfig, PoseidonSponge},
206 CryptographicSponge,
207 };
208 use ark_ff::{BigInteger, PrimeField};
209 use ark_pallas::{Fr, Projective};
210 use ark_std::{ops::Mul, test_rng, UniformRand};
211
212 use crate::arith::r1cs::tests::{get_test_r1cs, get_test_z};
213 use crate::commitment::pedersen::{Params as PedersenParams, Pedersen};
214 use crate::folding::nova::circuits::ChallengeGadget;
215 use crate::folding::nova::traits::NovaR1CS;
216 use crate::transcript::poseidon::poseidon_canonical_config;
217
218 #[allow(clippy::type_complexity)]
219 pub(crate) fn prepare_simple_fold_inputs<C>() -> (
220 PedersenParams<C>,
221 PoseidonConfig<C::ScalarField>,
222 R1CS<C::ScalarField>,
223 Witness<C>, // w1
224 CommittedInstance<C>, // ci1
225 Witness<C>, // w2
226 CommittedInstance<C>, // ci2
227 Witness<C>, // w3
228 CommittedInstance<C>, // ci3
229 Vec<C::ScalarField>, // T
230 C, // cmT
231 Vec<bool>, // r_bits
232 C::ScalarField, // r_Fr
233 )
234 where
235 C: CurveGroup,
236 <C as CurveGroup>::BaseField: PrimeField,
237 C::ScalarField: Absorb,
238 {
239 let r1cs = get_test_r1cs();
240 let z1 = get_test_z(3);
241 let z2 = get_test_z(4);
242 let (w1, x1) = r1cs.split_z(&z1);
243 let (w2, x2) = r1cs.split_z(&z2);
244
245 let w1 = Witness::<C>::new::<false>(w1.clone(), r1cs.A.n_rows, test_rng());
246 let w2 = Witness::<C>::new::<false>(w2.clone(), r1cs.A.n_rows, test_rng());
247
248 let mut rng = ark_std::test_rng();
249 let (pedersen_params, _) = Pedersen::<C>::setup(&mut rng, r1cs.A.n_cols).unwrap();
250
251 // compute committed instances
252 let ci1 = w1
253 .commit::<Pedersen<C>, false>(&pedersen_params, x1.clone())
254 .unwrap();
255 let ci2 = w2
256 .commit::<Pedersen<C>, false>(&pedersen_params, x2.clone())
257 .unwrap();
258
259 // NIFS.P
260 let (T, cmT) =
261 NIFS::<C, Pedersen<C>>::compute_cmT(&pedersen_params, &r1cs, &w1, &ci1, &w2, &ci2)
262 .unwrap();
263
264 let poseidon_config = poseidon_canonical_config::<C::ScalarField>();
265 let mut transcript = PoseidonSponge::<C::ScalarField>::new(&poseidon_config);
266
267 let pp_hash = C::ScalarField::from(42u32); // only for test
268 let r_bits = ChallengeGadget::<C>::get_challenge_native(
269 &mut transcript,
270 pp_hash,
271 ci1.clone(),
272 ci2.clone(),
273 cmT,
274 );
275 let r_Fr = C::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
276
277 let (w3, ci3) =
278 NIFS::<C, Pedersen<C>>::fold_instances(r_Fr, &w1, &ci1, &w2, &ci2, &T, cmT).unwrap();
279
280 (
281 pedersen_params,
282 poseidon_config,
283 r1cs,
284 w1,
285 ci1,
286 w2,
287 ci2,
288 w3,
289 ci3,
290 T,
291 cmT,
292 r_bits,
293 r_Fr,
294 )
295 }
296
297 // fold 2 dummy instances and check that the folded instance holds the relaxed R1CS relation
298 #[test]
299 fn test_nifs_fold_dummy() {
300 let r1cs = get_test_r1cs::<Fr>();
301 let z1 = get_test_z(3);
302 let (w1, x1) = r1cs.split_z(&z1);
303
304 let mut rng = ark_std::test_rng();
305 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
306
307 // dummy instance, witness and public inputs zeroes
308 let w_dummy = Witness::<Projective>::dummy(w1.len(), r1cs.A.n_rows);
309 let mut u_dummy = w_dummy
310 .commit::<Pedersen<Projective>, false>(&pedersen_params, vec![Fr::zero(); x1.len()])
311 .unwrap();
312 u_dummy.u = Fr::zero();
313
314 let w_i = w_dummy.clone();
315 let u_i = u_dummy.clone();
316 let W_i = w_dummy.clone();
317 let U_i = u_dummy.clone();
318 r1cs.check_relaxed_instance_relation(&w_i, &u_i).unwrap();
319 r1cs.check_relaxed_instance_relation(&W_i, &U_i).unwrap();
320
321 let r_Fr = Fr::from(3_u32);
322
323 let (T, cmT) = NIFS::<Projective, Pedersen<Projective>>::compute_cmT(
324 &pedersen_params,
325 &r1cs,
326 &w_i,
327 &u_i,
328 &W_i,
329 &U_i,
330 )
331 .unwrap();
332 let (W_i1, U_i1) = NIFS::<Projective, Pedersen<Projective>>::fold_instances(
333 r_Fr, &w_i, &u_i, &W_i, &U_i, &T, cmT,
334 )
335 .unwrap();
336 r1cs.check_relaxed_instance_relation(&W_i1, &U_i1).unwrap();
337 }
338
339 // fold 2 instances into one
340 #[test]
341 fn test_nifs_one_fold() {
342 let (pedersen_params, poseidon_config, r1cs, w1, ci1, w2, ci2, w3, ci3, T, cmT, _, r) =
343 prepare_simple_fold_inputs();
344
345 // NIFS.V
346 let ci3_v = NIFS::<Projective, Pedersen<Projective>>::verify(r, &ci1, &ci2, &cmT);
347 assert_eq!(ci3_v, ci3);
348
349 // check that relations hold for the 2 inputted instances and the folded one
350 r1cs.check_relaxed_instance_relation(&w1, &ci1).unwrap();
351 r1cs.check_relaxed_instance_relation(&w2, &ci2).unwrap();
352 r1cs.check_relaxed_instance_relation(&w3, &ci3).unwrap();
353
354 // check that folded commitments from folded instance (ci) are equal to folding the
355 // use folded rE, rW to commit w3
356 let ci3_expected = w3
357 .commit::<Pedersen<Projective>, false>(&pedersen_params, ci3.x.clone())
358 .unwrap();
359 assert_eq!(ci3_expected.cmE, ci3.cmE);
360 assert_eq!(ci3_expected.cmW, ci3.cmW);
361
362 // next equalities should hold since we started from two cmE of zero-vector E's
363 assert_eq!(ci3.cmE, cmT.mul(r));
364 assert_eq!(w3.E, vec_scalar_mul(&T, &r));
365
366 // NIFS.Verify_Folded_Instance:
367 NIFS::<Projective, Pedersen<Projective>>::verify_folded_instance(r, &ci1, &ci2, &ci3, &cmT)
368 .unwrap();
369
370 // init Prover's transcript
371 let mut transcript_p = PoseidonSponge::<Fr>::new(&poseidon_config);
372 // init Verifier's transcript
373 let mut transcript_v = PoseidonSponge::<Fr>::new(&poseidon_config);
374
375 // prove the ci3.cmE, ci3.cmW, cmT commitments
376 let cm_proofs = NIFS::<Projective, Pedersen<Projective>>::prove_commitments(
377 &mut transcript_p,
378 &pedersen_params,
379 &w3,
380 &ci3,
381 T,
382 &cmT,
383 )
384 .unwrap();
385
386 // verify the ci3.cmE, ci3.cmW, cmT commitments
387 assert_eq!(cm_proofs.len(), 3);
388 Pedersen::<Projective>::verify(
389 &pedersen_params,
390 &mut transcript_v,
391 &ci3.cmE,
392 &cm_proofs[0].clone(),
393 )
394 .unwrap();
395 Pedersen::<Projective>::verify(
396 &pedersen_params,
397 &mut transcript_v,
398 &ci3.cmW,
399 &cm_proofs[1].clone(),
400 )
401 .unwrap();
402 Pedersen::<Projective>::verify(
403 &pedersen_params,
404 &mut transcript_v,
405 &cmT,
406 &cm_proofs[2].clone(),
407 )
408 .unwrap();
409 }
410
411 #[test]
412 fn test_nifs_fold_loop() {
413 let r1cs = get_test_r1cs();
414 let z = get_test_z(3);
415 let (w, x) = r1cs.split_z(&z);
416
417 let mut rng = ark_std::test_rng();
418 let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
419
420 // prepare the running instance
421 let mut running_instance_w =
422 Witness::<Projective>::new::<false>(w.clone(), r1cs.A.n_rows, test_rng());
423 let mut running_committed_instance = running_instance_w
424 .commit::<Pedersen<Projective>, false>(&pedersen_params, x)
425 .unwrap();
426
427 r1cs.check_relaxed_instance_relation(&running_instance_w, &running_committed_instance)
428 .unwrap();
429
430 let num_iters = 10;
431 for i in 0..num_iters {
432 // prepare the incoming instance
433 let incoming_instance_z = get_test_z(i + 4);
434 let (w, x) = r1cs.split_z(&incoming_instance_z);
435 let incoming_instance_w =
436 Witness::<Projective>::new::<false>(w.clone(), r1cs.A.n_rows, test_rng());
437 let incoming_committed_instance = incoming_instance_w
438 .commit::<Pedersen<Projective>, false>(&pedersen_params, x)
439 .unwrap();
440 r1cs.check_relaxed_instance_relation(
441 &incoming_instance_w,
442 &incoming_committed_instance,
443 )
444 .unwrap();
445
446 let r = Fr::rand(&mut rng); // folding challenge would come from the RO
447
448 // NIFS.P
449 let (T, cmT) = NIFS::<Projective, Pedersen<Projective>>::compute_cmT(
450 &pedersen_params,
451 &r1cs,
452 &running_instance_w,
453 &running_committed_instance,
454 &incoming_instance_w,
455 &incoming_committed_instance,
456 )
457 .unwrap();
458 let (folded_w, _) = NIFS::<Projective, Pedersen<Projective>>::fold_instances(
459 r,
460 &running_instance_w,
461 &running_committed_instance,
462 &incoming_instance_w,
463 &incoming_committed_instance,
464 &T,
465 cmT,
466 )
467 .unwrap();
468
469 // NIFS.V
470 let folded_committed_instance = NIFS::<Projective, Pedersen<Projective>>::verify(
471 r,
472 &running_committed_instance,
473 &incoming_committed_instance,
474 &cmT,
475 );
476
477 r1cs.check_relaxed_instance_relation(&folded_w, &folded_committed_instance)
478 .unwrap();
479
480 // set running_instance for next loop iteration
481 running_instance_w = folded_w;
482 running_committed_instance = folded_committed_instance;
483 }
484 }
485}