barretenberg
Loading...
Searching...
No Matches
pairing_impl.hpp
1#pragma once
2
3#include "./fq12.hpp"
4#include "./g1.hpp"
5#include "./g2.hpp"
6#include "barretenberg/ecc/curves/bn254/pairing.hpp"
7
8namespace barretenberg::pairing {
9constexpr fq two_inv = fq(2).invert();
10inline constexpr g2::element mul_by_q(const g2::element& a)
11{
12
13 fq2 T0 = a.x.frobenius_map();
14 fq2 T1 = a.y.frobenius_map();
15 return {
16 fq2::twist_mul_by_q_x() * T0,
17 fq2::twist_mul_by_q_y() * T1,
18 a.z.frobenius_map(),
19 };
20}
21constexpr void doubling_step_for_flipped_miller_loop(g2::element& current, fq12::ell_coeffs& ell)
22{
23 fq2 a = current.x.mul_by_fq(two_inv);
24 a *= current.y;
25
26 fq2 b = current.y.sqr();
27 fq2 c = current.z.sqr();
28 fq2 d = c + c;
29 d += c;
30 fq2 e = d * fq2::twist_coeff_b();
31 fq2 f = e + e;
32 f += e;
33
34 fq2 g = b + f;
35 g = g.mul_by_fq(two_inv);
36 fq2 h = current.y + current.z;
37 h = h.sqr();
38 fq2 i = b + c;
39 h -= i;
40 i = e - b;
41 fq2 j = current.x.sqr();
42 fq2 ee = e.sqr();
43 fq2 k = b - f;
44 current.x = a * k;
45
46 k = ee + ee;
47 k += ee;
48
49 c = g.sqr();
50 current.y = c - k;
51 current.z = b * h;
52
53 ell.o = fq6::mul_by_non_residue(i);
54
55 ell.vw = -h;
56 ell.vv = j + j;
57 ell.vv += j;
58}
59
60constexpr void mixed_addition_step_for_flipped_miller_loop(const g2::element& base,
61 g2::element& Q,
62 fq12::ell_coeffs& line)
63{
64 fq2 d = base.x * Q.z;
65 d = Q.x - d;
66
67 fq2 e = base.y * Q.z;
68 e = Q.y - e;
69
70 fq2 f = d.sqr();
71 fq2 g = e.sqr();
72 fq2 h = d * f;
73 fq2 i = Q.x * f;
74
75 fq2 j = Q.z * g;
76 j += h;
77 j -= i;
78 j -= i;
79
80 Q.x = d * j;
81 i -= j;
82 i *= e;
83 j = Q.y * h;
84 Q.y = i - j;
85 Q.z *= h;
86
87 h = e * base.x;
88 i = d * base.y;
89
90 h -= i;
91 line.o = fq6::mul_by_non_residue(h);
92
93 line.vv = -e;
94 line.vw = d;
95}
96
97constexpr void precompute_miller_lines(const g2::element& Q, miller_lines& lines)
98{
99 g2::element Q_neg{ Q.x, -Q.y, fq2::one() };
100 g2::element work_point = Q;
101
102 size_t it = 0;
103 for (unsigned char loop_bit : loop_bits) {
104 doubling_step_for_flipped_miller_loop(work_point, lines.lines[it]);
105 ++it;
106 if (loop_bit == 1) {
107 mixed_addition_step_for_flipped_miller_loop(Q, work_point, lines.lines[it]);
108 ++it;
109 } else if (loop_bit == 3) {
110 mixed_addition_step_for_flipped_miller_loop(Q_neg, work_point, lines.lines[it]);
111 ++it;
112 }
113 }
114
115 g2::element Q1 = mul_by_q(Q);
116 g2::element Q2 = mul_by_q(Q1);
117 Q2 = -Q2;
118 mixed_addition_step_for_flipped_miller_loop(Q1, work_point, lines.lines[it]);
119 ++it;
120 mixed_addition_step_for_flipped_miller_loop(Q2, work_point, lines.lines[it]);
121}
122
123constexpr fq12 miller_loop(g1::element& P, miller_lines& lines)
124{
125 fq12 work_scalar = fq12::one();
126
127 size_t it = 0;
128 fq12::ell_coeffs work_line;
129
130 for (unsigned char loop_bit : loop_bits) {
131 work_scalar = work_scalar.sqr();
132
133 work_line.o = lines.lines[it].o;
134 work_line.vw = lines.lines[it].vw.mul_by_fq(P.y);
135 work_line.vv = lines.lines[it].vv.mul_by_fq(P.x);
136 work_scalar.self_sparse_mul(work_line);
137 ++it;
138
139 if (loop_bit != 0) {
140 work_line.o = lines.lines[it].o;
141 work_line.vw = lines.lines[it].vw.mul_by_fq(P.y);
142 work_line.vv = lines.lines[it].vv.mul_by_fq(P.x);
143 work_scalar.self_sparse_mul(work_line);
144 ++it;
145 }
146 }
147
148 work_line.o = lines.lines[it].o;
149 work_line.vw = lines.lines[it].vw.mul_by_fq(P.y);
150 work_line.vv = lines.lines[it].vv.mul_by_fq(P.x);
151 work_scalar.self_sparse_mul(work_line);
152 ++it;
153 work_line.o = lines.lines[it].o;
154 work_line.vw = lines.lines[it].vw.mul_by_fq(P.y);
155 work_line.vv = lines.lines[it].vv.mul_by_fq(P.x);
156 work_scalar.self_sparse_mul(work_line);
157 ++it;
158 return work_scalar;
159}
160
161constexpr fq12 miller_loop_batch(const g1::element* points, const miller_lines* lines, size_t num_pairs)
162{
163 fq12 work_scalar = fq12::one();
164
165 size_t it = 0;
166 fq12::ell_coeffs work_line;
167
168 for (unsigned char loop_bit : loop_bits) {
169 work_scalar = work_scalar.sqr();
170 for (size_t j = 0; j < num_pairs; ++j) {
171 work_line.o = lines[j].lines[it].o;
172 work_line.vw = lines[j].lines[it].vw.mul_by_fq(points[j].y);
173 work_line.vv = lines[j].lines[it].vv.mul_by_fq(points[j].x);
174 work_scalar.self_sparse_mul(work_line);
175 }
176 ++it;
177 if (loop_bit != 0) {
178 for (size_t j = 0; j < num_pairs; ++j) {
179 work_line.o = lines[j].lines[it].o;
180 work_line.vw = lines[j].lines[it].vw.mul_by_fq(points[j].y);
181 work_line.vv = lines[j].lines[it].vv.mul_by_fq(points[j].x);
182 work_scalar.self_sparse_mul(work_line);
183 }
184 ++it;
185 }
186 }
187
188 for (size_t j = 0; j < num_pairs; ++j) {
189 work_line.o = lines[j].lines[it].o;
190 work_line.vw = lines[j].lines[it].vw.mul_by_fq(points[j].y);
191 work_line.vv = lines[j].lines[it].vv.mul_by_fq(points[j].x);
192 work_scalar.self_sparse_mul(work_line);
193 }
194 ++it;
195 for (size_t j = 0; j < num_pairs; ++j) {
196 work_line.o = lines[j].lines[it].o;
197 work_line.vw = lines[j].lines[it].vw.mul_by_fq(points[j].y);
198 work_line.vv = lines[j].lines[it].vv.mul_by_fq(points[j].x);
199 work_scalar.self_sparse_mul(work_line);
200 }
201 ++it;
202 return work_scalar;
203}
204
205constexpr fq12 final_exponentiation_easy_part(const fq12& elt)
206{
207 fq12 a{ elt.c0, -elt.c1 };
208 a *= elt.invert();
209 return a * a.frobenius_map_two();
210}
211
212constexpr fq12 final_exponentiation_exp_by_neg_z(const fq12& elt)
213{
214 fq12 r = elt;
215
216 for (bool neg_z_loop_bit : neg_z_loop_bits) {
217 r = r.cyclotomic_squared();
218 if (neg_z_loop_bit) {
219 r *= elt;
220 }
221 }
222 return r.unitary_inverse();
223}
224
225constexpr fq12 final_exponentiation_tricky_part(const fq12& elt)
226{
227 fq12 A = final_exponentiation_exp_by_neg_z(elt);
228 fq12 B = A.cyclotomic_squared();
229 fq12 C = B.cyclotomic_squared();
230 fq12 D = B * C;
231 fq12 E = final_exponentiation_exp_by_neg_z(D);
232 fq12 F = E.cyclotomic_squared();
233 fq12 G = final_exponentiation_exp_by_neg_z(F);
234 fq12 H = D.unitary_inverse();
235 fq12 I = G.unitary_inverse();
236 fq12 J = I * E;
237 fq12 K = J * H;
238 fq12 L = B * K;
239 fq12 M = E * K;
240 fq12 N = M * elt;
241 fq12 O = L.frobenius_map_one();
242 fq12 P = O * N;
243 fq12 Q = K.frobenius_map_two();
244 fq12 R = P * Q;
245 fq12 S = elt.unitary_inverse();
246 fq12 T = L * S;
247 fq12 U = T.frobenius_map_three();
248
249 return R * U;
250}
251
252constexpr fq12 reduced_ate_pairing(const g1::affine_element& P_affine, const g2::affine_element& Q_affine)
253{
254 g1::element P(P_affine);
255 g2::element Q(Q_affine);
256
257 miller_lines lines;
258 precompute_miller_lines(Q, lines);
259
260 fq12 result = miller_loop(P, lines);
261 result = final_exponentiation_easy_part(result);
262 result = final_exponentiation_tricky_part(result);
263 return result;
264}
265
266fq12 reduced_ate_pairing_batch_precomputed(const g1::affine_element* P_affines,
267 const miller_lines* lines,
268 const size_t num_points)
269{
270 std::vector<g1::element> P(num_points);
271 for (size_t i = 0; i < num_points; ++i) {
272 P[i] = g1::element(P_affines[i]);
273 }
274 fq12 result = miller_loop_batch(&P[0], &lines[0], num_points);
275 result = final_exponentiation_easy_part(result);
276 result = final_exponentiation_tricky_part(result);
277 return result;
278}
279
280fq12 reduced_ate_pairing_batch(const g1::affine_element* P_affines,
281 const g2::affine_element* Q_affines,
282 const size_t num_points)
283{
284 std::vector<g1::element> P(num_points);
285 std::vector<g2::element> Q(num_points);
286 std::vector<miller_lines> lines(num_points);
287
288 for (size_t i = 0; i < num_points; ++i) {
289 P[i] = g1::element(P_affines[i]);
290 Q[i] = g2::element(Q_affines[i]);
291
292 precompute_miller_lines(Q[i], lines[i]);
293 }
294
295 fq12 result = miller_loop_batch(&P[0], &lines[0], num_points);
296 result = final_exponentiation_easy_part(result);
297 result = final_exponentiation_tricky_part(result);
298 return result;
299}
300
301} // namespace barretenberg::pairing
Generated by doxygen 1.9.6