Part 2: Technical Overview

Curve BLS12-381

This chapter is a revised and updated version of my original homage to curve BLS12-381. It is not required reading – it's fine to treat the elliptic curve implementation as a black box – but I've included it for those who enjoy digging deeper. While curve BLS12-281 is the main focus, much of what follows covers broader background material on elliptic curves and pairings in general. As a non-mathematician¹, all of this was very mysterious when I first encountered it; it has taken me quite a while to feel that I have some grasp of what's going on.

Introduction

Elliptic curves have been part of the blockchain toolkit since day one. For example, both Bitcoin and Ethereum use the curve known as secp256k1 to sign users' transactions with ECDSA, the "elliptic curve digital signature algorithm".

Curve secp256k1 is not used in Ethereum's consensus layer, however. Instead we use a curve called BLS12-381 because it supports a mathematical operation called bilinear pairing - it is a "pairing-friendly" elliptic curve. Pairings are very cool because, among other things, they allow us to do signature aggregation and polynomial commitments, operations that have become foundational to Ethereum's consensus but are not supported by most elliptic curves.

Pairing-friendly elliptic curves are curves with both a favourable embedding degree (to be explained below), and a large prime-order subgroup (also see below). These are rare. If you create an elliptic curve at random, it has a miniscule chance of being pairing-friendly. Nevertheless, they can be constructed, and several families of pairing-friendly curves are known in addition to the BLS curves.

Some good reading if you want to learn more about pairing-based cryptography:

• Vitalik has a great general introduction to elliptic curve pairings.
• Alin Tomescu gives an entertaining review of the history of the development of pairing based cryptography and some of its applications in a blog post, Pairings or bilinear maps².
• The NIST report on pairing-based cryptography is quite readable. I recommend Section 2 and the Appendix.
• Also good background is the draft IETF standard for pairing-friendly curves.

If you really want to understand this stuff then Pairings for Beginners is unsurpassed. It turns out to be a lot less scary than it looks if you work through it carefully, studying the examples as you go.

BLS12-381 in Ethereum

The possibility of signature aggregation was the key breakthrough that made Ethereum's beacon chain possible. It allowed us to abandon the previous, impractical, proof of stake plans in mid-2018 and go all-in on the beacon chain approach.

To perform signature aggregation, we need to use a cryptographically secure, pairing-friendly elliptic curve. As noted, these are quite rare.

The main reason for the choice of BLS12-381 for the beacon chain is that it is a sweet-spot among the available pairing-friendly curves in terms of security (originally thought to be around 128 bits, but see below), speed of the pairing operation, and the sizes of the public key (48 bytes) and signature (96 bytes). Among other candidates, the BN128/BN254 curve has smaller signatures but lower security (~100 bits). Other pairing-friendly curves (such as the BW, MNT, and KSS families) tend to have larger signatures or slower pairings for a similar security level.

Other influential factors were the following.

• BLS12-381 was designed for Zcash and was already being adopted by other chains such as Chia. There is safety in numbers (more scrutiny, better libraries), and interoperability between chains was a guiding principle at the time, although that ambition has faded since.
• The original paper³ about signature aggregation for blockchains used BLS12-381 in its analysis.
• BLS curves are included in the IETF pairing-friendly curve standardisation process. Standardisation makes everything easier⁴.

It's worth mentioning that BLS12-381 is also designed to be efficient for ZK-SNARK proving (which is Zcash's main purpose for it), but this wasn't a major consideration for Ethereum's original adoption of it.

All in all, I don't recall any significant debate about the adoption of curve BLS12-381; it was simply the obvious choice at the time.

About curve BLS12-381

History

Curve BLS12-381 was designed by Sean Bowe in early 2017 as the foundation for an upgrade to the Zcash protocol. It is both pairing-friendly (making it efficient for digital signatures) and effective for constructing ZK-SNARKs.

Ethereum 2.0 was a fairly early adopter of the curve. A number of other blockchains (Zcash, Chia, Dfinity, Filecoin, Algorand) also use BLS12-381, and several cryptographic libraries support it. The main library used by Ethereum clients is Blst, which was commissioned by the Ethereum Foundation for this purpose; other libraries that implement the curve are Gnark, Noble, Herumi/mcl, and Constantine.

As for standardisation, BLS12-381 is included in the emerging IETF standard for Pairing-Friendly Curves. It also appears in the draft standards for Hashing to Elliptic Curves, and BLS signatures⁵.

Naming

BLS12-381 is part of a family of curves described by Barreto, Lynn, and Scott (they are the B, L, and S in view here - a mostly different BLS trio appears in connection with BLS signatures).

The 12 is the embedding degree of the curve: neither too low, nor too high. We'll discuss embedding degrees in a little while.

The 381 is the number of bits needed to represent coordinates on the curve: the field modulus, $q$. The coordinates of a point come from a finite field that has a prime order, and that prime number, $q$, is 381 bits wide. 381 is a fairly handy number as we can use 48 bytes per field element, with 3 bits left over for useful flags or arithmetic optimisations. The size of this number is guided both by security requirements and implementation efficiency.

Curve equation and parameters

The basic equation of the BLS12-381 curve is $y^2=x^3+4$.⁶

The key parameters for a BLS curve are set using a single parameter $\tt x$ (different from the $x$ in the curve equation!) that can be selected to give the curve nice properties for implementation. BLS12-381 is derived from the $k\equiv0\,\text{(mod 6)}$ case of Construction 6.6 in the taxonomy.

Specific design goals for BLS12-381 are:

• $\tt x$ has "low hamming weight", meaning that it has very few bits set to 1. This is particularly important for the efficiency of the algorithm that calculates pairings (the Miller loop).
• The field modulus $q$ mentioned above is prime and has 383 bits or fewer, which makes 64-bit or 32-bit arithmetic on it more efficient.
• The order $r$ of the subgroups we use is prime and has 255 bits or fewer, which is good for the same reason as above.
• The security target is 128 bits - see below.
• To support ZK-SNARK schemes, we want to have a large power of two root of unity in the field $F_r$. This means we want $2^n$ to be a factor of $r-1$, for some biggish $n$. Making $\tt x$ a multiple of $2^\frac{n}{2}$ will achieve this. This property is key to being able to use fast Fourier transforms for interesting things like polynomial multiplication.

The value ${\tt x}=$ -0xd201000000010000 (hexadecimal, note that it is negative) gives the largest $q$ and the lowest Hamming weight meeting these criteria. With this $\tt x$ value we have,

Field extensions

Field extensions are fundamental to elliptic curve pairings. The "12" in BLS12-381 is not only the embedding degree, it is also (relatedly) the degree of field extension that we will need to use to calculate pairings.

The field $F_q$ can be thought of as just the integers modulo $q$: $0,1,\ldots,q-1$. But what kind of beast is $F_{q^{12}}$, the twelfth extension of $F_q$?

I have been unable to find any straightforward explainers of field extensions, so here's my attempt.

Let's construct $F_{q^2}$, the quadratic extension of $F_q$. In $F_{q^2}$ we will represent field elements as first-degree polynomials like $a_0 + a_1x$, which we can write more concisely as $(a_0, a_1)$ if we wish.

Adding two elements is easy: ${(a, b) + (c, d)} = {a + bx + c + dx} = {(a+c) + (b+d)x} = {(a+c, b+d)}$. We just need to be sure to reduce $a+c$ and $b+d$ modulo $q$.

What about multiplying? ${(a, b) \times (c, d)} = {(a + bx)(c + dx)} = {ac + (ad+bc)x+ bdx^2} = {\tt ???}$. Oops - what are we supposed to do with the $x^2$ that's appeared?

We need a rule for reducing polynomials so that they have a degree less than two. In this example we're going to take ${x^2 + 1} = 0$ as our rule, but we could make other choices. There are only two rules about our rule⁷,

1. it must be a degree $k$ polynomial, where $k$ is our extension degree, $2$ in this case; and
2. it must be irreducible in the field we are extending. That means it must not be possible to factor it into two or more lower degree polynomials.

Applying our rule, by substituting $x^2 = -1$ to eliminate the unwanted $x^2$ term, gives us the final result ${(a, b) \times (c, d)} = {ac + (ad+bc)x + bdx^2} = {(ac-bd) + (ad+bc)x} = {(ac-bd, ad+bc)}$. This might look a little familiar from complex arithmetic: ${(a+ib) \times (c+id)} = {(ac-bd) + (ad+bc)i}$. This is not a coincidence! The complex numbers are a quadratic extension of the real numbers.

Complex numbers can't be extended any further because there are no irreducible polynomials over the complex numbers. But for finite fields, if we can find an irreducible $k$-degree polynomial in our field $F_q$, and we often can, then we are able to extend the field to $F_{q^k}$, and represent the elements of the extended field as degree $k-1$ polynomials, $a_0 + a_1x + \cdots + a_{k-1}x^{k-1}$. We can write this compactly as $(a_0,\ldots,a_{k-1})$, as long as we remember that there may be some very funky arithmetic going on.

Also worth noting is that modular reductions like this (our reduction rule) can be chosen so that they play nicely with the twisting operation.

In practice, large extension fields like $F_{q^{12}}$ are implemented as towers of smaller extensions. That's an implementation aspect, so I've put it in the more practical section below.

The curves

One of the initially non-obvious things about BLS12-381 is that we're really dealing with two curves, not one. Both curves share more-or-less the same curve equation, but are defined over different fields.

The simpler one is over the finite field $F_q$, which is just the integers mod $q$. So the curve has points only where the equation $y^2=x^3+4$ has solutions with $x$ and $y$ both integers less than $q$. Such a point is $(0,2)$, for example⁸. We shall call this curve $E(F_q)$.

The other curve is defined over an extension of $F_q$ to $F_{q^2}$ (think complex numbers). In this case, the curve equation is slightly modified to be $y^2=x^3+4(1+i)$⁹, and we'll call the curve $E'(F_{q^2})$¹⁰. We'll explain where this comes from in the section on Twists.

As an aside, the curve order of $E'(F_{q^2})$ (the number of points on the curve) is vastly bigger than that of $E(F_q)$; the curve equation has many more solutions when the domain is extended to the complex numbers. In fact, the order of $E$ is close to $q$, and the order of $E'$ is close to $q^2$. This is not a coincidence, but a result of the Hasse bound. See the reference section for the actual values of these numbers.

The Subgroups

In this section and the next I'll attempt to explain how BLS12-381 ended up having two curve equations rather than one.

A pairing is a bilinear map. This means that it takes as input two points, each from a group of the same order, $r$. This $r$ must be prime, and for security needs to be large. Also, for rather technical reasons¹¹, these two groups need to be distinct. Let's call them $G_1$ and $G_2$.

Unfortunately, our simple curve $E(F_q)$ has only a single large subgroup, so we can't define a useful pairing based solely on $E(F_q)$.

However, if we keep extending the field over which $E$ is defined, it can be proved that we eventually find a curve that has more than one subgroup of order $r$ (in fact, $r+1$ of them). That is, for some $k$, $E(F_{q^k})$¹² contains other subgroups of order $r$ that we can use. One of these subgroups contains only points having a trace of zero¹³, and we choose that subgroup to be $G_2$.

This number $k$, the amount that we need to extend the base field by to find the new group, is called the embedding degree of the curve, which in our case is the "12" in BLS12-381. We'll discuss embedding degree more in a moment.

For completeness, note that each of $G_1$ and $G_2$ shares with its containing curve the "point at infinity". This is the identity element of the elliptic curve arithmetic group, often denoted $\mathcal{O}$. For any point $P$, $P+\mathcal{O}=\mathcal{O}+P=P$.

To summarise where we've got to, we now have a group $G_1$ of order $r$ in $E(F_q)$, and we have a distinct group $G_2$ of order $r$ in $E(F_{q^{12}})$. Yay - we can do pairings!

Twists

But there's another challenge. As discussed earlier, doing arithmetic in $F_{q^{12}}$ is horribly complicated and inefficient, and curve operations need a lot of arithmetic. But there is a way to side-step this.

A twist is something like a coordinate transformation. Rather wonderfully, this can be used to transform our $E(F_{q^{12}})$ curve into a curve defined over a lower degree field that still has an order $r$ subgroup. Moreover, this subgroup has a simple mapping to and from our $G_2$ group¹⁴.

Curve BLS12-381 uses a "sextic twist". This means that it reduces the degree of the extension field by a factor of six. So $G_2$ on the twisted curve can be defined over $F_{q^2}$ instead of $F_{q^{12}}$, which is a huge saving in complexity.

If we can find a $u$ such that $u^6=(1+i)^{-1}$, then we can define our twisting transformation as $(x,y)\rightarrow(x/u^2,y/u^3)$¹⁵. This transforms our original curve $E:y^2=x^3+4$ into the curve $E':y^2 = {x^3 + 4/u^6} = {x^3 + 4(1+i)}$. $E$ and $E'$ look different, but are actually the same object presented with respect to coefficients in different base fields¹⁶.

When the twist is done correctly, the resulting $E'$ has a subgroup of order $r$ that maps to our $G_2$ group and vice-versa. So, it turns out that we can work in $E'$ over $F_{q^2}$ for most purposes, and map $G_2$ back to $E(F_{q^{12}})$ only when required (that is, only while actually computing pairings).

So these are the two groups we will be using:

• $G_1$ $\subset E(F_q)$ where $E: y^2 = x^3 + 4$
• $G_2$ $\subset E'(F_{q^2})$ where $E': y^2 = x^3 + 4(1+i)$

And that's the story of why BLS12-381 looks like two curves, not one. $E'(F_{q^2})$ is called the twist of, or the twisted curve corresponding to, $E(F_q)$.

Note that coordinates of points in the $G_1$ group are pairs of integers, and coordinates of points in the $G_2$ group are pairs of complex integers, so $G_2$ points take twice the amount of storage, and are more expensive to work with. This leads to interesting implementation trade-offs.

Pairings

So, what's this pairing thing all about?

As far as BLS12-381 is concerned, a pairing is a function that simply takes a point $P\in G_1\subset E(F_q)$, and a point $Q\in G_2\subset E'(F_{q^2})$ and outputs a point from a group $G_T\subset F_{q^{12}}$. That is, a pairing $e$ is a mapping, $e:G_1\times G_2\rightarrow G_T$.

Elliptic curve pairings are usually denoted $e(\cdot,\cdot)$ (they take a pair of operands, hence the name) and have certain properties.

1. $e(\cdot,\cdot)$ is bilinear.
2. $e(\cdot,\cdot)$ is efficiently computable. For any $P$ and $Q$, we must have a polynomial time algorithm for computing $e(P,Q)$.
3. $e(\cdot,\cdot)$ is non-degenerate. That is, for a non-zero $P \in G_1$ there must exist some $Q \in G_2$ such that $e(P,Q) \neq 1$ (the identity in $G_T$), and vice versa. This ensures that the pairing is "non-trivial" and actually useful.

Bilinearity

The property of pairings that we are most interested in is that they are bilinear. That is, $e(P,Q)$ is linear in both its arguments.

Anyone who can do multiplication is familiar with bilinearity : let $f(a,b) \equiv a \times b$, then ${f(a_1 + a_2, b)} = {f(a_1, b) + f(a_2, b)}$, and ${f(a, b_1 + b_2)} = {f(a, b_1) + f(a, b_2)}$ - multiplication is linear in both its arguments.

We could construct a similar bilinear function for elliptic curve points by multiplying the discrete logarithms of the two input points. If $g$ is a generator of an elliptic curve group, then a point $P$ is, by definition, a multiple of that generator, $P=[p]g$, and $p$ is said to be the discrete logarithm of $P$¹⁷. So, given points $P=[p]g$ and $Q=[q]g$, we could find $p$ and $q$ and define $e(P,Q) = [pq]g$ - this boils down to integer multiplication and is therefore bilinear. The flaw with this, however, is that taking discrete logarithms on our elliptic curve is assumed to be very, very expensive by design. It basically requires brute-force calculation with a cost proportional to the curve order, which is what keeps our signature scheme secure. This is why the pairing operation needs its second property: it must be efficiently computable.

Bilinear pairings

I'm not going to go into all the details of how the efficiently computable pairing function $e(\cdot,\cdot)$ is constructed – we can pretty much treat it as a black box – nevertheless, a great introduction is Vitalik's article, and for all the glorious details let me pitch again Pairings for Beginners.

Recall that $e$ is a mapping, $e:G_1\times G_2\rightarrow G_T$. Since $e(\cdot,\cdot)$ is linear in both its arguments, it behaves as follows.

• $e(P, Q + R) = e(P, Q) \cdot e(P, R)$, and
• $e(P + S, R) = e(P, R) \cdot e(S, R)$

From this, we can deduce that all of the following identities hold:

• ${e([a]P,[b]Q)} = {e(P,[b]Q)^a} = {e(P,Q)^{ab}} = {e(P,[a]Q)^b} = {e([b]P,[a]Q)}$

Note that, traditionally, the group operation in $G_1$ and $G_2$ is written additively, and the group operation in $G_T$ is written multiplicatively¹⁸ - I've used a "$\cdot$" to show that above. So we write $[n]P$ or $[n]Q$ for applying the group operation $n$ times on $P \in G_1$ or on $Q \in G_2$, but we write $e(P,Q)^n$ (rather than $[n]e(P,Q)$) because $e(P,Q) \in G_T$.

If we look past this notational weirdness, then we can loosely think of a pairing as being a way to "multiply" a point in $G_1$ by a point in $G_2$, an operation that cryptographically secure elliptic curves don't normally support in any practical way.

In any case, bilinearity is just what we need when verifying BLS digital signatures.

Embedding degree

We've mentioned the embedding degree several times, and it is significant enough to appear in the name of the curve.

The embedding degree, $k$, is calculated as the smallest positive integer such that $r$ divides $(q^k − 1)$. So, in the case of BLS12-381, $r$ is a factor of $(q^{12}-1)$¹⁹, but not of any lower power.

It turns out that this number, $k$, gives the smallest field extension $F_{q^k}$ that satisfies the two equivalent conditions:

• $F_{q^k}$ contains more than one subgroup of order $r$ (used for constructing $G_2$, see above);
• $F_{q^k}$ contains all the $r$th roots of unity (used for constructing $G_T$, see below)

These are the conditions we need to satisfy for pairings to be possible.

The choice of an embedding degree is a balance between security and efficiency (as ever). On the security front, the embedding degree is also known as the security multiplier: a higher embedding degree makes the discrete logarithm problem harder to solve in $G_T$. However, a high embedding degree means we have to do field operations in high-degree extensions, such as $F_{q^{12}}$, which is clunky and inefficient. (This is true even when using twists: the maximum available twist is degree six, so the best we can do is to reduce the field extension degree by six. And in any case pairing must be done in the large extension field.)

Embedding degrees of 12 or 24 seem to be a current sweet-spot for many applications. Once again, the embedding degree of BLS12-381 is 12 - it's in the name.

Security level

Security of cryptographic systems is measured in bits. Informally, I take $n$-bit security to mean something like, "would need about $2^n$ operations to break it".

For elliptic curve cryptography, security is all about making the discrete logarithm problem hard. That is, given a point $g$ and a point $g^k$ (in multiplicative group notation), finding $k$ must be infeasible without prior knowledge, meaning that we want it to take at least $2^n$ operations for $n>100$ or so, in today's terms.

For pairing-friendly curves, the discrete logarithm problem must be hard in each of the three of the groups we are using, $G_1$, $G_2$, and $G_T$. Thus, to target $n$-bit security,

• The prime group order $r$ must be at least $2n$ bits long as there are algorithms such as Pollard's rho algorithm that have cost $O(\sqrt{r})$.
• Our extension field $F_{q^k}$ must be large enough not to be vulnerable to methods like the number field sieve.

BLS12-381 was intended to offer around a 128 bit security level, based on these criteria, and this was supported by initial analyses. See Table 1.1 in the Taxonomy, for example.

However, on closer examination it seems that "the finite extension field of size 3072 = 12 × 256 bits is not big enough" (quoting section 2 here), in view of the second criterion above.

According to a report by NCC Group, citing other sources, the actual security level is probably between 117 and 120 bits (see pages 8 and 9). They regard this as a perfectly adequate level of security: "The value of reaching '128-bit' [being] mostly psychological". Sean Bowe has also commented on the security level in the light of the original design goals. The draft IETF specification for BLS12-381 is less pessimistic than the NCC Group, and cites a security level of 126 bits.

Cofactor

A subgroup's cofactor is the ratio of the size of the whole group to the size of the subgroup. Normal elliptic curve cryptography requires the cofactor to be very small, usually one, in order to avoid small subgroup attacks on discrete logarithms. In pairing-based cryptography, however, this is not the case, and the cofactors of the $G_1$ and $G_2$ groups can be truly enormous.

It turns out that, with care, we can have large cofactors and still be secure. Namely, when the cofactors of $G_1$, $G_2$ and $G_T$ contain no prime factors smaller than $r$. Section 3.2 of this paper discusses this in detail. This is not the case for BLS12-381, however, and the $G_1$ and $G_2$ cofactors both have several small factors. Thus, we have to be mindful of small subgroup attacks in our implementations.

I've listed the prime factors of the curve orders in the reference section, as well as the cofactors themselves. The $G_1$ cofactor contains small prime factors like 3, 11, and 10177; the $G_2$ cofactor contains small prime factors like 13, 23, and 2713.

It's not all bad news when it comes to the cofactors, though. It turns out that multiplying by the group's cofactor is a straightforward way to map any arbitrary point on the elliptic curve into the respective subgroup, $G_1$ or $G_2$²⁰. This is important when doing "hash to curve" operations and the like: we first make a point on the curve, and then we map it into the appropriate group by multiplying by the cofactor, so-called cofactor clearing.

Roots of unity

Just a note on roots of unity, because they appear in two completely different and unrelated contexts, which can be confusing.

First, we said that to support ZK-SNARK schemes with this curve, for some biggish $n$ we want to have a $2^n$th root of unity in the field $F_r$ (not $F_q$, note). This is to facilitate efficient fast Fourier transforms for manipulating very large polynomials over the scalar field $F_r$. From the hexadecimal representation of $r-1$, it's clearly a multiple of $2^{32}$, so there is a $2^{32}$th root of unity ($2^{32}$ of them, in fact).

Second, and completely unrelated, the effect of the pairing is to map the two points from $G_1$ and $G_2$ onto an $r$th root of unity in $F_{q^{12}}$. These $r$th roots of unity actually form a subgroup in $F_{q^{12}}$ of order $r$²¹, which is the group we call $G_T$.

Let's briefly revisit our discussion of extending the base field for $E$ to $F_{q^{12}}$, which we did in order to find another subgroup of order $r$. It also turns out $F_{q^{12}}$ treated as a multiplicative group is the smallest field extension that contains the $r$th roots of unity in the field, the 12 coming from the embedding degree once again. This is why $G_T$ is defined over $F_{q^{12}}$.

Using curve BLS12-381

This section is a miscellany of things relevant to using BLS12-381 in practice.

BLS digital signatures

Now it's time to introduce the other BLS: Boneh, Lynn and Shacham. (The L is the same L as in BLS12-381; the B and the S are different.)

BLS signatures were introduced back in 2001, a little before the BLS curve family was published in 2002. Pleasingly, they go hand-in-hand. (BLS signatures can use other curves; BLS curves have uses other than signatures. But it's nice when they come together.)

The BLS signature scheme is described briefly below. See the BLS Signatures chapter for a fuller exploration of how we have implemented them in Ethereum 2. You can find a pretty concise but lucid description of the BLS signature scheme in the draft IETF standard.

Private and public keys

The private/secret key (to be used for signing) is just a randomly chosen number between $1$ and $r-1$ inclusive. We'll call it $sk$.

The corresponding public key (if we're using $G_1$ for public keys) is $pk = [sk]g_1$, where $g_1$ is the chosen generator of $G_1$. That is, $g_1$ multiplied by $sk$, which is $g_1$ added to itself $sk$ times.

The discrete logarithm problem means that it is unfeasible to recover $sk$ given the public key $pk$.

Signing

To sign a message $m$ we first need to map $m$ onto a point in group $G_2$ (if we're using $G_2$ for signatures). See hashing to the curve, below, for a discussion on ways to do this. Anyway, let's assume we can do this, and call the resulting $G_2$ point $H(m)$.

We sign the message by calculating the signature $\sigma = [sk]H(m)$. That is, by multiplying the hash point by our secret key.

Verification

Given a message $m$, a signature $\sigma$, and a public key $pk$, we want to verify that it was signed with the $sk$ corresponding to $pk$.

This is where pairing comes in. The signature is valid if, and only if, $e(g_1,\sigma) = e(pk,H(m))$.

We can confirm this using the properties of pairings: ${e(pk,H(m))} = {e([sk]g_1,H(m))} = {e(g_1,H(m))^{(sk)}} = {e(g_1,[sk]H(m))} = {e(g_1,\sigma)}$.

Aggregation

A really neat property of BLS signatures is that they can be aggregated (see also the original paper), so that we need only two pairings to verify a single message signed by $n$ parties, or $n+1$ pairings to verify $n$ different messages signed by $n$ parties, rather than $2n$ pairings you might naively expect to need. Pairings are expensive to compute, so this is very attractive.

It's possible to aggregate signatures over different messages, or signatures over the same message. In the case of Ethereum 2.0 we aggregate over the same message, so for brevity I'm just going to consider that.

To aggregate signatures we just have to add up the $G_2$ points they correspond to: $\sigma_{agg} = \sigma_1+\sigma_2+\cdots+\sigma_n$. We also aggregate the corresponding $G_1$ public key points $pk_{agg} = pk_1+pk_2+\cdots+pk_n$.

Now the magic of pairings means that we can just verify that $e(g_1,\sigma_{agg}) = e(pk_{agg},H(m))$ to verify all the signatures together with just two pairings.

Swapping G1 and G2

For many purposes, the $G_1$ and $G_2$ groups are interchangeable. For example, with the BLS signature scheme, we can choose our public keys to be members of $G_1$ and our signatures to be members of $G_2$, or we can do it the other way round - the pairing function doesn't care; everything still works if we swap the groups over.

The trade-offs are execution speed and storage size. $G_1$ has small points and is fast; $G_2$ has large points and is slow. BLS12-381 was initially designed to implement Zcash, and for performance reasons they chose to use $G_1$ to represent signatures and $G_2$ to represent public keys.

With respect to Zcash, most other implementations are "reversed". In Ethereum 2.0 we use $G_1$ for public keys: for one thing, aggregation of public keys happens much more often than aggregation of signatures; for another, public keys of validators need to be stored in state, so keeping the representation small is important. Signatures, then, are $G_2$ points.

Point compression

(Note that sometimes, the twisting operation is referred to as point compression - that's something completely different to what we're discussing here.)

For storing and transmitting elliptic curve points, it is common to drop the $y$-coordinate. This halves the amount of data. For BLS12-381, $G_1$ points are reduced from 96 bytes (2 × 381 bits-rounded-to-bytes) to 48 bytes, and $G_2$ points are reduced from 192 bytes to 96 bytes.

Any elliptic curve point can be regenerated from the $x$ coordinate by using the relevant curve equation, $E$ or $E'$. For any valid $x$ coordinate on the curve, $y$ is either zero or has two possible values that are the negative of each other: $y=\pm\sqrt{x^3+4}$ for $G_1$, and analogously for $G_2$.

Since field elements are 381 bits, and 48 bytes is 384 bits, we have some bits to spare for flags. The most important is a flag to show which of the $y$ values the point corresponds to (positive or negative). Another bit is used to signal whether this is the point at infinity (which has many possible representations). A third is simply to indicate whether this is a compressed or uncompressed representation, though context should handle this in practice.

For both $G_1$ and $G_2$, about half of $x$ values are not on the curve. In this case, the point is conventionally decoded to the point at infinity. But unless the infinity flag is set – in which case we would not have attempted to decode the point – this is an error condition.

The specific details of how the flag bits and $x$ values are encoded is here.

Subgroup membership checks

When dealing with any point with an unknown origin, whether it comes to us compressed or uncompressed, it's important that we check that it lies in the correct subgroup. The point decompression described above only results in a point on the curve; we don't know whether it lies in the appropriate $G_1$ or $G_2$.

The main issue seems to be that both $E(F_{q})$ and $E'(F_{q^2})$ contain small subgroups (you can see this by factoring the cofactors²² - see the reference section for the actual factors). Inadvertently working with points in these small subgroups could lead to vulnerabilities, as discussed in this paper.

Subgroup checks are easy in principle: simply multiply our point by $r$. For points in $G_1$ or $G_2$ this will result in the respective points at infinity; for points outside the groups, it won't.

Unfortunately, this is slow in practice, especially for $G_2$, since $r$ is so large. As an alternative, there are new techniques making use of endomorphisms for performing faster subgroup checks.

Generators

$G_1$ and $G_2$ are cyclic groups of prime order, so any point (except the identity/point at infinity) is a generator. Thus, picking generators is just a matter of convention.

Generator points for $G_1$ and $G_2$ are specified in decimal here and the same points in hexadecimal here.

These were chosen as follows:

The generators of $G_1$ and $G_2$ 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.

By my calculations, with $h_1$ and $h_2$ the respective group cofactors, this makes the $G_1$ generator $g_1=[h_1]p_1$, with $p_1$ as follows,

• $p_1 =$ (0x04, 0x0a989badd40d6212b33cffc3f3763e9bc760f988c9926b26da9dd85e928483446346b8ed00e1de5d5ea93e354abe706c)

and the $G_2$ generator $g_2=[h_2]p_2$, with $p_2$ as follows,

• $p_2 =$ ([0x02, 0x00],[0x013a59858b6809fca4d9a3b6539246a70051a3c88899964a42bc9a69cf9acdd9dd387cfa9086b894185b9a46a402be73,0x02d27e0ec3356299a346a09ad7dc4ef68a483c3aed53f9139d2f929a3eecebf72082e5e58c6da24ee32e03040c406d4f])

(I think "lexicographically smallest" means treating all numbers in the base field as non-negative, and just taking the smaller one, prioritising real parts over imaginary parts.)

Final exponentiation

Calculation of a pairing has two parts: the Miller loop and the final exponentiation. Both parts are quite expensive, but there's a nice hack you can do to reduce the impact of the final exponentiation.

Normally, we calculate two full pairings in order to perform signature verification, to check whether $e(g_1,\sigma)=e(pk,H(m))$.

If we denote as $e'(\cdot,\cdot)$ the pairing without the final exponentiation, then for, some $x$, we are checking whether $e'(g_1,\sigma)^x=e'(pk,H(m))^x$. ($x$ happens to be $(q^{12} − 1)/r$, which is huge²³.)

We know how to multiply in group $G_T$, so we can reorganise this as a check whether $(e'(-g_1,\sigma)e'(pk,H(m)))^x=1$. (We can negate any one of the points: the magic of pairings makes this equivalent to taking the inverse in $G_T$.)

So, to verify a signature, we do the two Miller loops, one with a negated input value, multiply the results and then do a single final exponentiation. If the result is unity in $G_T$ then our pairings match. This ought to give a worthwhile speedup.

Hashing to the curve

To calculate a digital signature over a message, we first need to transform an arbitrary message (byte string) to a point on the $G_2$ curve (if we are using $G_2$ for signatures). There are many ways to do this, with varying degrees of efficiency and security.

Hash and check

The initial implementation in Eth2 was "hash-and-check". This is very simple.

1. Hash your message to an integer modulo $q$.
2. Check if there is a point on the curve with this $x$-coordinate (real part $x$, imaginary part $0$). If not, add one to $x$ and repeat this step.
3. We have a point on the curve! Multiply by the $G_2$ cofactor to convert it into a point in $G_2$ (cofactor clearing).

About half the points that we try will result in a point on the curve, so this is not constant time: we don't know how many iterations it will take to find one. In one sense it doesn't matter: all the information is public, so we're not leaking anything. However, it does open up a griefing attack. An attacker could pre-calculate messages that take a very long time to find a point (1 in one million messages will take 20 tries, for example) and slow us down considerably.

Simplified SWU map

We have now adopted a better approach which is described in this paper and defined in RFC 9380, the IETF standard for hashing to curves. As before (but a bit differently to ensure a uniform distribution of output points) we first create a field point by hashing the message mod $q$ (the "expand message" step).

Next we use a special map (the SWU map) that is guaranteed to translate that field point into a valid point on an elliptic curve. For technical reasons, this is not the curve $E'(F_{q^2})$, but a curve isogenous to it (i.e. having the same number of points). We then use another map (3-isogeny) to transfer this to a point on $E'(F_{q^2})$. Finally we use cofactor clearing to end up with a point in $G_2$.

You can take a look at my implementation of this in Java , based on the reference code in Python. The idea is for this approach to be generally adopted to enhance the interoperability of blockchains.

Cofactor clearing

We discussed multiplying by the cofactor as a way to make an arbitrary point on $E$ or $E'$ into a point in $G_1$ or $G_2$ respectively. This is useful when hashing to the curve, for example.

The $G_2$ co-factor is huge, so multiplying by it is slow. However, there are faster ways to map curve points into $G_2$ using an endomorphism (a map of a group to itself). This features in the RFC 9380 standard.

The endomorphism we use was until recently subject to a patent, but, as of 2020, this patent has expired everywhere.

As a workaround to the patent before it expired, instead of multiplying by the $G_2$ cofactor, the standard suggests multiplying by an effective cofactor, $h_{eff}$ (see section 8.8.2 of RFC 9380 for the value), which gives the same result as the endomorphism. The effective cofactor is even larger than the $G_2$ cofactor, but the multiplication can be implemented using an addition chain as an optimisation.

Now that the patent has expired, the endomorphism can be just dropped in as a replacement for the effective cofactor multiplication.

Extension towers

Recall our discussion of field extensions? In practice, rather than implementing a massive 12th-degree extension directly, it is more efficient to build it up from smaller extensions: a tower of extensions.

For BLS12-381, the $F_{q^{12}}$ field is implemented as a quadratic (degree two) extension, on top of a cubic (degree three) extension, on top of a quadratic extension of $F_q$.

As long as the modular reduction polynomial (our reduction rule) is irreducible (can't be factored) in the field being extended at each stage, then this all works out fine.

Specifically:

1. $F_{q^2}$ is constructed as $F_q(u) / (u^2 - \beta)$ where $\beta = -1$.
2. $F_{q^6}$ is constructed as $F_{q^2}(v) / (v^3 - \xi)$ where $\xi = u + 1$.
3. $F_{q^{12}}$ is constructed as $F_{q^6}(w) / (w^2 - \gamma)$ where $\gamma = v$

Interpreting these in terms of our previous explanation:

1. We write elements of the $F_{q^2}$ field as first degree polynomials in $u$, with coefficients from $F_q$, and apply the reduction rule $u^2 + 1 = 0$, which is irreducible in $F_q$.
   • an element of $F_{q^2}$ looks like $a_0 + a_1u$ where $a_j \in F_q$.
2. We write elements of the $F_{q^6}$ field as second degree polynomials in $v$, with coefficients from the $F_{q^2}$ field we just constructed, and apply the reduction rule $v^3 - (u + 1) = 0$, which is irreducible in $F_{q^2}$.
   • an element of $F_{q^6}$ looks like $b_0 + b_1v + b_2v^2$ where $b_j \in F_{q^2}$.
3. We write elements of the $F_{q^{12}}$ field as first degree polynomials in $w$, with coefficients from the $F_{q^6}$ field we just constructed, and apply the reduction rule $w^2 - v = 0$, which is irreducible in $F_{q^6}$.
   • an element of $F_{q^{12}}$ looks like $c_0 + c_1w$ where $c_j \in F_{q^6}$.

This towered extension can replace the direct extension as a basis for pairings, and when well-implemented can save a huge amount of arithmetic when multiplying $F_{q^{12}}$ points. See Pairings for Beginners section 7.3 for a full discussion of the advantages.

Coordinate systems

Finding the inverse of a field element (i.e. division) is an expensive operation, so implementations of elliptic curve arithmetic try to avoid it as much as possible. It helps if we choose the right coordinate system for representing our points.

Affine coordinates

Affine coordinates are the traditional representation of points with just an $(x,y)$ pair of coordinates, where $x$ and $y$ satisfy the curve equation. This is what we normally use when storing and transmitting points.

However, it is not always the most efficient form to use when actually working with points, and there are two other schemes I'm aware of that are used for BLS12-381.

The basic idea is to represent the coordinate using notional fractions, reducing the number of actual division operations needed. To do this, a third coordinate is introduced and we use $(X, Y, Z)$ for the internal representation of a point. Like our familiar fractions, there are many representations of the same value, all corresponding to a single actual value ($\frac{1}{2}$, $\frac{3}{6}$, $\frac{197}{394}$ are all the same number).

The two systems I know of in use for BLS12-381 are Standard Projective coordinates and Jacobian coordinates.

Standard Projective coordinates

The Standard Projective coordinate point $(X, Y, Z)$ represents the Affine coordinate point $(X/Z, Y/Z)$.

These are also called homogeneous projective coordinates because the curve equation takes on the homogeneous form $Y^2Z=X^3+4Z^3$. Points become straight lines through the origin in $(X, Y, Z)$ space, with the Affine point being the intersection of the line with the plane $Z=1$. Figure 2.10 in Pairings for Beginners gives a nice illustration.

Standard Projective coordinates are used by the Apache Milagro BLS12-381 library, and also by the noble-curves implementation.

Jacobian coordinates

A different kind of projective coordinates are Jacobian coordinates. In this scheme, the Jacobian point $(X, Y, Z)$ represents the Affine point $(X/Z^2, Y/Z^3)$. The curve equation becomes $Y^2=X^3+4Z^6$.

The sample code for the constant-time hash-to-curve uses Jacobian coordinates, as does the gnark-crypto library.

Note that, in both schemes, the easiest way to import the Affine point $(x, y)$ is to map it to $(x, y, 1)$.

BLS12-381 Reference

General

Curve E(F_q)

The product of the factors of the group order, excluding $r$, are (by definition) the cofactor of the subgroup with order $r$ ($G_1$ in this case).

Observe that the number of points on curve $E$, its order, $|E(F_q)|$, is (in some sense) very close to the field modulus, $q$. This is a consequence of the Hasse bound.

Subgroup G_1

The $G_1$ cofactor is the factorisation of the curve order, $|E(F_q)|$, excluding the $r$ term.

Curve E'(F_q^2)

The order of curve $E'$, $|E'(F_{q^2})|$, is close to the square of the field modulus, $q^2$.

Subgroup G_2

The $G_2$ cofactor is the factorisation of the curve order, $|E'(F_{q^2})|$, excluding the $r$ term.

Resources and further reading

There are lots of references linked in the above, and I'm not going to repeat many here. I'll just pick out a few particularly useful or interesting things.

Useful reference material:

• The original BLS12-381 announcement
• Concise description of the parameters and serialisation
• Draft IETF standard

In general, implementations of pairing libraries tend to be highly optimised and/or very generic (supporting many curves) which makes them quite hard to learn from. The Noble BLS12-381 library in JavaScript/TypeScript by Paul Miller is among the easier to follow.

The blsh REPL (a wrapper around the BLST library) is excellent for exploring the curve itself. See the grammar for the full functionality - the info command alone is worth it. You can manually verify BLS signatures if you like.

Finally, a couple of random but fun and interesting reads:

• This white paper on Curve9769 is not directly relevant to BLS12-381, but is a well-written and wonderful exploration of the joys and pains of designing and implementing an elliptic curve (not a pairing-friendly one in this case).
• Pairings are not dead, just resting. A great overview presentation. Some BLS12-381 things.