Skip to content

Latest commit

 

History

History
71 lines (44 loc) · 5.97 KB

README.md

File metadata and controls

71 lines (44 loc) · 5.97 KB
Raw

BLS12-381

This is an implementation of the BLS12-381 pairing-friendly elliptic curve construction.

BLS12 Parameterization

BLS12 curves are parameterized by a value x such that the base field modulus q and subgroup r can be computed by:

  • q = (x - 1)2 ((x4 - x2 + 1) / 3) + x
  • r = (x4 - x2 + 1)

Given primes q and r parameterized as above, we can easily construct an elliptic curve over the prime field Fq which contains a subgroup of order r such that r | (q12 - 1), giving it an embedding degree of 12. Instantiating its sextic twist over an extension field Fq2 gives rise to an efficient bilinear pairing function between elements of the order r subgroups of either curves, into an order r multiplicative subgroup of Fq12.

In zk-SNARK schemes, we require Fr with large 2n roots of unity for performing efficient fast-fourier transforms. As such, guaranteeing that large 2n | (r - 1), or equivalently that x has a large 2n factor, gives rise to BLS12 curves suitable for zk-SNARKs.

Due to recent research, it is estimated by many that q should be approximately 384 bits to target 128-bit security. Conveniently, r is approximately 256 bits when q is approximately 384 bits, making BLS12 curves ideal for 128-bit security. It also makes them ideal for many zk-SNARK applications, as the scalar field can be used for keying material such as embedded curve constructions.

Many curves match our descriptions, but we require some extra properties for efficiency purposes:

  • q should be smaller than 2383, and r should be smaller than 2255, so that the most significant bit is unset when using 64-bit or 32-bit limbs. This allows for cheap reductions.
  • Fq12 is typically constructed using towers of extension fields. As a byproduct of research for BLS curves of embedding degree 24, we can identify subfamilies of BLS12 curves (for our purposes, where x mod 72 = {16, 64}) that produce efficient extension field towers and twisting isomorphisms.
  • We desire x of small Hamming weight, to increase the performance of the pairing function.

BLS12-381 Instantiation

The BLS12-381 construction is instantiated by x = -0xd201000000010000, which produces the largest q and smallest Hamming weight of x that meets the above requirements. This produces:

  • q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab (381 bits)
  • r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 (255 bits)

Our extension field tower is constructed as follows:

  1. Fq2 is constructed as Fq(u) / (u2 - β) where β = -1.
  2. Fq6 is constructed as Fq2(v) / (v3 - ξ) where ξ = u + 1
  3. Fq12 is constructed as Fq6(w) / (w2 - γ) where γ = v

Now, we instantiate the elliptic curve E(Fq) : y2 = x3 + 4, and the elliptic curve E'(Fq2) : y2 = x3 + 4(u + 1).

The group G1 is the r order subgroup of E, which has cofactor (x - 1)2 / 3. The group G2 is the r order subgroup of E', which has cofactor (x8 - 4x7 + 5x6 - 4x4 + 6x3 - 4x2 - 4x + 13) / 9.

Generators

The generators of G1 and G2 are computed by finding the lexicographically smallest valid x-coordinate, and its lexicographically smallest y-coordinate and scaling it by the cofactor such that the result is not the point at infinity.

G1

x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569

G2

x = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758*u + 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
y = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582*u + 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905

Serialization

  • Fq elements are encoded in big-endian form. They occupy 48 bytes in this form.
  • Fq2 elements are encoded in big-endian form, meaning that the Fq element c0 + c1 * u is represented by the Fq element c1 followed by the Fq element c0. This means Fq2 elements occupy 96 bytes in this form.
  • The group G1 uses Fq elements for coordinates. The group G2 uses Fq2 elements for coordinates.
  • G1 and G2 elements can be encoded in uncompressed form (the x-coordinate followed by the y-coordinate) or in compressed form (just the x-coordinate). G1 elements occupy 96 bytes in uncompressed form, and 48 bytes in compressed form. G2 elements occupy 192 bytes in uncompressed form, and 96 bytes in compressed form.

The most-significant three bits of a G1 or G2 encoding should be masked away before the coordinate(s) are interpreted. These bits are used to unambiguously represent the underlying element:

  • The most significant bit, when set, indicates that the point is in compressed form. Otherwise, the point is in uncompressed form.
  • The second-most significant bit indicates that the point is at infinity. If this bit is set, the remaining bits of the group element's encoding should be set to zero.
  • The third-most significant bit is set if (and only if) this point is in compressed form and it is not the point at infinity and its y-coordinate is the lexicographically largest of the two associated with the encoded x-coordinate.