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