Try   HackMD

BN254 For The Rest Of Us

The pairing friendly elliptic curve BN254 was previously used by ZCash (Section 5.4.9.1) and is currently the only curve with precompiled contracts on Ethereum for elliptic curve addition, scalar multiplication, and pairings (EIP 196, 197). Due to these precompiles, BN254 is the most practical choice of a pairing friendly curve to use for verifying on-chain zkSNARKs using proof schemes such as Groth16 and PlonK.

While the number of bits of security of BN254 dropped from 128 to around 100 after new algorithms of Kim-Barbulescu, due to the Ethereum precompiles BN254 is still the most practical choice of a pairing friendly curve to use for on-chain zkSNARK verification using proof schemes such as Groth16 and PlonK.

I have found that information around BN254 is hard to find (due in part to the multiple names, see below), so the purpose of this document is to gather all information relevant to developers/researchers using this curve in practice in one place. This document is of course inspired by the existence of BLS12-381 For The Rest Of Us.

To add to the confusion around BN254, it is colloquially referred to by several different names such as:

  • BN128 (128 previously referred to the bits of security) or
  • alt_bn_128

(254 stands for the number of bits in the prime associated to the base field.)

Warning: This is NOT the BN254 referenced here: https://neuromancer.sk/std/bn/bn254

BN254 (alt_bn_128) is a different Barreto-Naehrig (BN) curve with 254-bit prime. The curve is defined by:

Y^2 = X^3 + 3
over the field F_p with
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

We will refer to this curve as BN254 for the rest of the article.

Barreto-Naehrig curves

A Barreto-Naehrig (BN) curve is an elliptic curve

E of the form
Y2=X3+b
over a prime field
Fp
where the prime
p
is given by
p=36x4+36x3+24x2+6x+1
for a parameter
x
.

The parameter

x also determines other constants attached to the curve
E
of interest:
r=36x4+36x3+18x2+6x+1,t=6x2+1
where
x
is chosen so that
r
is prime and
t
is the trace of Frobenius of the curve.

The embedding degree of a BN curve is always 12, meaning that 12 is the smallest integer

k such that
E(Fpk)[r]=E(Fp)[r]
.

BN curves are constructed (using the CM method) to always have CM discriminant

3 and
j
-invariant equal to
0
.

How to find
b
from parameter
x

Given the parameter

x, the coefficient
b
that makes the curve
y2=x3+b
have order
r
over
Fp
is computed using what is called the CM method (CM stands for complex multiplication). For an overview of the CM method and BN curves, see [Shirase, 3.1]. For BN curves, the
j
-invariant equals
0
, which greatly simplifies the CM method:

  • Iterate through
    b
    such that
    b+1
    is a quadratic residue mod
    p
  • For such
    b
    , the point
    G=(1,b+1)
    lies on
    E(Fp)
    .
  • Check whether
    rG=O
    , i.e., the point
    G
    has order
    r
    .
  • If
    rGO
    , iterate to next
    b
    .

Parameter for BN254

The parameter

x for BN254 (alt_bn128) is

x = 4965661367192848881

(source: libff). One can check that this gives the 254-bit prime

p given at the top of this doc.

For this particular

x, the curve order
r
is

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

which happens to also be a 254-bit prime. For BN254, r is the Baby Jubjub prime.

For BN254, b = 3. As mentioned in the previous section, if we try

b=1, then
b+1=2
is a quadratic residue mod
p
but
y2=x3+1
does not have order
r
. Thus we move on to
b=3
and
b+1=22
is a quadratic residue, and one can check that the point
(1,2)E(Fp)
indeed has order
r
.

In conclusion,

y2=x3+3 is a BN curve for the parameter x = 4965661367192848881.

Field extension towers

For the purposes of pairings, we need to choose a representation of the field extension

Fp12. The standard way to do this is to represent
Fp12
as a specific tower of field extensions of
Fp
:
Fp2=Fp[u]/(u2β)Fp6=Fp2[v]/(v3ξ)Fp12=Fp6[w]/(w2v)
where
β
is a quadratic non-residue in
Fp
and
ξ
is not a quadratic residue or a cubic residue in
Fp2
. The condition on
ξ
is equivalent to saying that the polynomial
X6ξ
is irreducible over
Fp2[X]
.

For BN254, we use

β=1 and
ξ=9+u
. So the explicit tower of field extensions used is
Fp2=Fp[u]/(u2+1)Fp6=Fp2[v]/(v3(9+u))Fp12=Fp6[w]/(w2v)
The most important equations are
u2=1
and
w6=9+u
.

We can also directly write

Fp12=Fp[w]/((w69)2+1)=Fp[w]/(w1218w6+82). This agrees with the Python implementation here.

Twists

Twists work in almost the same way as for BLS12-381:

Recall that

X6ξ is irreducible over
Fp2[X]
, where
ξ=9+u
. By [Section 3, Barreto-Naehrig], we can use
ξ
to define a D-type sextic twist of the BN254 curve
E:y2=x3+3
by
E:y2=x3+3/ξ=x3+3/(9+u).
(Footnote: BLS12-381 has an M-type sextic twist.) The curve
E
is defined over
Fp2
. This definition matches EIP 197. For concreteness,

E' : y^2 = x^3 + (19485874751759354771024239261021720505790618469301721065564631296452457478373 + 266929791119991161246907387137283842545076965332900288569378510910307636690 u)

We have

wFp12 is a root of
X6ξ
, so
Ψ(x,y)=(w2x,w3y)
defines a group homomorphism
Ψ:E(Fp2)E(Fp12)
. We have the following facts:

  • Ψ:E(Fp2)E(Fp12)
    is injective (but not surjective)
  • Ψ
    extends to an isomorphism
    Ψ~:E(Fp12)E(Fp12)
    .
  • There exists an order
    r
    subgroup
    G2
    of
    E(Fp2)
    that
    Ψ
    sends to a subgroup of
    E(Fp)[r]
    linearly independent of
    E(Fp)[r]
    .

It is useful to know that

E(Fp2) and
E(Fp)
have no points of order 2.

Frobenius morphism

Define the Frobenius morphism

ϕp:E(Fp)E(Fp) by
ϕp(x,y)=(xp,yp)
. This is well-defined since
E
is defined over
Fp
. The Frobenius morphism is an isogeny of degree
p
with characteristic polynomial
X2tX+p
. This means that
ϕp2[t]ϕp+[p]=[0]
on
E(Fp)
.

Since

E(Fp) are the Frobenius fixed points of
E(Fp)
, we get
G1:=E(Fp)[r]=E(Fp)[r]ker(ϕp[1]).
Let
Ψ(G2)
denote the image of
G2:=E(Fp2)[r]
under the twist map
Ψ
. Then we have an alternate description of
Ψ(G2)
as
Ψ(G2)=E(Fp)[r]ker(ϕp[p]).
Note that there is no contradiction with the fact that "trace" of
ϕp
equals
[t]
because
p+1t(modr)
.

Optimal Ate pairing

For BN curves, the optimal Ate pairing

e:G1×G2GT, with
GT=μrFp12×
the
r
th roots of unity, is defined by
e(P,Q)=(f6x+2,Q(P)l[6x+2]Q,ϕp(Q)(P)l[6x+2]Q+ϕp(Q),ϕp2(Q)(P))p121r
where

  • fi,Q
    for
    iN,QG2
    is a
    Fp12
    rational function on
    E
    with
    i
    zeros at
    Ψ(Q)
    , a pole at
    [i]Ψ(Q)
    , and
    i1
    poles at the origin
    O
    .
  • fi,Q
    is computed recursively using Miller's algorithm
    fi+j,Q=fi,Qfj,Ql[i]Ψ(Q),[j]Ψ(Q)v[i+j]Ψ(Q).
    Here
    lP1,P2
    denotes the equation for a line passing through
    P1,P2
    , while
    vP
    denotes the equation for a vertical line passing through
    P
    .
    • An optimization due to the final exponentiation is that the final value of
      e(P,Q)
      remains unchanged if we omit the division by
      v[i+j]Ψ(Q)
      in the equation above.
  • x
    is the parameter of the curve
  • ϕp(x,y)=(xp,yp)
    is Frobenius operator

Subgroup checks

Subgroup check for
G1

Given a pair

(x,y)Fp2, it is easy to check if
(x,y)
is a point on the curve
E(Fp)
. We need to further check whether it belongs to the subgroup
G1=E(Fp)[r]
. Fortunately, for BN curves we have
G1=E(Fp)
so no further check is required.

One way to see this is that the Weil conjectures [Theorem 2.3.1, Silverman] imply

#E(Fp)=p+1t. One can check that for BN curves generated by a parameter
x
, we have
p(x)+1t(x)=r(x)
using the formulas above. We conclude that
#E(Fp)=r
.

The Weil conjectures also tell us that if

α,βC are the roots of the characteristic polynomial
X2tX+p
of the Frobenius morphism, then
α,β
have absolute values
p
(so
β=α
) and
(1)#E(Fpk)=pk+1αkαk.

Subgroup check for
G2

Given a pair

P=(x,y)Fp22, it is easy to check if
P
is a point on the twisted curve
E(Fp2).
However we need to further check if
P
lies in the subgroup
G2=E(Fp2)[r]
. Let
#E(Fp2)=c2r
. Unfortunately in our case
c21
. This number
c2
is known as the
G2
cofactor.

G2
order

We can compute

#E(Fp2) from [Proposition 2, HSV] with some modifications:

The CM method for constructing curves produces integers

D,V such that
DV2=4pt2
where
D
is the discriminant and the resulting curve
E
has
End(E)Q(D)
. For BN curves,
D=3
so
End(E)
is an order in
Q(3)
. Since
E
is a sextic twist of
E
, we know that the sixth roots of unity
μ6Aut(E)
. The only order for which this is true is
Z[ω]
with
ω=1+i32
. We conclude that any BN curve has complex multiplication by
End(E)=Z[ω]
.

The roots of

X2tX+p equals
t±t24p2=t±V32
by quadratic formula, so we can take
α=t+V32
. Now the twist
E
is defined over
Fp2
so we can consider the Frobenius map
ϕp2
on
E(Fp)
. Let
α
be one of the roots of the characteristic polynomial of
ϕp2
. Since
E
and
E
are isomorphic over
Fp12
we have
#E(Fp12)=p12+1α12α12=p12+1α6α6=#E(Fp12).
We deduce that up to conjugation,
α=ζα2
for some
ζμ6
. Moreover since
Fp12
is the smallest field extension for which the above is true,
ζ
must be a primitive sixth root of unity
ζ=1±i32
. Some computation gives
α+α=t23tV2p
where
V=(4pt2)/3
. Therefore
#E(Fp2)=p2+p+1t23tV2

where there are two possibilities on the right hand side, corresponding to the two possible sextic twists (type D vs. type M) of
E
.

For BN curves,

V=6x2+4+1 where
x
is the parameter. Plugging in formulas for
p
and
t
in terms of the parameter
x
, we find that the correct sign to make
#E(Fp2)
divisible by
r=pt+1
is
#E(Fp2)=p2+p+1t2+3tV2
, which simplifies to
#E(Fp2)=(pt+1)(p+t1)c2=p+t1.
For the specific case of BN254, we get:

#E'(F_{p^2}) = 479095176016622842441988045216678740799252316531100822436447802254070093686356349204969212544220033486413271283566945264650845755880805213916963058350733
c_2 = 21888242871839275222246405745257275088844257914179612981679871602714643921549

G2
membership check using efficient endomorphism

An easy, but slow, way to check if

PE(Fp2)[r] is to see if
[r]P=O
. This is undesirable since
r
has 254 bits in the case of BN254.

There are various methods to speed up the

G2 membership check for different curves by finding an efficiently computable endomorphism. For BN curves we can use a new method of [Section 4.3, HGP] adapted from Scott. This relies on the untwist-Frobenius-twist endomorphism
ψ:E(Fp2)E(Fp2)
introduced by Galbraith-Scott. It is defined by
ψ=Ψ1ϕpΨ
where
Ψ:E(Fp2)E(Fp12)
is the twist map and
ϕp(x,y)=(xp,yp)
is the Frobenius morphism. Note that
Ψ
is only injective but one can directly check that
ϕpΨ
lies in the image of
Ψ
. For a D-type sextic twist of a BN curve, we have
ψ(x,y)=(ξ(p1)/3xp,ξ(p1)/2yp)
(recall that
ξ=9+u
for BN254).

By [Proposition 3, HGP], we have

PE(Fp2) belongs to G2 if and only if ψ(P)=[6x2]P where
x
denotes the parameter of the curve
E
. (There is a small typo in the statement of loc cit. but the argument is correct.) We provide a proof for convenience:

We have

r=pt+1 and given
PE(Fp2)
we need to check if
[r]P=O
. This is equivalent to
[p]P=[t1]P
. On the other hand,
ψ
satisfies the characteristic polynomial of the Frobenius operator, which means that
ψ2[t]ψ+[p]=0
. Thus
[p]P=[t1]P
is equivalent to
ψ2(P)[t]ψ(P)+[t1]P=O
.

Write

λ=t1=6x2. Then the above factors as
(ψ[1])(ψ[λ])(P)=O
. Clearly
ψ(P)=[λ](P)
implies the equation holds. Conversely, suppose
[r]P=O
so the equation holds. Let
Q=(ψ[λ])P
. Then
ψ(Q)=Q
implies that the twist
Ψ(Q)E(Fp)=E(Fp)[r]
. The intersection
Ψ(E(Fp2))E(Fp)[r]={O}
, so
Q=O
. In other words,
ψ(P)=[λ]P
.

Resources