BLS12-381

This is a non-exhaustive introduction to some of the key characteristics of the elliptic curve BLS12-381. For further reading have a look at BLS12-381-For The Rest Of Us or the announcement.

Origin

BLS12-381 was proposed by Sean Bowe in 2017 and is part of a group of elliptic curves described by Barreto, Lynn and Scott (hence BLS) back in 2002.

The curve is defined by the equation:

The points on the curve are pairs that solve the curve equation plus an artificial point at infinity, called , that has no affine coordinates and serves as the neutral element in point addition. ¹

For example: The point is on the curve and by definition: .

Curve Definition

Other than our curves from back in school, which commonly had coordinates in the real numbers , elliptic curves have coordinates in a finite field and in the case of BLS12-381 is the prime number

which is in hexadecimal is

This prime number is exactly 381 bits long (hence 381).

The field can be thought of as the natural numbers modulo . These are the integers from to and when you hit you simply start at again.

So becomes , and becomes , and becomes and so on.

At this point we have an elliptic curve (let’s call it ) and this curve consists of points with coordinates where and satisfy the following equation plus the artificial point at infinity.

We call this the group of -rational points of . ²

Subgroup of Elliptic Curve Points

The group of -rational points of is rather large and we are actually only interested in a subgroup of it. This subgroup (we call it ) is cyclic under addition, which means that there is a point , called the generator of , that reaches all the other point in when being added to itself.

So with the point , we can construct the whole group:

The number is the amount of elements in , also called the order of , and in the case of the BLS12-381 curve:

which in hexadecimal is

Because is a prime number it follows that all points except the point at infinity can function as the generator. ³

BLS Scalar

Since every point in generates all other points in , we can fix an arbitrary point ⁴ and reach all other points in simply by multiplying with a scalar that is smaller than . This scalar is what we call a BlsScalar and we often write it framed with square brackets ⁵.

In our cryptographic scheme we often use the BlsScalar as a our secret key and the corresponding group element as our public key.

Embedding degree

The 12 in BLS12-381 refers to the embedding degree ⁶. But what exactly is the embedding degree? To explore that we need to have a look at elliptic curve pairings. However, since this is an introduction to the BLS12-381 curve and not to elliptic curve pairings, we won’t go into too much detail here. For further reading please check out Pairings for Beginners.

So this is only a short summary on those aspects of elliptic curve pairing that help us understand the embedding degree.

Elliptic curve pairing

A pairing is a function that takes a point from a group and another point from a group and maps the two points onto a third point from a group , where , and are all of the same order, i.e. have the same amount of elements.

One of the most important properties of pairings is that for points and :

From this we can deduce that for two integers and their corresponding BlsScalar :

We use this property in nearly all of our cryptographic schemes.

The groups , and must be of the same order. But so far we only have one group like that: the above group . Let’s pick it for ⁷.

Then what about and ?

Let’s start by looking at which is defined as the group of roots of unity of order (we will get to the meaning of that in a bit) and closely related to the embedding degree. But before we get into that, we also need to understand extension fields:

Extension Fields

Do you remember the complex numbers ?

For all complex numbers there exist two real numbers such that

Sometimes we also write

We say that the complex numbers are a quadratic extension of the real numbers and it is easy to see that the real numbers are a subset of the complex numbers (when ).

We can not extend the complex numbers any further ⁸, but that is a different story for finite fields.

Roots of Unity

Moreover, we can construct the 12th extension field , which is the smallest extension field of containing a group of th roots of unity (the group that we need for pairing).

This group is defined as follows:

with

To understand what that means, let’s give an example. Over the field we have the group of the th roots of unity , since

With what we learned so far, we can now formally define the embedding degree as the smallest integer such that (that is the th extension field over without zero). This is equivalent to being the smallest such that divides .

Twists

Now we have and , but we still need . This group is required to be a group of elliptic curve points on of the same order as and .

As it turns out, our group of curve points has only one group of order , the group we use as .

But the group does have such a subgroup of order

In this case the coordinates of the curve points are in

The problem that we are facing now, is that doing any kind of arithmetic with points in is so cumbersome and computationally intensive (not to mention the huge amount of memory needed for storage) that we would like to avoid this. And that is what we need twists for.

A twist can be seen as a function that maps points from one elliptic curve to points on another curve . In our case we will use a sextic twist which will reduce the field of the coordinates of points on from by a factor of six to for points on :

The points in are much easier to handle compared to points in and also has a subgroup of order which maps to our previous group .

This means that for easier arithmetic we can use that subgroup of as our group and map the points back to only when needed.

Summary

BLS12-381 is a pairing friendly elliptic curve with an embedding degree of 12. The coordinates of points on that curve are elements of the finite field and its extension fields.

The groups of order that we use for pairing are

which is a subset of the curve

which is a subset of the curve

which is the group of th roots of unity in .

Note that this is not the point at . ↩
This is not the same as our curve being defined over . Generally speaking, an elliptic curve of the form is said to be defined over a field if the parameters and are in but not necessarily the coordinates and . This is denoted by . In the case of BLS12-381 however, the curve is both defined over the field (so ) and has coordinates in the field (so ). ↩
This is a direct consequence of Lagrange’s Theorem. ↩
Check the crate documentation on how the generator is chosen. ↩
In order to ease the arithmetics with BlsScalar we still do some tricks under the hood. So even though BlsScalar essentially are just integers from to , internally we multiply them with and take the resulting number modulo . This is called the Montgomery form of the BlsScalar and to add to the complexity we store that scalar in its Montgomery form the other way round (i.e. in little endian). ↩
Indeed the curve has been specifically designed to have an embedding degree of 12, which is a compromise between security (the higher the better) and performance (the lower the better). ↩
Depending on what the pairing scheme is used for, can also be set to instead of . ↩
This is due to the fact that there are no irreducible polynomials with a degree over the complex numbers and what that means is explained rather nicely here. ↩