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