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