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::*;
 11use crate::Error;
 12
 13/// Implements the Non-Interactive Folding Scheme described in section 4 of
 14/// 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
 89    #[allow(clippy::type_complexity)]
 90    pub fn prove(
 91        pedersen_params: &PedersenParams<C>,
 92        // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
 93        r: C::ScalarField,
 94        r1cs: &R1CS<C::ScalarField>,
 95        w1: &Witness<C>,
 96        ci1: &CommittedInstance<C>,
 97        w2: &Witness<C>,
 98        ci2: &CommittedInstance<C>,
 99    ) -> Result<(Witness<C>, CommittedInstance<C>, Vec<C::ScalarField>, C), Error> {
100        let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
101        let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
102
103        // compute cross terms
104        let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
105        let rT = C::ScalarField::one(); // use 1 as rT since we don't need hiding property for cm(T)
106        let cmT = Pedersen::commit(pedersen_params, &T, &rT)?;
107
108        // fold witness
109        let w3 = NIFS::<C>::fold_witness(r, w1, w2, &T, rT)?;
110
111        // fold committed instancs
112        let ci3 = NIFS::<C>::fold_committed_instance(r, ci1, ci2, &cmT);
113
114        Ok((w3, ci3, T, cmT))
115    }
116
117    // NIFS.V
118    pub fn verify(
119        // r comes from the transcript, and is a n-bit (N_BITS_CHALLENGE) element
120        r: C::ScalarField,
121        ci1: &CommittedInstance<C>,
122        ci2: &CommittedInstance<C>,
123        cmT: &C,
124    ) -> CommittedInstance<C> {
125        NIFS::<C>::fold_committed_instance(r, ci1, ci2, cmT)
126    }
127
128    /// Verify commited folded instance (ci) relations. Notice that this method does not open the
129    /// commitments, but just checks that the given committed instances (ci1, ci2) when folded
130    /// result in the folded committed instance (ci3) values.
131    pub fn verify_folded_instance(
132        r: C::ScalarField,
133        ci1: &CommittedInstance<C>,
134        ci2: &CommittedInstance<C>,
135        ci3: &CommittedInstance<C>,
136        cmT: &C,
137    ) -> Result<(), Error> {
138        let r2 = r * r;
139        if ci3.cmE != (ci1.cmE + cmT.mul(r) + ci2.cmE.mul(r2))
140            || ci3.u != ci1.u + r * ci2.u
141            || ci3.cmW != (ci1.cmW + ci2.cmW.mul(r))
142            || ci3.x != vec_add(&ci1.x, &vec_scalar_mul(&ci2.x, &r))?
143        {
144            return Err(Error::NotSatisfied);
145        }
146        Ok(())
147    }
148
149    pub fn open_commitments(
150        tr: &mut impl Transcript<C>,
151        pedersen_params: &PedersenParams<C>,
152        w: &Witness<C>,
153        ci: &CommittedInstance<C>,
154        T: Vec<C::ScalarField>,
155        cmT: &C,
156    ) -> Result<[PedersenProof<C>; 3], Error> {
157        let cmE_proof = Pedersen::prove(pedersen_params, tr, &ci.cmE, &w.E, &w.rE)?;
158        let cmW_proof = Pedersen::prove(pedersen_params, tr, &ci.cmW, &w.W, &w.rW)?;
159        let cmT_proof = Pedersen::prove(pedersen_params, tr, cmT, &T, &C::ScalarField::one())?; // cm(T) is committed with rT=1
160        Ok([cmE_proof, cmW_proof, cmT_proof])
161    }
162    pub fn verify_commitments(
163        tr: &mut impl Transcript<C>,
164        pedersen_params: &PedersenParams<C>,
165        ci: CommittedInstance<C>,
166        cmT: C,
167        cm_proofs: [PedersenProof<C>; 3],
168    ) -> Result<(), Error> {
169        if cm_proofs.len() != 3 {
170            // cm_proofs should have length 3: [cmE_proof, cmW_proof, cmT_proof]
171            return Err(Error::NotExpectedLength);
172        }
173        Pedersen::verify(pedersen_params, tr, ci.cmE, cm_proofs[0].clone())?;
174        Pedersen::verify(pedersen_params, tr, ci.cmW, cm_proofs[1].clone())?;
175        Pedersen::verify(pedersen_params, tr, cmT, cm_proofs[2].clone())?;
176        Ok(())
177    }
178}
179
180#[cfg(test)]
181pub mod tests {
182    use super::*;
183    use ark_ff::PrimeField;
184    use ark_pallas::{Fr, Projective};
185    use ark_std::{ops::Mul, UniformRand, Zero};
186
187    use crate::ccs::r1cs::tests::{get_test_r1cs, get_test_z};
188    use crate::transcript::poseidon::{tests::poseidon_test_config, PoseidonTranscript};
189    use crate::utils::vec::vec_scalar_mul;
190
191    pub fn check_relaxed_r1cs<F: PrimeField>(r1cs: &R1CS<F>, z: &[F], u: &F, E: &[F]) -> bool {
192        let Az = mat_vec_mul_sparse(&r1cs.A, z);
193        let Bz = mat_vec_mul_sparse(&r1cs.B, z);
194        let Cz = mat_vec_mul_sparse(&r1cs.C, z);
195        hadamard(&Az, &Bz).unwrap() == vec_add(&vec_scalar_mul(&Cz, u), E).unwrap()
196    }
197
198    // fold 2 dummy instances and check that the folded instance holds the relaxed R1CS relation
199    #[test]
200    fn test_nifs_fold_dummy() {
201        let r1cs = get_test_r1cs::<Fr>();
202        let z1 = get_test_z(3);
203        let (w1, x1) = r1cs.split_z(&z1);
204
205        let mut rng = ark_std::test_rng();
206        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
207
208        // dummy instance, witness and public inputs zeroes
209        let w_dummy = Witness::<Projective>::new(vec![Fr::zero(); w1.len()], r1cs.A.n_rows);
210        let mut u_dummy = w_dummy
211            .commit(&pedersen_params, vec![Fr::zero(); x1.len()])
212            .unwrap();
213        u_dummy.u = Fr::zero();
214
215        let w_i = w_dummy.clone();
216        let u_i = u_dummy.clone();
217        let W_i = w_dummy.clone();
218        let U_i = u_dummy.clone();
219        let z_dummy = vec![Fr::zero(); z1.len()];
220        assert!(check_relaxed_r1cs(&r1cs, &z_dummy, &u_i.u, &w_i.E));
221        assert!(check_relaxed_r1cs(&r1cs, &z_dummy, &U_i.u, &W_i.E));
222
223        let r_Fr = Fr::from(3_u32);
224
225        let (W_i1, U_i1, _, _) =
226            NIFS::<Projective>::prove(&pedersen_params, r_Fr, &r1cs, &w_i, &u_i, &W_i, &U_i)
227                .unwrap();
228
229        let z: Vec<Fr> = [vec![U_i1.u], U_i1.x.to_vec(), W_i1.W.to_vec()].concat();
230        assert_eq!(z.len(), z1.len());
231        assert!(check_relaxed_r1cs(&r1cs, &z, &U_i1.u, &W_i1.E));
232    }
233
234    // fold 2 instances into one
235    #[test]
236    fn test_nifs_one_fold() {
237        let r1cs = get_test_r1cs();
238        let z1 = get_test_z(3);
239        let z2 = get_test_z(4);
240        let (w1, x1) = r1cs.split_z(&z1);
241        let (w2, x2) = r1cs.split_z(&z2);
242
243        let w1 = Witness::<Projective>::new(w1.clone(), r1cs.A.n_rows);
244        let w2 = Witness::<Projective>::new(w2.clone(), r1cs.A.n_rows);
245
246        let mut rng = ark_std::test_rng();
247        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
248
249        let r = Fr::rand(&mut rng); // folding challenge would come from the transcript
250
251        // compute committed instances
252        let ci1 = w1.commit(&pedersen_params, x1.clone()).unwrap();
253        let ci2 = w2.commit(&pedersen_params, x2.clone()).unwrap();
254
255        // NIFS.P
256        let (w3, ci3_aux, T, cmT) =
257            NIFS::<Projective>::prove(&pedersen_params, r, &r1cs, &w1, &ci1, &w2, &ci2).unwrap();
258
259        // NIFS.V
260        let ci3 = NIFS::<Projective>::verify(r, &ci1, &ci2, &cmT);
261        assert_eq!(ci3, ci3_aux);
262
263        // naive check that the folded witness satisfies the relaxed r1cs
264        let z3: Vec<Fr> = [vec![ci3.u], ci3.x.to_vec(), w3.W.to_vec()].concat();
265        // check that z3 is as expected
266        let z3_aux = vec_add(&z1, &vec_scalar_mul(&z2, &r)).unwrap();
267        assert_eq!(z3, z3_aux);
268        // check that relations hold for the 2 inputted instances and the folded one
269        assert!(check_relaxed_r1cs(&r1cs, &z1, &ci1.u, &w1.E));
270        assert!(check_relaxed_r1cs(&r1cs, &z2, &ci2.u, &w2.E));
271        assert!(check_relaxed_r1cs(&r1cs, &z3, &ci3.u, &w3.E));
272
273        // check that folded commitments from folded instance (ci) are equal to folding the
274        // use folded rE, rW to commit w3
275        let ci3_expected = w3.commit(&pedersen_params, ci3.x.clone()).unwrap();
276        assert_eq!(ci3_expected.cmE, ci3.cmE);
277        assert_eq!(ci3_expected.cmW, ci3.cmW);
278
279        // next equalities should hold since we started from two cmE of zero-vector E's
280        assert_eq!(ci3.cmE, cmT.mul(r));
281        assert_eq!(w3.E, vec_scalar_mul(&T, &r));
282
283        // NIFS.Verify_Folded_Instance:
284        NIFS::<Projective>::verify_folded_instance(r, &ci1, &ci2, &ci3, &cmT).unwrap();
285
286        let poseidon_config = poseidon_test_config::<Fr>();
287        // init Prover's transcript
288        let mut transcript_p = PoseidonTranscript::<Projective>::new(&poseidon_config);
289        // init Verifier's transcript
290        let mut transcript_v = PoseidonTranscript::<Projective>::new(&poseidon_config);
291
292        // check openings of ci3.cmE, ci3.cmW and cmT
293        let cm_proofs = NIFS::<Projective>::open_commitments(
294            &mut transcript_p,
295            &pedersen_params,
296            &w3,
297            &ci3,
298            T,
299            &cmT,
300        )
301        .unwrap();
302
303        NIFS::<Projective>::verify_commitments(
304            &mut transcript_v,
305            &pedersen_params,
306            ci3,
307            cmT,
308            cm_proofs,
309        )
310        .unwrap();
311    }
312
313    #[test]
314    fn test_nifs_fold_loop() {
315        let r1cs = get_test_r1cs();
316        let z = get_test_z(3);
317        let (w, x) = r1cs.split_z(&z);
318
319        let mut rng = ark_std::test_rng();
320        let pedersen_params = Pedersen::<Projective>::new_params(&mut rng, r1cs.A.n_cols);
321
322        // prepare the running instance
323        let mut running_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
324        let mut running_committed_instance =
325            running_instance_w.commit(&pedersen_params, x).unwrap();
326        assert!(check_relaxed_r1cs(
327            &r1cs,
328            &z,
329            &running_committed_instance.u,
330            &running_instance_w.E,
331        ));
332
333        let num_iters = 10;
334        for i in 0..num_iters {
335            // prepare the incomming instance
336            let incomming_instance_z = get_test_z(i + 4);
337            let (w, x) = r1cs.split_z(&incomming_instance_z);
338            let incomming_instance_w = Witness::<Projective>::new(w.clone(), r1cs.A.n_rows);
339            let incomming_committed_instance =
340                incomming_instance_w.commit(&pedersen_params, x).unwrap();
341            assert!(check_relaxed_r1cs(
342                &r1cs,
343                &incomming_instance_z.clone(),
344                &incomming_committed_instance.u,
345                &incomming_instance_w.E,
346            ));
347
348            let r = Fr::rand(&mut rng); // folding challenge would come from the transcript
349
350            // NIFS.P
351            let (folded_w, _, _, cmT) = NIFS::<Projective>::prove(
352                &pedersen_params,
353                r,
354                &r1cs,
355                &running_instance_w,
356                &running_committed_instance,
357                &incomming_instance_w,
358                &incomming_committed_instance,
359            )
360            .unwrap();
361
362            // NIFS.V
363            let folded_committed_instance = NIFS::<Projective>::verify(
364                r,
365                &running_committed_instance,
366                &incomming_committed_instance,
367                &cmT,
368            );
369
370            let folded_z: Vec<Fr> = [
371                vec![folded_committed_instance.u],
372                folded_committed_instance.x.to_vec(),
373                folded_w.W.to_vec(),
374            ]
375            .concat();
376
377            assert!(check_relaxed_r1cs(
378                &r1cs,
379                &folded_z,
380                &folded_committed_instance.u,
381                &folded_w.E
382            ));
383
384            // set running_instance for next loop iteration
385            running_instance_w = folded_w;
386            running_committed_instance = folded_committed_instance;
387        }
388    }
389}