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