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