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};
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 pub fn comp_T(
57 cs1: &RelaxedR1CS<C::ScalarField>,
58 cs2: &RelaxedR1CS<C::ScalarField>,
59 z1: &Vec<C::ScalarField>,
60 z2: &Vec<C::ScalarField>,
61 ) -> Vec<C::ScalarField> {
62 // assuming cs1.R1CS == cs2.R1CS
63 let (A, B, C) = (cs1.ABC.A.clone(), cs1.ABC.B.clone(), cs1.ABC.C.clone());
64
65 // this is parallelizable (for the future)
66 let Az1 = matrix_vector_product(&A, &z1);
67 let Bz1 = matrix_vector_product(&B, &z1);
68 let Cz1 = matrix_vector_product(&C, &z1);
69 let Az2 = matrix_vector_product(&A, &z2);
70 let Bz2 = matrix_vector_product(&B, &z2);
71 let Cz2 = matrix_vector_product(&C, &z2);
72
73 let Az1_Bz2 = hadamard_product(Az1, Bz2);
74 let Az2_Bz1 = hadamard_product(Az2, Bz1);
75 let u1Cz2 = vector_elem_product(&Cz2, &cs1.u);
76 let u2Cz1 = vector_elem_product(&Cz1, &cs2.u);
77
78 // let T = vec_sub(vec_sub(vec_add(Az1_Bz2, Az2_Bz1), u1Cz2), u2Cz1);
79 let T = ((Ve(Az1_Bz2) + Ve(Az2_Bz1)) - Ve(u1Cz2)) - Ve(u2Cz1);
80 T.0
81 }
82
83 pub fn fold_witness(
84 r: C::ScalarField,
85 fw1: &FWit<C>,
86 fw2: &FWit<C>,
87 T: Vec<C::ScalarField>,
88 rT: C::ScalarField,
89 ) -> FWit<C> {
90 // TODO compute T inside this method, and output cmT to be later inputed into fold_instance
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
132#[cfg(test)]
133mod tests {
134 use super::*;
135 use crate::pedersen::Pedersen;
136 use ark_bn254::{g1::G1Affine, Fr};
137 use ark_ec::CurveGroup;
138 use ark_std::{
139 rand::{Rng, RngCore},
140 UniformRand,
141 };
142 use ark_std::{One, Zero};
143 use std::ops::Mul;
144
145 fn gen_test_values<R: Rng>(
146 rng: &mut R,
147 ) -> (
148 RelaxedR1CS<Fr>,
149 RelaxedR1CS<Fr>,
150 Vec<Fr>,
151 Vec<Fr>,
152 Vec<Fr>,
153 Vec<Fr>,
154 Vec<Fr>,
155 Vec<Fr>,
156 ) {
157 // R1CS for: x^3 + x + 5 = y (example from article
158 // https://www.vitalik.ca/general/2016/12/10/qap.html )
159 let A = to_F_matrix::<Fr>(vec![
160 vec![0, 1, 0, 0, 0, 0],
161 vec![0, 0, 0, 1, 0, 0],
162 vec![0, 1, 0, 0, 1, 0],
163 vec![5, 0, 0, 0, 0, 1],
164 ]);
165 let B = to_F_matrix::<Fr>(vec![
166 vec![0, 1, 0, 0, 0, 0],
167 vec![0, 1, 0, 0, 0, 0],
168 vec![1, 0, 0, 0, 0, 0],
169 vec![1, 0, 0, 0, 0, 0],
170 ]);
171 let C = to_F_matrix::<Fr>(vec![
172 vec![0, 0, 0, 1, 0, 0],
173 vec![0, 0, 0, 0, 1, 0],
174 vec![0, 0, 0, 0, 0, 1],
175 vec![0, 0, 1, 0, 0, 0],
176 ]);
177 // TODO in the future update this method to generate witness, and generate n witnesses
178 // instances
179 let z1 = to_F_vec::<Fr>(vec![1, 3, 35, 9, 27, 30]);
180 let x1 = to_F_vec::<Fr>(vec![35]);
181 let z2 = to_F_vec::<Fr>(vec![1, 4, 73, 16, 64, 68]);
182 let x2 = to_F_vec::<Fr>(vec![73]);
183 // let z3 = to_F_vec::<Fr>(vec![1, 4, 73, 16, 64, 68]);
184 // let x3 = to_F_vec::<Fr>(vec![73]);
185 let z3 = to_F_vec::<Fr>(vec![1, 5, 135, 25, 125, 130]);
186 let x3 = to_F_vec::<Fr>(vec![135]);
187
188 let relaxed_r1cs_1 = R1CS::<Fr> {
189 A: A.clone(),
190 B: B.clone(),
191 C: C.clone(),
192 }
193 .relax();
194 let relaxed_r1cs_2 = R1CS::<Fr> {
195 A: A.clone(),
196 B: B.clone(),
197 C: C.clone(),
198 }
199 .relax();
200 (relaxed_r1cs_1, relaxed_r1cs_2, z1, z2, z3, x1, x2, x3)
201 }
202
203 // fold 2 instances into one
204 #[test]
205 fn test_one_fold() {
206 let mut rng = ark_std::test_rng();
207 let (relaxed_r1cs_1, relaxed_r1cs_2, z1, z2, _, x1, x2, _) = gen_test_values(&mut rng);
208 let (A, B, C) = (
209 relaxed_r1cs_1.ABC.A.clone(),
210 relaxed_r1cs_1.ABC.B.clone(),
211 relaxed_r1cs_1.ABC.C.clone(),
212 );
213
214 let T = NIFS::<G1Affine>::comp_T(&relaxed_r1cs_1, &relaxed_r1cs_2, &z1, &z2);
215 let pedersen_params = Pedersen::<G1Affine>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
216 let rT: Fr = Fr::rand(&mut rng);
217 let cmT = Pedersen::commit(&pedersen_params, &T, &rT);
218
219 let r = Fr::rand(&mut rng); // this would come from the transcript
220
221 let fw1 = FWit::<G1Affine>::new(z1, A.len());
222 let fw2 = FWit::<G1Affine>::new(z2, A.len());
223
224 // fold witness
225 let fw3 = NIFS::<G1Affine>::fold_witness(r, &fw1, &fw2, T, rT);
226
227 // get committed instances
228 let phi1 = fw1.commit(&pedersen_params); // wip
229 let phi2 = fw2.commit(&pedersen_params);
230
231 // fold instance
232 let phi3 = NIFS::<G1Affine>::fold_instance(r, phi1, phi2, cmT);
233
234 // naive check that the folded witness satisfies the relaxed r1cs
235 let Az = matrix_vector_product(&A, &fw3.W);
236 let Bz = matrix_vector_product(&B, &fw3.W);
237 let Cz = matrix_vector_product(&C, &fw3.W);
238 assert_eq!(
239 hadamard_product(Az, Bz),
240 vec_add(&vector_elem_product(&Cz, &phi3.u), &fw3.E)
241 );
242
243 // check that folded commitments from folded instance (phi) are equal to folding the
244 // use folded rE, rW to commit fw3
245 let phi3_expected = fw3.commit(&pedersen_params);
246 assert_eq!(phi3_expected.cmE.0, phi3.cmE.0);
247 assert_eq!(phi3_expected.cmW.0, phi3.cmW.0);
248
249 // init Prover's transcript
250 let mut transcript_p: Transcript<Fr> = Transcript::<Fr>::new();
251 // init Verifier's transcript
252 let mut transcript_v: Transcript<Fr> = Transcript::<Fr>::new();
253
254 // check openings of phi3.cmE and phi3.cmW
255 let phi3_cmE_proof = Pedersen::prove(
256 &pedersen_params,
257 &mut transcript_p,
258 &phi3.cmE,
259 fw3.E,
260 fw3.rE,
261 );
262 let v = Pedersen::verify(
263 &pedersen_params,
264 &mut transcript_v,
265 phi3.cmE,
266 phi3_cmE_proof,
267 );
268
269 let phi3_cmW_proof = Pedersen::prove(
270 &pedersen_params,
271 &mut transcript_p,
272 &phi3.cmW,
273 fw3.W,
274 fw3.rW,
275 );
276 let v = Pedersen::verify(
277 &pedersen_params,
278 &mut transcript_v,
279 phi3.cmW,
280 phi3_cmW_proof,
281 );
282 }
283
284 // fold i_1, i_2 instances into i_12, and then i_12, i_3 into i_123
285 #[test]
286 fn test_two_fold() {
287 let mut rng = ark_std::test_rng();
288 let pedersen_params = Pedersen::<G1Affine>::new_params(&mut rng, 6);
289
290 let (relaxed_r1cs_1, relaxed_r1cs_2, z1, z2, z3, x1, x2, x3) = gen_test_values(&mut rng);
291
292 let T_12 = NIFS::<G1Affine>::comp_T(&relaxed_r1cs_1, &relaxed_r1cs_2, &z1, &z2);
293 let rT_12: Fr = Fr::rand(&mut rng);
294 let cmT_12 = Pedersen::commit(&pedersen_params, &T_12, &rT_12);
295
296 // let r = Fr::rand(&mut rng); // this would come from the transcript
297 let r = Fr::from(3_u32);
298
299 let fw1 = FWit::<G1Affine>::new(z1, T_12.len());
300 let fw2 = FWit::<G1Affine>::new(z2, T_12.len());
301
302 // fold witness
303 let fw_12 = NIFS::<G1Affine>::fold_witness(r, &fw1, &fw2, T_12, rT_12);
304
305 // get committed instances
306 let phi1 = fw1.commit(&pedersen_params); // wip
307 let phi2 = fw2.commit(&pedersen_params);
308
309 // fold instance
310 let phi_12 = NIFS::<G1Affine>::fold_instance(r, phi1, phi2, cmT_12);
311
312 // 2nd fold
313 // tmp: set relaxed_r1cs instances
314 let relaxed_r1cs_12 = RelaxedR1CS::<Fr> {
315 ABC: relaxed_r1cs_1.ABC,
316 u: phi_12.u,
317 E: Fr::zero(), // not used in comp_T. TODO update RelaxedR1CS & comp_T to work different
318 };
319 let relaxed_r1cs_3 = RelaxedR1CS::<Fr> {
320 ABC: relaxed_r1cs_2.ABC,
321 u: Fr::one(), // as this is a non-yet-folded instance
322 E: Fr::zero(),
323 };
324 let fw3 = FWit::<G1Affine>::new(z3, relaxed_r1cs_3.ABC.A.len());
325
326 // compute cross terms
327 let T_123 = NIFS::<G1Affine>::comp_T(&relaxed_r1cs_12, &relaxed_r1cs_3, &fw_12.W, &fw3.W);
328 // let rT_123: Fr = Fr::rand(&mut rng);
329 let rT_123: Fr = rT_12.clone(); // TMP TODO
330 let cmT_123 = Pedersen::commit(&pedersen_params, &T_123, &rT_123);
331
332 // V sets rand challenge r
333 // let r = Fr::rand(&mut rng); // this would come from the transcript
334
335 // fold witness
336 let fw_123 = NIFS::<G1Affine>::fold_witness(r, &fw_12, &fw3, T_123, rT_123);
337
338 // get committed instances
339 // phi_12 is already known for Verifier from folding phi1, phi2
340 // rm: let phi_12 = fw_12.commit(&pedersen_params); // wip
341 let phi3 = fw3.commit(&pedersen_params);
342
343 // fold instance
344 let phi_123 = NIFS::<G1Affine>::fold_instance(r, phi_12, phi3, cmT_123);
345
346 // naive check that the folded witness satisfies the relaxed r1cs
347 let Az = matrix_vector_product(&relaxed_r1cs_3.ABC.A, &fw_123.W);
348 let Bz = matrix_vector_product(&relaxed_r1cs_3.ABC.B, &fw_123.W);
349 let Cz = matrix_vector_product(&relaxed_r1cs_3.ABC.C, &fw_123.W);
350 assert_eq!(
351 hadamard_product(Az, Bz),
352 vec_add(&vector_elem_product(&Cz, &phi_123.u), &fw_123.E)
353 );
354
355 // check that folded commitments from folded instance (phi) are equal to folding the
356 // use folded rE, rW to commit fw3
357 let phi_123_expected = fw_123.commit(&pedersen_params);
358 assert_eq!(phi_123_expected.cmE.0, phi_123.cmE.0);
359 assert_eq!(phi_123_expected.cmW.0, phi_123.cmW.0);
360
361 // init Prover's transcript
362 let mut transcript_p: Transcript<Fr> = Transcript::<Fr>::new();
363 // init Verifier's transcript
364 let mut transcript_v: Transcript<Fr> = Transcript::<Fr>::new();
365
366 // check openings of phi_123.cmE and phi_123.cmW
367 let phi_123_cmE_proof = Pedersen::prove(
368 &pedersen_params,
369 &mut transcript_p,
370 &phi_123.cmE,
371 fw_123.E,
372 fw_123.rE,
373 );
374 let v = Pedersen::verify(
375 &pedersen_params,
376 &mut transcript_v,
377 phi_123.cmE,
378 phi_123_cmE_proof,
379 );
380
381 let phi_123_cmW_proof = Pedersen::prove(
382 &pedersen_params,
383 &mut transcript_p,
384 &phi_123.cmW,
385 fw_123.W,
386 fw_123.rW,
387 );
388 let v = Pedersen::verify(
389 &pedersen_params,
390 &mut transcript_v,
391 phi_123.cmW,
392 phi_123_cmW_proof,
393 );
394 }
395}