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