1use ark_crypto_primitives::sponge::{
  2    poseidon::constraints::PoseidonSpongeVar, CryptographicSponge,
  3};
  4use ark_ec::CurveGroup;
  5use ark_ff::PrimeField;
  6use ark_poly::Polynomial;
  7use ark_r1cs_std::{
  8    fields::{fp::FpVar, FieldVar},
  9    poly::{domain::Radix2DomainVar, evaluations::univariate::EvaluationsVar},
 10    ToConstraintFieldGadget,
 11};
 12use ark_relations::r1cs::SynthesisError;
 13use ark_std::log2;
 14
 15use crate::folding::traits::{CommittedInstanceOps, CommittedInstanceVarOps, Dummy, WitnessOps};
 16use crate::transcript::{Transcript, TranscriptVar};
 17use crate::utils::vec::poly_from_vec;
 18use crate::Error;
 19use crate::{arith::Arith, folding::circuits::CF1};
 20
 21pub mod off_chain;
 22pub mod on_chain;
 23
 24/// Gadget that computes the KZG challenges.
 25/// It also offers the rust native implementation compatible with the gadget.
 26pub struct KZGChallengesGadget {}
 27
 28impl KZGChallengesGadget {
 29    pub fn get_challenges_native<
 30        C: CurveGroup,
 31        T: Transcript<CF1<C>>,
 32        U: CommittedInstanceOps<C>,
 33    >(
 34        transcript: &mut T,
 35        U_i: &U,
 36    ) -> Vec<CF1<C>> {
 37        let mut challenges = vec![];
 38        for cm in U_i.get_commitments() {
 39            transcript.absorb_nonnative(&cm);
 40            challenges.push(transcript.get_challenge());
 41        }
 42        challenges
 43    }
 44
 45    pub fn get_challenges_gadget<
 46        C: CurveGroup,
 47        S: CryptographicSponge,
 48        T: TranscriptVar<CF1<C>, S>,
 49        U: CommittedInstanceVarOps<C>,
 50    >(
 51        transcript: &mut T,
 52        U_i: &U,
 53    ) -> Result<Vec<FpVar<CF1<C>>>, SynthesisError> {
 54        let mut challenges = vec![];
 55        for cm in U_i.get_commitments() {
 56            transcript.absorb(&cm.to_constraint_field()?)?;
 57            challenges.push(transcript.get_challenge()?);
 58        }
 59        Ok(challenges)
 60    }
 61}
 62
 63/// Gadget that interpolates the polynomial from the given vector and returns
 64/// its evaluation at the given point.
 65/// It also offers the rust native implementation compatible with the gadget.
 66pub struct EvalGadget {}
 67
 68impl EvalGadget {
 69    pub fn evaluate_native<F: PrimeField>(v: &[F], point: F) -> Result<F, Error> {
 70        let mut v = v.to_vec();
 71        v.resize(v.len().next_power_of_two(), F::zero());
 72
 73        Ok(poly_from_vec(v)?.evaluate(&point))
 74    }
 75
 76    pub fn evaluate_gadget<F: PrimeField>(
 77        v: &[FpVar<F>],
 78        point: &FpVar<F>,
 79    ) -> Result<FpVar<F>, SynthesisError> {
 80        let mut v = v.to_vec();
 81        v.resize(v.len().next_power_of_two(), FpVar::zero());
 82        let n = v.len() as u64;
 83        let gen = F::get_root_of_unity(n).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
 84        // `unwrap` below is safe because `Radix2DomainVar::new` only fails if
 85        // `offset.enforce_not_equal(&FpVar::zero())` returns an error.
 86        // But in our case, `offset` is `FpVar::one()`, i.e., both operands of
 87        // `enforce_not_equal` are constants.
 88        // Consequently, `FpVar`'s implementation of `enforce_not_equal` will
 89        // always return `Ok(())`.
 90        let domain = Radix2DomainVar::new(gen, log2(v.len()) as u64, FpVar::one()).unwrap();
 91
 92        let evaluations_var = EvaluationsVar::from_vec_and_domain(v, domain, true);
 93        evaluations_var.interpolate_and_evaluate(point)
 94    }
 95}
 96
 97/// This is a temporary workaround for step 6 (running NIFS.V for group elements
 98/// in circuit) in an NIFS-agnostic way, because different folding schemes have
 99/// different interfaces of folding verification now.
100///
101/// In the future, we may introduce a better solution that uses a trait for all
102/// folding schemes that specifies their native and in-circuit behaviors.
103pub trait DeciderEnabledNIFS<
104    C: CurveGroup,
105    RU: CommittedInstanceOps<C>, // Running instance
106    IU: CommittedInstanceOps<C>, // Incoming instance
107    W: WitnessOps<CF1<C>>,
108    A: Arith<W, RU>,
109>
110{
111    type ProofDummyCfg;
112    type Proof: Dummy<Self::ProofDummyCfg>;
113    type RandomnessDummyCfg;
114    type Randomness: Dummy<Self::RandomnessDummyCfg>;
115
116    /// Fold the field elements in `U` and `u` inside the circuit.
117    ///
118    /// `U_vec` is `U` expressed as a vector of `FpVar`s, which can be reused
119    /// before or after calling this function to save constraints.
120    #[allow(clippy::too_many_arguments)]
121    fn fold_field_elements_gadget(
122        arith: &A,
123        transcript: &mut PoseidonSpongeVar<CF1<C>>,
124        pp_hash: FpVar<CF1<C>>,
125        U: RU::Var,
126        U_vec: Vec<FpVar<CF1<C>>>,
127        u: IU::Var,
128        proof: Self::Proof,
129        randomness: Self::Randomness,
130    ) -> Result<RU::Var, SynthesisError>;
131
132    /// Fold the group elements (i.e., commitments) in `U` and `u` outside the
133    /// circuit.
134    fn fold_group_elements_native(
135        U_commitments: &[C],
136        u_commitments: &[C],
137        proof: Option<Self::Proof>,
138        randomness: Self::Randomness,
139    ) -> Result<Vec<C>, Error>;
140}
141
142#[cfg(test)]
143pub mod tests {
144    use ark_crypto_primitives::sponge::{
145        constraints::CryptographicSpongeVar, poseidon::PoseidonSponge,
146    };
147    use ark_pallas::{Fr, Projective};
148    use ark_r1cs_std::{alloc::AllocVar, R1CSVar};
149    use ark_relations::r1cs::ConstraintSystem;
150    use ark_std::UniformRand;
151
152    use super::*;
153    use crate::folding::nova::{circuits::CommittedInstanceVar, CommittedInstance};
154    use crate::transcript::poseidon::poseidon_canonical_config;
155
156    // checks that the gadget and native implementations of the challenge computation match
157    #[test]
158    fn test_kzg_challenge_gadget() {
159        let mut rng = ark_std::test_rng();
160        let poseidon_config = poseidon_canonical_config::<Fr>();
161        let mut transcript = PoseidonSponge::<Fr>::new(&poseidon_config);
162
163        let U_i = CommittedInstance::<Projective> {
164            cmE: Projective::rand(&mut rng),
165            u: Fr::rand(&mut rng),
166            cmW: Projective::rand(&mut rng),
167            x: vec![Fr::rand(&mut rng); 1],
168        };
169
170        // compute the challenge natively
171        let challenges = KZGChallengesGadget::get_challenges_native(&mut transcript, &U_i);
172
173        let cs = ConstraintSystem::<Fr>::new_ref();
174        let U_iVar =
175            CommittedInstanceVar::<Projective>::new_witness(cs.clone(), || Ok(U_i.clone()))
176                .unwrap();
177        let mut transcript_var = PoseidonSpongeVar::<Fr>::new(cs.clone(), &poseidon_config);
178
179        let challenges_var =
180            KZGChallengesGadget::get_challenges_gadget(&mut transcript_var, &U_iVar).unwrap();
181        assert!(cs.is_satisfied().unwrap());
182
183        // check that the natively computed and in-circuit computed hashes match
184        assert_eq!(challenges_var.value().unwrap(), challenges);
185    }
186
187    #[test]
188    fn test_polynomial_interpolation() {
189        let mut rng = ark_std::test_rng();
190        let n = 12;
191        let l = 1 << n;
192
193        let v: Vec<Fr> = std::iter::repeat_with(|| Fr::rand(&mut rng))
194            .take(l)
195            .collect();
196        let challenge = Fr::rand(&mut rng);
197
198        use ark_poly::Polynomial;
199        let polynomial = poly_from_vec(v.to_vec()).unwrap();
200        let eval = polynomial.evaluate(&challenge);
201
202        let cs = ConstraintSystem::<Fr>::new_ref();
203        let vVar = Vec::<FpVar<Fr>>::new_witness(cs.clone(), || Ok(v)).unwrap();
204        let challengeVar = FpVar::<Fr>::new_witness(cs.clone(), || Ok(challenge)).unwrap();
205
206        let evalVar = EvalGadget::evaluate_gadget(&vVar, &challengeVar).unwrap();
207
208        assert_eq!(evalVar.value().unwrap(), eval);
209        assert!(cs.is_satisfied().unwrap());
210    }
211}