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