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