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