1/// contains [Nova](https://eprint.iacr.org/2021/370.pdf) NIFS related circuits
  2use ark_crypto_primitives::sponge::{constraints::AbsorbGadget, Absorb, CryptographicSponge};
  3use ark_ec::{CurveGroup, Group};
  4use ark_r1cs_std::{
  5    alloc::{AllocVar, AllocationMode},
  6    boolean::Boolean,
  7    eq::EqGadget,
  8    fields::{fp::FpVar, FieldVar},
  9    uint8::UInt8,
 10    ToConstraintFieldGadget,
 11};
 12use ark_relations::r1cs::{ConstraintSystemRef, Namespace, SynthesisError};
 13use ark_std::{fmt::Debug, Zero};
 14use core::{borrow::Borrow, marker::PhantomData};
 15
 16use super::NIFSGadgetTrait;
 17use crate::folding::circuits::{
 18    nonnative::{affine::NonNativeAffineVar, uint::NonNativeUintVar},
 19    CF1, CF2,
 20};
 21use crate::folding::nova::CommittedInstance;
 22use crate::folding::traits::CommittedInstanceVarOps;
 23use crate::transcript::TranscriptVar;
 24
 25use super::nova::ChallengeGadget;
 26
 27/// CommittedInstanceVar contains the u, x, cmE and cmW values which are folded on the main Nova
 28/// constraints field (E1::Fr, where E1 is the main curve). The peculiarity is that cmE and cmW are
 29/// represented non-natively over the constraint field.
 30#[derive(Debug, Clone)]
 31pub struct CommittedInstanceVar<C: CurveGroup> {
 32    pub u: FpVar<C::ScalarField>,
 33    pub x: Vec<FpVar<C::ScalarField>>,
 34    pub cmE: NonNativeAffineVar<C>,
 35    pub cmW: NonNativeAffineVar<C>,
 36}
 37
 38impl<C> AllocVar<CommittedInstance<C>, CF1<C>> for CommittedInstanceVar<C>
 39where
 40    C: CurveGroup,
 41{
 42    fn new_variable<T: Borrow<CommittedInstance<C>>>(
 43        cs: impl Into<Namespace<CF1<C>>>,
 44        f: impl FnOnce() -> Result<T, SynthesisError>,
 45        mode: AllocationMode,
 46    ) -> Result<Self, SynthesisError> {
 47        f().and_then(|val| {
 48            let cs = cs.into();
 49
 50            let u = FpVar::<C::ScalarField>::new_variable(cs.clone(), || Ok(val.borrow().u), mode)?;
 51            let x: Vec<FpVar<C::ScalarField>> =
 52                Vec::new_variable(cs.clone(), || Ok(val.borrow().x.clone()), mode)?;
 53
 54            let cmE =
 55                NonNativeAffineVar::<C>::new_variable(cs.clone(), || Ok(val.borrow().cmE), mode)?;
 56            let cmW =
 57                NonNativeAffineVar::<C>::new_variable(cs.clone(), || Ok(val.borrow().cmW), mode)?;
 58
 59            Ok(Self { u, x, cmE, cmW })
 60        })
 61    }
 62}
 63
 64impl<C> AbsorbGadget<C::ScalarField> for CommittedInstanceVar<C>
 65where
 66    C: CurveGroup,
 67{
 68    fn to_sponge_bytes(&self) -> Result<Vec<UInt8<C::ScalarField>>, SynthesisError> {
 69        FpVar::batch_to_sponge_bytes(&self.to_sponge_field_elements()?)
 70    }
 71
 72    fn to_sponge_field_elements(&self) -> Result<Vec<FpVar<C::ScalarField>>, SynthesisError> {
 73        Ok([
 74            vec![self.u.clone()],
 75            self.x.clone(),
 76            self.cmE.to_constraint_field()?,
 77            self.cmW.to_constraint_field()?,
 78        ]
 79        .concat())
 80    }
 81}
 82
 83impl<C: CurveGroup> CommittedInstanceVarOps<C> for CommittedInstanceVar<C> {
 84    type PointVar = NonNativeAffineVar<C>;
 85
 86    fn get_commitments(&self) -> Vec<Self::PointVar> {
 87        vec![self.cmW.clone(), self.cmE.clone()]
 88    }
 89
 90    fn get_public_inputs(&self) -> &[FpVar<CF1<C>>] {
 91        &self.x
 92    }
 93
 94    fn enforce_incoming(&self) -> Result<(), SynthesisError> {
 95        let zero = NonNativeUintVar::new_constant(ConstraintSystemRef::None, CF2::<C>::zero())?;
 96        self.cmE.x.enforce_equal_unaligned(&zero)?;
 97        self.cmE.y.enforce_equal_unaligned(&zero)?;
 98        self.u.enforce_equal(&FpVar::one())
 99    }
100
101    fn enforce_partial_equal(&self, other: &Self) -> Result<(), SynthesisError> {
102        self.u.enforce_equal(&other.u)?;
103        self.x.enforce_equal(&other.x)
104    }
105}
106
107/// Implements the circuit that does the checks of the Non-Interactive Folding Scheme Verifier
108/// described in section 4 of [Nova](https://eprint.iacr.org/2021/370.pdf), where the cmE & cmW checks are
109/// delegated to the NIFSCycleFoldGadget.
110pub struct NIFSGadget<C: CurveGroup, S: CryptographicSponge, T: TranscriptVar<CF1<C>, S>> {
111    _c: PhantomData<C>,
112    _s: PhantomData<S>,
113    _t: PhantomData<T>,
114}
115
116impl<C, S, T> NIFSGadgetTrait<C, S, T> for NIFSGadget<C, S, T>
117where
118    C: CurveGroup,
119    S: CryptographicSponge,
120    T: TranscriptVar<CF1<C>, S>,
121    <C as Group>::ScalarField: Absorb,
122{
123    type CommittedInstance = CommittedInstance<C>;
124    type CommittedInstanceVar = CommittedInstanceVar<C>;
125    type Proof = C;
126    type ProofVar = NonNativeAffineVar<C>;
127
128    fn verify(
129        transcript: &mut T,
130        pp_hash: FpVar<CF1<C>>,
131        U_i: Self::CommittedInstanceVar,
132        // U_i_vec is passed to reuse the already computed U_i_vec from previous methods
133        U_i_vec: Vec<FpVar<CF1<C>>>,
134        u_i: Self::CommittedInstanceVar,
135        cmT: Option<Self::ProofVar>,
136    ) -> Result<(Self::CommittedInstanceVar, Vec<Boolean<CF1<C>>>), SynthesisError> {
137        let r_bits = ChallengeGadget::<C, CommittedInstance<C>>::get_challenge_gadget(
138            transcript,
139            pp_hash.clone(),
140            U_i_vec,
141            u_i.clone(),
142            cmT.clone(),
143        )?;
144        let r = Boolean::le_bits_to_fp_var(&r_bits)?;
145
146        Ok((
147            Self::CommittedInstanceVar {
148                cmE: NonNativeAffineVar::new_constant(ConstraintSystemRef::None, C::zero())?,
149                cmW: NonNativeAffineVar::new_constant(ConstraintSystemRef::None, C::zero())?,
150                // ci3.u = U_i.u + r * u_i.u
151                u: U_i.u + &r * u_i.u,
152                // ci3.x = U_i.x + r * u_i.x
153                x: U_i
154                    .x
155                    .iter()
156                    .zip(u_i.x)
157                    .map(|(a, b)| a + &r * &b)
158                    .collect::<Vec<FpVar<CF1<C>>>>(),
159            },
160            r_bits,
161        ))
162    }
163}
164
165#[cfg(test)]
166pub mod tests {
167    use super::*;
168    use ark_crypto_primitives::sponge::poseidon::constraints::PoseidonSpongeVar;
169    use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
170    use ark_pallas::{Fr, Projective};
171    use ark_r1cs_std::R1CSVar;
172    use ark_std::UniformRand;
173
174    use crate::commitment::pedersen::Pedersen;
175    use crate::folding::nova::nifs::{
176        nova::NIFS,
177        tests::{
178            test_committed_instance_hash_opt, test_committed_instance_to_sponge_preimage_opt,
179            test_nifs_gadget_opt,
180        },
181    };
182
183    #[test]
184    fn test_nifs_gadget() {
185        let mut rng = ark_std::test_rng();
186        // prepare the committed instances to test in-circuit
187        let ci: Vec<CommittedInstance<Projective>> = (0..2)
188            .into_iter()
189            .map(|_| CommittedInstance::<Projective> {
190                cmE: Projective::rand(&mut rng),
191                u: Fr::rand(&mut rng),
192                cmW: Projective::rand(&mut rng),
193                x: vec![Fr::rand(&mut rng); 1],
194            })
195            .collect();
196        let cmT = Projective::rand(&mut rng);
197
198        let (ci_out, ciVar_out) = test_nifs_gadget_opt::<
199            NIFS<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
200            NIFSGadget<Projective, PoseidonSponge<Fr>, PoseidonSpongeVar<Fr>>,
201        >(ci, cmT)
202        .unwrap();
203        assert_eq!(ciVar_out.u.value().unwrap(), ci_out.u);
204        assert_eq!(ciVar_out.x.value().unwrap(), ci_out.x);
205    }
206
207    #[test]
208    fn test_committed_instance_to_sponge_preimage() {
209        let mut rng = ark_std::test_rng();
210        let ci = CommittedInstance::<Projective> {
211            cmE: Projective::rand(&mut rng),
212            u: Fr::rand(&mut rng),
213            cmW: Projective::rand(&mut rng),
214            x: vec![Fr::rand(&mut rng); 1],
215        };
216
217        test_committed_instance_to_sponge_preimage_opt::<
218            NIFS<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
219            NIFSGadget<Projective, PoseidonSponge<Fr>, PoseidonSpongeVar<Fr>>,
220        >(ci);
221    }
222
223    #[test]
224    fn test_committed_instance_hash() {
225        let mut rng = ark_std::test_rng();
226        let ci = CommittedInstance::<Projective> {
227            cmE: Projective::rand(&mut rng),
228            u: Fr::rand(&mut rng),
229            cmW: Projective::rand(&mut rng),
230            x: vec![Fr::rand(&mut rng); 1],
231        };
232        test_committed_instance_hash_opt::<
233            NIFS<Projective, Pedersen<Projective>, PoseidonSponge<Fr>>,
234            NIFSGadget<Projective, PoseidonSponge<Fr>, PoseidonSpongeVar<Fr>>,
235        >(ci);
236    }
237}