nova-study/src/nifs.rs
src/nifs.rsRaw
1// use ark_ec::AffineRepr;
2use ark_ec::{CurveGroup, Group};
3use ark_ff::fields::PrimeField;
4use ark_std::{One, Zero};
5use std::marker::PhantomData;
6
7use crate::pedersen::{Commitment, Params as PedersenParams, Pedersen, Proof as PedersenProof};
8use crate::transcript::Transcript;
9use crate::utils::*;
10use ark_crypto_primitives::sponge::Absorb;
11
12pub struct R1CS<F: PrimeField> {
13 pub A: Vec<Vec<F>>,
14 pub B: Vec<Vec<F>>,
15 pub C: Vec<Vec<F>>,
16}
17
18// Phi: φ in the paper (later 𝖴), a folded instance
19#[derive(Clone, Debug)]
20pub struct Phi<C: CurveGroup> {
21 pub cmE: Commitment<C>,
22 pub u: C::ScalarField,
23 pub cmW: Commitment<C>,
24 pub x: C::ScalarField,
25}
26
27// FWit: Folded Witness
28pub struct FWit<C: CurveGroup> {
29 pub E: Vec<C::ScalarField>,
30 pub rE: C::ScalarField,
31 pub W: Vec<C::ScalarField>,
32 pub rW: C::ScalarField,
33}
34
35impl<C: CurveGroup> FWit<C>
36where
37 <C as Group>::ScalarField: Absorb,
38 <C as CurveGroup>::BaseField: Absorb,
39{
40 pub fn new(z: Vec<C::ScalarField>, e_len: usize) -> Self {
41 FWit::<C> {
42 E: vec![C::ScalarField::zero(); e_len],
43 rE: C::ScalarField::one(),
44 W: z,
45 rW: C::ScalarField::one(),
46 }
47 }
48 pub fn commit(&self, params: &PedersenParams<C>) -> Phi<C> {
49 let cmE = Pedersen::commit(params, &self.E, &self.rE);
50 let cmW = Pedersen::commit(params, &self.W, &self.rW);
51 Phi {
52 cmE,
53 u: C::ScalarField::one(),
54 cmW,
55 x: self.W[0], // TODO WIP review
56 }
57 }
58}
59
60pub struct NIFS<C: CurveGroup> {
61 _phantom: PhantomData<C>,
62}
63
64impl<C: CurveGroup> NIFS<C>
65where
66 <C as Group>::ScalarField: Absorb,
67 <C as CurveGroup>::BaseField: Absorb,
68{
69 // comp_T: compute cross-terms T
70 pub fn comp_T(
71 r1cs: &R1CS<C::ScalarField>,
72 u1: C::ScalarField,
73 u2: C::ScalarField,
74 z1: &[C::ScalarField],
75 z2: &[C::ScalarField],
76 ) -> Vec<C::ScalarField> {
77 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
78
79 // this is parallelizable (for the future)
80 let Az1 = matrix_vector_product(&A, z1);
81 let Bz1 = matrix_vector_product(&B, z1);
82 let Cz1 = matrix_vector_product(&C, z1);
83 let Az2 = matrix_vector_product(&A, z2);
84 let Bz2 = matrix_vector_product(&B, z2);
85 let Cz2 = matrix_vector_product(&C, z2);
86
87 let Az1_Bz2 = hadamard_product(Az1, Bz2);
88 let Az2_Bz1 = hadamard_product(Az2, Bz1);
89 let u1Cz2 = vector_elem_product(&Cz2, &u1);
90 let u2Cz1 = vector_elem_product(&Cz1, &u2);
91
92 // let T = vec_sub(vec_sub(vec_add(Az1_Bz2, Az2_Bz1), u1Cz2), u2Cz1);
93 let T = ((Ve(Az1_Bz2) + Ve(Az2_Bz1)) - Ve(u1Cz2)) - Ve(u2Cz1);
94 T.0
95 }
96
97 pub fn fold_witness(
98 r: C::ScalarField,
99 fw1: &FWit<C>,
100 fw2: &FWit<C>,
101 T: &Vec<C::ScalarField>,
102 rT: C::ScalarField,
103 ) -> FWit<C> {
104 let r2 = r * r;
105 let E: Vec<C::ScalarField> = vec_add(
106 // this syntax will be simplified with future operators impl (or at least a method
107 // for r-lin)
108 &vec_add(&fw1.E, &vector_elem_product(T, &r)),
109 &vector_elem_product(&fw2.E, &r2),
110 );
111 let rE = fw1.rE + r * rT + r2 * fw2.rE;
112 let W = vec_add(&fw1.W, &vector_elem_product(&fw2.W, &r));
113 let rW = fw1.rW + r * fw2.rW;
114 FWit::<C> { E, rE, W, rW }
115 }
116
117 pub fn fold_instance(
118 r: C::ScalarField,
119 phi1: &Phi<C>,
120 phi2: &Phi<C>,
121 cmT: &Commitment<C>,
122 ) -> Phi<C> {
123 let r2 = r * r;
124
125 let cmE = phi1.cmE.0 + cmT.0.mul(r) + phi2.cmE.0.mul(r2);
126 let u = phi1.u + r * phi2.u;
127 let cmW = phi1.cmW.0 + phi2.cmW.0.mul(r);
128 // let x = vec_add(&phi1.x, &vector_elem_product(&phi2.x, &r));
129 let x = phi1.x + r * phi2.x;
130
131 Phi::<C> {
132 cmE: Commitment(cmE),
133 u,
134 cmW: Commitment(cmW),
135 x,
136 }
137 }
138
139 // NIFS.P
140 #[allow(clippy::type_complexity)]
141 pub fn P(
142 tr: &mut Transcript<C::ScalarField, C>,
143 pedersen_params: &PedersenParams<C>,
144 r: C::ScalarField,
145 r1cs: &R1CS<C::ScalarField>,
146 fw1: FWit<C>,
147 fw2: FWit<C>,
148 ) -> (FWit<C>, Phi<C>, Phi<C>, Vec<C::ScalarField>, Commitment<C>) {
149 // compute committed instances
150 let phi1 = fw1.commit(pedersen_params); // wip
151 let phi2 = fw2.commit(pedersen_params);
152
153 // compute cross terms
154 let T = Self::comp_T(r1cs, phi1.u, phi2.u, &fw1.W, &fw2.W);
155 let rT = tr.get_challenge(); // r_T
156 let cmT = Pedersen::commit(pedersen_params, &T, &rT);
157
158 // fold witness
159 let fw3 = NIFS::<C>::fold_witness(r, &fw1, &fw2, &T, rT);
160
161 // fold committed instancs
162 // let phi3 = NIFS::<C>::fold_instance(r, &phi1, &phi2, &cmT);
163 (fw3, phi1, phi2, T, cmT) // maybe return phi3
164 }
165
166 // NIFS.V
167 pub fn V(r: C::ScalarField, phi1: &Phi<C>, phi2: &Phi<C>, cmT: &Commitment<C>) -> Phi<C> {
168 NIFS::<C>::fold_instance(r, phi1, phi2, cmT)
169 }
170
171 // verify commited folded instance (phi) relations
172 pub fn verify(
173 r: C::ScalarField,
174 phi1: &Phi<C>,
175 phi2: &Phi<C>,
176 phi3: &Phi<C>,
177 cmT: &Commitment<C>,
178 ) -> bool {
179 let r2 = r * r;
180 if phi3.cmE.0 != (phi1.cmE.0 + cmT.0.mul(r) + phi2.cmE.0.mul(r2)) {
181 return false;
182 }
183 if phi3.u != phi1.u + r * phi2.u {
184 return false;
185 }
186 if phi3.cmW.0 != (phi1.cmW.0 + phi2.cmW.0.mul(r)) {
187 return false;
188 }
189 // if phi3.x != vec_add(&phi1.x, &vector_elem_product(&phi2.x, &r)) {
190 if phi3.x != phi1.x + r * phi2.x {
191 return false;
192 }
193 true
194 }
195
196 pub fn open_commitments(
197 tr: &mut Transcript<C::ScalarField, C>,
198 pedersen_params: &PedersenParams<C>,
199 fw: &FWit<C>,
200 phi: &Phi<C>,
201 T: Vec<C::ScalarField>,
202 rT: C::ScalarField,
203 cmT: &Commitment<C>,
204 ) -> (PedersenProof<C>, PedersenProof<C>, PedersenProof<C>) {
205 let cmE_proof = Pedersen::prove(pedersen_params, tr, &phi.cmE, &fw.E, &fw.rE);
206 let cmW_proof = Pedersen::prove(pedersen_params, tr, &phi.cmW, &fw.W, &fw.rW);
207 let cmT_proof = Pedersen::prove(pedersen_params, tr, cmT, &T, &rT);
208 (cmE_proof, cmW_proof, cmT_proof)
209 }
210 pub fn verify_commitments(
211 tr: &mut Transcript<C::ScalarField, C>,
212 pedersen_params: &PedersenParams<C>,
213 phi: Phi<C>,
214 cmT: Commitment<C>,
215 cmE_proof: PedersenProof<C>,
216 cmW_proof: PedersenProof<C>,
217 cmT_proof: PedersenProof<C>,
218 ) -> bool {
219 if !Pedersen::verify(pedersen_params, tr, phi.cmE, cmE_proof) {
220 return false;
221 }
222 if !Pedersen::verify(pedersen_params, tr, phi.cmW, cmW_proof) {
223 return false;
224 }
225 if !Pedersen::verify(pedersen_params, tr, cmT, cmT_proof) {
226 return false;
227 }
228 true
229 }
230}
231
232// only for tests across different files
233pub fn gen_test_values<F: PrimeField>(n: usize) -> (R1CS<F>, Vec<Vec<F>>, Vec<Vec<F>>) {
234 // R1CS for: x^3 + x + 5 = y (example from article
235 // https://www.vitalik.ca/general/2016/12/10/qap.html )
236 let A = to_F_matrix::<F>(vec![
237 vec![0, 1, 0, 0, 0, 0],
238 vec![0, 0, 0, 1, 0, 0],
239 vec![0, 1, 0, 0, 1, 0],
240 vec![5, 0, 0, 0, 0, 1],
241 ]);
242 let B = to_F_matrix::<F>(vec![
243 vec![0, 1, 0, 0, 0, 0],
244 vec![0, 1, 0, 0, 0, 0],
245 vec![1, 0, 0, 0, 0, 0],
246 vec![1, 0, 0, 0, 0, 0],
247 ]);
248 let C = to_F_matrix::<F>(vec![
249 vec![0, 0, 0, 1, 0, 0],
250 vec![0, 0, 0, 0, 1, 0],
251 vec![0, 0, 0, 0, 0, 1],
252 vec![0, 0, 1, 0, 0, 0],
253 ]);
254
255 // generate n witnesses
256 let mut w: Vec<Vec<F>> = Vec::new();
257 let mut x: Vec<Vec<F>> = Vec::new();
258 for i in 0..n {
259 let input = 3 + i;
260 let w_i = to_F_vec::<F>(vec![
261 1,
262 input,
263 input * input * input + input + 5, // x^3 + x + 5
264 input * input, // x^2
265 input * input * input, // x^2 * x
266 input * input * input + input, // x^3 + x
267 ]);
268 w.push(w_i.clone());
269 let x_i = to_F_vec::<F>(vec![input * input * input + input + 5]);
270 x.push(x_i.clone());
271 }
272
273 let r1cs = R1CS::<F> { A, B, C };
274 (r1cs, w, x)
275}
276
277#[cfg(test)]
278mod tests {
279 use super::*;
280 use crate::pedersen::Pedersen;
281 use crate::transcript::poseidon_test_config;
282 use ark_mnt4_298::{Fr, G1Projective};
283 use ark_std::One;
284 use ark_std::UniformRand;
285
286 // fold 2 instances into one
287 #[test]
288 fn test_one_fold() {
289 let mut rng = ark_std::test_rng();
290 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
291 let poseidon_config = poseidon_test_config::<Fr>();
292
293 let (r1cs, ws, _) = gen_test_values(2);
294 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
295
296 let r = Fr::rand(&mut rng); // this would come from the transcript
297
298 let fw1 = FWit::<G1Projective>::new(ws[0].clone(), A.len());
299 let fw2 = FWit::<G1Projective>::new(ws[1].clone(), A.len());
300
301 // get committed instances
302 let phi1 = fw1.commit(&pedersen_params); // wip
303 let phi2 = fw2.commit(&pedersen_params);
304
305 let T = NIFS::<G1Projective>::comp_T(&r1cs, phi1.u, phi2.u, &ws[0], &ws[1]);
306 let rT: Fr = Fr::rand(&mut rng);
307 let cmT = Pedersen::commit(&pedersen_params, &T, &rT);
308
309 // fold witness
310 let fw3 = NIFS::<G1Projective>::fold_witness(r, &fw1, &fw2, &T, rT);
311
312 // fold instance
313 let phi3 = NIFS::<G1Projective>::fold_instance(r, &phi1, &phi2, &cmT);
314
315 // naive check that the folded witness satisfies the relaxed r1cs
316 let Az = matrix_vector_product(&A, &fw3.W);
317 let Bz = matrix_vector_product(&B, &fw3.W);
318 let Cz = matrix_vector_product(&C, &fw3.W);
319 assert_eq!(
320 hadamard_product(Az, Bz),
321 vec_add(&vector_elem_product(&Cz, &phi3.u), &fw3.E)
322 );
323
324 // check that folded commitments from folded instance (phi) are equal to folding the
325 // use folded rE, rW to commit fw3
326 let phi3_expected = fw3.commit(&pedersen_params);
327 assert_eq!(phi3_expected.cmE.0, phi3.cmE.0);
328 assert_eq!(phi3_expected.cmW.0, phi3.cmW.0);
329
330 // NIFS.Verify:
331 assert!(NIFS::<G1Projective>::verify(r, &phi1, &phi2, &phi3, &cmT));
332
333 // init Prover's transcript
334 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
335 // init Verifier's transcript
336 let mut transcript_v = Transcript::<Fr, G1Projective>::new(&poseidon_config);
337
338 // check openings of phi3.cmE, phi3.cmW and cmT
339 let (cmE_proof, cmW_proof, cmT_proof) = NIFS::<G1Projective>::open_commitments(
340 &mut transcript_p,
341 &pedersen_params,
342 &fw3,
343 &phi3,
344 T,
345 rT,
346 &cmT,
347 );
348 let v = NIFS::<G1Projective>::verify_commitments(
349 &mut transcript_v,
350 &pedersen_params,
351 phi3,
352 cmT,
353 cmE_proof,
354 cmW_proof,
355 cmT_proof,
356 );
357 assert!(v);
358 }
359
360 // fold i_1, i_2 instances into i_12, and then i_12, i_3 into i_123
361 #[test]
362 fn test_two_fold() {
363 let mut rng = ark_std::test_rng();
364 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, 6);
365 let poseidon_config = poseidon_test_config::<Fr>();
366
367 let (r1cs, ws, _) = gen_test_values(3);
368
369 let u1: Fr = Fr::one();
370 let u2: Fr = Fr::one();
371
372 let T_12 = NIFS::<G1Projective>::comp_T(&r1cs, u1, u2, &ws[0], &ws[1]);
373 let rT_12: Fr = Fr::rand(&mut rng);
374 let cmT_12 = Pedersen::commit(&pedersen_params, &T_12, &rT_12);
375
376 let r = Fr::rand(&mut rng); // this would come from the transcript
377
378 let fw1 = FWit::<G1Projective>::new(ws[0].clone(), T_12.len());
379 let fw2 = FWit::<G1Projective>::new(ws[1].clone(), T_12.len());
380
381 // fold witness
382 let fw_12 = NIFS::<G1Projective>::fold_witness(r, &fw1, &fw2, &T_12, rT_12);
383
384 // get committed instances
385 let phi1 = fw1.commit(&pedersen_params); // wip
386 let phi2 = fw2.commit(&pedersen_params);
387
388 // fold instance
389 let phi_12 = NIFS::<G1Projective>::fold_instance(r, &phi1, &phi2, &cmT_12);
390
391 // NIFS.Verify:
392 assert!(NIFS::<G1Projective>::verify(
393 r, &phi1, &phi2, &phi_12, &cmT_12
394 ));
395
396 //----
397 // 2nd fold
398 let fw3 = FWit::<G1Projective>::new(ws[2].clone(), r1cs.A.len());
399
400 // compute cross terms
401 let T_123 = NIFS::<G1Projective>::comp_T(&r1cs, phi_12.u, Fr::one(), &fw_12.W, &fw3.W);
402 let rT_123: Fr = Fr::rand(&mut rng);
403 let cmT_123 = Pedersen::commit(&pedersen_params, &T_123, &rT_123);
404
405 // V sets rand challenge r
406 let r = Fr::rand(&mut rng); // this would come from the transcript
407
408 // fold witness
409 let fw_123 = NIFS::<G1Projective>::fold_witness(r, &fw_12, &fw3, &T_123, rT_123);
410
411 // get committed instances
412 // phi_12 is already known for Verifier from folding phi1, phi2
413 // rm: let phi_12 = fw_12.commit(&pedersen_params); // wip
414 let phi3 = fw3.commit(&pedersen_params);
415
416 // fold instance
417 let phi_123 = NIFS::<G1Projective>::fold_instance(r, &phi_12, &phi3, &cmT_123);
418
419 // NIFS.Verify:
420 assert!(NIFS::<G1Projective>::verify(
421 r, &phi_12, &phi3, &phi_123, &cmT_123
422 ));
423
424 // naive check that the folded witness satisfies the relaxed r1cs
425 let Az = matrix_vector_product(&r1cs.A, &fw_123.W);
426 let Bz = matrix_vector_product(&r1cs.B, &fw_123.W);
427 let Cz = matrix_vector_product(&r1cs.C, &fw_123.W);
428 assert_eq!(
429 hadamard_product(Az, Bz),
430 vec_add(&vector_elem_product(&Cz, &phi_123.u), &fw_123.E)
431 );
432
433 // check that folded commitments from folded instance (phi) are equal to folding the
434 // use folded rE, rW to commit fw3
435 let phi_123_expected = fw_123.commit(&pedersen_params);
436 assert_eq!(phi_123_expected.cmE.0, phi_123.cmE.0);
437 assert_eq!(phi_123_expected.cmW.0, phi_123.cmW.0);
438
439 // init Prover's transcript
440 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
441 // init Verifier's transcript
442 let mut transcript_v = Transcript::<Fr, G1Projective>::new(&poseidon_config);
443
444 // check openings of phi_123.cmE, phi_123.cmW and cmT_123
445 let (cmE_proof, cmW_proof, cmT_proof) = NIFS::<G1Projective>::open_commitments(
446 &mut transcript_p,
447 &pedersen_params,
448 &fw_123,
449 &phi_123,
450 T_123,
451 rT_123,
452 &cmT_123,
453 );
454 let v = NIFS::<G1Projective>::verify_commitments(
455 &mut transcript_v,
456 &pedersen_params,
457 phi_123,
458 cmT_123,
459 cmE_proof,
460 cmW_proof,
461 cmT_proof,
462 );
463 assert!(v);
464 }
465
466 #[test]
467 fn test_nifs_interface() {
468 let mut rng = ark_std::test_rng();
469 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
470 let poseidon_config = poseidon_test_config::<Fr>();
471
472 let (r1cs, ws, _) = gen_test_values(3);
473 let (A, _, _) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
474
475 let r = Fr::rand(&mut rng); // this would come from the transcript
476
477 let fw1 = FWit::<G1Projective>::new(ws[0].clone(), A.len());
478 let fw2 = FWit::<G1Projective>::new(ws[1].clone(), A.len());
479
480 // init Prover's transcript
481 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
482
483 // NIFS.P
484 let (_fw3, phi1, phi2, _T, cmT) =
485 NIFS::<G1Projective>::P(&mut transcript_p, &pedersen_params, r, &r1cs, fw1, fw2);
486
487 // init Verifier's transcript
488 // let mut transcript_v = Transcript::<Fr, G1Projective>::new(&poseidon_config);
489
490 // NIFS.V
491 let phi3 = NIFS::<G1Projective>::V(r, &phi1, &phi2, &cmT);
492
493 assert!(NIFS::<G1Projective>::verify(r, &phi1, &phi2, &phi3, &cmT));
494 }
495}