BLS-12-381 Basics

This post lays out the bare minimal basics required to understand BLS signatures. Most of the hard work is about setting up cryptographic primitives. To make things concrete, I only use the details from the BLS-12-381 curve. The post on vanilla elliptical curve cryptography contains some basics on how EC groups are defined.

Preliminary

Let’s define the following constants.

k = 12
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
q = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
u = -0xd201000000010000

Note that \(r = u^4 - u^2 + 1\) is a 255 bit prime, and \(q = \frac{1}{3} (u-1)^2(u^4-u^2+1) + u\) is a 381 bit prime. We also define field extensions. See the Implementing Pairing paper for more details.

\begin{eqnarray*} \mathcal{F}_{q^2} &=& \mathcal{F}_q[u]/(u^2 − \beta), \beta \in \mathcal{F_q} \\ \mathcal{F}_{q^6} &=& \mathcal{F}_{q^2}[v]/(v^3 −ξ), \xi \in \mathcal{F}_{q^2} \\ \mathcal{F}_{q^{12}} &=& \mathcal{F}_{q^6}[w]/(w^2 −\gamma), \gamma \in \mathcal{F}_{q^6}. \end{eqnarray*}

First Group

The first group is defined by the curve equation on the prime field \(\mathcal{F}_q\):

\begin{equation} \mathbb{G_1} = \{ x, y \in \mathcal{F}_q: y^2 = x^3 + 4\} \end{equation}

\(\mathbb{G_1}\) has a cofactor of \(h_1 = (u -1)^2 / 3\), which is a 32 bit integer. A point in this group is a value with two coordinates, each is a 381 bit integer. The point could be encoded in compressed form with only 48 bytes. Only one coordinate needs to be provided. Let \(g_1 = (x, y)\) be this group’s generator.

x:
0x21a6 d67ef250 191fadba 34a0a301 60b9ac92 64b6f95f 63b3edbe c3cf4b2e 689db1bb b4e69a41 6a0b1e79 239c0372 e5cd7011 3c98d91f 36b6980d
y:
0x0118 ea0460f7 f7abb82b 33676a74 32a490ee da842ccc fa7d788c 65965042 6e6af77d f11b8ae4 0eb80f47 5432c666 00622eca a8a5734d 36fb03de

Second Group

The second group is defined by the following curve equation on the quadratic field \(\mathcal{F}_{q^2}\).

\begin{equation} \mathbb{G_2} = \{ x, y \in \mathcal{F}_{q^2}: y^2 = x^3 + 4(i + 1)\} \end{equation}

\(\mathbb{G_2}\) has a cofactor of \(h_2 = (u^8 - 4u^7 + 5u^6 - 4u^4 + 6u^3 - 4u^2 - 4u + 13) / 9\), which is a 127 bit integer. A point in this group is two values in \(\mathcal{F_{q^2}}\). It is 96 bytes in compressed form. Let \(g_2 = (x, y)\) be this group’s generator. Note that \(x, y \in \mathcal{F}_{q^2}\). To be more explicit, \(x_0, x_1, y_0, y_1 \in \mathcal{F}_q\), and

\begin{eqnarray*} x &=& x_0 + x_1 i \\ y &=& y_0 + y_1 i \end{eqnarray*}

x_0:
0x24aa2b2 f08f0a91 26080527 2dc51051 c6e47ad4 fa403b02 b4510b64 7ae3d177 0bac0326 a805bbef d48056c8 c121bdb8
x_1:
0x13e02b60 52719f60 7dacd3a0 88274f65 596bd0d0 9920b61a b5da61bb dc7f5049 334cf112 13945d57 e5ac7d05 5d042b7e
y_0:
0xce5d527 727d6e11 8cc9cdc6 da2e351a adfd9baa 8cbdd3a7 6d429a69 5160d12c 923ac9cc 3baca289 e1935486 08b82801
y_1:
0x606c4a0 2ea734cc 32acd2b0 2bc28b99 cb3e287e 85a763af 267492ab 572e99ab 3f370d27 5cec1da1 aaa9075f f05f79be

Third Group and Bilinear Map

The third group is \(G_T\), the \(r\)-th roots of unity in \(\mathcal{F}_{q^{12}}\). It is a subgroup of \(\mathcal{F}_{q^{12}}\), with an subgroup order \(r\). The bilinear map \(e : \mathbb{G_1} \times \mathbb{G_2} \mapsto \mathbb{G_T}\) is defined as the following. For any \(P\in \mathbb{G_1}\) and \(Q \in \mathbb{G}_2\),

\begin{equation} e(P, Q) = [f_{r, P}(Q) ] ^{(q^k - 1)/r} \end{equation}

Note that \(r\) is the group order of \(\mathbb{G}_T\), \(k\) is the embedding number \(12\), \(q\) is the 381 bit prime. \(f_{r, P}\) is a polynomial, the miller function. Miller function could be computed by Miller’s algorithm, which looks like a double-and-add technique.

These parameter setup could be found in the IETF specs.

Signing

We could use either \(\mathbb{G}_1\) or \(\mathbb{G}_2\) as the public key space. To keep things simple, we use \(\mathbb{G}_1\) as the public key space. Public keys are 48 bytes.

A secret key is any number \(\rho \in \{1, 2, ... , r -1\}\). The associated public key is \(\rho g_1 \in \mathbb{G}_1\). Let the message be \(m\). Assume that we have a hash function, \(H: M \mapsto \mathbb{G}_2\), where \(M\) is a the message space. The signature is calcuculated as

\begin{equation} s = \rho H(m) \in \mathbb{G}_2. \end{equation}

Note that the signature is a point in the group \(\mathbb{G}_2\). It is 96 bytes in length.

Verification

Verify the following relationship is sufficient,

\begin{equation} e(\rho g_1, H(m)) = e(g_1, s). \end{equation}

Note that \(\rho g_1\) is the public key of the signer.

Aggregation

Let say that the message is signed by many public keys, \(\rho_1 g_1, \rho_2 g_1, ..., \rho_n g_1\). The signatures are \(s_1, s_2, ..., s_n\). The aggregate public key is then

\begin{equation} \rho_A g_1 = \rho_1 g_1 + \rho_2 g_1 + ... + \rho_n g_1. \end{equation}

The aggregate signature is

\begin{equation} S_A = s_1 + s_2 + ... + s_n \end{equation}

The verification critieria is more or less the same.

\begin{equation} e(\rho_A g_1, H(m)) = e(g_1, s_A) \end{equation}

Notes

Using the BLS-12-381 curve is straight forward once all parameters are well setup.
The name of BLS-12-381 comes from \(k=12\), which is the embedded degree. One way to interpret it is that \(12\) is chosen so that \(\mathcal{F}_{q^{k}}\) contains all the \(r\)-th root of unity. \(381\) is the bit length of of the prime number \(q\) used to define the finite field, \(\mathcal{F}_q\).
The role of \(\mathbb{G}_1\) and \(\mathbb{G}_2\) could be swapped.
One signing party could tamper with the aggregate public key. It is sufficient to ask each public key holder to shows that they also has possession of the corresponding private key.
For the sake of simplicity, I ignore most of the discussions about security. I will add those discussion in a later post if there are interests.

References

A gentle but verbose introduction to BLS12-381:
IETF specs
Ethereum BLS Spec
Miller algorithm
How to compute pairing