1use std::marker::PhantomData;
  2
  3/// Implements the scheme described in [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?view).
  4/// Ova is a slight modification to Nova that shaves off 1 group operation and a few hashes.
  5/// The key idea is that we can commit to $T$ and $W$ in one commitment.
  6///
  7/// This slightly breaks the abstraction between the IVC scheme and the accumulation scheme.
  8/// We assume that the accumulation prover receives $\vec{w}$ as input which proves the current step
  9/// of the computation and that the *previous* accumulation was performed correctly.
 10/// Note that $\vec{w}$ can be generated without being aware of $\vec{t}$ or $\alpha$.
 11/// Alternatively the accumulation prover can receive the commitment to $\vec{w}$ as input
 12/// and add to it the commitment to $\vec{t}$.
 13///
 14/// This yields a commitment to the concatenated vector $\vec{w}||\vec{t}$.
 15/// This works because both $W$ and $T$ are multiplied by the same challenge $\alpha$ in Nova.
 16use ark_crypto_primitives::sponge::Absorb;
 17use ark_ec::{CurveGroup, Group};
 18use ark_ff::PrimeField;
 19use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
 20use ark_std::fmt::Debug;
 21use ark_std::rand::RngCore;
 22use ark_std::{One, UniformRand, Zero};
 23
 24use crate::arith::r1cs::R1CS;
 25use crate::commitment::CommitmentScheme;
 26use crate::constants::NOVA_N_BITS_RO;
 27use crate::folding::{circuits::CF1, traits::Dummy};
 28use crate::transcript::{AbsorbNonNative, Transcript};
 29use crate::Error;
 30
 31pub mod nifs;
 32
 33/// A CommittedInstance in [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?view) is represented by `W` or `W'`.
 34/// It is the result of the commitment to a vector that contains the witness `w` concatenated
 35/// with `t` or `e` + the public inputs `x` and a relaxation factor `mu`.
 36#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 37pub struct CommittedInstance<C: CurveGroup> {
 38    pub mu: C::ScalarField,
 39    pub x: Vec<C::ScalarField>,
 40    pub cmWE: C,
 41}
 42
 43impl<C: CurveGroup> Absorb for CommittedInstance<C>
 44where
 45    C::ScalarField: Absorb,
 46{
 47    fn to_sponge_bytes(&self, dest: &mut Vec<u8>) {
 48        C::ScalarField::batch_to_sponge_bytes(&self.to_sponge_field_elements_as_vec(), dest);
 49    }
 50
 51    fn to_sponge_field_elements<F: PrimeField>(&self, dest: &mut Vec<F>) {
 52        self.mu.to_sponge_field_elements(dest);
 53        self.x.to_sponge_field_elements(dest);
 54        // We cannot call `to_native_sponge_field_elements(dest)` directly, as
 55        // `to_native_sponge_field_elements` needs `F` to be `C::ScalarField`,
 56        // but here `F` is a generic `PrimeField`.
 57        self.cmWE
 58            .to_native_sponge_field_elements_as_vec()
 59            .to_sponge_field_elements(dest);
 60    }
 61}
 62
 63// Clippy flag needed for now.
 64#[allow(dead_code)]
 65/// A Witness in [Ova](https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?view) is represented by `w`.
 66/// It also contains a blinder which can or not be used when committing to the witness itself.
 67#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
 68pub struct Witness<C: CurveGroup> {
 69    pub w: Vec<C::ScalarField>,
 70    pub rW: C::ScalarField,
 71}
 72
 73impl<C: CurveGroup> Witness<C> {
 74    /// Generates a new `Witness` instance from a given witness vector.
 75    /// If `H = true`, then we assume we want to blind it at commitment time,
 76    /// hence sampling `rW` from the randomness passed.
 77    pub fn new<const H: bool>(w: Vec<C::ScalarField>, mut rng: impl RngCore) -> Self {
 78        Self {
 79            w,
 80            rW: if H {
 81                C::ScalarField::rand(&mut rng)
 82            } else {
 83                C::ScalarField::zero()
 84            },
 85        }
 86    }
 87
 88    /// Computes the `W` or `W'` commitment (The accumulated-instance W' or the incoming-instance W)
 89    /// as specified in Ova. See: <https://hackmd.io/V4838nnlRKal9ZiTHiGYzw?view#Construction>.
 90    ///
 91    /// This is the result of concatenating the accumulated-instance `w` vector with
 92    /// `e` or `t`.
 93    /// Generates a [`CommittedInstance`] as a result which will or not be blinded depending on how the
 94    /// const generic `HC` is set up.
 95    ///
 96    /// This is the exact trick that allows Ova to save up 1 commitment with respect to Nova.
 97    /// At the cost of loosing the PCD property and only maintaining the IVC one.
 98    pub fn commit<CS: CommitmentScheme<C, HC>, const HC: bool>(
 99        &self,
100        params: &CS::ProverParams,
101        t_or_e: Vec<C::ScalarField>,
102        x: Vec<C::ScalarField>,
103    ) -> Result<CommittedInstance<C>, Error> {
104        let cmWE = CS::commit(params, &[self.w.clone(), t_or_e].concat(), &self.rW)?;
105        Ok(CommittedInstance {
106            mu: C::ScalarField::one(),
107            cmWE,
108            x,
109        })
110    }
111}
112
113impl<C: CurveGroup> Dummy<&R1CS<CF1<C>>> for Witness<C> {
114    fn dummy(r1cs: &R1CS<CF1<C>>) -> Self {
115        Self {
116            w: vec![C::ScalarField::zero(); r1cs.A.n_cols - 1 - r1cs.l],
117            rW: C::ScalarField::zero(),
118        }
119    }
120}
121
122pub struct ChallengeGadget<C: CurveGroup> {
123    _c: PhantomData<C>,
124}
125impl<C: CurveGroup> ChallengeGadget<C>
126where
127    C: CurveGroup,
128    <C as CurveGroup>::BaseField: PrimeField,
129    <C as Group>::ScalarField: Absorb,
130{
131    pub fn get_challenge_native<T: Transcript<C::ScalarField>>(
132        transcript: &mut T,
133        pp_hash: C::ScalarField, // public params hash
134        // Running instance
135        U_i: CommittedInstance<C>,
136        // Incoming instance
137        u_i: CommittedInstance<C>,
138    ) -> Vec<bool> {
139        // NOTICE: This isn't following the order of the HackMD.
140        // As long as we match it. We should not have any issues.
141        transcript.absorb(&pp_hash);
142        transcript.absorb(&U_i);
143        transcript.absorb(&u_i);
144        transcript.squeeze_bits(NOVA_N_BITS_RO)
145    }
146}
147
148// Simple auxiliary structure mainly used to help pass a witness for which we can check
149// easily an R1CS relation.
150// Notice that checking it requires us to have `E` as per [`Arith`] trait definition.
151// But since we don't hold `E` nor `e` within the NIFS, we create this structure to pass
152// `e` such that the check can be done.
153#[derive(Debug, Clone)]
154pub(crate) struct TestingWitness<C: CurveGroup> {
155    pub(crate) w: Vec<C::ScalarField>,
156    pub(crate) e: Vec<C::ScalarField>,
157}