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