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