Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
bls12_381_g1.cpp
Go to the documentation of this file.
2 
3 namespace libff
4 {
5 
6 #ifdef PROFILE_OP_COUNTS
7 long long bls12_381_G1::add_cnt = 0;
8 long long bls12_381_G1::dbl_cnt = 0;
9 #endif
10 
11 std::vector<size_t> bls12_381_G1::wnaf_window_table;
13 bls12_381_G1 bls12_381_G1::G1_zero;
14 bls12_381_G1 bls12_381_G1::G1_one;
17 bigint<bls12_381_G1::h_limbs> bls12_381_G1::h;
18 
20 {
21  this->X = G1_zero.X;
22  this->Y = G1_zero.Y;
23  this->Z = G1_zero.Z;
24 }
25 
26 void bls12_381_G1::print() const
27 {
28  if (this->is_zero()) {
29  printf("O\n");
30  } else {
31  bls12_381_G1 copy(*this);
32  copy.to_affine_coordinates();
33  gmp_printf(
34  "(%Nd , %Nd)\n",
35  copy.X.as_bigint().data,
37  copy.Y.as_bigint().data,
39  }
40 }
41 
43 {
44  if (this->is_zero()) {
45  printf("O\n");
46  } else {
47  gmp_printf(
48  "(%Nd : %Nd : %Nd)\n",
49  this->X.as_bigint().data,
51  this->Y.as_bigint().data,
53  this->Z.as_bigint().data,
55  }
56 }
57 
59 {
60  if (this->is_zero()) {
61  this->X = bls12_381_Fq::zero();
62  this->Y = bls12_381_Fq::one();
63  this->Z = bls12_381_Fq::zero();
64  } else {
65  bls12_381_Fq Z_inv = Z.inverse();
66  bls12_381_Fq Z2_inv = Z_inv.squared();
67  bls12_381_Fq Z3_inv = Z2_inv * Z_inv;
68  this->X = this->X * Z2_inv;
69  this->Y = this->Y * Z3_inv;
70  this->Z = bls12_381_Fq::one();
71  }
72 }
73 
75 
77 {
78  return (this->is_zero() || this->Z == bls12_381_Fq::one());
79 }
80 
81 bool bls12_381_G1::is_zero() const { return (this->Z.is_zero()); }
82 
83 bool bls12_381_G1::operator==(const bls12_381_G1 &other) const
84 {
85  if (this->is_zero()) {
86  return other.is_zero();
87  }
88 
89  if (other.is_zero()) {
90  return false;
91  }
92 
93  /* now neither is O */
94 
95  // Using Jacobian coordinates so:
96  // (X1:Y1:Z1) = (X2:Y2:Z2) <=>
97  // X1/Z1^2 == X2/Z2^2 AND Y1/Z1^3 == Y2/Z2^3 <=>
98  // X1 * Z2^2 == X2 * Z1^2 and Y1 * Z2^3 == Y2 * Z1^3
99  bls12_381_Fq Z1_squared = (this->Z).squared();
100  bls12_381_Fq Z2_squared = (other.Z).squared();
101  bls12_381_Fq Z1_cubed = (this->Z) * Z1_squared;
102  bls12_381_Fq Z2_cubed = (other.Z) * Z2_squared;
103  if (((this->X * Z2_squared) != (other.X * Z1_squared)) ||
104  ((this->Y * Z2_cubed) != (other.Y * Z1_cubed))) {
105  return false;
106  }
107 
108  return true;
109 }
110 
111 bool bls12_381_G1::operator!=(const bls12_381_G1 &other) const
112 {
113  return !(operator==(other));
114 }
115 
117 {
118  // handle special cases having to do with O
119  if (this->is_zero()) {
120  return other;
121  }
122 
123  if (other.is_zero()) {
124  return *this;
125  }
126 
127  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
128  // no need to handle points of order 2,4
129  // (they cannot exist in a prime-order subgroup)
130 
131  // check for doubling case
132 
133  // using Jacobian coordinates so:
134  // (X1:Y1:Z1) = (X2:Y2:Z2)
135  // iff
136  // X1/Z1^2 == X2/Z2^2 and Y1/Z1^3 == Y2/Z2^3
137  // iff
138  // X1 * Z2^2 == X2 * Z1^2 and Y1 * Z2^3 == Y2 * Z1^3
139 
140  bls12_381_Fq Z1Z1 = (this->Z).squared();
141  bls12_381_Fq Z2Z2 = (other.Z).squared();
142 
143  bls12_381_Fq U1 = this->X * Z2Z2;
144  bls12_381_Fq U2 = other.X * Z1Z1;
145 
146  // S1 = Y1 * Z2 * Z2Z2
147  bls12_381_Fq S1 = (this->Y) * ((other.Z) * Z2Z2);
148  // S2 = Y2 * Z1 * Z1Z1
149  bls12_381_Fq S2 = (other.Y) * ((this->Z) * Z1Z1);
150 
151  if (U1 == U2 && S1 == S2) {
152  // dbl case; nothing of above can be reused
153  return this->dbl();
154  }
155 
156  // rest of add case
157  // H = U2-U1
158  bls12_381_Fq H = U2 - U1;
159  // I = (2 * H)^2
160  bls12_381_Fq I = (H + H).squared();
161  // J = H * I
162  bls12_381_Fq J = H * I;
163  // r = 2 * (S2-S1)
164  bls12_381_Fq S2_minus_S1 = S2 - S1;
165  bls12_381_Fq r = S2_minus_S1 + S2_minus_S1;
166  // V = U1 * I
167  bls12_381_Fq V = U1 * I;
168  // X3 = r^2 - J - 2 * V
169  bls12_381_Fq X3 = r.squared() - J - (V + V);
170  bls12_381_Fq S1_J = S1 * J;
171  // Y3 = r * (V-X3)-2 S1 J
172  bls12_381_Fq Y3 = r * (V - X3) - (S1_J + S1_J);
173  // Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2) * H
174  bls12_381_Fq Z3 = ((this->Z + other.Z).squared() - Z1Z1 - Z2Z2) * H;
175 
176  return bls12_381_G1(X3, Y3, Z3);
177 }
178 
180 {
181  return bls12_381_G1(this->X, -(this->Y), this->Z);
182 }
183 
185 {
186  return (*this) + (-other);
187 }
188 
190 {
191  return (*this) + other;
192 }
193 
195 {
196 #ifdef DEBUG
197  assert(other.is_special());
198 #endif
199 
200  // handle special cases having to do with O
201  if (this->is_zero()) {
202  return other;
203  }
204 
205  if (other.is_zero()) {
206  return *this;
207  }
208 
209  // no need to handle points of order 2,4
210  // (they cannot exist in a prime-order subgroup)
211 
212  // check for doubling case
213 
214  // using Jacobian coordinates so:
215  // (X1:Y1:Z1) = (X2:Y2:Z2)
216  // iff
217  // X1/Z1^2 == X2/Z2^2 and Y1/Z1^3 == Y2/Z2^3
218  // iff
219  // X1 * Z2^2 == X2 * Z1^2 and Y1 * Z2^3 == Y2 * Z1^3
220 
221  // we know that Z2 = 1
222 
223  const bls12_381_Fq Z1Z1 = (this->Z).squared();
224  // U2 = X2*Z1Z1
225  const bls12_381_Fq U2 = other.X * Z1Z1;
226  // S2 = Y2 * Z1 * Z1Z1
227  const bls12_381_Fq S2 = (other.Y) * ((this->Z) * Z1Z1);
228 
229  if (this->X == U2 && this->Y == S2) {
230  // dbl case; nothing of above can be reused
231  return this->dbl();
232  }
233 
234 #ifdef PROFILE_OP_COUNTS
235  this->add_cnt++;
236 #endif
237 
238  // NOTE: does not handle O and pts of order 2,4
239  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
240  // H = U2-X1
241  bls12_381_Fq H = U2 - (this->X);
242  // HH = H^2
243  bls12_381_Fq HH = H.squared();
244  // I = 4*HH
245  bls12_381_Fq I = HH + HH;
246  I = I + I;
247  // J = H*I
248  bls12_381_Fq J = H * I;
249  // r = 2*(S2-Y1)
250  bls12_381_Fq r = S2 - (this->Y);
251  r = r + r;
252  // V = X1*I
253  bls12_381_Fq V = (this->X) * I;
254  // X3 = r^2-J-2*V
255  bls12_381_Fq X3 = r.squared() - J - V - V;
256  // Y3 = r*(V-X3)-2*Y1*J
257  bls12_381_Fq Y3 = (this->Y) * J;
258  Y3 = r * (V - X3) - Y3 - Y3;
259  // Z3 = (Z1+H)^2-Z1Z1-HH
260  bls12_381_Fq Z3 = ((this->Z) + H).squared() - Z1Z1 - HH;
261 
262  return bls12_381_G1(X3, Y3, Z3);
263 }
264 
266 {
267 #ifdef PROFILE_OP_COUNTS
268  this->dbl_cnt++;
269 #endif
270  // handle point at infinity
271  if (this->is_zero()) {
272  return (*this);
273  }
274 
275  // no need to handle points of order 2,4
276  // (they cannot exist in a prime-order subgroup)
277 
278  // NOTE: does not handle O and pts of order 2,4
279  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
280 
281  // A = X1^2
282  bls12_381_Fq A = (this->X).squared();
283  // B = Y1^2
284  bls12_381_Fq B = (this->Y).squared();
285  // C = B^2
286  bls12_381_Fq C = B.squared();
287  bls12_381_Fq D = (this->X + B).squared() - A - C;
288  // D = 2 * ((X1 + B)^2 - A - C)
289  D = D + D;
290  // E = 3 * A
291  bls12_381_Fq E = A + A + A;
292  // F = E^2
293  bls12_381_Fq F = E.squared();
294  // X3 = F - 2 D
295  bls12_381_Fq X3 = F - (D + D);
296  bls12_381_Fq eightC = C + C;
297  eightC = eightC + eightC;
298  eightC = eightC + eightC;
299  // Y3 = E * (D - X3) - 8 * C
300  bls12_381_Fq Y3 = E * (D - X3) - eightC;
301  bls12_381_Fq Y1Z1 = (this->Y) * (this->Z);
302  // Z3 = 2 * Y1 * Z1
303  bls12_381_Fq Z3 = Y1Z1 + Y1Z1;
304 
305  return bls12_381_G1(X3, Y3, Z3);
306 }
307 
309 {
310  return bls12_381_G1::h * (*this);
311 }
312 
314 {
315  if (this->is_zero()) {
316  return true;
317  }
318 
319  // The curve equation is
320  // E': y^2 = x^3 + ax + b, where a=0
321  // We are using Jacobian coordinates. As such, the equation becomes:
322  // y^2/z^6 = x^3/z^6 + b
323  // = y^2 = x^3 + b z^6
324  bls12_381_Fq X2 = this->X.squared();
325  bls12_381_Fq Y2 = this->Y.squared();
326  bls12_381_Fq Z2 = this->Z.squared();
327 
328  bls12_381_Fq X3 = this->X * X2;
329  bls12_381_Fq Z3 = this->Z * Z2;
330  bls12_381_Fq Z6 = Z3.squared();
331 
332  return (Y2 == X3 + bls12_381_coeff_b * Z6);
333 }
334 
336 {
337  return zero() == scalar_field::mod * (*this);
338 }
339 
341 
343 
345 {
346  return (scalar_field::random_element().as_bigint()) * G1_one;
347 }
348 
349 void bls12_381_G1::write_uncompressed(std::ostream &out) const
350 {
351  bls12_381_G1 copy(*this);
352  copy.to_affine_coordinates();
353  out << (copy.is_zero() ? 1 : 0) << OUTPUT_SEPARATOR;
354  out << copy.X << OUTPUT_SEPARATOR << copy.Y;
355 }
356 
357 void bls12_381_G1::write_compressed(std::ostream &out) const
358 {
359  bls12_381_G1 copy(*this);
360  copy.to_affine_coordinates();
361  out << (copy.is_zero() ? 1 : 0) << OUTPUT_SEPARATOR;
362  /* storing LSB of Y */
363  out << copy.X << OUTPUT_SEPARATOR << (copy.Y.as_bigint().data[0] & 1);
364 }
365 
367 {
368  char is_zero;
369  bls12_381_Fq tX, tY;
370 
371  in >> is_zero >> tX >> tY;
372  is_zero -= '0';
373 
374  // using Jacobian coordinates
375  if (!is_zero) {
376  g.X = tX;
377  g.Y = tY;
378  g.Z = bls12_381_Fq::one();
379  } else {
380  g = bls12_381_G1::zero();
381  }
382 }
383 
384 void bls12_381_G1::read_compressed(std::istream &in, bls12_381_G1 &g)
385 {
386  char is_zero;
387  bls12_381_Fq tX, tY;
388 
389  // this reads is_zero;
390  in.read((char *)&is_zero, 1);
391  is_zero -= '0';
393 
394  unsigned char Y_lsb;
395  in >> tX;
397  in.read((char *)&Y_lsb, 1);
398  Y_lsb -= '0';
399 
400  // y = +/- sqrt(x^3 + b)
401  if (!is_zero) {
402  bls12_381_Fq tX2 = tX.squared();
403  bls12_381_Fq tY2 = tX2 * tX + bls12_381_coeff_b;
404  tY = tY2.sqrt();
405 
406  if ((tY.as_bigint().data[0] & 1) != Y_lsb) {
407  tY = -tY;
408  }
409  }
410 
411  // using Jacobian coordinates
412  if (!is_zero) {
413  g.X = tX;
414  g.Y = tY;
415  g.Z = bls12_381_Fq::one();
416  } else {
417  g = bls12_381_G1::zero();
418  }
419 }
420 
421 std::ostream &operator<<(std::ostream &out, const bls12_381_G1 &g)
422 {
423 #ifdef NO_PT_COMPRESSION
424  g.write_uncompressed(out);
425 #else
426  g.write_compressed(out);
427 #endif
428  return out;
429 }
430 
431 std::istream &operator>>(std::istream &in, bls12_381_G1 &g)
432 {
433 #ifdef NO_PT_COMPRESSION
435 #else
437 #endif
438  return in;
439 }
440 
442  std::vector<bls12_381_G1> &vec)
443 {
444  std::vector<bls12_381_Fq> Z_vec;
445  Z_vec.reserve(vec.size());
446 
447  for (auto &el : vec) {
448  Z_vec.emplace_back(el.Z);
449  }
450  batch_invert<bls12_381_Fq>(Z_vec);
451 
453 
454  for (size_t i = 0; i < vec.size(); ++i) {
455  bls12_381_Fq Z2 = Z_vec[i].squared();
456  bls12_381_Fq Z3 = Z_vec[i] * Z2;
457 
458  vec[i].X = vec[i].X * Z2;
459  vec[i].Y = vec[i].Y * Z3;
460  vec[i].Z = one;
461  }
462 }
463 
464 } // namespace libff
libff::bls12_381_G1::is_special
bool is_special() const
Definition: bls12_381_g1.cpp:76
libff::bls12_381_G1::is_well_formed
bool is_well_formed() const
Definition: bls12_381_g1.cpp:313
libff::bls12_381_G1::coeff_a
static bls12_381_Fq coeff_a
Definition: bls12_381_g1.hpp:32
libff::bls12_381_G1::mixed_add
bls12_381_G1 mixed_add(const bls12_381_G1 &other) const
Definition: bls12_381_g1.cpp:194
libff::bls12_381_G1::add
bls12_381_G1 add(const bls12_381_G1 &other) const
Definition: bls12_381_g1.cpp:189
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff::bls12_381_G1::h
static bigint< h_limbs > h
Definition: bls12_381_g1.hpp:42
libff
Definition: ffi.cpp:8
libff::Fp_model::squared
Fp_model squared() const
libff::bls12_381_G1::one
static const bls12_381_G1 & one()
Definition: bls12_381_g1.cpp:342
libff::bls12_381_G1::wnaf_window_table
static std::vector< std::size_t > wnaf_window_table
Definition: bls12_381_g1.hpp:28
libff::bls12_381_Fq
Fp_model< bls12_381_q_limbs, bls12_381_modulus_q > bls12_381_Fq
Definition: bls12_381_init.hpp:31
libff::bls12_381_G1::Y
bls12_381_Fq Y
Definition: bls12_381_g1.hpp:44
libff::Fp_model< bls12_381_q_limbs, bls12_381_modulus_q >::zero
static const Fp_model< n, modulus > & zero()
libff::Fp_model::is_zero
bool is_zero() const
libff::operator>>
std::istream & operator>>(std::istream &in, alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:446
libff::bls12_381_G1
Definition: bls12_381_g1.hpp:21
libff::bls12_381_G1::fixed_base_exp_window_table
static std::vector< std::size_t > fixed_base_exp_window_table
Definition: bls12_381_g1.hpp:29
libff::bls12_381_G1::operator==
bool operator==(const bls12_381_G1 &other) const
Definition: bls12_381_g1.cpp:83
libff::bls12_381_G1::operator-
bls12_381_G1 operator-() const
Definition: bls12_381_g1.cpp:179
libff::Fp_model::inverse
Fp_model inverse() const
libff::bls12_381_G1::zero
static const bls12_381_G1 & zero()
Definition: bls12_381_g1.cpp:340
libff::bls12_381_G1::mul_by_cofactor
bls12_381_G1 mul_by_cofactor() const
Definition: bls12_381_g1.cpp:308
libff::bls12_381_G1::bls12_381_G1
bls12_381_G1()
Definition: bls12_381_g1.cpp:19
libff::bls12_381_G1::random_element
static bls12_381_G1 random_element()
Definition: bls12_381_g1.cpp:344
libff::Fp_model::sqrt
Fp_model sqrt() const
HAS TO BE A SQUARE (else does not terminate)
libff::Fp_model< bls12_381_q_limbs, bls12_381_modulus_q >::one
static const Fp_model< n, modulus > & one()
OUTPUT_SEPARATOR
#define OUTPUT_SEPARATOR
Definition: serialization.hpp:69
libff::bls12_381_G1::G1_one
static bls12_381_G1 G1_one
Definition: bls12_381_g1.hpp:31
libff::bls12_381_G1::batch_to_special_all_non_zeros
static void batch_to_special_all_non_zeros(std::vector< bls12_381_G1 > &vec)
Definition: bls12_381_g1.cpp:441
libff::bls12_381_G1::read_uncompressed
static void read_uncompressed(std::istream &, bls12_381_G1 &)
Definition: bls12_381_g1.cpp:366
libff::bls12_381_G1::operator+
bls12_381_G1 operator+(const bls12_381_G1 &other) const
Definition: bls12_381_g1.cpp:116
libff::consume_OUTPUT_SEPARATOR
void consume_OUTPUT_SEPARATOR(std::istream &in)
libff::bls12_381_G1::to_special
void to_special()
Definition: bls12_381_g1.cpp:74
libff::Fp_model< bls12_381_q_limbs, bls12_381_modulus_q >::num_limbs
static const mp_size_t num_limbs
Definition: fp.hpp:47
libff::bls12_381_G1::to_affine_coordinates
void to_affine_coordinates()
Definition: bls12_381_g1.cpp:58
libff::bls12_381_G1::operator!=
bool operator!=(const bls12_381_G1 &other) const
Definition: bls12_381_g1.cpp:111
libff::bls12_381_G1::print_coordinates
void print_coordinates() const
Definition: bls12_381_g1.cpp:42
libff::bls12_381_G1::G1_zero
static bls12_381_G1 G1_zero
Definition: bls12_381_g1.hpp:30
libff::Fp_model::as_bigint
bigint< n > as_bigint() const
libff::Fp_model
Definition: fp.hpp:20
libff::bls12_381_G1::print
void print() const
Definition: bls12_381_g1.cpp:26
libff::bls12_381_G1::coeff_b
static bls12_381_Fq coeff_b
Definition: bls12_381_g1.hpp:33
libff::operator<<
std::ostream & operator<<(std::ostream &out, const alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:436
libff::bls12_381_G1::Z
bls12_381_Fq Z
Definition: bls12_381_g1.hpp:44
libff::bls12_381_G1::is_zero
bool is_zero() const
Definition: bls12_381_g1.cpp:81
libff::bls12_381_G1::dbl
bls12_381_G1 dbl() const
Definition: bls12_381_g1.cpp:265
libff::bls12_381_G1::read_compressed
static void read_compressed(std::istream &, bls12_381_G1 &)
Definition: bls12_381_g1.cpp:384
libff::bls12_381_G1::write_uncompressed
void write_uncompressed(std::ostream &) const
Definition: bls12_381_g1.cpp:349
libff::bls12_381_coeff_b
bls12_381_Fq bls12_381_coeff_b
Definition: bls12_381_init.cpp:11
libff::Fp_model::mod
static const constexpr bigint< n > & mod
Definition: fp.hpp:48
libff::bls12_381_G1::X
bls12_381_Fq X
Definition: bls12_381_g1.hpp:44
libff::bls12_381_G1::write_compressed
void write_compressed(std::ostream &) const
Definition: bls12_381_g1.cpp:357
libff::bls12_381_G1::is_in_safe_subgroup
bool is_in_safe_subgroup() const
Definition: bls12_381_g1.cpp:335
bls12_381_g1.hpp