1use ark_crypto_primitives::sponge::CryptographicSponge;
  2use ark_ec::CurveGroup;
  3use ark_poly::{univariate::DensePolynomial, EvaluationDomain, GeneralEvaluationDomain};
  4use ark_r1cs_std::{
  5    alloc::AllocVar,
  6    fields::{fp::FpVar, FieldVar},
  7    poly::polynomial::univariate::dense::DensePolynomialVar,
  8};
  9use ark_relations::r1cs::{ConstraintSystemRef, SynthesisError};
 10
 11use super::{
 12    folding::lagrange_polys,
 13    utils::{all_powers_var, betas_star_var, exponential_powers_var},
 14    CommittedInstanceVar,
 15};
 16use crate::{
 17    folding::circuits::nonnative::affine::NonNativeAffineVar, transcript::TranscriptVar,
 18    utils::gadgets::VectorGadget,
 19};
 20
 21pub struct FoldingGadget {}
 22
 23impl FoldingGadget {
 24    pub fn fold_committed_instance<C: CurveGroup, S: CryptographicSponge>(
 25        transcript: &mut impl TranscriptVar<C::ScalarField, S>,
 26        // running instance
 27        instance: &CommittedInstanceVar<C>,
 28        // incoming instances
 29        vec_instances: &[CommittedInstanceVar<C>],
 30        // polys from P
 31        F_coeffs: Vec<FpVar<C::ScalarField>>,
 32        K_coeffs: Vec<FpVar<C::ScalarField>>,
 33    ) -> Result<CommittedInstanceVar<C>, SynthesisError> {
 34        let t = instance.betas.len();
 35        let n = F_coeffs.len();
 36
 37        // absorb the committed instances
 38        transcript.absorb(instance)?;
 39        transcript.absorb(&vec_instances)?;
 40
 41        let delta = transcript.get_challenge()?;
 42        let deltas = exponential_powers_var(delta, t);
 43
 44        transcript.absorb(&F_coeffs)?;
 45
 46        let alpha = transcript.get_challenge()?;
 47        let alphas = all_powers_var(alpha.clone(), n);
 48
 49        // F(alpha) = e + \sum_t F_i * alpha^i
 50        let mut F_alpha = instance.e.clone();
 51        for (i, F_i) in F_coeffs.iter().skip(1).enumerate() {
 52            F_alpha += F_i * &alphas[i + 1];
 53        }
 54
 55        let betas_star = betas_star_var(&instance.betas, &deltas, &alpha);
 56
 57        let k = vec_instances.len();
 58        let H = GeneralEvaluationDomain::new(k + 1).unwrap();
 59        let L_X = lagrange_polys(H)
 60            .into_iter()
 61            .map(|poly| {
 62                DensePolynomialVar::from_coefficients_vec(
 63                    poly.coeffs
 64                        .into_iter()
 65                        .map(FpVar::constant)
 66                        .collect::<Vec<_>>(),
 67                )
 68            })
 69            .collect::<Vec<_>>();
 70        let Z_X = DensePolynomialVar::from_coefficients_vec(
 71            DensePolynomial::from(H.vanishing_polynomial())
 72                .coeffs
 73                .into_iter()
 74                .map(FpVar::constant)
 75                .collect::<Vec<_>>(),
 76        );
 77        let K_X = DensePolynomialVar { coeffs: K_coeffs };
 78
 79        transcript.absorb(&K_X.coeffs)?;
 80
 81        let gamma = transcript.get_challenge()?;
 82
 83        let L_X_evals = L_X
 84            .iter()
 85            .take(k + 1)
 86            .map(|L| L.evaluate(&gamma))
 87            .collect::<Result<Vec<_>, _>>()?;
 88
 89        let e_star = F_alpha * &L_X_evals[0] + Z_X.evaluate(&gamma)? * K_X.evaluate(&gamma)?;
 90
 91        let mut u_star = &instance.u * &L_X_evals[0];
 92        let mut x_star = instance.x.mul_scalar(&L_X_evals[0])?;
 93        for i in 0..k {
 94            u_star += &vec_instances[i].u * &L_X_evals[i + 1];
 95            x_star = x_star.add(&vec_instances[i].x.mul_scalar(&L_X_evals[i + 1])?)?;
 96        }
 97
 98        // return the folded instance
 99        Ok(CommittedInstanceVar {
100            betas: betas_star,
101            // phi will be computed in CycleFold
102            phi: NonNativeAffineVar::new_constant(ConstraintSystemRef::None, C::zero())?,
103            e: e_star,
104            u: u_star,
105            x: x_star,
106        })
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use ark_crypto_primitives::sponge::{
113        constraints::CryptographicSpongeVar,
114        poseidon::{constraints::PoseidonSpongeVar, PoseidonSponge},
115    };
116    use ark_pallas::{Fr, Projective};
117    use ark_r1cs_std::R1CSVar;
118    use ark_relations::r1cs::ConstraintSystem;
119    use std::error::Error;
120
121    use super::*;
122    use crate::{
123        arith::r1cs::tests::get_test_r1cs,
124        folding::protogalaxy::folding::{tests::prepare_inputs, Folding},
125        transcript::poseidon::poseidon_canonical_config,
126    };
127
128    #[test]
129    fn test_fold_gadget() -> Result<(), Box<dyn Error>> {
130        let k = 7;
131        let (witness, instance, witnesses, instances) = prepare_inputs(k);
132        let r1cs = get_test_r1cs::<Fr>();
133
134        // init Prover & Verifier's transcript
135        let poseidon_config = poseidon_canonical_config::<Fr>();
136        let mut transcript_p = PoseidonSponge::new(&poseidon_config);
137        let mut transcript_v = PoseidonSponge::new(&poseidon_config);
138
139        let (_, _, F_coeffs, K_coeffs) = Folding::<Projective>::prove(
140            &mut transcript_p,
141            &r1cs,
142            &instance,
143            &witness,
144            &instances,
145            &witnesses,
146        )?;
147
148        let folded_instance = Folding::<Projective>::verify(
149            &mut transcript_v,
150            &r1cs,
151            &instance,
152            &instances,
153            F_coeffs.clone(),
154            K_coeffs.clone(),
155        )?;
156
157        let cs = ConstraintSystem::new_ref();
158        let mut transcript_var = PoseidonSpongeVar::new(cs.clone(), &poseidon_config);
159        let instance_var = CommittedInstanceVar::new_witness(cs.clone(), || Ok(instance))?;
160        let instances_var = Vec::new_witness(cs.clone(), || Ok(instances))?;
161        let F_coeffs_var = Vec::new_witness(cs.clone(), || Ok(F_coeffs))?;
162        let K_coeffs_var = Vec::new_witness(cs.clone(), || Ok(K_coeffs))?;
163
164        let folded_instance_var = FoldingGadget::fold_committed_instance(
165            &mut transcript_var,
166            &instance_var,
167            &instances_var,
168            F_coeffs_var,
169            K_coeffs_var,
170        )?;
171        assert_eq!(folded_instance.betas, folded_instance_var.betas.value()?);
172        assert_eq!(folded_instance.e, folded_instance_var.e.value()?);
173        assert_eq!(folded_instance.u, folded_instance_var.u.value()?);
174        assert_eq!(folded_instance.x, folded_instance_var.x.value()?);
175        assert!(cs.is_satisfied()?);
176
177        Ok(())
178    }
179}