1/// This module contains the implementation the NIFSTrait for the
  2/// [Nova](https://eprint.iacr.org/2021/370.pdf) NIFS (Non-Interactive Folding Scheme).
  3use ark_crypto_primitives::sponge::Absorb;
  4use ark_ec::{CurveGroup, Group};
  5use ark_ff::{BigInteger, PrimeField};
  6use ark_std::rand::RngCore;
  7use ark_std::Zero;
  8use std::marker::PhantomData;
  9
 10use super::NIFSTrait;
 11use crate::arith::r1cs::R1CS;
 12use crate::commitment::CommitmentScheme;
 13use crate::folding::circuits::cyclefold::{CycleFoldCommittedInstance, CycleFoldWitness};
 14use crate::folding::nova::circuits::ChallengeGadget;
 15use crate::folding::nova::{CommittedInstance, Witness};
 16use crate::transcript::Transcript;
 17use crate::utils::vec::{hadamard, mat_vec_mul, vec_add, vec_scalar_mul, vec_sub};
 18use crate::Error;
 19
 20/// Implements the Non-Interactive Folding Scheme described in section 4 of
 21/// [Nova](https://eprint.iacr.org/2021/370.pdf).
 22/// `H` specifies whether the NIFS will use a blinding factor
 23pub struct NIFS<
 24    C: CurveGroup,
 25    CS: CommitmentScheme<C, H>,
 26    T: Transcript<C::ScalarField>,
 27    const H: bool = false,
 28> {
 29    _c: PhantomData<C>,
 30    _cp: PhantomData<CS>,
 31    _t: PhantomData<T>,
 32}
 33
 34impl<C: CurveGroup, CS: CommitmentScheme<C, H>, T: Transcript<C::ScalarField>, const H: bool>
 35    NIFSTrait<C, CS, T, H> for NIFS<C, CS, T, H>
 36where
 37    <C as Group>::ScalarField: Absorb,
 38    <C as CurveGroup>::BaseField: PrimeField,
 39    <C as Group>::ScalarField: PrimeField,
 40{
 41    type CommittedInstance = CommittedInstance<C>;
 42    type Witness = Witness<C>;
 43    type ProverAux = Vec<C::ScalarField>;
 44    type Proof = C;
 45
 46    fn new_witness(w: Vec<C::ScalarField>, e_len: usize, rng: impl RngCore) -> Self::Witness {
 47        Witness::new::<H>(w, e_len, rng)
 48    }
 49
 50    fn new_instance(
 51        _rng: impl RngCore,
 52        params: &CS::ProverParams,
 53        W: &Self::Witness,
 54        x: Vec<C::ScalarField>,
 55        _aux: Vec<C::ScalarField>,
 56    ) -> Result<Self::CommittedInstance, Error> {
 57        W.commit::<CS, H>(params, x)
 58    }
 59
 60    fn fold_witness(
 61        r: C::ScalarField,
 62        W_i: &Self::Witness,
 63        w_i: &Self::Witness,
 64        aux: &Self::ProverAux, // T in Nova's notation
 65    ) -> Result<Self::Witness, Error> {
 66        let r2 = r * r;
 67        let E: Vec<C::ScalarField> = vec_add(
 68            &vec_add(&W_i.E, &vec_scalar_mul(aux, &r))?, // aux is Nova's T
 69            &vec_scalar_mul(&w_i.E, &r2),
 70        )?;
 71        // use r_T=0 since we don't need hiding property for cm(T)
 72        let rT = C::ScalarField::zero();
 73        let rE = W_i.rE + r * rT + r2 * w_i.rE;
 74        let W: Vec<C::ScalarField> = W_i
 75            .W
 76            .iter()
 77            .zip(&w_i.W)
 78            .map(|(a, b)| *a + (r * b))
 79            .collect();
 80
 81        let rW = W_i.rW + r * w_i.rW;
 82        Ok(Self::Witness { E, rE, W, rW })
 83    }
 84
 85    fn prove(
 86        cs_prover_params: &CS::ProverParams,
 87        r1cs: &R1CS<C::ScalarField>,
 88        transcript: &mut T,
 89        pp_hash: C::ScalarField,
 90        W_i: &Self::Witness,
 91        U_i: &Self::CommittedInstance,
 92        w_i: &Self::Witness,
 93        u_i: &Self::CommittedInstance,
 94    ) -> Result<
 95        (
 96            Self::Witness,
 97            Self::CommittedInstance,
 98            Self::Proof,
 99            Vec<bool>,
100        ),
101        Error,
102    > {
103        // compute the cross terms
104        let z1: Vec<C::ScalarField> = [vec![U_i.u], U_i.x.to_vec(), W_i.W.to_vec()].concat();
105        let z2: Vec<C::ScalarField> = [vec![u_i.u], u_i.x.to_vec(), w_i.W.to_vec()].concat();
106        let T = Self::compute_T(r1cs, U_i.u, u_i.u, &z1, &z2)?;
107
108        // use r_T=0 since we don't need hiding property for cm(T)
109        let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
110
111        let r_bits = ChallengeGadget::<C, Self::CommittedInstance>::get_challenge_native(
112            transcript,
113            pp_hash,
114            U_i,
115            u_i,
116            Some(&cmT),
117        );
118        let r_Fr = C::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
119            .ok_or(Error::OutOfBounds)?;
120
121        let w = Self::fold_witness(r_Fr, W_i, w_i, &T)?;
122
123        let ci = Self::fold_committed_instances(r_Fr, U_i, u_i, &cmT);
124
125        Ok((w, ci, cmT, r_bits))
126    }
127
128    fn verify(
129        transcript: &mut T,
130        pp_hash: C::ScalarField,
131        U_i: &Self::CommittedInstance,
132        u_i: &Self::CommittedInstance,
133        cmT: &C, // Proof
134    ) -> Result<(Self::CommittedInstance, Vec<bool>), Error> {
135        let r_bits = ChallengeGadget::<C, Self::CommittedInstance>::get_challenge_native(
136            transcript,
137            pp_hash,
138            U_i,
139            u_i,
140            Some(cmT),
141        );
142        let r = C::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
143            .ok_or(Error::OutOfBounds)?;
144
145        Ok((Self::fold_committed_instances(r, U_i, u_i, cmT), r_bits))
146    }
147}
148
149impl<C: CurveGroup, CS: CommitmentScheme<C, H>, T: Transcript<C::ScalarField>, const H: bool>
150    NIFS<C, CS, T, H>
151where
152    <C as Group>::ScalarField: Absorb,
153    <C as CurveGroup>::BaseField: PrimeField,
154{
155    /// compute_T: compute cross-terms T
156    pub fn compute_T(
157        r1cs: &R1CS<C::ScalarField>,
158        u1: C::ScalarField,
159        u2: C::ScalarField,
160        z1: &[C::ScalarField],
161        z2: &[C::ScalarField],
162    ) -> Result<Vec<C::ScalarField>, Error> {
163        let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
164
165        // this is parallelizable (for the future)
166        let Az1 = mat_vec_mul(&A, z1)?;
167        let Bz1 = mat_vec_mul(&B, z1)?;
168        let Cz1 = mat_vec_mul(&C, z1)?;
169        let Az2 = mat_vec_mul(&A, z2)?;
170        let Bz2 = mat_vec_mul(&B, z2)?;
171        let Cz2 = mat_vec_mul(&C, z2)?;
172
173        let Az1_Bz2 = hadamard(&Az1, &Bz2)?;
174        let Az2_Bz1 = hadamard(&Az2, &Bz1)?;
175        let u1Cz2 = vec_scalar_mul(&Cz2, &u1);
176        let u2Cz1 = vec_scalar_mul(&Cz1, &u2);
177
178        vec_sub(&vec_sub(&vec_add(&Az1_Bz2, &Az2_Bz1)?, &u1Cz2)?, &u2Cz1)
179    }
180
181    pub fn compute_cyclefold_cmT(
182        cs_prover_params: &CS::ProverParams,
183        r1cs: &R1CS<C::ScalarField>, // R1CS over C2.Fr=C1.Fq (here C=C2)
184        w1: &CycleFoldWitness<C>,
185        ci1: &CycleFoldCommittedInstance<C>,
186        w2: &CycleFoldWitness<C>,
187        ci2: &CycleFoldCommittedInstance<C>,
188    ) -> Result<(Vec<C::ScalarField>, C), Error>
189    where
190        <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
191    {
192        let z1: Vec<C::ScalarField> = [vec![ci1.u], ci1.x.to_vec(), w1.W.to_vec()].concat();
193        let z2: Vec<C::ScalarField> = [vec![ci2.u], ci2.x.to_vec(), w2.W.to_vec()].concat();
194
195        // compute cross terms
196        let T = Self::compute_T(r1cs, ci1.u, ci2.u, &z1, &z2)?;
197        // use r_T=0 since we don't need hiding property for cm(T)
198        let cmT = CS::commit(cs_prover_params, &T, &C::ScalarField::zero())?;
199        Ok((T, cmT))
200    }
201
202    /// folds two committed instances with the given r and cmT. This method is used by
203    /// Nova::verify, but also by Nova::prove and the CycleFoldNIFS::verify.
204    pub fn fold_committed_instances(
205        r: C::ScalarField,
206        U_i: &CommittedInstance<C>,
207        u_i: &CommittedInstance<C>,
208        cmT: &C,
209    ) -> CommittedInstance<C> {
210        let r2 = r * r;
211        let cmE = U_i.cmE + cmT.mul(r) + u_i.cmE.mul(r2);
212        let u = U_i.u + r * u_i.u;
213        let cmW = U_i.cmW + u_i.cmW.mul(r);
214        let x = U_i
215            .x
216            .iter()
217            .zip(&u_i.x)
218            .map(|(a, b)| *a + (r * b))
219            .collect::<Vec<C::ScalarField>>();
220
221        CommittedInstance { cmE, u, cmW, x }
222    }
223
224    pub fn prove_commitments(
225        tr: &mut impl Transcript<C::ScalarField>,
226        cs_prover_params: &CS::ProverParams,
227        w: &Witness<C>,
228        ci: &CommittedInstance<C>,
229        T: Vec<C::ScalarField>,
230        cmT: &C,
231    ) -> Result<[CS::Proof; 3], Error> {
232        let cmE_proof = CS::prove(cs_prover_params, tr, &ci.cmE, &w.E, &w.rE, None)?;
233        let cmW_proof = CS::prove(cs_prover_params, tr, &ci.cmW, &w.W, &w.rW, None)?;
234        let cmT_proof = CS::prove(cs_prover_params, tr, cmT, &T, &C::ScalarField::zero(), None)?; // cm(T) is committed with rT=0
235        Ok([cmE_proof, cmW_proof, cmT_proof])
236    }
237}
238
239#[cfg(test)]
240pub mod tests {
241    use super::*;
242    use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
243    use ark_pallas::{Fr, Projective};
244
245    use crate::arith::{r1cs::tests::get_test_r1cs, Arith};
246    use crate::commitment::pedersen::Pedersen;
247    use crate::folding::nova::nifs::tests::test_nifs_opt;
248
249    #[test]
250    fn test_nifs_nova() {
251        let (W, U) = test_nifs_opt::<NIFS<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>>();
252
253        // check the last folded instance relation
254        let r1cs = get_test_r1cs();
255        r1cs.check_relation(&W, &U).unwrap();
256    }
257}