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.)
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 of the form over a prime field where the prime is given by for a parameter .
The parameter also determines other constants attached to the curve of interest: where is chosen so that is prime and 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 such that .
BN curves are constructed (using the CM method) to always have CM discriminant and -invariant equal to .
How to find from parameter
Given the parameter , the coefficient that makes the curve have order over 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 -invariant equals , which greatly simplifies the CM method:
Iterate through such that is a quadratic residue mod
For such , the point lies on .
Check whether , i.e., the point has order .
If , iterate to next .
Parameter for BN254
The parameter for BN254 (alt_bn128) is
x = 4965661367192848881
(source: libff). One can check that this gives the 254-bit prime given at the top of this doc.
For this particular , the curve order 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 , then is a quadratic residue mod but does not have order . Thus we move on to and is a quadratic residue, and one can check that the point indeed has order .
In conclusion, 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 . The standard way to do this is to represent as a specific tower of field extensions of : where is a quadratic non-residue in and is not a quadratic residue or a cubic residue in . The condition on is equivalent to saying that the polynomial is irreducible over .
For BN254, we use and . So the explicit tower of field extensions used is The most important equations are and .
We can also directly write This agrees with the Python implementation here.
Twists
Twists work in almost the same way as for BLS12-381:
Recall that is irreducible over , where . By [Section 3, Barreto-Naehrig], we can use to define a D-typesextic twist of the BN254 curve by (Footnote: BLS12-381 has an M-type sextic twist.) The curve is defined over . This definition matches EIP 197. For concreteness,
E' : y^2 = x^3 + (19485874751759354771024239261021720505790618469301721065564631296452457478373 + 266929791119991161246907387137283842545076965332900288569378510910307636690 u)
We have is a root of , so defines a group homomorphism . We have the following facts:
is injective (but not surjective)
extends to an isomorphism .
There exists an order subgroup of that sends to a subgroup of linearly independent of .
It is useful to know that and have no points of order 2.
Frobenius morphism
Define the Frobenius morphism by . This is well-defined since is defined over . The Frobenius morphism is an isogeny of degree with characteristic polynomial . This means that on .
Since are the Frobenius fixed points of , we get Let denote the image of under the twist map . Then we have an alternate description of as Note that there is no contradiction with the fact that "trace" of equals because .
Optimal Ate pairing
For BN curves, the optimal Ate pairing, with the th roots of unity, is defined by where
for is a rational function on with zeros at , a pole at , and poles at the origin .
is computed recursively using Miller's algorithm Here denotes the equation for a line passing through , while denotes the equation for a vertical line passing through .
An optimization due to the final exponentiation is that the final value of remains unchanged if we omit the division by in the equation above.
is the parameter of the curve
is Frobenius operator
Subgroup checks
Subgroup check for
Given a pair , it is easy to check if is a point on the curve . We need to further check whether it belongs to the subgroup . Fortunately, for BN curves we have so no further check is required.
One way to see this is that the Weil conjectures [Theorem 2.3.1, Silverman] imply One can check that for BN curves generated by a parameter , we have using the formulas above. We conclude that .
The Weil conjectures also tell us that if are the roots of the characteristic polynomial of the Frobenius morphism, then have absolute values (so ) and
Subgroup check for
Given a pair , it is easy to check if is a point on the twisted curve However we need to further check if lies in the subgroup . Let . Unfortunately in our case . This number is known as the cofactor.
order
We can compute from [Proposition 2, HSV] with some modifications:
The CM method for constructing curves produces integers such that where is the discriminant and the resulting curve has . For BN curves, so is an order in . Since is a sextic twist of , we know that the sixth roots of unity . The only order for which this is true is with . We conclude that any BN curve has complex multiplication by .
The roots of equals by quadratic formula, so we can take . Now the twist is defined over so we can consider the Frobenius map on . Let be one of the roots of the characteristic polynomial of . Since and are isomorphic over we have We deduce that up to conjugation, for some . Moreover since is the smallest field extension for which the above is true, must be a primitive sixth root of unity . Some computation gives where . Therefore where there are two possibilities on the right hand side, corresponding to the two possible sextic twists (type D vs. type M) of .
For BN curves, where is the parameter. Plugging in formulas for and in terms of the parameter , we find that the correct sign to make divisible by is , which simplifies to For the specific case of BN254, we get:
An easy, but slow, way to check if is to see if . This is undesirable since has 254 bits in the case of BN254.
There are various methods to speed up the 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 introduced by Galbraith-Scott. It is defined by where is the twist map and is the Frobenius morphism. Note that is only injective but one can directly check that lies in the image of . For a D-type sextic twist of a BN curve, we have (recall that for BN254).
By [Proposition 3, HGP], we have where denotes the parameter of the curve . (There is a small typo in the statement of loc cit. but the argument is correct.) We provide a proof for convenience:
We have and given we need to check if . This is equivalent to . On the other hand, satisfies the characteristic polynomial of the Frobenius operator, which means that . Thus is equivalent to .
Write . Then the above factors as . Clearly implies the equation holds. Conversely, suppose so the equation holds. Let . Then implies that the twist . The intersection , so . In other words, .