1/// This module defines the NIFSTrait, which is set to implement the NIFS (Non-Interactive Folding
  2/// Scheme) by the various schemes (Nova, Mova, Ova).
  3use ark_crypto_primitives::sponge::Absorb;
  4use ark_ec::CurveGroup;
  5use ark_std::fmt::Debug;
  6use ark_std::rand::RngCore;
  7
  8use crate::arith::r1cs::R1CS;
  9use crate::commitment::CommitmentScheme;
 10use crate::transcript::Transcript;
 11use crate::Error;
 12
 13pub mod mova;
 14pub mod nova;
 15pub mod ova;
 16pub mod pointvsline;
 17
 18/// Defines the NIFS (Non-Interactive Folding Scheme) trait, initially defined in
 19/// [Nova](https://eprint.iacr.org/2021/370.pdf), and it's variants
 20/// [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw) and
 21/// [Mova](https://eprint.iacr.org/2024/1220.pdf).
 22/// `H` specifies whether the NIFS will use a blinding factor.
 23pub trait NIFSTrait<
 24    C: CurveGroup,
 25    CS: CommitmentScheme<C, H>,
 26    T: Transcript<C::ScalarField>,
 27    const H: bool = false,
 28>
 29{
 30    type CommittedInstance: Debug + Clone + Absorb;
 31    type Witness: Debug + Clone;
 32    type ProverAux: Debug + Clone; // Prover's aux params. eg. in Nova is T
 33    type Proof: Debug + Clone; // proof. eg. in Nova is cmT
 34
 35    fn new_witness(w: Vec<C::ScalarField>, e_len: usize, rng: impl RngCore) -> Self::Witness;
 36
 37    fn new_instance(
 38        rng: impl RngCore,
 39        params: &CS::ProverParams,
 40        w: &Self::Witness,
 41        x: Vec<C::ScalarField>,
 42        aux: Vec<C::ScalarField>, // t_or_e in Ova, empty for Nova
 43    ) -> Result<Self::CommittedInstance, Error>;
 44
 45    fn fold_witness(
 46        r: C::ScalarField,
 47        W: &Self::Witness, // running witness
 48        w: &Self::Witness, // incoming witness
 49        aux: &Self::ProverAux,
 50    ) -> Result<Self::Witness, Error>;
 51
 52    /// NIFS.P. Returns a tuple containing the folded Witness, the folded CommittedInstance, and
 53    /// the used challenge `r` as a vector of bits, so that it can be reused in other methods.
 54    #[allow(clippy::type_complexity)]
 55    #[allow(clippy::too_many_arguments)]
 56    fn prove(
 57        cs_prover_params: &CS::ProverParams,
 58        r1cs: &R1CS<C::ScalarField>,
 59        transcript: &mut T,
 60        pp_hash: C::ScalarField,
 61        W_i: &Self::Witness,           // running witness
 62        U_i: &Self::CommittedInstance, // running committed instance
 63        w_i: &Self::Witness,           // incoming witness
 64        u_i: &Self::CommittedInstance, // incoming committed instance
 65    ) -> Result<
 66        (
 67            Self::Witness,
 68            Self::CommittedInstance,
 69            Self::Proof,
 70            Vec<bool>,
 71        ),
 72        Error,
 73    >;
 74
 75    /// NIFS.V. Returns the folded CommittedInstance and the used challenge `r` as a vector of
 76    /// bits, so that it can be reused in other methods.
 77    fn verify(
 78        transcript: &mut T,
 79        pp_hash: C::ScalarField,
 80        U_i: &Self::CommittedInstance,
 81        u_i: &Self::CommittedInstance,
 82        proof: &Self::Proof,
 83    ) -> Result<(Self::CommittedInstance, Vec<bool>), Error>;
 84}
 85
 86#[cfg(test)]
 87pub mod tests {
 88    use super::*;
 89    use crate::transcript::poseidon::poseidon_canonical_config;
 90    use ark_crypto_primitives::sponge::{poseidon::PoseidonSponge, CryptographicSponge};
 91    use ark_pallas::{Fr, Projective};
 92    use ark_std::{test_rng, UniformRand};
 93
 94    use super::NIFSTrait;
 95    use crate::arith::r1cs::tests::{get_test_r1cs, get_test_z};
 96    use crate::commitment::pedersen::Pedersen;
 97
 98    /// Test method used to test the different implementations of the NIFSTrait (ie. Nova, Mova,
 99    /// Ova). Runs a loop using the NIFS trait, and returns the last Witness and CommittedInstance
100    /// so that their relation can be checked.
101    pub(crate) fn test_nifs_opt<
102        N: NIFSTrait<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
103    >() -> (N::Witness, N::CommittedInstance) {
104        let r1cs = get_test_r1cs();
105        let z = get_test_z(3);
106        let (w, x) = r1cs.split_z(&z);
107
108        let mut rng = ark_std::test_rng();
109        let (pedersen_params, _) = Pedersen::<Projective>::setup(&mut rng, r1cs.A.n_cols).unwrap();
110
111        let poseidon_config = poseidon_canonical_config::<Fr>();
112        let mut transcript_p = PoseidonSponge::<Fr>::new(&poseidon_config);
113        let mut transcript_v = PoseidonSponge::<Fr>::new(&poseidon_config);
114        let pp_hash = Fr::rand(&mut rng);
115
116        // prepare the running instance
117        let mut W_i = N::new_witness(w.clone(), r1cs.A.n_rows, test_rng());
118        let mut U_i = N::new_instance(&mut rng, &pedersen_params, &W_i, x, vec![]).unwrap();
119
120        let num_iters = 10;
121        for i in 0..num_iters {
122            // prepare the incoming instance
123            let incoming_instance_z = get_test_z(i + 4);
124            let (w, x) = r1cs.split_z(&incoming_instance_z);
125            let w_i = N::new_witness(w.clone(), r1cs.A.n_rows, test_rng());
126            let u_i = N::new_instance(&mut rng, &pedersen_params, &w_i, x, vec![]).unwrap();
127
128            // NIFS.P
129            let (folded_witness, _, proof, _) = N::prove(
130                &pedersen_params,
131                &r1cs,
132                &mut transcript_p,
133                pp_hash,
134                &W_i,
135                &U_i,
136                &w_i,
137                &u_i,
138            )
139            .unwrap();
140
141            // NIFS.V
142            let (folded_committed_instance, _) =
143                N::verify(&mut transcript_v, pp_hash, &U_i, &u_i, &proof).unwrap();
144
145            // set running_instance for next loop iteration
146            W_i = folded_witness;
147            U_i = folded_committed_instance;
148        }
149
150        (W_i, U_i)
151    }
152}