sonobe/src/folding/nova/nifs.rs
src/folding/nova/nifs.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_std::One;
4use std::marker::PhantomData;
5
6use crate::ccs::r1cs::R1CS;
7use crate::folding::nova::{CommittedInstance, Witness};
8use crate::pedersen::{Params as PedersenParams, Pedersen, Proof as PedersenProof};
9use crate::transcript::Transcript;
10use crate::utils::vec::*;
11
12pub struct NIFS<C: CurveGroup> {
13 _phantom: PhantomData<C>,
14}
15
16impl<C: CurveGroup> NIFS<C>
17where
18 <C as Group>::ScalarField: Absorb,
19{
20 // compute_T: compute cross-terms T
21 pub fn compute_T(
22 r1cs: &R1CS<C::ScalarField>,
23 u1: C::ScalarField,
24 u2: C::ScalarField,
25 z1: &[C::ScalarField],
26 z2: &[C::ScalarField],
27 ) -> Vec<C::ScalarField> {
28 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
29
30 // this is parallelizable (for the future)
31 let Az1 = mat_vec_mul_sparse(&A, z1);
32 let Bz1 = mat_vec_mul_sparse(&B, z1);
33 let Cz1 = mat_vec_mul_sparse(&C, z1);
34 let Az2 = mat_vec_mul_sparse(&A, z2);
35 let Bz2 = mat_vec_mul_sparse(&B, z2);
36 let Cz2 = mat_vec_mul_sparse(&C, z2);
37
38 let Az1_Bz2 = hadamard(&Az1, &Bz2);
39 let Az2_Bz1 = hadamard(&Az2, &Bz1);
40 let u1Cz2 = vec_scalar_mul(&Cz2, &u1);
41 let u2Cz1 = vec_scalar_mul(&Cz1, &u2);
42
43 vec_sub(&vec_sub(&vec_add(&Az1_Bz2, &Az2_Bz1), &u1Cz2), &u2Cz1)
44 }
45
46 pub fn fold_witness(
47 r: C::ScalarField,
48 w1: &Witness<C>,
49 w2: &Witness<C>,
50 T: &[C::ScalarField],
51 rT: C::ScalarField,
52 ) -> Witness<C> {
53 let r2 = r * r;
54 let E: Vec<C::ScalarField> = vec_add(
55 &vec_add(&w1.E, &vec_scalar_mul(T, &r)),
56 &vec_scalar_mul(&w2.E, &r2),
57 );
58 let rE = w1.rE + r * rT + r2 * w2.rE;
59 let W = vec_add(&w1.W, &vec_scalar_mul(&w2.W, &r));
60 let rW = w1.rW + r * w2.rW;
61 Witness::<C> { E, rE, W, rW }
62 }
63
64 pub fn fold_committed_instance(
65 r: C::ScalarField,
66 ci1: &CommittedInstance<C>,
67 ci2: &CommittedInstance<C>,
68 cmT: &C,
69 ) -> CommittedInstance<C> {
70 let r2 = r * r;
71
72 let cmE = ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2);
73 let u = ci1.u + r * ci2.u;
74 let cmW = ci1.cmW + ci2.cmW.mul(r);
75 let x = vec_add(&ci1.x, &vec_scalar_mul(&ci2.x, &r));
76
77 CommittedInstance::<C> { cmE, u, cmW, x }
78 }
79
80 // NIFS.P
81 #[allow(clippy::type_complexity)]
82 pub fn prove(
83 pedersen_params: &PedersenParams<C>,
84 r: C::ScalarField,
85 r1cs: &R1CS<C::ScalarField>,
86 w1: &Witness<C>,
87 ci1: &CommittedInstance<C>,
88 w2: &Witness<C>,
89 ci2: &CommittedInstance<C>,
90 ) -> (Witness<C>, CommittedInstance<C>, Vec<C::ScalarField>, C) {
91 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
92 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
93
94 // compute cross terms
95 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2);
96 let rT = C::ScalarField::one(); // use 1 as rT since we don't need hiding property for cm(T)
97 let cmT = Pedersen::commit(pedersen_params, &T, &rT);
98
99 // fold witness
100 let w3 = NIFS::<C>::fold_witness(r, w1, w2, &T, rT);
101
102 // fold committed instancs
103 let ci3 = NIFS::<C>::fold_committed_instance(r, ci1, ci2, &cmT);
104
105 (w3, ci3, T, cmT)
106 }
107
108 // NIFS.V
109 pub fn verify(
110 r: C::ScalarField,
111 ci1: &CommittedInstance<C>,
112 ci2: &CommittedInstance<C>,
113 cmT: &C,
114 ) -> CommittedInstance<C> {
115 NIFS::<C>::fold_committed_instance(r, ci1, ci2, cmT)
116 }
117
118 // verify commited folded instance (ci) relations
119 pub fn verify_folded_instance(
120 r: C::ScalarField,
121 ci1: &CommittedInstance<C>,
122 ci2: &CommittedInstance<C>,
123 ci3: &CommittedInstance<C>,
124 cmT: &C,
125 ) -> bool {
126 let r2 = r * r;
127 if ci3.cmE != (ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2)) {
128 return false;
129 }
130 if ci3.u != ci1.u + r * ci2.u {
131 return false;
132 }
133 if ci3.cmW != (ci1.cmW + ci2.cmW.mul(r)) {
134 return false;
135 }
136 if ci3.x != vec_add(&ci1.x, &vec_scalar_mul(&ci2.x, &r)) {
137 return false;
138 }
139 true
140 }
141
142 pub fn open_commitments(
143 tr: &mut impl Transcript<C>,
144 pedersen_params: &PedersenParams<C>,
145 w: &Witness<C>,
146 ci: &CommittedInstance<C>,
147 T: Vec<C::ScalarField>,
148 cmT: &C,
149 ) -> (PedersenProof<C>, PedersenProof<C>, PedersenProof<C>) {
150 let cmE_proof = Pedersen::prove(pedersen_params, tr, &ci.cmE, &w.E, &w.rE);
151 let cmW_proof = Pedersen::prove(pedersen_params, tr, &ci.cmW, &w.W, &w.rW);
152 let cmT_proof = Pedersen::prove(pedersen_params, tr, cmT, &T, &C::ScalarField::one()); // cm(T) is committed with rT=1
153 (cmE_proof, cmW_proof, cmT_proof)
154 }
155 pub fn verify_commitments(
156 tr: &mut impl Transcript<C>,
157 pedersen_params: &PedersenParams<C>,
158 ci: CommittedInstance<C>,
159 cmT: C,
160 cmE_proof: PedersenProof<C>,
161 cmW_proof: PedersenProof<C>,
162 cmT_proof: PedersenProof<C>,
163 ) -> bool {
164 if !Pedersen::verify(pedersen_params, tr, ci.cmE, cmE_proof) {
165 return false;
166 }
167 if !Pedersen::verify(pedersen_params, tr, ci.cmW, cmW_proof) {
168 return false;
169 }
170 if !Pedersen::verify(pedersen_params, tr, cmT, cmT_proof) {
171 return false;
172 }
173 true
174 }
175}
176
177#[cfg(test)]
178mod tests {
179 use super::*;
180 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
181 use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
182 use ark_bls12_377::{Fr, G1Projective};
183 use ark_ff::PrimeField;
184 use ark_std::UniformRand;
185
186 pub fn check_relaxed_r1cs<F: PrimeField>(r1cs: &R1CS<F>, z: Vec<F>, u: F, E: &[F]) {
187 let Az = mat_vec_mul_sparse(&r1cs.A, &z);
188 let Bz = mat_vec_mul_sparse(&r1cs.B, &z);
189 let Cz = mat_vec_mul_sparse(&r1cs.C, &z);
190 assert_eq!(hadamard(&Az, &Bz), vec_add(&vec_scalar_mul(&Cz, &u), E));
191 }
192
193 // fold 2 instances into one
194 #[test]
195 fn test_nifs_one_fold() {
196 let r1cs = get_test_r1cs();
197 let z1 = get_test_z(3);
198 let z2 = get_test_z(4);
199 let (w1, x1) = r1cs.split_z(&z1);
200 let (w2, x2) = r1cs.split_z(&z2);
201
202 let w1 = Witness::<G1Projective>::new(w1.clone(), r1cs.A.n_cols);
203 let w2 = Witness::<G1Projective>::new(w2.clone(), r1cs.A.n_cols);
204
205 let mut rng = ark_std::test_rng();
206 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, r1cs.A.n_cols);
207
208 let r = Fr::rand(&mut rng); // folding challenge would come from the transcript
209
210 // compute committed instances
211 let ci1 = w1.commit(&pedersen_params, x1.clone());
212 let ci2 = w2.commit(&pedersen_params, x2.clone());
213 // NIFS.P
214 let (w3, _, T, cmT) =
215 NIFS::<G1Projective>::prove(&pedersen_params, r, &r1cs, &w1, &ci1, &w2, &ci2);
216
217 // NIFS.V
218 let ci3 = NIFS::<G1Projective>::verify(r, &ci1, &ci2, &cmT);
219
220 // naive check that the folded witness satisfies the relaxed r1cs
221 let z3: Vec<Fr> = [vec![ci3.u], ci3.x.to_vec(), w3.W.to_vec()].concat();
222 // check that z3 is as expected
223 let z3_aux = vec_add(&z1, &vec_scalar_mul(&z2, &r));
224 assert_eq!(z3, z3_aux);
225 // check that relations hold for the 2 inputted instances and the folded one
226 check_relaxed_r1cs(&r1cs, z1, ci1.u, &w1.E);
227 check_relaxed_r1cs(&r1cs, z2, ci2.u, &w2.E);
228 check_relaxed_r1cs(&r1cs, z3, ci3.u, &w3.E);
229
230 // check that folded commitments from folded instance (ci) are equal to folding the
231 // use folded rE, rW to commit w3
232 let ci3_expected = w3.commit(&pedersen_params, ci3.x.clone());
233 assert_eq!(ci3_expected.cmE, ci3.cmE);
234 assert_eq!(ci3_expected.cmW, ci3.cmW);
235
236 // NIFS.Verify_Folded_Instance:
237 assert!(NIFS::<G1Projective>::verify_folded_instance(
238 r, &ci1, &ci2, &ci3, &cmT
239 ));
240
241 let poseidon_config = poseidon_test_config::<Fr>();
242 // init Prover's transcript
243 let mut transcript_p = PoseidonTranscript::<G1Projective>::new(&poseidon_config);
244 // init Verifier's transcript
245 let mut transcript_v = PoseidonTranscript::<G1Projective>::new(&poseidon_config);
246
247 // check openings of ci3.cmE, ci3.cmW and cmT
248 let (cmE_proof, cmW_proof, cmT_proof) = NIFS::<G1Projective>::open_commitments(
249 &mut transcript_p,
250 &pedersen_params,
251 &w3,
252 &ci3,
253 T,
254 &cmT,
255 );
256 let v = NIFS::<G1Projective>::verify_commitments(
257 &mut transcript_v,
258 &pedersen_params,
259 ci3,
260 cmT,
261 cmE_proof,
262 cmW_proof,
263 cmT_proof,
264 );
265 assert!(v);
266 }
267
268 #[test]
269 fn test_nifs_fold_loop() {
270 let r1cs = get_test_r1cs();
271 let z = get_test_z(3);
272 let (w, x) = r1cs.split_z(&z);
273
274 let mut rng = ark_std::test_rng();
275 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, r1cs.A.n_cols);
276
277 // prepare the running instance
278 let mut running_instance_w = Witness::<G1Projective>::new(w.clone(), r1cs.A.n_cols);
279 let mut running_committed_instance = running_instance_w.commit(&pedersen_params, x);
280 check_relaxed_r1cs(
281 &r1cs,
282 z,
283 running_committed_instance.u,
284 &running_instance_w.E,
285 );
286
287 let num_iters = 10;
288 for i in 0..num_iters {
289 // prepare the incomming instance
290 let incomming_instance_z = get_test_z(i + 4);
291 let (w, x) = r1cs.split_z(&incomming_instance_z);
292 let incomming_instance_w = Witness::<G1Projective>::new(w.clone(), r1cs.A.n_cols);
293 let incomming_committed_instance = incomming_instance_w.commit(&pedersen_params, x);
294 check_relaxed_r1cs(
295 &r1cs,
296 incomming_instance_z.clone(),
297 incomming_committed_instance.u,
298 &incomming_instance_w.E,
299 );
300
301 let r = Fr::rand(&mut rng); // folding challenge would come from the transcript
302
303 // NIFS.P
304 let (folded_w, _, _, cmT) = NIFS::<G1Projective>::prove(
305 &pedersen_params,
306 r,
307 &r1cs,
308 &running_instance_w,
309 &running_committed_instance,
310 &incomming_instance_w,
311 &incomming_committed_instance,
312 );
313
314 // NIFS.V
315 let folded_committed_instance = NIFS::<G1Projective>::verify(
316 r,
317 &running_committed_instance,
318 &incomming_committed_instance,
319 &cmT,
320 );
321
322 let folded_z: Vec<Fr> = [
323 vec![folded_committed_instance.u],
324 folded_committed_instance.x.to_vec(),
325 folded_w.W.to_vec(),
326 ]
327 .concat();
328
329 check_relaxed_r1cs(&r1cs, folded_z, folded_committed_instance.u, &folded_w.E);
330
331 // set running_instance for next loop iteration
332 running_instance_w = folded_w;
333 running_committed_instance = folded_committed_instance;
334 }
335 }
336}