ark-r1cs-std/r1cs-std/src/pairing/mnt6/mod.rs
r1cs-std/src/pairing/mnt6/mod.rsRaw
1use r1cs_core::{ConstraintSystem, SynthesisError};
2
3use super::PairingGadget as PG;
4
5use crate::{
6 fields::{fp::FpGadget, fp3::Fp3Gadget, fp6_2over3::Fp6Gadget, FieldGadget},
7 groups::mnt6::{
8 AteAdditionCoefficientsGadget, AteDoubleCoefficientsGadget, G1Gadget, G1PreparedGadget,
9 G2Gadget, G2PreparedGadget, G2ProjectiveExtendedGadget,
10 },
11};
12use algebra::{
13 curves::mnt6::{MNT6Parameters, MNT6},
14 fields::BitIterator,
15};
16use core::marker::PhantomData;
17
18pub struct PairingGadget<P: MNT6Parameters>(PhantomData<P>);
19
20type Fp3G<P> = Fp3Gadget<<P as MNT6Parameters>::Fp3Params, <P as MNT6Parameters>::Fp>;
21type Fp6G<P> = Fp6Gadget<<P as MNT6Parameters>::Fp6Params, <P as MNT6Parameters>::Fp>;
22pub type GTGadget<P> = Fp6G<P>;
23
24impl<P: MNT6Parameters> PairingGadget<P> {
25 pub(crate) fn doubling_step_for_flipped_miller_loop<CS: ConstraintSystem<P::Fp>>(
26 mut cs: CS,
27 r: &G2ProjectiveExtendedGadget<P>,
28 ) -> Result<
29 (
30 G2ProjectiveExtendedGadget<P>,
31 AteDoubleCoefficientsGadget<P>,
32 ),
33 SynthesisError,
34 > {
35 let a = r.t.square(cs.ns(|| "r.t^2"))?;
36 let b = r.x.square(cs.ns(|| "r.x^2"))?;
37 let c = r.y.square(cs.ns(|| "r.y^2"))?;
38 let d = c.square(cs.ns(|| "c^2"))?;
39 let mut e = r.x.add(cs.ns(|| "r.x + c"), &c)?;
40 e.square_in_place(cs.ns(|| "(r.x + c)^2"))?;
41 e.sub_in_place(cs.ns(|| "(r.x + c)^2 - b"), &b)?;
42 e.sub_in_place(cs.ns(|| "(r.x + c)^2 - b - d"), &d)?;
43
44 let mut f = b.double(cs.ns(|| "b + b"))?;
45 f.add_in_place(cs.ns(|| "b + b + b"), &b)?;
46 let twist_a = a.mul_by_constant(cs.ns(|| "TWIST_COEFF_A * a"), &P::TWIST_COEFF_A)?;
47 f.add_in_place(cs.ns(|| "(b + b + b) + (TWIST_COEFF_A * a)"), &twist_a)?;
48 let g = f.square(cs.ns(|| "f^2"))?;
49
50 let d_eight = d
51 .double(cs.ns(|| "2 * d"))?
52 .double(cs.ns(|| "4 * d"))?
53 .double(cs.ns(|| "8 * d"))?;
54
55 let e2 = e.double(cs.ns(|| "2 * e"))?;
56 let e4 = e2.double(cs.ns(|| "4 * e"))?;
57 let x = g.sub(cs.ns(|| "- (e + e + e + e) + g"), &e4)?;
58
59 let mut y = e2.sub(cs.ns(|| "e + e - x"), &x)?;
60 y.mul_in_place(cs.ns(|| "f * (e + e - x)"), &f)?;
61 y.sub_in_place(cs.ns(|| "- d_eight + f * (e + e - x)"), &d_eight)?;
62 let mut z = r.y.add(cs.ns(|| "r.y + r.z"), &r.z)?;
63 z.square_in_place(cs.ns(|| "(r.y + r.z)^2"))?;
64 z.sub_in_place(cs.ns(|| "(r.y + r.z)^2 - c"), &c)?;
65 let z2 = r.z.square(cs.ns(|| "r.z^2"))?;
66 z.sub_in_place(cs.ns(|| "(r.y + r.z)^2 - c - r.z^2"), &z2)?;
67 let t = z.square(cs.ns(|| "z^2"))?;
68
69 let r2 = G2ProjectiveExtendedGadget { x, y, z, t };
70
71 let c_h =
72 r2.z.add(cs.ns(|| "r2.z + r.t"), &r.t)?
73 .square(cs.ns(|| "(r2.z + r.t)^2"))?
74 .sub(cs.ns(|| "(r2.z + r.t)^2 - r2.t"), &r2.t)?
75 .sub(cs.ns(|| "(r2.z + r.t)^2 - r2.t - a"), &a)?;
76 let c_4c = c.double(cs.ns(|| "2 * c"))?.double(cs.ns(|| "4 * c"))?;
77 let mut c_j = f.add(cs.ns(|| "f + r.t"), &r.t)?;
78 c_j.square_in_place(cs.ns(|| "(f + r.t)^2"))?;
79 c_j.sub_in_place(cs.ns(|| "(f + r.t)^2 - g"), &g)?;
80 c_j.sub_in_place(cs.ns(|| "(f + r.t)^2 - g - a"), &a)?;
81 let mut c_l = f.add(cs.ns(|| "f + r.x"), &r.x)?;
82 c_l.square_in_place(cs.ns(|| "(f + r.x)^2"))?;
83 c_l.sub_in_place(cs.ns(|| "(f + r.x)^2 - g"), &g)?;
84 c_l.sub_in_place(cs.ns(|| "(f + r.x)^2 - g - b"), &b)?;
85 let coeff = AteDoubleCoefficientsGadget {
86 c_h,
87 c_4c,
88 c_j,
89 c_l,
90 };
91
92 Ok((r2, coeff))
93 }
94
95 pub(crate) fn mixed_addition_step_for_flipped_miller_loop<CS: ConstraintSystem<P::Fp>>(
96 mut cs: CS,
97 x: &Fp3G<P>,
98 y: &Fp3G<P>,
99 r: &G2ProjectiveExtendedGadget<P>,
100 ) -> Result<
101 (
102 G2ProjectiveExtendedGadget<P>,
103 AteAdditionCoefficientsGadget<P>,
104 ),
105 SynthesisError,
106 > {
107 let a = y.square(cs.ns(|| "y^2"))?;
108 let b = r.t.mul(cs.ns(|| "r.t * x"), &x)?;
109 let mut d = r.z.add(cs.ns(|| "r.z + y"), &y)?;
110 d.square_in_place(cs.ns(|| "(r.z + y)^2"))?;
111 d.sub_in_place(cs.ns(|| "(r.z + y)^2 - a"), &a)?;
112 d.sub_in_place(cs.ns(|| "(r.z + y)^2 - a - r.t"), &r.t)?;
113 d.mul_in_place(cs.ns(|| "((r.z + y)^2 - a - r.t) * r.t"), &r.t)?;
114 let h = b.sub(cs.ns(|| "b - r.x"), &r.x)?;
115 let i = h.square(cs.ns(|| "h^2"))?;
116 let e = i.double(cs.ns(|| "2 * i"))?.double(cs.ns(|| "4 * i"))?;
117 let j = h.mul(cs.ns(|| "h * e"), &e)?;
118 let v = r.x.mul(cs.ns(|| "r.x * e"), &e)?;
119 let ry2 = r.y.double(cs.ns(|| "r.y + r.y"))?;
120 let l1 = d.sub(cs.ns(|| "d - (r.y + r.y)"), &ry2)?;
121
122 let v2 = v.double(cs.ns(|| "v + v"))?;
123 let x = l1
124 .square(cs.ns(|| "l1^2"))?
125 .sub(cs.ns(|| "l1^2 - j"), &j)?
126 .sub(cs.ns(|| "l1^2 - j - (v + v)"), &v2)?;
127 let v_minus_x = v.sub(cs.ns(|| "v - x"), &x)?;
128 let j_ry2 = j.mul(cs.ns(|| "j * (r.y + r.y)"), &ry2)?;
129 let y = l1
130 .mul(cs.ns(|| "l1 * (v - x)"), &v_minus_x)?
131 .sub(cs.ns(|| "l1 * (v - x) - (j * (r.y + r.y)"), &j_ry2)?;
132 let mut z = r.z.add(cs.ns(|| "r.z + h"), &h)?;
133 z.square_in_place(cs.ns(|| "(r.z + h)^2"))?;
134 z.sub_in_place(cs.ns(|| "(r.z + h)^2 - r.t"), &r.t)?;
135 z.sub_in_place(cs.ns(|| "(r.z + h)^2 - r.t - i"), &i)?;
136 let t = z.square(cs.ns(|| "z^2"))?;
137
138 let r2 = G2ProjectiveExtendedGadget {
139 x,
140 y,
141 z: z.clone(),
142 t,
143 };
144 let coeff = AteAdditionCoefficientsGadget { c_l1: l1, c_rz: z };
145
146 Ok((r2, coeff))
147 }
148
149 pub fn ate_miller_loop<CS: ConstraintSystem<P::Fp>>(
150 mut cs: CS,
151 p: &G1PreparedGadget<P>,
152 q: &G2PreparedGadget<P>,
153 ) -> Result<Fp6G<P>, SynthesisError> {
154 let zero = FpGadget::<P::Fp>::zero(cs.ns(|| "zero"))?;
155 let mut l1_coeff = Fp3G::<P>::new(p.x.clone(), zero.clone(), zero);
156 l1_coeff.sub_in_place(cs.ns(|| "l1_coeff"), &q.x_over_twist)?;
157
158 let mut f = Fp6G::<P>::one(cs.ns(|| "one"))?;
159
160 let mut dbl_idx: usize = 0;
161 let mut add_idx: usize = 0;
162
163 let mut found_one = false;
164
165 for (j, bit) in BitIterator::new(P::ATE_LOOP_COUNT).enumerate() {
166 // code below gets executed for all bits (EXCEPT the MSB itself) of
167 // mnt6_param_p (skipping leading zeros) in MSB to LSB order
168 if !found_one && bit {
169 found_one = true;
170 continue;
171 } else if !found_one {
172 continue;
173 }
174
175 let mut cs = cs.ns(|| format!("bit {}", j));
176
177 let dc = &q.double_coefficients[dbl_idx];
178 dbl_idx += 1;
179
180 let c_j_x_twist = dc.c_j.mul(cs.ns(|| "dc.c_j * p.x_twist"), &p.x_twist)?;
181 let c0 = dc.c_l.sub(cs.ns(|| "-dc.c_4c + dc.c_l"), &dc.c_4c)?.sub(
182 cs.ns(|| "-dc.c_4c - (dc.c_j * p.x_twist) + dc.c_l"),
183 &c_j_x_twist,
184 )?;
185 let c1 = dc.c_h.mul(cs.ns(|| "dc.c_h * p.y_twist"), &p.y_twist)?;
186 let g_rr_at_p = Fp6G::<P>::new(c0, c1);
187
188 f = f
189 .square(cs.ns(|| "f^2"))?
190 .mul(cs.ns(|| "f^2 * g_rr_at_p"), &g_rr_at_p)?;
191
192 if bit {
193 let ac = &q.addition_coefficients[add_idx];
194 add_idx += 1;
195
196 let l1_coeff_c_l1 = l1_coeff.mul(cs.ns(|| "l1_coeff * ac.c_l1"), &ac.c_l1)?;
197 let g_rq_at_p = Fp6G::<P>::new(
198 ac.c_rz.mul(cs.ns(|| "ac.c_rz * p.y_twist"), &p.y_twist)?,
199 q.y_over_twist
200 .mul(cs.ns(|| "q.y_over_twist * ac.c_rz"), &ac.c_rz)?
201 .add(
202 cs.ns(|| "q.y_over_twist * ac.c_rz + (l1_coeff * ac.c_l1)"),
203 &l1_coeff_c_l1,
204 )?
205 .negate(cs.ns(|| "-(q.y_over_twist * ac.c_rz + (l1_coeff * ac.c_l1))"))?,
206 );
207 f.mul_in_place(cs.ns(|| "f *= g_rq_at_p"), &g_rq_at_p)?;
208 }
209 }
210
211 if P::ATE_IS_LOOP_COUNT_NEG {
212 let ac = &q.addition_coefficients[add_idx];
213
214 let l1_coeff_c_l1 = l1_coeff.mul(cs.ns(|| "l1_coeff * ac.c_l1"), &ac.c_l1)?;
215 let g_rnegr_at_p = Fp6G::<P>::new(
216 ac.c_rz.mul(cs.ns(|| "ac.c_rz * p.y_twist"), &p.y_twist)?,
217 q.y_over_twist
218 .mul(cs.ns(|| "q.y_over_twist * ac.c_rz"), &ac.c_rz)?
219 .add(
220 cs.ns(|| "q.y_over_twist * ac.c_rz + (l1_coeff * ac.c_l1)"),
221 &l1_coeff_c_l1,
222 )?
223 .negate(cs.ns(|| "-(q.y_over_twist * ac.c_rz + (l1_coeff * ac.c_l1))"))?,
224 );
225 f = f
226 .mul(cs.ns(|| "f * g_rnegr_at_p"), &g_rnegr_at_p)?
227 .inverse(cs.ns(|| "inverse f"))?;
228 }
229
230 Ok(f)
231 }
232
233 pub fn final_exponentiation<CS: ConstraintSystem<P::Fp>>(
234 mut cs: CS,
235 value: &Fp6G<P>,
236 ) -> Result<GTGadget<P>, SynthesisError> {
237 let value_inv = value.inverse(cs.ns(|| "value inverse"))?;
238 let value_to_first_chunk = Self::final_exponentiation_first_chunk(
239 cs.ns(|| "value_to_first_chunk"),
240 value,
241 &value_inv,
242 )?;
243 let value_inv_to_first_chunk = Self::final_exponentiation_first_chunk(
244 cs.ns(|| "value_inv_to_first_chunk"),
245 &value_inv,
246 value,
247 )?;
248 Self::final_exponentiation_last_chunk(
249 cs.ns(|| "final_exp_last_chunk"),
250 &value_to_first_chunk,
251 &value_inv_to_first_chunk,
252 )
253 }
254
255 fn final_exponentiation_first_chunk<CS: ConstraintSystem<P::Fp>>(
256 mut cs: CS,
257 elt: &Fp6G<P>,
258 elt_inv: &Fp6G<P>,
259 ) -> Result<Fp6G<P>, SynthesisError> {
260 // (q^3-1)*(q+1)
261
262 // elt_q3 = elt^(q^3)
263 let mut elt_q3 = elt.clone();
264 elt_q3.frobenius_map_in_place(cs.ns(|| "frobenius 3"), 3)?;
265 // elt_q3_over_elt = elt^(q^3-1)
266 let elt_q3_over_elt = elt_q3.mul(cs.ns(|| "elt_q3 * elt_inv"), elt_inv)?;
267 // alpha = elt^((q^3-1) * q)
268 let mut alpha = elt_q3_over_elt.clone();
269 alpha.frobenius_map_in_place(cs.ns(|| "frobenius 1"), 1)?;
270 // beta = elt^((q^3-1)*(q+1)
271 alpha.mul(cs.ns(|| "alpha * elt_q3_over_elt"), &elt_q3_over_elt)
272 }
273
274 fn final_exponentiation_last_chunk<CS: ConstraintSystem<P::Fp>>(
275 mut cs: CS,
276 elt: &Fp6G<P>,
277 elt_inv: &Fp6G<P>,
278 ) -> Result<Fp6G<P>, SynthesisError> {
279 let elt_clone = elt.clone();
280 let elt_inv_clone = elt_inv.clone();
281
282 let mut elt_q = elt.clone();
283 elt_q.frobenius_map_in_place(cs.ns(|| "frobenius 1"), 1)?;
284
285 let w1_part = elt_q.cyclotomic_exp(cs.ns(|| "w1_part"), &P::FINAL_EXPONENT_LAST_CHUNK_1)?;
286 let w0_part;
287 if P::FINAL_EXPONENT_LAST_CHUNK_W0_IS_NEG {
288 w0_part = elt_inv_clone
289 .cyclotomic_exp(cs.ns(|| "w0_part"), &P::FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0)?;
290 } else {
291 w0_part = elt_clone
292 .cyclotomic_exp(cs.ns(|| "w0_part"), &P::FINAL_EXPONENT_LAST_CHUNK_ABS_OF_W0)?;
293 }
294
295 w1_part.mul(cs.ns(|| "w1_part * w0_part"), &w0_part)
296 }
297}
298
299impl<P: MNT6Parameters> PG<MNT6<P>, P::Fp> for PairingGadget<P> {
300 type G1Gadget = G1Gadget<P>;
301 type G2Gadget = G2Gadget<P>;
302 type G1PreparedGadget = G1PreparedGadget<P>;
303 type G2PreparedGadget = G2PreparedGadget<P>;
304 type GTGadget = GTGadget<P>;
305
306 fn miller_loop<CS: ConstraintSystem<P::Fp>>(
307 mut cs: CS,
308 ps: &[Self::G1PreparedGadget],
309 qs: &[Self::G2PreparedGadget],
310 ) -> Result<Self::GTGadget, SynthesisError> {
311 let mut result = Fp6G::<P>::one(cs.ns(|| "one"))?;
312 for (i, (p, q)) in ps.iter().zip(qs.iter()).enumerate() {
313 let miller =
314 Self::ate_miller_loop(cs.ns(|| format!("ate miller loop iteration {}", i)), p, q)?;
315 result.mul_in_place(
316 cs.ns(|| format!("mul ate miller loop iteration {}", i)),
317 &miller,
318 )?;
319 }
320
321 Ok(result)
322 }
323
324 fn final_exponentiation<CS: ConstraintSystem<P::Fp>>(
325 cs: CS,
326 r: &Self::GTGadget,
327 ) -> Result<Self::GTGadget, SynthesisError> {
328 Self::final_exponentiation(cs, r)
329 }
330
331 fn prepare_g1<CS: ConstraintSystem<P::Fp>>(
332 cs: CS,
333 p: &Self::G1Gadget,
334 ) -> Result<Self::G1PreparedGadget, SynthesisError> {
335 Self::G1PreparedGadget::from_affine(cs, p)
336 }
337
338 fn prepare_g2<CS: ConstraintSystem<P::Fp>>(
339 cs: CS,
340 q: &Self::G2Gadget,
341 ) -> Result<Self::G2PreparedGadget, SynthesisError> {
342 Self::G2PreparedGadget::from_affine(cs, q)
343 }
344}