1/// Implements the scheme described in [Nova](https://eprint.iacr.org/2021/370.pdf)
  2use ark_crypto_primitives::{
  3    crh::{poseidon::CRH, CRHScheme},
  4    sponge::{poseidon::PoseidonConfig, Absorb},
  5};
  6use ark_ec::{CurveGroup, Group};
  7use ark_std::fmt::Debug;
  8use ark_std::{One, Zero};
  9
 10use crate::ccs::r1cs::R1CS;
 11use crate::folding::circuits::nonnative::point_to_nonnative_limbs;
 12use crate::pedersen::{Params as PedersenParams, Pedersen};
 13use crate::utils::vec::is_zero_vec;
 14use crate::Error;
 15
 16pub mod circuits;
 17pub mod nifs;
 18
 19#[derive(Debug, Clone, Eq, PartialEq)]
 20pub struct CommittedInstance<C: CurveGroup> {
 21    pub cmE: C,
 22    pub u: C::ScalarField,
 23    pub cmW: C,
 24    pub x: Vec<C::ScalarField>,
 25}
 26
 27impl<C: CurveGroup> CommittedInstance<C>
 28where
 29    <C as Group>::ScalarField: Absorb,
 30    <C as ark_ec::CurveGroup>::BaseField: ark_ff::PrimeField,
 31{
 32    pub fn dummy(io_len: usize) -> Self {
 33        Self {
 34            cmE: C::zero(),
 35            u: C::ScalarField::zero(),
 36            cmW: C::zero(),
 37            x: vec![C::ScalarField::zero(); io_len],
 38        }
 39    }
 40
 41    /// hash implements the committed instance hash compatible with the gadget implemented in
 42    /// nova/circuits.rs::CommittedInstanceVar.hash.
 43    /// Returns `H(i, z_0, z_i, U_i)`, where `i` can be `i` but also `i+1`, and `U` is the
 44    /// `CommittedInstance`.
 45    pub fn hash(
 46        &self,
 47        poseidon_config: &PoseidonConfig<C::ScalarField>,
 48        i: C::ScalarField,
 49        z_0: Vec<C::ScalarField>,
 50        z_i: Vec<C::ScalarField>,
 51    ) -> Result<C::ScalarField, Error> {
 52        let (cmE_x, cmE_y) = point_to_nonnative_limbs::<C>(self.cmE)?;
 53        let (cmW_x, cmW_y) = point_to_nonnative_limbs::<C>(self.cmW)?;
 54
 55        Ok(CRH::<C::ScalarField>::evaluate(
 56            poseidon_config,
 57            vec![
 58                vec![i],
 59                z_0,
 60                z_i,
 61                vec![self.u],
 62                self.x.clone(),
 63                cmE_x,
 64                cmE_y,
 65                cmW_x,
 66                cmW_y,
 67            ]
 68            .concat(),
 69        )
 70        .unwrap())
 71    }
 72}
 73
 74#[derive(Debug, Clone, Eq, PartialEq)]
 75pub struct Witness<C: CurveGroup> {
 76    pub E: Vec<C::ScalarField>,
 77    pub rE: C::ScalarField,
 78    pub W: Vec<C::ScalarField>,
 79    pub rW: C::ScalarField,
 80}
 81
 82impl<C: CurveGroup> Witness<C>
 83where
 84    <C as Group>::ScalarField: Absorb,
 85{
 86    pub fn new(w: Vec<C::ScalarField>, e_len: usize) -> Self {
 87        Self {
 88            E: vec![C::ScalarField::zero(); e_len],
 89            rE: C::ScalarField::zero(), // because we use C::zero() as cmE
 90            W: w,
 91            rW: C::ScalarField::one(),
 92        }
 93    }
 94    pub fn commit(
 95        &self,
 96        params: &PedersenParams<C>,
 97        x: Vec<C::ScalarField>,
 98    ) -> Result<CommittedInstance<C>, Error> {
 99        let mut cmE = C::zero();
100        if !is_zero_vec::<C::ScalarField>(&self.E) {
101            cmE = Pedersen::commit(params, &self.E, &self.rE)?;
102        }
103        let cmW = Pedersen::commit(params, &self.W, &self.rW)?;
104        Ok(CommittedInstance {
105            cmE,
106            u: C::ScalarField::one(),
107            cmW,
108            x,
109        })
110    }
111}
112
113pub fn check_instance_relation<C: CurveGroup>(
114    r1cs: &R1CS<C::ScalarField>,
115    W: &Witness<C>,
116    U: &CommittedInstance<C>,
117) -> Result<(), Error> {
118    let mut rel_r1cs = r1cs.clone().relax();
119    rel_r1cs.u = U.u;
120    rel_r1cs.E = W.E.clone();
121
122    let Z: Vec<C::ScalarField> = [vec![U.u], U.x.to_vec(), W.W.to_vec()].concat();
123    rel_r1cs.check_relation(&Z)
124}