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: C::ScalarField,
 50        z_i: 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, z_0, z_i, self.u],
 59                self.x.clone(),
 60                cmE_x,
 61                cmE_y,
 62                cmW_x,
 63                cmW_y,
 64            ]
 65            .concat(),
 66        )
 67        .unwrap())
 68    }
 69}
 70
 71#[derive(Debug, Clone, Eq, PartialEq)]
 72pub struct Witness<C: CurveGroup> {
 73    pub E: Vec<C::ScalarField>,
 74    pub rE: C::ScalarField,
 75    pub W: Vec<C::ScalarField>,
 76    pub rW: C::ScalarField,
 77}
 78
 79impl<C: CurveGroup> Witness<C>
 80where
 81    <C as Group>::ScalarField: Absorb,
 82{
 83    pub fn new(w: Vec<C::ScalarField>, e_len: usize) -> Self {
 84        Self {
 85            E: vec![C::ScalarField::zero(); e_len],
 86            rE: C::ScalarField::zero(), // because we use C::zero() as cmE
 87            W: w,
 88            rW: C::ScalarField::one(),
 89        }
 90    }
 91    pub fn commit(
 92        &self,
 93        params: &PedersenParams<C>,
 94        x: Vec<C::ScalarField>,
 95    ) -> CommittedInstance<C> {
 96        let mut cmE = C::zero();
 97        if !is_zero_vec::<C::ScalarField>(&self.E) {
 98            cmE = Pedersen::commit(params, &self.E, &self.rE);
 99        }
100        let cmW = Pedersen::commit(params, &self.W, &self.rW);
101        CommittedInstance {
102            cmE,
103            u: C::ScalarField::one(),
104            cmW,
105            x,
106        }
107    }
108}
109
110pub fn check_instance_relation<C: CurveGroup>(
111    r1cs: &R1CS<C::ScalarField>,
112    W: &Witness<C>,
113    U: &CommittedInstance<C>,
114) -> Result<(), Error> {
115    let mut rel_r1cs = r1cs.clone().relax();
116    rel_r1cs.u = U.u;
117    rel_r1cs.E = W.E.clone();
118
119    let Z: Vec<C::ScalarField> = [vec![U.u], U.x.to_vec(), W.W.to_vec()].concat();
120    rel_r1cs.check_relation(&Z)
121}