Explaining BLS12–381 … The “Zero Knowledge Proof” Curve

What’s “BLS”, “12” and “381” in BLS12–381?
Photo by Marten Bjork on Unsplash

Explaining BLS12–381 … The “Zero Knowledge Proof” Curve

What’s “BLS”, “12” and “381” in BLS12–381?

Introduction

A good deal of my work involves using elliptic curves, along with implementing pairing-based cryptography for things like zero knowledge proofs (ZKPs). At the core of this is often the magical BLS12–381 curve, and which has not one curve, but two. If you want a little bit of the basics on elliptic curve cryptography (ECC), try here:

Well, the “BLS” part is easy, as it is named after its creators: Barreto, Lynn and Scott (BLS) [1]:

The first curve (G1)

The first curve on BLS12–381 is just y²=x³+4 (mod p) over a finite field defined by:

p= 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab

This prime number has 381 bits (and thus where the second part of the name comes from). Just by looking at this equation, we can see we have a point at (0,2) — as y²=4 (mod p) gives us a solution of y=2.

We can now create a program to determine the points:


import libnum
import sys
p= 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
x=0
if (len(sys.argv)>1):
    x=int(sys.argv[1])
    
z=x**3+4 % p
print("== Points on BLS12-381 curve ==")
print("y^2=x^3+4 (mod p)")
if (libnum.has_sqrtmod(z,{p:1} )):
    y=list(libnum.sqrtmod(z,{p:1}))
    
    print (f"({x},{y[0]})")
    print (f"({x},{y[1]})")
    print("\nIn hex:")
    print (f"({hex(x)},{hex(y[0])})")
    print (f"({hex(x)},{hex(y[1])})")
else:
    print("No point")

In this case sqrtmod() gives us the quadratic residue — and which is the square root of a value with a given modulus. Running for x=0, we get [here]:

We can see we get two points. One of these is odd and the other is even. This is similar to having a square root which is positive or negative. The two points at x=0 is then [here]:

== Points on BLS12-381 curve ==
y^2=x^3+4 (mod p)
(0,4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559785)
(0,2)

Now, if we try x=1, x=2 or x=3, we will get no points [here]:

But, now if we try x=4 we get a valid point [here]:

== Points on BLS12-381 curve ==
y^2=x^3+4 (mod p)
(4,1630892974828014537729259858097113969650871260980656934049590190201941782487224876496582135785777461178964897591404)
(4,2371516580393652855688529967638790186906011558958350951282467945922089868003612987946105493343238202858929374968383)

We can see that not all the points are valid on the curve, and so we define the order of the curve (r). This defines the total number of valid points on the curve. If we use a field of p, the curve is defined as E(F_p) and where all our values are constrained between 0 and p-1. The base point of this curve has been selected at:

(0x17F1D3A73197D7942695638C4FA9AC0FC3688C4F9774B905A14E3A3F171BAC586C55E83FF97A1AEFFB3AF00ADB22C6BB, 0x08B3F481E3AAA0F1A09E30ED741D8AE4FCF5E095D5D00AF600DB18CB2C04B3EDD03CC744A2888AE40CAA232946C5E7E1)

and the order is defined as 0x73eda753 299d7d48 3339d808 09a1d805 53bda402 fffe5bfe ffffffff 00000001. If we try our program with a value of x=3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507 (and which is the integer equivalent of the x value above), we get [here]:

== Points on BLS12-381 curve ==
y^2=x^3+4 (mod p)
(3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507,1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569)
(3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507,2662903010277190920397318445793982934971948944000658264905514399707520226534504357969962973775649129045502516118218)
In hex:
(0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb,0x8b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1)
(0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb,0x114d1d6855d545a8aa7d76c8cf2e21f267816aef1db507c96655b9d5caac42364e6f38ba0ecb751bad54dcd6b939c2ca)

Okay. So all of this was just normally elliptic curve theory. Now, we will discover the second curve.

The second curve (G2)

And so BLS12–381 has another curve. One way we can do this is to define a larger field, such as extending F_p into F_p². This second curve will thus have a much larger number of points (from 0 to p²-1). And so we can define a subgroup of our base curve to provide another curve — and which can be defined by F_{p^k} and k as the embedding degree.

In BLS12, we use a value of k=12 (and where the “12” part of the name comes from). This is defined as a subgroup of G2. We now have a new set of points in the group.

The pairing between the two curve s(G1 and G2) is known as a bilinear map. Unfortunately, F_p^{12} is a fairly complex curve, and so we add in a twist to the curve, and which reduces the complexity down to F_p². This is a “sextic twist”, and which reduces the degree by a factor of six (from F_p^{12} to F_p². It should thus be noted that working on G1 is faster than working on G2 (and there is a smaller field for the calculations). Also, we need more memory to store G2 points than G1.

Basic parameters for BLS12–381

The basic parameters we have for BLS12–381 are [here]:

Base field modulus = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
B coefficient = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
Main subgroup order = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
Extension tower
Fp2 construction:
Fp quadratic non-residue = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaaa
Fp6/Fp12 construction:
Fp2 cubic non-residue c0 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Fp2 cubic non-residue c1 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Twist parameters:
Twist type: M
B coefficient for twist c0 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
B coefficient for twist c1 = 0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004
Generators:
G1:
X = 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
Y = 0x08b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1
G2:
X c0 = 0x024aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8
X c1 = 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049334cf11213945d57e5ac7d055d042b7e
Y c0 = 0x0ce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a76d429a695160d12c923ac9cc3baca289e193548608b82801
Y c1 = 0x0606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e99ab3f370d275cec1da1aaa9075ff05f79be
Pairing parameters:
|x| (miller loop scalar) = 0xd201000000010000
x is negative = true

We can see that the base field modulus is the prime number we defined earlier. The reason that G2 has two values for the x and y co-ordinates, is that these are complex numbers (and not integers, as with G1). This is the reason that points on G2 take up more memory.

In programming terms, we often use type values of Fp2, Fp6 and Fp12 to order to represent the fields involved. Overall the twisted curve (E’) is then defined as:

E’: y² = x³ + 4(u + 1)

And so, I have created a number of demonstrators of the usage of BLS12 curves here:

https://asecuritysite.com/bls/

Pairings

And so, we can now create a pairing of e(P,Q), and where we have a point P on G1 (E(F_q)), and a point Q on G2 (E(F_q²)) and can then create a pairing (e) of e:G1×G2→GT. With this, we have the special properties of:

  • e(P,Q+R)=e(P,Q)⋅e(P,R)
  • e(P+S,R)=e(P,R)⋅e(S,R)

Here is an outline of how this is used:

and there are examples here:

https://asecuritysite.com/pairing/

Conclusions

I do hope that this article has provided a little bit more depth to the usage of the BLS12–381 curve, and in how wonderful it it.

Postscript

I am lucky to be involved with MIRACL, and who have the “S” in BLS as their lead cryptographer (Mike Scott). So, here’s some cool MIRACL things:

https://asecuritysite.com/miracl/

References

[1] Barreto, P. S., Lynn, B., & Scott, M. (2002, September). Constructing elliptic curves with prescribed embedding degrees. In International conference on security in communication networks (pp. 257–267). Springer, Berlin, Heidelberg [here].