1use ark_ec::AffineRepr;
  2use ark_std::ops::Add;
  3use ark_std::One;
  4use std::marker::PhantomData;
  5
  6use crate::pedersen::{Commitment, CommitmentVec, 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: CommitmentVec<C>, // TODO not Commitment but directly C (without rE)
 18    cmE: C,
 19    u: C::ScalarField,
 20    // cmW: CommitmentVec<C>, // TODO not Commitment but directly C (without rW)
 21    cmW: C,
 22    x: Vec<C::ScalarField>,
 23}
 24
 25// FWit: Folded Witness
 26pub struct FWit<C: AffineRepr> {
 27    E: Vec<C::ScalarField>,
 28    rE: C::ScalarField,
 29    W: Vec<C::ScalarField>,
 30    rW: C::ScalarField,
 31}
 32
 33impl<C: AffineRepr> FWit<C> {
 34    pub fn commit<R: Rng>(
 35        &self,
 36        rng: &mut R,
 37        params: &PedersenParams<C>,
 38        x: Vec<C::ScalarField>,
 39    ) -> Phi<C> {
 40        // TODO instead of rand r, use self.rE and self.rW for the commit_vec
 41        let cmE = Pedersen::commit_vec(rng, &params, &self.E);
 42        let cmW = Pedersen::commit_vec(rng, &params, &self.W);
 43        Phi {
 44            cmE: cmE.cm,
 45            u: C::ScalarField::one(),
 46            cmW: cmW.cm,
 47            x,
 48        }
 49    }
 50}
 51
 52pub struct NIFS<C: AffineRepr> {
 53    _phantom: PhantomData<C>,
 54}
 55
 56impl<C: AffineRepr> NIFS<C> {
 57    pub fn comp_T(
 58        cs1: RelaxedR1CS<C::ScalarField>,
 59        cs2: RelaxedR1CS<C::ScalarField>,
 60        z1: &Vec<C::ScalarField>,
 61        z2: &Vec<C::ScalarField>,
 62    ) -> Vec<C::ScalarField> {
 63        // assuming cs1.R1CS == cs2.R1CS
 64        let (A, B, C) = (cs1.ABC.A, cs1.ABC.B, cs1.ABC.C);
 65
 66        // this is parallelizable (for the future)
 67        let Az1 = matrix_vector_product(&A, &z1);
 68        let Bz1 = matrix_vector_product(&B, &z1);
 69        let Cz1 = matrix_vector_product(&C, &z1);
 70        let Az2 = matrix_vector_product(&A, &z2);
 71        let Bz2 = matrix_vector_product(&B, &z2);
 72        let Cz2 = matrix_vector_product(&C, &z2);
 73
 74        let Az1_Bz2 = hadamard_product(Az1, Bz2);
 75        let Az2_Bz1 = hadamard_product(Az2, Bz1);
 76        let u1Cz2 = vector_elem_product(&Cz2, &cs1.u);
 77        let u2Cz1 = vector_elem_product(&Cz1, &cs2.u);
 78
 79        // let T = vec_sub(vec_sub(vec_add(Az1_Bz2, Az2_Bz1), u1Cz2), u2Cz1);
 80        let T = ((Ve(Az1_Bz2) + Ve(Az2_Bz1)) - Ve(u1Cz2)) - Ve(u2Cz1);
 81        T.0
 82    }
 83
 84    pub fn fold_witness(
 85        r: C::ScalarField,
 86        fw1: &FWit<C>,
 87        fw2: &FWit<C>,
 88        T: Vec<C::ScalarField>,
 89    ) -> FWit<C> {
 90        let r2 = r * r;
 91        let E: Vec<C::ScalarField> = vec_add(
 92            // this syntax will be simplified with future operators impl (or at least a method
 93            // for r-lin)
 94            vec_add(fw1.E.clone(), vector_elem_product(&T, &r)),
 95            // rlin(fw1.E.clone(), T, r),
 96            vector_elem_product(&fw2.E, &r2),
 97        );
 98        let rE = fw1.rE + r2 * fw2.rE; // TODO rT
 99        let W = vec_add(fw1.W.clone(), vector_elem_product(&fw2.W, &r));
100        // let W = rlin(fw1.W.clone(), fw2.W.clone(), r);
101        let rW = fw1.rW + r * fw2.rW;
102        FWit::<C> {
103            E: E.into(),
104            rE,
105            W: W.into(),
106            rW,
107        }
108    }
109
110    pub fn fold_instance(
111        r: C::ScalarField,
112        phi1: Phi<C>,
113        phi2: Phi<C>,
114        cmT: CommitmentVec<C>,
115    ) -> Phi<C> {
116        let r2 = r * r;
117
118        let cmE = phi1.cmE + cmT.cm.mul(r) + phi2.cmE.mul(r2);
119        let u = phi1.u + r * phi2.u;
120        let cmW = phi1.cmW + phi2.cmW.mul(r);
121        let x = vec_add(phi1.x, vector_elem_product(&phi2.x, &r));
122        // let x = rlin(phi1.x, phi2.x, r);
123
124        Phi::<C> {
125            // cmE: Commitment::<C> {
126            //     cm: cmE.into(),
127            //     r: phi1.cmE.r,
128            // },
129            cmE: cmE.into(),
130            u,
131            // cmW: Commitment::<C> {
132            //     cm: cmW.into(),
133            //     r: phi1.cmW.r,
134            // },
135            cmW: cmW.into(),
136            x,
137        }
138    }
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144    use crate::pedersen::Pedersen;
145    use ark_bn254::{g1::G1Affine, Fr};
146    use ark_ec::CurveGroup;
147    use ark_std::{
148        rand::{Rng, RngCore},
149        UniformRand,
150    };
151    use ark_std::{One, Zero};
152    use std::ops::Mul;
153
154    #[test]
155    fn test_simple_folding() {
156        let mut rng = ark_std::test_rng();
157
158        // R1CS for: x^3 + x + 5 = y (example from article
159        // https://www.vitalik.ca/general/2016/12/10/qap.html )
160        let A = to_F_matrix::<Fr>(vec![
161            vec![0, 1, 0, 0, 0, 0],
162            vec![0, 0, 0, 1, 0, 0],
163            vec![0, 1, 0, 0, 1, 0],
164            vec![5, 0, 0, 0, 0, 1],
165        ]);
166        let B = to_F_matrix::<Fr>(vec![
167            vec![0, 1, 0, 0, 0, 0],
168            vec![0, 1, 0, 0, 0, 0],
169            vec![1, 0, 0, 0, 0, 0],
170            vec![1, 0, 0, 0, 0, 0],
171        ]);
172        let C = to_F_matrix::<Fr>(vec![
173            vec![0, 0, 0, 1, 0, 0],
174            vec![0, 0, 0, 0, 1, 0],
175            vec![0, 0, 0, 0, 0, 1],
176            vec![0, 0, 1, 0, 0, 0],
177        ]);
178        let z1 = to_F_vec::<Fr>(vec![1, 3, 35, 9, 27, 30]);
179        let x1 = to_F_vec::<Fr>(vec![35]);
180        let z2 = to_F_vec::<Fr>(vec![1, 4, 73, 16, 64, 68]);
181        let x2 = to_F_vec::<Fr>(vec![73]);
182
183        let relaxed_r1cs_1 = R1CS::<Fr> {
184            A: A.clone(),
185            B: B.clone(),
186            C: C.clone(),
187        }
188        .relax();
189        let relaxed_r1cs_2 = R1CS::<Fr> {
190            A: A.clone(),
191            B: B.clone(),
192            C: C.clone(),
193        }
194        .relax();
195
196        let T = NIFS::<G1Affine>::comp_T(relaxed_r1cs_1, relaxed_r1cs_2, &z1, &z2);
197        let params = Pedersen::<G1Affine>::new_params(&mut rng);
198        let cmT = Pedersen::commit_vec(&mut rng, &params, &T);
199
200        let r = Fr::rand(&mut rng); // this would come from the transcript
201
202        // WIP TMP
203        let fw1 = FWit::<G1Affine> {
204            E: vec![Fr::zero(); T.len()],
205            rE: Fr::zero(),
206            W: z1,
207            rW: Fr::zero(),
208        };
209        let fw2 = FWit::<G1Affine> {
210            E: vec![Fr::zero(); T.len()],
211            rE: Fr::zero(),
212            W: z2,
213            rW: Fr::zero(),
214        };
215
216        // fold witness
217        let folded_witness = NIFS::<G1Affine>::fold_witness(r, &fw1, &fw2, T);
218
219        let pedersen_params = Pedersen::<G1Affine>::new_params(&mut rng);
220        let phi1 = fw1.commit(&mut rng, &pedersen_params, x1); // wip
221        let phi2 = fw2.commit(&mut rng, &pedersen_params, x2);
222        // fold instance
223        let folded_instance = NIFS::<G1Affine>::fold_instance(r, phi1, phi2, cmT);
224
225        // naive check that the folded witness satisfies the relaxed r1cs
226        let Az = matrix_vector_product(&A, &folded_witness.W);
227        let Bz = matrix_vector_product(&B, &folded_witness.W);
228        let Cz = matrix_vector_product(&C, &folded_witness.W);
229        assert_eq!(
230            hadamard_product(Az, Bz),
231            vec_add(
232                vector_elem_product(&Cz, &folded_instance.u),
233                folded_witness.E
234            )
235        );
236    }
237}