ark_groth16/
generator.rs

1use crate::{r1cs_to_qap::R1CSToQAP, Groth16, ProvingKey, Vec, VerifyingKey};
2use ark_ec::{pairing::Pairing, scalar_mul::BatchMulPreprocessing, CurveGroup};
3use ark_ff::{Field, UniformRand, Zero};
4use ark_poly::{EvaluationDomain, GeneralEvaluationDomain};
5use ark_relations::r1cs::{
6    ConstraintSynthesizer, ConstraintSystem, OptimizationGoal, Result as R1CSResult,
7    SynthesisError, SynthesisMode,
8};
9use ark_std::rand::Rng;
10use ark_std::{cfg_into_iter, cfg_iter};
11
12#[cfg(feature = "parallel")]
13use rayon::prelude::*;
14
15impl<E: Pairing, QAP: R1CSToQAP> Groth16<E, QAP> {
16    /// Generates a random common reference string for
17    /// a circuit using the provided R1CS-to-QAP reduction.
18    #[inline]
19    pub fn generate_random_parameters_with_reduction<C>(
20        circuit: C,
21        rng: &mut impl Rng,
22    ) -> R1CSResult<ProvingKey<E>>
23    where
24        C: ConstraintSynthesizer<E::ScalarField>,
25    {
26        let alpha = E::ScalarField::rand(rng);
27        let beta = E::ScalarField::rand(rng);
28        let gamma = E::ScalarField::rand(rng);
29        let delta = E::ScalarField::rand(rng);
30
31        let g1_generator = E::G1::rand(rng);
32        let g2_generator = E::G2::rand(rng);
33
34        Self::generate_parameters_with_qap(
35            circuit,
36            alpha,
37            beta,
38            gamma,
39            delta,
40            g1_generator,
41            g2_generator,
42            rng,
43        )
44    }
45
46    /// Create parameters for a circuit, given some toxic waste, R1CS to QAP calculator and group generators
47    pub fn generate_parameters_with_qap<C>(
48        circuit: C,
49        alpha: E::ScalarField,
50        beta: E::ScalarField,
51        gamma: E::ScalarField,
52        delta: E::ScalarField,
53        g1_generator: E::G1,
54        g2_generator: E::G2,
55        rng: &mut impl Rng,
56    ) -> R1CSResult<ProvingKey<E>>
57    where
58        C: ConstraintSynthesizer<E::ScalarField>,
59    {
60        type D<F> = GeneralEvaluationDomain<F>;
61
62        let setup_time = start_timer!(|| "Groth16::Generator");
63        let cs = ConstraintSystem::new_ref();
64        cs.set_optimization_goal(OptimizationGoal::Constraints);
65        cs.set_mode(SynthesisMode::Setup);
66
67        // Synthesize the circuit.
68        let synthesis_time = start_timer!(|| "Constraint synthesis");
69        circuit.generate_constraints(cs.clone())?;
70        end_timer!(synthesis_time);
71
72        let lc_time = start_timer!(|| "Inlining LCs");
73        cs.finalize();
74        end_timer!(lc_time);
75
76        // Following is the mapping of symbols from the Groth16 paper to this implementation
77        // l -> num_instance_variables
78        // m -> qap_num_variables
79        // x -> t
80        // t(x) - zt
81        // u_i(x) -> a
82        // v_i(x) -> b
83        // w_i(x) -> c
84
85        ///////////////////////////////////////////////////////////////////////////
86        let domain_time = start_timer!(|| "Constructing evaluation domain");
87
88        let domain_size = cs.num_constraints() + cs.num_instance_variables();
89        let domain = D::new(domain_size).ok_or(SynthesisError::PolynomialDegreeTooLarge)?;
90        let t = domain.sample_element_outside_domain(rng);
91
92        end_timer!(domain_time);
93        ///////////////////////////////////////////////////////////////////////////
94
95        let reduction_time = start_timer!(|| "R1CS to QAP Instance Map with Evaluation");
96        let num_instance_variables = cs.num_instance_variables();
97        let (a, b, c, zt, qap_num_variables, m_raw) =
98            QAP::instance_map_with_evaluation::<E::ScalarField, D<E::ScalarField>>(cs, &t)?;
99        end_timer!(reduction_time);
100
101        // Compute query densities
102        let non_zero_a: usize = cfg_into_iter!(0..qap_num_variables)
103            .map(|i| usize::from(!a[i].is_zero()))
104            .sum();
105
106        let non_zero_b: usize = cfg_into_iter!(0..qap_num_variables)
107            .map(|i| usize::from(!b[i].is_zero()))
108            .sum();
109
110        let gamma_inverse = gamma.inverse().ok_or(SynthesisError::UnexpectedIdentity)?;
111        let delta_inverse = delta.inverse().ok_or(SynthesisError::UnexpectedIdentity)?;
112
113        let gamma_abc = cfg_iter!(a[..num_instance_variables])
114            .zip(&b[..num_instance_variables])
115            .zip(&c[..num_instance_variables])
116            .map(|((a, b), c)| (beta * a + &(alpha * b) + c) * &gamma_inverse)
117            .collect::<Vec<_>>();
118
119        let l = cfg_iter!(a[num_instance_variables..])
120            .zip(&b[num_instance_variables..])
121            .zip(&c[num_instance_variables..])
122            .map(|((a, b), c)| (beta * a + &(alpha * b) + c) * &delta_inverse)
123            .collect::<Vec<_>>();
124
125        drop(c);
126
127        // Compute B window table
128        let g2_time = start_timer!(|| "Compute G2 table");
129        let g2_table = BatchMulPreprocessing::new(g2_generator, non_zero_b);
130        end_timer!(g2_time);
131
132        // Compute the B-query in G2
133        let b_g2_time = start_timer!(|| format!("Calculate B G2 of size {}", b.len()));
134        let b_g2_query = g2_table.batch_mul(&b);
135        drop(g2_table);
136        end_timer!(b_g2_time);
137
138        // Compute G window table
139        let g1_window_time = start_timer!(|| "Compute G1 window table");
140        let num_scalars = non_zero_a + non_zero_b + qap_num_variables + m_raw + 1;
141        let g1_table = BatchMulPreprocessing::new(g1_generator, num_scalars);
142        end_timer!(g1_window_time);
143
144        // Generate the R1CS proving key
145        let proving_key_time = start_timer!(|| "Generate the R1CS proving key");
146
147        let alpha_g1 = g1_generator * &alpha;
148        let beta_g1 = g1_generator * &beta;
149        let beta_g2 = g2_generator * &beta;
150        let delta_g1 = g1_generator * &delta;
151        let delta_g2 = g2_generator * &delta;
152
153        // Compute the A-query
154        let a_time = start_timer!(|| "Calculate A");
155        let a_query = g1_table.batch_mul(&a);
156        drop(a);
157        end_timer!(a_time);
158
159        // Compute the B-query in G1
160        let b_g1_time = start_timer!(|| "Calculate B G1");
161        let b_g1_query = g1_table.batch_mul(&b);
162        drop(b);
163        end_timer!(b_g1_time);
164
165        // Compute the H-query
166        let h_time = start_timer!(|| "Calculate H");
167        let h_scalars =
168            QAP::h_query_scalars::<_, D<E::ScalarField>>(m_raw - 1, t, zt, delta_inverse)?;
169        let h_query = g1_table.batch_mul(&h_scalars);
170        end_timer!(h_time);
171
172        // Compute the L-query
173        let l_time = start_timer!(|| "Calculate L");
174        let l_query = g1_table.batch_mul(&l);
175        drop(l);
176        end_timer!(l_time);
177
178        end_timer!(proving_key_time);
179
180        // Generate R1CS verification key
181        let verifying_key_time = start_timer!(|| "Generate the R1CS verification key");
182        let gamma_g2 = g2_generator * &gamma;
183        let gamma_abc_g1 = g1_table.batch_mul(&gamma_abc);
184        drop(g1_table);
185
186        end_timer!(verifying_key_time);
187
188        let vk = VerifyingKey::<E> {
189            alpha_g1: alpha_g1.into_affine(),
190            beta_g2: beta_g2.into_affine(),
191            gamma_g2: gamma_g2.into_affine(),
192            delta_g2: delta_g2.into_affine(),
193            gamma_abc_g1,
194        };
195
196        end_timer!(setup_time);
197
198        Ok(ProvingKey {
199            vk,
200            beta_g1: beta_g1.into_affine(),
201            delta_g1: delta_g1.into_affine(),
202            a_query,
203            b_g1_query,
204            b_g2_query,
205            h_query,
206            l_query,
207        })
208    }
209}
ark_groth16/generator.rs

ark_groth16/
generator.rs
