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>, // TODO do not contain Commitment, only Commitment.cm (without the randomness)
17 u: C::ScalarField,
18 cmW: Commitment<C>, // TODO same as in cmE
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 commit(&self, params: &PedersenParams<C>, x: &Vec<C::ScalarField>) -> Phi<C> {
32 let cmE = Pedersen::commit(¶ms, &self.E, &self.rE);
33 let cmW = Pedersen::commit(¶ms, &self.W, &self.rW);
34 Phi {
35 cmE,
36 u: C::ScalarField::one(),
37 cmW,
38 x: x.clone(),
39 }
40 }
41}
42
43pub struct NIFS<C: AffineRepr> {
44 _phantom: PhantomData<C>,
45}
46
47impl<C: AffineRepr> NIFS<C> {
48 pub fn comp_T(
49 cs1: RelaxedR1CS<C::ScalarField>,
50 cs2: RelaxedR1CS<C::ScalarField>,
51 z1: &Vec<C::ScalarField>,
52 z2: &Vec<C::ScalarField>,
53 ) -> Vec<C::ScalarField> {
54 // assuming cs1.R1CS == cs2.R1CS
55 let (A, B, C) = (cs1.ABC.A, cs1.ABC.B, cs1.ABC.C);
56
57 // this is parallelizable (for the future)
58 let Az1 = matrix_vector_product(&A, &z1);
59 let Bz1 = matrix_vector_product(&B, &z1);
60 let Cz1 = matrix_vector_product(&C, &z1);
61 let Az2 = matrix_vector_product(&A, &z2);
62 let Bz2 = matrix_vector_product(&B, &z2);
63 let Cz2 = matrix_vector_product(&C, &z2);
64
65 let Az1_Bz2 = hadamard_product(Az1, Bz2);
66 let Az2_Bz1 = hadamard_product(Az2, Bz1);
67 let u1Cz2 = vector_elem_product(&Cz2, &cs1.u);
68 let u2Cz1 = vector_elem_product(&Cz1, &cs2.u);
69
70 // let T = vec_sub(vec_sub(vec_add(Az1_Bz2, Az2_Bz1), u1Cz2), u2Cz1);
71 let T = ((Ve(Az1_Bz2) + Ve(Az2_Bz1)) - Ve(u1Cz2)) - Ve(u2Cz1);
72 T.0
73 }
74
75 pub fn fold_witness(
76 r: C::ScalarField,
77 fw1: &FWit<C>,
78 fw2: &FWit<C>,
79 T: Vec<C::ScalarField>,
80 rT: C::ScalarField,
81 ) -> FWit<C> {
82 let r2 = r * r;
83 let E: Vec<C::ScalarField> = vec_add(
84 // this syntax will be simplified with future operators impl (or at least a method
85 // for r-lin)
86 &vec_add(&fw1.E, &vector_elem_product(&T, &r)),
87 &vector_elem_product(&fw2.E, &r2),
88 );
89 let rE = fw1.rE + r * rT + r2 * fw2.rE;
90 let W = vec_add(&fw1.W, &vector_elem_product(&fw2.W, &r));
91 let rW = fw1.rW + r * fw2.rW;
92 FWit::<C> {
93 E: E.into(),
94 rE,
95 W: W.into(),
96 rW,
97 }
98 }
99
100 pub fn fold_instance(
101 r: C::ScalarField,
102 phi1: Phi<C>,
103 phi2: Phi<C>,
104 cmT: Commitment<C>,
105 ) -> Phi<C> {
106 let r2 = r * r;
107
108 let cmE = phi1.cmE.0 + cmT.0.mul(r) + phi2.cmE.0.mul(r2);
109 let u = phi1.u + r * phi2.u;
110 let cmW = phi1.cmW.0 + phi2.cmW.0.mul(r);
111 let x = vec_add(&phi1.x, &vector_elem_product(&phi2.x, &r));
112 // let x = rlin(phi1.x, phi2.x, r);
113
114 Phi::<C> {
115 cmE: Commitment(cmE.into()),
116 u,
117 cmW: Commitment(cmW.into()),
118 x,
119 }
120 }
121}
122
123#[cfg(test)]
124mod tests {
125 use super::*;
126 use crate::pedersen::Pedersen;
127 use ark_bn254::{g1::G1Affine, Fr};
128 use ark_ec::CurveGroup;
129 use ark_std::{
130 rand::{Rng, RngCore},
131 UniformRand,
132 };
133 use ark_std::{One, Zero};
134 use std::ops::Mul;
135
136 #[test]
137 fn test_simple_folding() {
138 let mut rng = ark_std::test_rng();
139
140 // R1CS for: x^3 + x + 5 = y (example from article
141 // https://www.vitalik.ca/general/2016/12/10/qap.html )
142 let A = to_F_matrix::<Fr>(vec![
143 vec![0, 1, 0, 0, 0, 0],
144 vec![0, 0, 0, 1, 0, 0],
145 vec![0, 1, 0, 0, 1, 0],
146 vec![5, 0, 0, 0, 0, 1],
147 ]);
148 let B = to_F_matrix::<Fr>(vec![
149 vec![0, 1, 0, 0, 0, 0],
150 vec![0, 1, 0, 0, 0, 0],
151 vec![1, 0, 0, 0, 0, 0],
152 vec![1, 0, 0, 0, 0, 0],
153 ]);
154 let C = to_F_matrix::<Fr>(vec![
155 vec![0, 0, 0, 1, 0, 0],
156 vec![0, 0, 0, 0, 1, 0],
157 vec![0, 0, 0, 0, 0, 1],
158 vec![0, 0, 1, 0, 0, 0],
159 ]);
160 let z1 = to_F_vec::<Fr>(vec![1, 3, 35, 9, 27, 30]);
161 let x1 = to_F_vec::<Fr>(vec![35]);
162 let z2 = to_F_vec::<Fr>(vec![1, 4, 73, 16, 64, 68]);
163 let x2 = to_F_vec::<Fr>(vec![73]);
164
165 let relaxed_r1cs_1 = R1CS::<Fr> {
166 A: A.clone(),
167 B: B.clone(),
168 C: C.clone(),
169 }
170 .relax();
171 let relaxed_r1cs_2 = R1CS::<Fr> {
172 A: A.clone(),
173 B: B.clone(),
174 C: C.clone(),
175 }
176 .relax();
177
178 let T = NIFS::<G1Affine>::comp_T(relaxed_r1cs_1, relaxed_r1cs_2, &z1, &z2);
179 let pedersen_params = Pedersen::<G1Affine>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
180 let rT: Fr = Fr::rand(&mut rng);
181 let cmT = Pedersen::commit(&pedersen_params, &T, &rT);
182
183 let r = Fr::rand(&mut rng); // this would come from the transcript
184
185 // WIP TMP
186 let fw1 = FWit::<G1Affine> {
187 E: vec![Fr::zero(); T.len()],
188 rE: Fr::one(),
189 W: z1,
190 rW: Fr::one(),
191 };
192 let fw2 = FWit::<G1Affine> {
193 E: vec![Fr::zero(); T.len()],
194 rE: Fr::one(),
195 W: z2,
196 rW: Fr::one(),
197 };
198
199 // fold witness
200 let fw3 = NIFS::<G1Affine>::fold_witness(r, &fw1, &fw2, T, rT);
201
202 // get committed instances
203 let phi1 = fw1.commit(&pedersen_params, &x1); // wip
204 let phi2 = fw2.commit(&pedersen_params, &x2);
205
206 // fold instance
207 let phi3 = NIFS::<G1Affine>::fold_instance(r, phi1, phi2, cmT);
208
209 // naive check that the folded witness satisfies the relaxed r1cs
210 let Az = matrix_vector_product(&A, &fw3.W);
211 let Bz = matrix_vector_product(&B, &fw3.W);
212 let Cz = matrix_vector_product(&C, &fw3.W);
213 assert_eq!(
214 hadamard_product(Az, Bz),
215 vec_add(&vector_elem_product(&Cz, &phi3.u), &fw3.E)
216 );
217
218 // check that folded commitments from folded instance (phi) are equal to folding the
219 // witnesses and committing into it
220 let x3 = vec_add(&x1, &vector_elem_product(&x2, &r));
221 // use folded rE, rW to commit fw3
222 let phi3_expected = fw3.commit(&pedersen_params, &x3);
223 assert_eq!(phi3_expected.cmE.0, phi3.cmE.0);
224 assert_eq!(phi3_expected.cmW.0, phi3.cmW.0);
225
226 // init Prover's transcript
227 let mut transcript_p: Transcript<Fr> = Transcript::<Fr>::new();
228 // init Verifier's transcript
229 let mut transcript_v: Transcript<Fr> = Transcript::<Fr>::new();
230
231 // check openings of phi3.cmE and phi3.cmW
232 let phi3_cmE_proof = Pedersen::prove(
233 &pedersen_params,
234 &mut transcript_p,
235 &phi3.cmE,
236 fw3.E,
237 fw3.rE,
238 );
239 let v = Pedersen::verify(
240 &pedersen_params,
241 &mut transcript_v,
242 phi3.cmE,
243 phi3_cmE_proof,
244 );
245
246 let phi3_cmW_proof = Pedersen::prove(
247 &pedersen_params,
248 &mut transcript_p,
249 &phi3.cmW,
250 fw3.W,
251 fw3.rW,
252 );
253 let v = Pedersen::verify(
254 &pedersen_params,
255 &mut transcript_v,
256 phi3.cmW,
257 phi3_cmW_proof,
258 );
259 }
260}