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 super::{CommittedInstance, Witness};
7use crate::ccs::r1cs::R1CS;
8use crate::pedersen::{Params as PedersenParams, Pedersen, Proof as PedersenProof};
9use crate::transcript::Transcript;
10use crate::utils::vec::*;
11use crate::Error;
12
13/// Implements the Non-Interactive Folding Scheme described in section 4 of
14/// [Nova](https://eprint.iacr.org/2021/370.pdf)
15pub struct NIFS<C: CurveGroup> {
16 _phantom: PhantomData<C>,
17}
18
19impl<C: CurveGroup> NIFS<C>
20where
21 <C as Group>::ScalarField: Absorb,
22{
23 // compute_T: compute cross-terms T
24 pub fn compute_T(
25 r1cs: &R1CS<C::ScalarField>,
26 u1: C::ScalarField,
27 u2: C::ScalarField,
28 z1: &[C::ScalarField],
29 z2: &[C::ScalarField],
30 ) -> Result<Vec<C::ScalarField>, Error> {
31 let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
32
33 // this is parallelizable (for the future)
34 let Az1 = mat_vec_mul_sparse(&A, z1)?;
35 let Bz1 = mat_vec_mul_sparse(&B, z1)?;
36 let Cz1 = mat_vec_mul_sparse(&C, z1)?;
37 let Az2 = mat_vec_mul_sparse(&A, z2)?;
38 let Bz2 = mat_vec_mul_sparse(&B, z2)?;
39 let Cz2 = mat_vec_mul_sparse(&C, z2)?;
40
41 let Az1_Bz2 = hadamard(&Az1, &Bz2)?;
42 let Az2_Bz1 = hadamard(&Az2, &Bz1)?;
43 let u1Cz2 = vec_scalar_mul(&Cz2, &u1);
44 let u2Cz1 = vec_scalar_mul(&Cz1, &u2);
45
46 vec_sub(&vec_sub(&vec_add(&Az1_Bz2, &Az2_Bz1)?, &u1Cz2)?, &u2Cz1)
47 }
48
49 pub fn fold_witness(
50 r: C::ScalarField,
51 w1: &Witness<C>,
52 w2: &Witness<C>,
53 T: &[C::ScalarField],
54 rT: C::ScalarField,
55 ) -> Result<Witness<C>, Error> {
56 let r2 = r * r;
57 let E: Vec<C::ScalarField> = vec_add(
58 &vec_add(&w1.E, &vec_scalar_mul(T, &r))?,
59 &vec_scalar_mul(&w2.E, &r2),
60 )?;
61 let rE = w1.rE + r * rT + r2 * w2.rE;
62 let W: Vec<C::ScalarField> = w1.W.iter().zip(&w2.W).map(|(a, b)| *a + (r * b)).collect();
63
64 let rW = w1.rW + r * w2.rW;
65 Ok(Witness::<C> { E, rE, W, rW })
66 }
67
68 pub fn fold_committed_instance(
69 r: C::ScalarField,
70 ci1: &CommittedInstance<C>,
71 ci2: &CommittedInstance<C>,
72 cmT: &C,
73 ) -> CommittedInstance<C> {
74 let r2 = r * r;
75 let cmE = ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2);
76 let u = ci1.u + r * ci2.u;
77 let cmW = ci1.cmW + ci2.cmW.mul(r);
78 let x = ci1
79 .x
80 .iter()
81 .zip(&ci2.x)
82 .map(|(a, b)| *a + (r * b))
83 .collect::<Vec<C::ScalarField>>();
84
85 CommittedInstance::<C> { cmE, u, cmW, x }
86 }
87
88 /// NIFS.P is the consecutive combination of compute_cmT with fold_instances
89
90 /// compute_cmT is part of the NIFS.P logic
91 pub fn compute_cmT(
92 pedersen_params: &PedersenParams<C>,
93 r1cs: &R1CS<C::ScalarField>,
94 w1: &Witness<C>,
95 ci1: &CommittedInstance<C>,
96 w2: &Witness<C>,
97 ci2: &CommittedInstance<C>,
98 ) -> Result<(Vec<C::ScalarField>, C), Error> {
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 // use r_T=1 since we don't need hiding property for cm(T)
105 let cmT = Pedersen::commit(pedersen_params, &T, &C::ScalarField::one())?;
106 Ok((T, cmT))
107 }
108 pub fn compute_cyclefold_cmT(
109 pedersen_params: &PedersenParams<C>,
110 r1cs: &R1CS<C::ScalarField>, // R1CS over C2.Fr=C1.Fq (here C=C2)
111 w1: &Witness<C>,
112 ci1: &CommittedInstance<C>,
113 w2: &Witness<C>,
114 ci2: &CommittedInstance<C>,
115 ) -> Result<(Vec<C::ScalarField>, C), Error>
116 where
117 <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
118 {
119 let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
120 let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
121
122 // compute cross terms
123 let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
124 // use r_T=1 since we don't need hiding property for cm(T)
125 let cmT = Pedersen::commit(pedersen_params, &T, &C::ScalarField::one())?;
126 Ok((T, cmT))
127 }
128
129 /// fold_instances is part of the NIFS.P logic described in
130 /// [Nova](https://eprint.iacr.org/2021/370.pdf)'s section 4. It returns the folded Committed
131 /// Instances and the Witness.
132 pub fn fold_instances(
133 r: C::ScalarField,
134 w1: &Witness<C>,
135 ci1: &CommittedInstance<C>,
136 w2: &Witness<C>,
137 ci2: &CommittedInstance<C>,
138 T: &[C::ScalarField],
139 cmT: C,
140 ) -> Result<(Witness<C>, CommittedInstance<C>), Error> {
141 // fold witness
142 // use r_T=1 since we don't need hiding property for cm(T)
143 let w3 = NIFS::<C>::fold_witness(r, w1, w2, T, C::ScalarField::one())?;
144
145 // fold committed instancs
146 let ci3 = NIFS::<C>::fold_committed_instance(r, ci1, ci2, &cmT);
147
148 Ok((w3, ci3))
149 }
150
151 /// verify implements NIFS.V logic described in [Nova](https://eprint.iacr.org/2021/370.pdf)'s
152 /// section 4. It returns the folded Committed Instance
153 pub fn verify(
154 // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
155 r: C::ScalarField,
156 ci1: &CommittedInstance<C>,
157 ci2: &CommittedInstance<C>,
158 cmT: &C,
159 ) -> CommittedInstance<C> {
160 NIFS::<C>::fold_committed_instance(r, ci1, ci2, cmT)
161 }
162
163 /// Verify commited folded instance (ci) relations. Notice that this method does not open the
164 /// commitments, but just checks that the given committed instances (ci1, ci2) when folded
165 /// result in the folded committed instance (ci3) values.
166 pub fn verify_folded_instance(
167 r: C::ScalarField,
168 ci1: &CommittedInstance<C>,
169 ci2: &CommittedInstance<C>,
170 ci3: &CommittedInstance<C>,
171 cmT: &C,
172 ) -> Result<(), Error> {
173 let expected = Self::fold_committed_instance(r, ci1, ci2, cmT);
174 if ci3.cmE != expected.cmE
175 || ci3.u != expected.u
176 || ci3.cmW != expected.cmW
177 || ci3.x != expected.x
178 {
179 return Err(Error::NotSatisfied);
180 }
181 Ok(())
182 }
183
184 pub fn open_commitments(
185 tr: &mut impl Transcript<C>,
186 pedersen_params: &PedersenParams<C>,
187 w: &Witness<C>,
188 ci: &CommittedInstance<C>,
189 T: Vec<C::ScalarField>,
190 cmT: &C,
191 ) -> Result<[PedersenProof<C>; 3], Error> {
192 let cmE_proof = Pedersen::prove(pedersen_params, tr, &ci.cmE, &w.E, &w.rE)?;
193 let cmW_proof = Pedersen::prove(pedersen_params, tr, &ci.cmW, &w.W, &w.rW)?;
194 let cmT_proof = Pedersen::prove(pedersen_params, tr, cmT, &T, &C::ScalarField::one())?; // cm(T) is committed with rT=1
195 Ok([cmE_proof, cmW_proof, cmT_proof])
196 }
197 pub fn verify_commitments(
198 tr: &mut impl Transcript<C>,
199 pedersen_params: &PedersenParams<C>,
200 ci: CommittedInstance<C>,
201 cmT: C,
202 cm_proofs: [PedersenProof<C>; 3],
203 ) -> Result<(), Error> {
204 if cm_proofs.len() != 3 {
205 // cm_proofs should have length 3: [cmE_proof, cmW_proof, cmT_proof]
206 return Err(Error::NotExpectedLength(cm_proofs.len(), 3));
207 }
208 Pedersen::verify(pedersen_params, tr, ci.cmE, cm_proofs[0].clone())?;
209 Pedersen::verify(pedersen_params, tr, ci.cmW, cm_proofs[1].clone())?;
210 Pedersen::verify(pedersen_params, tr, cmT, cm_proofs[2].clone())?;
211 Ok(())
212 }
213}
214
215#[cfg(test)]
216pub mod tests {
217 use super::*;
218 use ark_ff::{BigInteger, PrimeField};
219 use ark_pallas::{Fr, Projective};
220 use ark_std::{ops::Mul, UniformRand, Zero};
221
222 use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
223 use crate::folding::nova::circuits::ChallengeGadget;
224 use crate::folding::nova::traits::NovaR1CS;
225 use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
226 use crate::utils::vec::vec_scalar_mul;
227 use ark_crypto_primitives::sponge::poseidon::PoseidonConfig;
228
229 #[allow(clippy::type_complexity)]
230 pub(crate) fn prepare_simple_fold_inputs() -> (
231 PedersenParams<Projective>,
232 PoseidonConfig<Fr>,
233 R1CS<Fr>,
234 Witness<Projective>, // w1
235 CommittedInstance<Projective>, // ci1
236 Witness<Projective>, // w2
237 CommittedInstance<Projective>, // ci2
238 Witness<Projective>, // w3
239 CommittedInstance<Projective>, // ci3
240 Vec<Fr>, // T
241 Projective, // cmT
242 Vec<bool>, // r_bits
243 Fr, // r_Fr
244 ) {
245 let r1cs = get_test_r1cs();
246 let z1 = get_test_z(3);
247 let z2 = get_test_z(4);
248 let (w1, x1) = r1cs.split_z(&z1);
249 let (w2, x2) = r1cs.split_z(&z2);
250
251 let w1 = Witness::<Projective>::new(w1.clone(), r1cs.A.n_rows);
252 let w2 = Witness::<Projective>::new(w2.clone(), r1cs.A.n_rows);
253
254 let mut rng = ark_std::test_rng();
255 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
256
257 // compute committed instances
258 let ci1 = w1.commit(&pedersen_params, x1.clone()).unwrap();
259 let ci2 = w2.commit(&pedersen_params, x2.clone()).unwrap();
260
261 // NIFS.P
262 let (T, cmT) =
263 NIFS::<Projective>::compute_cmT(&pedersen_params, &r1cs, &w1, &ci1, &w2, &ci2).unwrap();
264
265 let poseidon_config = poseidon_test_config::<Fr>();
266
267 let r_bits = ChallengeGadget::<Projective>::get_challenge_native(
268 &poseidon_config,
269 ci1.clone(),
270 ci2.clone(),
271 cmT,
272 )
273 .unwrap();
274 let r_Fr = Fr::from_bigint(BigInteger::from_bits_le(&r_bits)).unwrap();
275
276 let (w3, ci3) =
277 NIFS::<Projective>::fold_instances(r_Fr, &w1, &ci1, &w2, &ci2, &T, cmT).unwrap();
278
279 (
280 pedersen_params,
281 poseidon_config,
282 r1cs,
283 w1,
284 ci1,
285 w2,
286 ci2,
287 w3,
288 ci3,
289 T,
290 cmT,
291 r_bits,
292 r_Fr,
293 )
294 }
295
296 // fold 2 dummy instances and check that the folded instance holds the relaxed R1CS relation
297 #[test]
298 fn test_nifs_fold_dummy() {
299 let r1cs = get_test_r1cs::<Fr>();
300 let z1 = get_test_z(3);
301 let (w1, x1) = r1cs.split_z(&z1);
302
303 let mut rng = ark_std::test_rng();
304 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
305
306 // dummy instance, witness and public inputs zeroes
307 let w_dummy = Witness::<Projective>::new(vec![Fr::zero(); w1.len()], r1cs.A.n_rows);
308 let mut u_dummy = w_dummy
309 .commit(&pedersen_params, vec![Fr::zero(); x1.len()])
310 .unwrap();
311 u_dummy.u = Fr::zero();
312
313 let w_i = w_dummy.clone();
314 let u_i = u_dummy.clone();
315 let W_i = w_dummy.clone();
316 let U_i = u_dummy.clone();
317 r1cs.check_relaxed_instance_relation(&w_i, &u_i).unwrap();
318 r1cs.check_relaxed_instance_relation(&W_i, &U_i).unwrap();
319
320 let r_Fr = Fr::from(3_u32);
321
322 let (T, cmT) =
323 NIFS::<Projective>::compute_cmT(&pedersen_params, &r1cs, &w_i, &u_i, &W_i, &U_i)
324 .unwrap();
325 let (W_i1, U_i1) =
326 NIFS::<Projective>::fold_instances(r_Fr, &w_i, &u_i, &W_i, &U_i, &T, cmT).unwrap();
327 r1cs.check_relaxed_instance_relation(&W_i1, &U_i1).unwrap();
328 }
329
330 // fold 2 instances into one
331 #[test]
332 fn test_nifs_one_fold() {
333 let (pedersen_params, poseidon_config, r1cs, w1, ci1, w2, ci2, w3, ci3, T, cmT, _, r) =
334 prepare_simple_fold_inputs();
335
336 // NIFS.V
337 let ci3_v = NIFS::<Projective>::verify(r, &ci1, &ci2, &cmT);
338 assert_eq!(ci3_v, ci3);
339
340 // check that relations hold for the 2 inputted instances and the folded one
341 r1cs.check_relaxed_instance_relation(&w1, &ci1).unwrap();
342 r1cs.check_relaxed_instance_relation(&w2, &ci2).unwrap();
343 r1cs.check_relaxed_instance_relation(&w3, &ci3).unwrap();
344
345 // check that folded commitments from folded instance (ci) are equal to folding the
346 // use folded rE, rW to commit w3
347 let ci3_expected = w3.commit(&pedersen_params, ci3.x.clone()).unwrap();
348 assert_eq!(ci3_expected.cmE, ci3.cmE);
349 assert_eq!(ci3_expected.cmW, ci3.cmW);
350
351 // next equalities should hold since we started from two cmE of zero-vector E's
352 assert_eq!(ci3.cmE, cmT.mul(r));
353 assert_eq!(w3.E, vec_scalar_mul(&T, &r));
354
355 // NIFS.Verify_Folded_Instance:
356 NIFS::<Projective>::verify_folded_instance(r, &ci1, &ci2, &ci3, &cmT).unwrap();
357
358 // init Prover's transcript
359 let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
360 // init Verifier's transcript
361 let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
362
363 // check openings of ci3.cmE, ci3.cmW and cmT
364 let cm_proofs = NIFS::<Projective>::open_commitments(
365 &mut transcript_p,
366 &pedersen_params,
367 &w3,
368 &ci3,
369 T,
370 &cmT,
371 )
372 .unwrap();
373
374 NIFS::<Projective>::verify_commitments(
375 &mut transcript_v,
376 &pedersen_params,
377 ci3,
378 cmT,
379 cm_proofs,
380 )
381 .unwrap();
382 }
383
384 #[test]
385 fn test_nifs_fold_loop() {
386 let r1cs = get_test_r1cs();
387 let z = get_test_z(3);
388 let (w, x) = r1cs.split_z(&z);
389
390 let mut rng = ark_std::test_rng();
391 let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
392
393 // prepare the running instance
394 let mut running_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
395 let mut running_committed_instance =
396 running_instance_w.commit(&pedersen_params, x).unwrap();
397
398 r1cs.check_relaxed_instance_relation(&running_instance_w, &running_committed_instance)
399 .unwrap();
400
401 let num_iters = 10;
402 for i in 0..num_iters {
403 // prepare the incomming instance
404 let incomming_instance_z = get_test_z(i + 4);
405 let (w, x) = r1cs.split_z(&incomming_instance_z);
406 let incomming_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
407 let incomming_committed_instance =
408 incomming_instance_w.commit(&pedersen_params, x).unwrap();
409 r1cs.check_relaxed_instance_relation(
410 &incomming_instance_w,
411 &incomming_committed_instance,
412 )
413 .unwrap();
414
415 let r = Fr::rand(&mut rng); // folding challenge would come from the RO
416
417 // NIFS.P
418 let (T, cmT) = NIFS::<Projective>::compute_cmT(
419 &pedersen_params,
420 &r1cs,
421 &running_instance_w,
422 &running_committed_instance,
423 &incomming_instance_w,
424 &incomming_committed_instance,
425 )
426 .unwrap();
427 let (folded_w, _) = NIFS::<Projective>::fold_instances(
428 r,
429 &running_instance_w,
430 &running_committed_instance,
431 &incomming_instance_w,
432 &incomming_committed_instance,
433 &T,
434 cmT,
435 )
436 .unwrap();
437
438 // NIFS.V
439 let folded_committed_instance = NIFS::<Projective>::verify(
440 r,
441 &running_committed_instance,
442 &incomming_committed_instance,
443 &cmT,
444 );
445
446 r1cs.check_relaxed_instance_relation(&folded_w, &folded_committed_instance)
447 .unwrap();
448
449 // set running_instance for next loop iteration
450 running_instance_w = folded_w;
451 running_committed_instance = folded_committed_instance;
452 }
453 }
454}