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