ark_circom/circom/
qap.rs

1use ark_ff::PrimeField;
2use ark_groth16::r1cs_to_qap::{LibsnarkReduction, R1CSToQAP, evaluate_constraint};
3use ark_poly::EvaluationDomain;
4use ark_relations::gr1cs::ConstraintSystemRef;
5use ark_relations::gr1cs::SynthesisError;
6use ark_std::vec;
7use rayon::prelude::*;
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_from_matrices<F: PrimeField, D: EvaluationDomain<F>>(
25        matrices: &[Vec<Vec<(F, usize)>>],
26        num_inputs: usize,
27        num_constraints: usize,
28        full_assignment: &[F],
29    ) -> Result<Vec<F>, SynthesisError> {
30        let zero = F::zero();
31        let domain =
32            D::new(num_constraints + num_inputs).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
33        let domain_size = domain.size();
34
35        let mut a = vec![zero; domain_size];
36        let mut b = vec![zero; domain_size];
37
38        a[..num_constraints]
39            .par_iter_mut()
40            .zip(&mut (b[..num_constraints]))
41            .zip(&matrices[0])
42            .zip(&matrices[1])
43            .for_each(|(((a, b), at_i), bt_i)| {
44                *a = evaluate_constraint(at_i, full_assignment);
45                *b = evaluate_constraint(bt_i, full_assignment);
46            });
47
48        {
49            let start = num_constraints;
50            let end = start + num_inputs;
51            a[start..end].clone_from_slice(&full_assignment[..num_inputs]);
52        }
53
54        let mut c = vec![zero; domain_size];
55        c[..num_constraints]
56            .par_iter_mut()
57            .zip(&a)
58            .zip(&b)
59            .for_each(|((c_i, &a), &b)| {
60                *c_i = a * b;
61            });
62
63        domain.ifft_in_place(&mut a);
64        domain.ifft_in_place(&mut b);
65
66        let root_of_unity = {
67            let domain_size_double = 2 * domain_size;
68            let domain_double =
69                D::new(domain_size_double).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
70            domain_double.element(1)
71        };
72        D::distribute_powers_and_mul_by_const(&mut a, root_of_unity, F::one());
73        D::distribute_powers_and_mul_by_const(&mut b, root_of_unity, F::one());
74
75        domain.fft_in_place(&mut a);
76        domain.fft_in_place(&mut b);
77
78        let mut ab = domain.mul_polynomials_in_evaluation_domain(&a, &b);
79        drop(a);
80        drop(b);
81
82        domain.ifft_in_place(&mut c);
83        D::distribute_powers_and_mul_by_const(&mut c, root_of_unity, F::one());
84        domain.fft_in_place(&mut c);
85
86        ab.par_iter_mut()
87            .zip(c)
88            .for_each(|(ab_i, c_i)| *ab_i -= &c_i);
89
90        Ok(ab)
91    }
92
93    fn h_query_scalars<F: PrimeField, D: EvaluationDomain<F>>(
94        max_power: usize,
95        t: F,
96        _: F,
97        delta_inverse: F,
98    ) -> Result<Vec<F>, SynthesisError> {
99        // the usual H query has domain-1 powers. Z has domain powers. So HZ has 2*domain-1 powers.
100        let mut scalars = (0..2 * max_power + 1)
101            .into_par_iter()
102            .map(|i| delta_inverse * t.pow([i as u64]))
103            .collect::<Vec<_>>();
104        let domain_size = scalars.len();
105        let domain = D::new(domain_size).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
106        // generate the lagrange coefficients
107        domain.ifft_in_place(&mut scalars);
108        Ok(scalars.into_par_iter().skip(1).step_by(2).collect())
109    }
110}
ark_circom/circom/qap.rs

ark_circom/circom/
qap.rs
