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