sonobe/src/folding/nova/nifs.rs
src/folding/nova/nifs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_std::One;
4use std::marker::PhantomData;
5
6use super::{CommittedInstance, Witness};
7use crate::ccs::r1cs::R1CS;
8use crate::commitment::{
9 pedersen::{Params as PedersenParams, Pedersen, Proof as PedersenProof},
10 CommitmentProver,
11};
12use crate::transcript::Transcript;
13use crate::utils::vec::*;
14use crate::Error;
15
16/// Implements the Non-Interactive Folding Scheme described in section 4 of
17/// [Nova](https://eprint.iacr.org/2021/370.pdf)
18pub struct NIFS<C: CurveGroup> {
19 _phantom: PhantomData<C>,
20}
21
22impl<C: CurveGroup> NIFS<C>
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_sparse(&A, z1)?;
38 let Bz1 = mat_vec_mul_sparse(&B, z1)?;
39 let Cz1 = mat_vec_mul_sparse(&C, z1)?;
40 let Az2 = mat_vec_mul_sparse(&A, z2)?;
41 let Bz2 = mat_vec_mul_sparse(&B, z2)?;
42 let Cz2 = mat_vec_mul_sparse(&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>,
74 ci2: &CommittedInstance<C>,
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 pedersen_params: &PedersenParams<C>,
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=1 since we don't need hiding property for cm(T)
108 let cmT = Pedersen::commit(pedersen_params, &T, &C::ScalarField::one())?;
109 Ok((T, cmT))
110 }
111 pub fn compute_cyclefold_cmT(
112 pedersen_params: &PedersenParams<C>,
113 r1cs: &R1CS<C::ScalarField>, // R1CS over C2.Fr=C1.Fq (here C=C2)
114 w1: &Witness<C>,
115 ci1: &CommittedInstance<C>,
116 w2: &Witness<C>,
117 ci2: &CommittedInstance<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=1 since we don't need hiding property for cm(T)
128 let cmT = Pedersen::commit(pedersen_params, &T, &C::ScalarField::one())?;
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=1 since we don't need hiding property for cm(T)
146 let w3 = NIFS::<C>::fold_witness(r, w1, w2, T, C::ScalarField::one())?;
147
148 // fold committed instancs
149 let ci3 = NIFS::<C>::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>::fold_committed_instance(r, ci1, ci2, cmT)
164 }
165
166 /// Verify commited 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 open_commitments(
188 tr: &mut impl Transcript<C>,
189 pedersen_params: &PedersenParams<C>,
190 w: &Witness<C>,
191 ci: &CommittedInstance<C>,
192 T: Vec<C::ScalarField>,
193 cmT: &C,
194 ) -> Result<[PedersenProof<C>; 3], Error> {
195 let cmE_proof = Pedersen::prove(pedersen_params, tr, &ci.cmE, &w.E, &w.rE)?;
196 let cmW_proof = Pedersen::prove(pedersen_params, tr, &ci.cmW, &w.W, &w.rW)?;
197 let cmT_proof = Pedersen::prove(pedersen_params, tr, cmT, &T, &C::ScalarField::one())?; // cm(T) is committed with rT=1
198 Ok([cmE_proof, cmW_proof, cmT_proof])
199 }
200 pub fn verify_commitments(
201 tr: &mut impl Transcript<C>,
202 pedersen_params: &PedersenParams<C>,
203 ci: CommittedInstance<C>,
204 cmT: C,
205 cm_proofs: [PedersenProof<C>; 3],
206 ) -> Result<(), Error> {
207 if cm_proofs.len() != 3 {
208 // cm_proofs should have length 3: [cmE_proof, cmW_proof, cmT_proof]
209 return Err(Error::NotExpectedLength(cm_proofs.len(), 3));
210 }
211 Pedersen::verify(pedersen_params, tr, ci.cmE, cm_proofs[0].clone())?;
212 Pedersen::verify(pedersen_params, tr, ci.cmW, cm_proofs[1].clone())?;
213 Pedersen::verify(pedersen_params, tr, cmT, cm_proofs[2].clone())?;
214 Ok(())
215 }
216}
217
218#[cfg(test)]
219pub mod tests {
220 use super::*;
221 use ark_ff::{BigInteger, PrimeField};
222 use ark_pallas::{Fr, Projective};
223 use ark_std::{ops::Mul, UniformRand, Zero};
224
225 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
226 use crate::folding::nova::circuits::ChallengeGadget;
227 use crate::folding::nova::traits::NovaR1CS;
228 use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
229 use crate::utils::vec::vec_scalar_mul;
230 use ark_crypto_primitives::sponge::poseidon::PoseidonConfig;
231
232 #[allow(clippy::type_complexity)]
233 pub(crate) fn prepare_simple_fold_inputs() -> (
234 PedersenParams<Projective>,
235 PoseidonConfig<Fr>,
236 R1CS<Fr>,
237 Witness<Projective>, // w1
238 CommittedInstance<Projective>, // ci1
239 Witness<Projective>, // w2
240 CommittedInstance<Projective>, // ci2
241 Witness<Projective>, // w3
242 CommittedInstance<Projective>, // ci3
243 Vec<Fr>, // T
244 Projective, // cmT
245 Vec<bool>, // r_bits
246 Fr, // r_Fr
247 ) {
248 let r1cs = get_test_r1cs();
249 let z1 = get_test_z(3);
250 let z2 = get_test_z(4);
251 let (w1, x1) = r1cs.split_z(&z1);
252 let (w2, x2) = r1cs.split_z(&z2);
253
254 let w1 = Witness::<Projective>::new(w1.clone(), r1cs.A.n_rows);
255 let w2 = Witness::<Projective>::new(w2.clone(), r1cs.A.n_rows);
256
257 let mut rng = ark_std::test_rng();
258 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
259
260 // compute committed instances
261 let ci1 = w1.commit(&pedersen_params, x1.clone()).unwrap();
262 let ci2 = w2.commit(&pedersen_params, x2.clone()).unwrap();
263
264 // NIFS.P
265 let (T, cmT) =
266 NIFS::<Projective>::compute_cmT(&pedersen_params, &r1cs, &w1, &ci1, &w2, &ci2).unwrap();
267
268 let poseidon_config = poseidon_test_config::<Fr>();
269
270 let r_bits = ChallengeGadget::<Projective>::get_challenge_native(
271 &poseidon_config,
272 ci1.clone(),
273 ci2.clone(),
274 cmT,
275 )
276 .unwrap();
277 let r_Fr = Fr::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
278
279 let (w3, ci3) =
280 NIFS::<Projective>::fold_instances(r_Fr, &w1, &ci1, &w2, &ci2, &T, cmT).unwrap();
281
282 (
283 pedersen_params,
284 poseidon_config,
285 r1cs,
286 w1,
287 ci1,
288 w2,
289 ci2,
290 w3,
291 ci3,
292 T,
293 cmT,
294 r_bits,
295 r_Fr,
296 )
297 }
298
299 // fold 2 dummy instances and check that the folded instance holds the relaxed R1CS relation
300 #[test]
301 fn test_nifs_fold_dummy() {
302 let r1cs = get_test_r1cs::<Fr>();
303 let z1 = get_test_z(3);
304 let (w1, x1) = r1cs.split_z(&z1);
305
306 let mut rng = ark_std::test_rng();
307 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
308
309 // dummy instance, witness and public inputs zeroes
310 let w_dummy = Witness::<Projective>::new(vec![Fr::zero(); w1.len()], r1cs.A.n_rows);
311 let mut u_dummy = w_dummy
312 .commit(&pedersen_params, vec![Fr::zero(); x1.len()])
313 .unwrap();
314 u_dummy.u = Fr::zero();
315
316 let w_i = w_dummy.clone();
317 let u_i = u_dummy.clone();
318 let W_i = w_dummy.clone();
319 let U_i = u_dummy.clone();
320 r1cs.check_relaxed_instance_relation(&w_i, &u_i).unwrap();
321 r1cs.check_relaxed_instance_relation(&W_i, &U_i).unwrap();
322
323 let r_Fr = Fr::from(3_u32);
324
325 let (T, cmT) =
326 NIFS::<Projective>::compute_cmT(&pedersen_params, &r1cs, &w_i, &u_i, &W_i, &U_i)
327 .unwrap();
328 let (W_i1, U_i1) =
329 NIFS::<Projective>::fold_instances(r_Fr, &w_i, &u_i, &W_i, &U_i, &T, cmT).unwrap();
330 r1cs.check_relaxed_instance_relation(&W_i1, &U_i1).unwrap();
331 }
332
333 // fold 2 instances into one
334 #[test]
335 fn test_nifs_one_fold() {
336 let (pedersen_params, poseidon_config, r1cs, w1, ci1, w2, ci2, w3, ci3, T, cmT, _, r) =
337 prepare_simple_fold_inputs();
338
339 // NIFS.V
340 let ci3_v = NIFS::<Projective>::verify(r, &ci1, &ci2, &cmT);
341 assert_eq!(ci3_v, ci3);
342
343 // check that relations hold for the 2 inputted instances and the folded one
344 r1cs.check_relaxed_instance_relation(&w1, &ci1).unwrap();
345 r1cs.check_relaxed_instance_relation(&w2, &ci2).unwrap();
346 r1cs.check_relaxed_instance_relation(&w3, &ci3).unwrap();
347
348 // check that folded commitments from folded instance (ci) are equal to folding the
349 // use folded rE, rW to commit w3
350 let ci3_expected = w3.commit(&pedersen_params, ci3.x.clone()).unwrap();
351 assert_eq!(ci3_expected.cmE, ci3.cmE);
352 assert_eq!(ci3_expected.cmW, ci3.cmW);
353
354 // next equalities should hold since we started from two cmE of zero-vector E's
355 assert_eq!(ci3.cmE, cmT.mul(r));
356 assert_eq!(w3.E, vec_scalar_mul(&T, &r));
357
358 // NIFS.Verify_Folded_Instance:
359 NIFS::<Projective>::verify_folded_instance(r, &ci1, &ci2, &ci3, &cmT).unwrap();
360
361 // init Prover's transcript
362 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
363 // init Verifier's transcript
364 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
365
366 // check openings of ci3.cmE, ci3.cmW and cmT
367 let cm_proofs = NIFS::<Projective>::open_commitments(
368 &mut transcript_p,
369 &pedersen_params,
370 &w3,
371 &ci3,
372 T,
373 &cmT,
374 )
375 .unwrap();
376
377 NIFS::<Projective>::verify_commitments(
378 &mut transcript_v,
379 &pedersen_params,
380 ci3,
381 cmT,
382 cm_proofs,
383 )
384 .unwrap();
385 }
386
387 #[test]
388 fn test_nifs_fold_loop() {
389 let r1cs = get_test_r1cs();
390 let z = get_test_z(3);
391 let (w, x) = r1cs.split_z(&z);
392
393 let mut rng = ark_std::test_rng();
394 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
395
396 // prepare the running instance
397 let mut running_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
398 let mut running_committed_instance =
399 running_instance_w.commit(&pedersen_params, x).unwrap();
400
401 r1cs.check_relaxed_instance_relation(&running_instance_w, &running_committed_instance)
402 .unwrap();
403
404 let num_iters = 10;
405 for i in 0..num_iters {
406 // prepare the incomming instance
407 let incomming_instance_z = get_test_z(i + 4);
408 let (w, x) = r1cs.split_z(&incomming_instance_z);
409 let incomming_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
410 let incomming_committed_instance =
411 incomming_instance_w.commit(&pedersen_params, x).unwrap();
412 r1cs.check_relaxed_instance_relation(
413 &incomming_instance_w,
414 &incomming_committed_instance,
415 )
416 .unwrap();
417
418 let r = Fr::rand(&mut rng); // folding challenge would come from the RO
419
420 // NIFS.P
421 let (T, cmT) = NIFS::<Projective>::compute_cmT(
422 &pedersen_params,
423 &r1cs,
424 &running_instance_w,
425 &running_committed_instance,
426 &incomming_instance_w,
427 &incomming_committed_instance,
428 )
429 .unwrap();
430 let (folded_w, _) = NIFS::<Projective>::fold_instances(
431 r,
432 &running_instance_w,
433 &running_committed_instance,
434 &incomming_instance_w,
435 &incomming_committed_instance,
436 &T,
437 cmT,
438 )
439 .unwrap();
440
441 // NIFS.V
442 let folded_committed_instance = NIFS::<Projective>::verify(
443 r,
444 &running_committed_instance,
445 &incomming_committed_instance,
446 &cmT,
447 );
448
449 r1cs.check_relaxed_instance_relation(&folded_w, &folded_committed_instance)
450 .unwrap();
451
452 // set running_instance for next loop iteration
453 running_instance_w = folded_w;
454 running_committed_instance = folded_committed_instance;
455 }
456 }
457}