1/// This module contains the implementation the NIFSTrait for the
  2/// [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw) NIFS (Non-Interactive Folding Scheme).
  3use ark_crypto_primitives::sponge::Absorb;
  4use ark_ec::{CurveGroup, Group};
  5use ark_ff::{BigInteger, PrimeField};
  6use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
  7use ark_std::fmt::Debug;
  8use ark_std::rand::RngCore;
  9use ark_std::{One, UniformRand, Zero};
 10use std::marker::PhantomData;
 11
 12use super::NIFSTrait;
 13use crate::arith::r1cs::R1CS;
 14use crate::commitment::CommitmentScheme;
 15use crate::folding::nova::circuits::ChallengeGadget;
 16use crate::folding::{circuits::CF1, traits::Dummy};
 17use crate::transcript::{AbsorbNonNative, Transcript};
 18use crate::utils::vec::{hadamard, mat_vec_mul, vec_scalar_mul, vec_sub};
 19use crate::Error;
 20
 21/// A CommittedInstance in [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw) is represented by `W` or
 22/// `W'`. It is the result of the commitment to a vector that contains the witness `w` concatenated
 23/// with `t` or `e` + the public inputs `x` and a relaxation factor `u`. (Notice that in the Ova
 24/// document `u` is denoted as `mu`, in this implementation we use `u` so it follows the original
 25/// Nova notation, so code is easier to follow).
 26#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 27pub struct CommittedInstance<C: CurveGroup> {
 28    pub u: C::ScalarField, // in the Ova document is denoted as `mu`
 29    pub x: Vec<C::ScalarField>,
 30    pub cmWE: C,
 31}
 32
 33impl<C: CurveGroup> Absorb for CommittedInstance<C>
 34where
 35    C::ScalarField: Absorb,
 36{
 37    fn to_sponge_bytes(&self, dest: &mut Vec<u8>) {
 38        C::ScalarField::batch_to_sponge_bytes(&self.to_sponge_field_elements_as_vec(), dest);
 39    }
 40
 41    fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
 42        self.u.to_sponge_field_elements(dest);
 43        self.x.to_sponge_field_elements(dest);
 44        // We cannot call `to_native_sponge_field_elements(dest)` directly, as
 45        // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
 46        // but here `F` is a generic `PrimeField`.
 47        self.cmWE
 48            .to_native_sponge_field_elements_as_vec()
 49            .to_sponge_field_elements(dest);
 50    }
 51}
 52
 53/// A Witness in Ova is represented by `w`. It also contains a blinder which can or not be used
 54/// when committing to the witness itself.
 55#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 56pub struct Witness<C: CurveGroup> {
 57    pub w: Vec<C::ScalarField>,
 58    pub rW: C::ScalarField,
 59}
 60
 61impl<C: CurveGroup> Witness<C> {
 62    /// Generates a new `Witness` instance from a given witness vector.
 63    /// If `H = true`, then we assume we want to blind it at commitment time,
 64    /// hence sampling `rW` from the randomness passed.
 65    pub fn new<const H: bool>(w: Vec<C::ScalarField>, mut rng: impl RngCore) -> Self {
 66        Self {
 67            w,
 68            rW: if H {
 69                C::ScalarField::rand(&mut rng)
 70            } else {
 71                C::ScalarField::zero()
 72            },
 73        }
 74    }
 75
 76    /// Given `x` (public inputs) and `t` or `e` (which we always concatenate in Ova) and the
 77    /// public inputs `x`, generates a [`CommittedInstance`] as a result which will or not be
 78    /// blinded depending on how the const generic `HC` is set up.
 79    pub fn commit<CS: CommitmentScheme<C, HC>, const HC: bool>(
 80        &self,
 81        params: &CS::ProverParams,
 82        x: Vec<C::ScalarField>,
 83        t_or_e: Vec<C::ScalarField>,
 84    ) -> Result<CommittedInstance<C>, Error> {
 85        let cmWE = CS::commit(params, &[self.w.clone(), t_or_e].concat(), &self.rW)?;
 86        Ok(CommittedInstance {
 87            u: C::ScalarField::one(),
 88            cmWE,
 89            x,
 90        })
 91    }
 92}
 93
 94impl<C: CurveGroup> Dummy<&R1CS<CF1<C>>> for Witness<C> {
 95    fn dummy(r1cs: &R1CS<CF1<C>>) -> Self {
 96        Self {
 97            w: vec![C::ScalarField::zero(); r1cs.A.n_cols - 1 - r1cs.l],
 98            rW: C::ScalarField::zero(),
 99        }
100    }
101}
102
103/// Implements the NIFS (Non-Interactive Folding Scheme) trait for Ova.
104pub struct NIFS<
105    C: CurveGroup,
106    CS: CommitmentScheme<C, H>,
107    T: Transcript<C::ScalarField>,
108    const H: bool = false,
109> {
110    _c: PhantomData<C>,
111    _cp: PhantomData<CS>,
112    _t: PhantomData<T>,
113}
114
115impl<C: CurveGroup, CS: CommitmentScheme<C, H>, T: Transcript<C::ScalarField>, const H: bool>
116    NIFSTrait<C, CS, T, H> for NIFS<C, CS, T, H>
117where
118    <C as Group>::ScalarField: Absorb,
119    <C as CurveGroup>::BaseField: PrimeField,
120{
121    type CommittedInstance = CommittedInstance<C>;
122    type Witness = Witness<C>;
123    type ProverAux = ();
124    type Proof = ();
125
126    fn new_witness(w: Vec<C::ScalarField>, _e_len: usize, rng: impl RngCore) -> Self::Witness {
127        Witness::new::<H>(w, rng)
128    }
129
130    fn new_instance(
131        _rng: impl RngCore,
132        params: &CS::ProverParams,
133        W: &Self::Witness,
134        x: Vec<C::ScalarField>,
135        aux: Vec<C::ScalarField>, // t_or_e
136    ) -> Result<Self::CommittedInstance, Error> {
137        W.commit::<CS, H>(params, x, aux)
138    }
139
140    fn fold_witness(
141        r: C::ScalarField, // in Ova's hackmd denoted as `alpha`
142        W_i: &Self::Witness,
143        w_i: &Self::Witness,
144        _aux: &Self::ProverAux,
145    ) -> Result<Self::Witness, Error> {
146        let w: Vec<C::ScalarField> = W_i
147            .w
148            .iter()
149            .zip(&w_i.w)
150            .map(|(a, b)| *a + (r * b))
151            .collect();
152
153        let rW = W_i.rW + r * w_i.rW;
154        Ok(Self::Witness { w, rW })
155    }
156
157    fn prove(
158        _cs_prover_params: &CS::ProverParams,
159        _r1cs: &R1CS<C::ScalarField>,
160        transcript: &mut T,
161        pp_hash: C::ScalarField,
162        W_i: &Self::Witness,
163        U_i: &Self::CommittedInstance,
164        w_i: &Self::Witness,
165        u_i: &Self::CommittedInstance,
166    ) -> Result<
167        (
168            Self::Witness,
169            Self::CommittedInstance,
170            Self::Proof,
171            Vec<bool>,
172        ),
173        Error,
174    > {
175        let mut transcript_v = transcript.clone();
176
177        let r_bits = ChallengeGadget::<C, Self::CommittedInstance>::get_challenge_native(
178            transcript, pp_hash, U_i, u_i, None, // cmT not used in Ova
179        );
180        let r_Fr = C::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
181            .ok_or(Error::OutOfBounds)?;
182
183        let w = Self::fold_witness(r_Fr, W_i, w_i, &())?;
184
185        let (ci, _r_bits_v) = Self::verify(&mut transcript_v, pp_hash, U_i, u_i, &())?;
186        #[cfg(test)]
187        assert_eq!(_r_bits_v, r_bits);
188
189        Ok((w, ci, (), r_bits))
190    }
191
192    fn verify(
193        transcript: &mut T,
194        pp_hash: C::ScalarField,
195        U_i: &Self::CommittedInstance,
196        u_i: &Self::CommittedInstance,
197        _proof: &Self::Proof, // unused in Ova
198    ) -> Result<(Self::CommittedInstance, Vec<bool>), Error> {
199        let r_bits = ChallengeGadget::<C, Self::CommittedInstance>::get_challenge_native(
200            transcript, pp_hash, U_i, u_i, None, // cmT not used in Ova
201        );
202        let r = C::ScalarField::from_bigint(BigInteger::from_bits_le(&r_bits))
203            .ok_or(Error::OutOfBounds)?;
204
205        // recall that r=alpha, and u=mu between Nova and Ova respectively
206        let u = U_i.u + r; // u_i.u is always 1 IN ova as we just can do sequential IVC.
207        let cmWE = U_i.cmWE + u_i.cmWE.mul(r);
208        let x = U_i
209            .x
210            .iter()
211            .zip(&u_i.x)
212            .map(|(a, b)| *a + (r * b))
213            .collect::<Vec<C::ScalarField>>();
214
215        Ok((Self::CommittedInstance { cmWE, u, x }, r_bits))
216    }
217}
218
219/// Computes the E parameter (error terms) for the given R1CS and the instance's z and u. This
220/// method is used by the verifier to obtain E in order to check the RelaxedR1CS relation.
221pub fn compute_E<C: CurveGroup>(
222    r1cs: &R1CS<C::ScalarField>,
223    z: &[C::ScalarField],
224    u: C::ScalarField,
225) -> Result<Vec<C::ScalarField>, Error> {
226    let (A, B, C) = (r1cs.A.clone(), r1cs.B.clone(), r1cs.C.clone());
227
228    // this is parallelizable (for the future)
229    let Az = mat_vec_mul(&A, z)?;
230    let Bz = mat_vec_mul(&B, z)?;
231    let Cz = mat_vec_mul(&C, z)?;
232
233    let Az_Bz = hadamard(&Az, &Bz)?;
234    let uCz = vec_scalar_mul(&Cz, &u);
235
236    vec_sub(&Az_Bz, &uCz)
237}
238
239#[cfg(test)]
240pub mod tests {
241    use super::*;
242    use ark_pallas::{Fr, Projective};
243
244    use crate::arith::{r1cs::tests::get_test_r1cs, Arith};
245    use crate::commitment::pedersen::Pedersen;
246    use crate::folding::nova::nifs::tests::test_nifs_opt;
247    use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
248
249    // Simple auxiliary structure mainly used to help pass a witness for which we can check
250    // easily an R1CS relation.
251    // Notice that checking it requires us to have `E` as per [`Arith`] trait definition.
252    // But since we don't hold `E` nor `e` within the NIFS, we create this structure to pass
253    // `e` such that the check can be done.
254    #[derive(Debug, Clone)]
255    pub(crate) struct TestingWitness<C: CurveGroup> {
256        pub(crate) w: Vec<C::ScalarField>,
257        pub(crate) e: Vec<C::ScalarField>,
258    }
259    impl<C: CurveGroup> Arith<TestingWitness<C>, CommittedInstance<C>> for R1CS<CF1<C>> {
260        type Evaluation = Vec<CF1<C>>;
261
262        fn eval_relation(
263            &self,
264            w: &TestingWitness<C>,
265            u: &CommittedInstance<C>,
266        ) -> Result<Self::Evaluation, Error> {
267            self.eval_at_z(&[&[u.u], u.x.as_slice(), &w.w].concat())
268        }
269
270        fn check_evaluation(
271            w: &TestingWitness<C>,
272            _u: &CommittedInstance<C>,
273            e: Self::Evaluation,
274        ) -> Result<(), Error> {
275            (w.e == e).then_some(()).ok_or(Error::NotSatisfied)
276        }
277    }
278
279    #[test]
280    fn test_nifs_ova() {
281        let (W, U) = test_nifs_opt::<NIFS<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>>();
282
283        // check the last folded instance relation
284        let r1cs = get_test_r1cs();
285        let z: Vec<Fr> = [&[U.u][..], &U.x, &W.w].concat();
286        let e = compute_E::<Projective>(&r1cs, &z, U.u).unwrap();
287        r1cs.check_relation(&TestingWitness::<Projective> { e, w: W.w.clone() }, &U)
288            .unwrap();
289    }
290}