1use ark_ff::PrimeField;
  2use ark_groth16::r1cs_to_qap::{evaluate_constraint, LibsnarkReduction, R1CSToQAP};
  3use ark_poly::EvaluationDomain;
  4use ark_relations::r1cs::{ConstraintMatrices, ConstraintSystemRef, SynthesisError};
  5use ark_std::{cfg_into_iter, cfg_iter, cfg_iter_mut, vec};
  6
  7/// Implements the witness map used by snarkjs. The arkworks witness map calculates the
  8/// coefficients of H through computing (AB-C)/Z in the evaluation domain and going back to the
  9/// coefficients domain. snarkjs instead precomputes the Lagrange form of the powers of tau bases
 10/// in a domain twice as large and the witness map is computed as the odd coefficients of (AB-C)
 11/// in that domain. This serves as HZ when computing the C proof element.
 12pub struct CircomReduction;
 13
 14impl R1CSToQAP for CircomReduction {
 15    #[allow(clippy::type_complexity)]
 16    fn instance_map_with_evaluation<F: PrimeField, D: EvaluationDomain<F>>(
 17        cs: ConstraintSystemRef<F>,
 18        t: &F,
 19    ) -> Result<(Vec<F>, Vec<F>, Vec<F>, F, usize, usize), SynthesisError> {
 20        LibsnarkReduction::instance_map_with_evaluation::<F, D>(cs, t)
 21    }
 22
 23    fn witness_map_from_matrices<F: PrimeField, D: EvaluationDomain<F>>(
 24        matrices: &ConstraintMatrices<F>,
 25        num_inputs: usize,
 26        num_constraints: usize,
 27        full_assignment: &[F],
 28    ) -> Result<Vec<F>, SynthesisError> {
 29        let zero = F::zero();
 30        let domain =
 31            D::new(num_constraints + num_inputs).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
 32        let domain_size = domain.size();
 33
 34        let mut a = vec![zero; domain_size];
 35        let mut b = vec![zero; domain_size];
 36
 37        cfg_iter_mut!(a[..num_constraints])
 38            .zip(cfg_iter_mut!(b[..num_constraints]))
 39            .zip(cfg_iter!(&matrices.a))
 40            .zip(cfg_iter!(&matrices.b))
 41            .for_each(|(((a, b), at_i), bt_i)| {
 42                *a = evaluate_constraint(at_i, full_assignment);
 43                *b = evaluate_constraint(bt_i, full_assignment);
 44            });
 45
 46        {
 47            let start = num_constraints;
 48            let end = start + num_inputs;
 49            a[start..end].clone_from_slice(&full_assignment[..num_inputs]);
 50        }
 51
 52        let mut c = vec![zero; domain_size];
 53        cfg_iter_mut!(c[..num_constraints])
 54            .zip(&a)
 55            .zip(&b)
 56            .for_each(|((c_i, &a), &b)| {
 57                *c_i = a * b;
 58            });
 59
 60        domain.ifft_in_place(&mut a);
 61        domain.ifft_in_place(&mut b);
 62
 63        let root_of_unity = {
 64            let domain_size_double = 2 * domain_size;
 65            let domain_double =
 66                D::new(domain_size_double).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
 67            domain_double.element(1)
 68        };
 69        D::distribute_powers_and_mul_by_const(&mut a, root_of_unity, F::one());
 70        D::distribute_powers_and_mul_by_const(&mut b, root_of_unity, F::one());
 71
 72        domain.fft_in_place(&mut a);
 73        domain.fft_in_place(&mut b);
 74
 75        let mut ab = domain.mul_polynomials_in_evaluation_domain(&a, &b);
 76        drop(a);
 77        drop(b);
 78
 79        domain.ifft_in_place(&mut c);
 80        D::distribute_powers_and_mul_by_const(&mut c, root_of_unity, F::one());
 81        domain.fft_in_place(&mut c);
 82
 83        cfg_iter_mut!(ab)
 84            .zip(c)
 85            .for_each(|(ab_i, c_i)| *ab_i -= &c_i);
 86
 87        Ok(ab)
 88    }
 89
 90    fn h_query_scalars<F: PrimeField, D: EvaluationDomain<F>>(
 91        max_power: usize,
 92        t: F,
 93        _: F,
 94        delta_inverse: F,
 95    ) -> Result<Vec<F>, SynthesisError> {
 96        // the usual H query has domain-1 powers. Z has domain powers. So HZ has 2*domain-1 powers.
 97        let mut scalars = cfg_into_iter!(0..2 * max_power + 1)
 98            .map(|i| delta_inverse * t.pow([i as u64]))
 99            .collect::<Vec<_>>();
100        let domain_size = scalars.len();
101        let domain = D::new(domain_size).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
102        // generate the lagrange coefficients
103        domain.ifft_in_place(&mut scalars);
104        Ok(cfg_into_iter!(scalars).skip(1).step_by(2).collect())
105    }
106}