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 #[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 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 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 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 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 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 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 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 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 let proving_key_time = start_timer!(|| "Generate the R1CS proving key");
146
147 let alpha_g1 = g1_generator * α
148 let beta_g1 = g1_generator * β
149 let beta_g2 = g2_generator * β
150 let delta_g1 = g1_generator * δ
151 let delta_g2 = g2_generator * δ
152
153 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 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 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 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 let verifying_key_time = start_timer!(|| "Generate the R1CS verification key");
182 let gamma_g2 = g2_generator * γ
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}