1use ark_ec::AffineRepr;
  2use ark_std::ops::Add;
  3use ark_std::One;
  4use std::marker::PhantomData;
  5
  6use crate::pedersen::{Commitment, Params as PedersenParams, Pedersen};
  7use crate::r1cs::*;
  8use crate::transcript::Transcript;
  9use crate::utils::*;
 10use ark_std::{
 11    rand::{Rng, RngCore},
 12    UniformRand,
 13};
 14
 15// Phi: φ in the paper (later 𝖴), a folded instance
 16pub struct Phi<C: AffineRepr> {
 17    cmE: Commitment<C>,
 18    u: C::ScalarField,
 19    cmW: Commitment<C>,
 20    x: Vec<C::ScalarField>,
 21}
 22
 23// FWit: Folded Witness
 24pub struct FWit<C: AffineRepr> {
 25    E: Vec<C::ScalarField>,
 26    W: Vec<C::ScalarField>,
 27}
 28
 29impl<C: AffineRepr> FWit<C> {
 30    pub fn commit(self, params: &PedersenParams<C>, x: &Vec<C::ScalarField>) -> Phi<C> {
 31        // TODO instead of r_vec, use self.rE and self.rW for the commit
 32        let cmE = Pedersen::commit(&params.r_vec, &self.E);
 33        let cmW = Pedersen::commit(&params.r_vec, &self.W);
 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    ) -> FWit<C> {
 81        let r2 = r * r;
 82        let E: Vec<C::ScalarField> = vec_add(
 83            // this syntax will be simplified with future operators impl (or at least a method
 84            // for r-lin)
 85            &vec_add(&fw1.E, &vector_elem_product(&T, &r)),
 86            // rlin(fw1.E.clone(), T, r),
 87            &vector_elem_product(&fw2.E, &r2),
 88        );
 89        let W = vec_add(&fw1.W, &vector_elem_product(&fw2.W, &r));
 90        // let W = rlin(fw1.W.clone(), fw2.W.clone(), r);
 91        FWit::<C> {
 92            E: E.into(),
 93            W: W.into(),
 94        }
 95    }
 96
 97    pub fn fold_instance(
 98        r: C::ScalarField,
 99        phi1: Phi<C>,
100        phi2: Phi<C>,
101        cmT: Commitment<C>,
102    ) -> Phi<C> {
103        let r2 = r * r;
104
105        let cmE = phi1.cmE.0 + cmT.0.mul(r) + phi2.cmE.0.mul(r2);
106        let u = phi1.u + r * phi2.u;
107        let cmW = phi1.cmW.0 + phi2.cmW.0.mul(r);
108        let x = vec_add(&phi1.x, &vector_elem_product(&phi2.x, &r));
109        // let x = rlin(phi1.x, phi2.x, r);
110
111        Phi::<C> {
112            cmE: Commitment(cmE.into()),
113            u,
114            cmW: Commitment(cmW.into()),
115            x,
116        }
117    }
118}
119
120#[cfg(test)]
121mod tests {
122    use super::*;
123    use crate::pedersen::Pedersen;
124    use ark_bn254::{g1::G1Affine, Fr};
125    use ark_ec::CurveGroup;
126    use ark_std::{
127        rand::{Rng, RngCore},
128        UniformRand,
129    };
130    use ark_std::{One, Zero};
131    use std::ops::Mul;
132
133    #[test]
134    fn test_simple_folding() {
135        let mut rng = ark_std::test_rng();
136
137        // R1CS for: x^3 + x + 5 = y (example from article
138        // https://www.vitalik.ca/general/2016/12/10/qap.html )
139        let A = to_F_matrix::<Fr>(vec![
140            vec![0, 1, 0, 0, 0, 0],
141            vec![0, 0, 0, 1, 0, 0],
142            vec![0, 1, 0, 0, 1, 0],
143            vec![5, 0, 0, 0, 0, 1],
144        ]);
145        let B = to_F_matrix::<Fr>(vec![
146            vec![0, 1, 0, 0, 0, 0],
147            vec![0, 1, 0, 0, 0, 0],
148            vec![1, 0, 0, 0, 0, 0],
149            vec![1, 0, 0, 0, 0, 0],
150        ]);
151        let C = to_F_matrix::<Fr>(vec![
152            vec![0, 0, 0, 1, 0, 0],
153            vec![0, 0, 0, 0, 1, 0],
154            vec![0, 0, 0, 0, 0, 1],
155            vec![0, 0, 1, 0, 0, 0],
156        ]);
157        let z1 = to_F_vec::<Fr>(vec![1, 3, 35, 9, 27, 30]);
158        let x1 = to_F_vec::<Fr>(vec![35]);
159        let z2 = to_F_vec::<Fr>(vec![1, 4, 73, 16, 64, 68]);
160        let x2 = to_F_vec::<Fr>(vec![73]);
161
162        let relaxed_r1cs_1 = R1CS::<Fr> {
163            A: A.clone(),
164            B: B.clone(),
165            C: C.clone(),
166        }
167        .relax();
168        let relaxed_r1cs_2 = R1CS::<Fr> {
169            A: A.clone(),
170            B: B.clone(),
171            C: C.clone(),
172        }
173        .relax();
174
175        let T = NIFS::<G1Affine>::comp_T(relaxed_r1cs_1, relaxed_r1cs_2, &z1, &z2);
176        let pedersen_params = Pedersen::<G1Affine>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
177        let cmT = Pedersen::commit(&pedersen_params.r_vec, &T);
178
179        let r = Fr::rand(&mut rng); // this would come from the transcript
180
181        // WIP TMP
182        let fw1 = FWit::<G1Affine> {
183            E: vec![Fr::zero(); T.len()],
184            W: z1,
185        };
186        let fw2 = FWit::<G1Affine> {
187            E: vec![Fr::zero(); T.len()],
188            W: z2,
189        };
190
191        // fold witness
192        let fw3 = NIFS::<G1Affine>::fold_witness(r, &fw1, &fw2, T);
193
194        // let pedersen_params = Pedersen::<G1Affine>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
195        let phi1 = fw1.commit(&pedersen_params, &x1); // wip
196        let phi2 = fw2.commit(&pedersen_params, &x2);
197        // fold instance
198        let phi3 = NIFS::<G1Affine>::fold_instance(r, phi1, phi2, cmT);
199
200        // naive check that the folded witness satisfies the relaxed r1cs
201        let Az = matrix_vector_product(&A, &fw3.W);
202        let Bz = matrix_vector_product(&B, &fw3.W);
203        let Cz = matrix_vector_product(&C, &fw3.W);
204        assert_eq!(
205            hadamard_product(Az, Bz),
206            vec_add(&vector_elem_product(&Cz, &phi3.u), &fw3.E)
207        );
208
209        // check that folded commitments from folded instance (phi) are equal to folding the
210        // witnesses and committing into it
211        let x3 = vec_add(&x1, &vector_elem_product(&x2, &r));
212        let phi3_expected = fw3.commit(&pedersen_params, &x3);
213        assert_eq!(phi3_expected.cmE.0, phi3.cmE.0);
214        assert_eq!(phi3_expected.cmW.0, phi3.cmW.0);
215    }
216}