# BN254 For The Rest Of Us

The [pairing friendly](https://tools.ietf.org/id/draft-yonezawa-pairing-friendly-curves-02.html) elliptic curve BN254 was previously used by [ZCash](https://zips.z.cash/protocol/protocol.pdf) (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](https://eips.ethereum.org/EIPS/eip-196), [197](https://eips.ethereum.org/EIPS/eip-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](https://github.com/zcash/zcash/issues/714) after new algorithms of [Kim-Barbulescu](https://eprint.iacr.org/2015/1027.pdf), 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](https://hackmd.io/@benjaminion/bls12-381).

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](https://www.cryptojedi.org/papers/pfcpo.pdf) (BN) curve is an elliptic curve $E$ of the form
$$
Y^2 = X^3 + b
$$ over a prime field $\mathbb F_p$ where the prime $p$ is given by
$$
p = 36x^4 + 36x^3 + 24x^2 + 6x + 1
$$ for a parameter $x$.

The parameter $x$ also determines other constants attached to the curve $E$ of interest:
$$\begin{align}
r &= 36x^4 + 36x^3 + 18x^2 + 6x + 1, \\
t &= 6 x^2 + 1
\end{align}$$ 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(\mathbb F_{p^k})[r] = E(\overline{\mathbb F}_p)[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 $y^2 = x^3 + b$ have order $r$ over $\mathbb F_p$ 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](https://eprint.iacr.org/2010/134.pdf), 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, \sqrt{b+1})$ lies on $E(\mathbb F_p)$.
* Check whether $r G = O$, i.e., the point $G$ has order $r$.
* If $r G \ne O$, iterate to next $b$.

### Parameter for BN254
The parameter $x$ for BN254 (alt_bn128) is

x = 4965661367192848881

(source: [libff](https://github.com/scipr-lab/libff/blob/develop/libff/algebra/curves/alt_bn128/alt_bn128.sage)). 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 $y^2 = x^3 + 1$ does not have order $r$. Thus we move on to $b=3$ and $b+1 = 2^2$ is a quadratic residue, and one can check that the point $(1, 2) \in E(\mathbb F_p)$ indeed has order $r$.

In conclusion, $y^2 = x^3+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 $\mathbb F_{p^{12}}$. The standard way to do this is to represent $\mathbb F_{p^{12}}$ as a specific tower of field extensions of $\mathbb F_p$:
$$\begin{align}
\mathbb F_{p^2} &= \mathbb F_p[u] / (u^2 - \beta) \\
\mathbb F_{p^6} &= \mathbb F_{p^2}[v] / (v^3 - \xi) \\
\mathbb F_{p^{12}} &= \mathbb F_{p^6}[w] / (w^2 - v)
\end{align}$$ where $\beta$ is a quadratic non-residue in $\mathbb F_p$ and $\xi$ is not a quadratic residue or a cubic residue in $\mathbb F_{p^2}$. The condition on $\xi$ is equivalent to saying that the polynomial $X^6 - \xi$ is irreducible over $\mathbb F_{p^2}[X]$.

For BN254, we use $\beta = -1$ and $\xi = 9 + u$. So the explicit tower of field extensions used is
$$\begin{align}
\mathbb F_{p^2} &= \mathbb F_p[u] / (u^2 + 1) \\
\mathbb F_{p^6} &= \mathbb F_{p^2}[v] / (v^3 - (9+u)) \\
\mathbb F_{p^{12}} &= \mathbb F_{p^6}[w] / (w^2 - v)
\end{align}$$ The most important equations are $u^2 = -1$ and $w^6 = 9+u$.

We can also directly write
$$
\mathbb F_{p^{12}} = \mathbb F_p[w] / ((w^6 - 9)^2 + 1) = \mathbb F_p[w] / (w^{12} - 18 w^6 + 82).
$$ This agrees with the Python implementation [here](https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py).

## Twists

Twists work in almost the same way as for [BLS12-381](https://hackmd.io/@benjaminion/bls12-381#Twists):

Recall that $X^6 - \xi$ is irreducible over $\mathbb F_{p^2}[X]$, where $\xi = 9 + u$. By [Section 3, [Barreto-Naehrig](https://eprint.iacr.org/2005/133.pdf)], we can use $\xi$ to define a [D-type](https://datatracker.ietf.org/doc/html/draft-kasamatsu-bncurves-02#section-4.1) **sextic twist** of the BN254 curve $E : y^2 = x^3 + 3$ by
$$
E' : y'^2 = x'^3 + 3 / \xi = x'^3 + 3 / (9 + u).
$$ (Footnote: BLS12-381 has an M-type sextic twist.) The curve $E'$ is defined over $\mathbb F_{p^2}$. This definition matches [EIP 197](https://eips.ethereum.org/EIPS/eip-197). For concreteness,

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

We have $w \in \mathbb F_{p^{12}}$ is a root of $X^6 - \xi$, so
$$
\Psi(x',y') = (w^2 x', w^3 y')
$$ defines a group homomorphism $\Psi : E'(\mathbb F_{p^2}) \to E(\mathbb F_{p^{12}})$. We have the following facts:
* $\Psi : E'(\mathbb F_{p^2}) \to E(\mathbb F_{p^{12}})$ is injective (but not surjective)
* $\Psi$ extends to an isomorphism $\tilde\Psi : E'(\mathbb F_{p^{12}}) \cong E(\mathbb F_{p^{12}})$.
* There exists an order $r$ subgroup $\mathbb G_2$ of $E'(\mathbb F_{p^2})$ that $\Psi$ sends to a subgroup of $E(\overline{\mathbb F}_p)[r]$ linearly independent of $E(\mathbb F_p)[r]$.

It is useful to know that $E'(\mathbb F_{p^2})$ and $E(\mathbb F_p)$ have no points of order 2.

### Frobenius morphism
Define the Frobenius morphism $\phi_p : E(\overline{\mathbb F}_p) \to E(\overline{\mathbb F}_p)$ by $\phi_p(x,y) = (x^p, y^p)$. This is well-defined since $E$ is defined over $\mathbb F_p$. The Frobenius morphism is an isogeny of degree $p$ with characteristic polynomial $X^2 - t X + p$. This means that $\phi_p^2 - [t] \phi_p + [p] = [0]$ on $E(\overline{\mathbb F}_p)$.

Since $E(\mathbb F_p)$ are the Frobenius fixed points of $E(\overline{\mathbb F}_p)$, we get
$$
\mathbb G_1 := E(\mathbb F_p)[r] = E(\overline{\mathbb F_p})[r] \cap \ker(\phi_p - [1]).
$$ Let $\Psi(\mathbb G_2)$ denote the image of $\mathbb G_2 := E'(\mathbb F_{p^2})[r]$ under the twist map $\Psi$. Then we have an alternate description of $\Psi(\mathbb G_2)$ as
$$
\Psi(\mathbb G_2) = E(\overline{\mathbb F}_p)[r] \cap \ker(\phi_p - [p]).
$$ Note that there is no contradiction with the fact that "trace" of $\phi_p$ equals $[t]$ because $p + 1 \equiv t \pmod{r}$.

## Optimal Ate pairing

For BN curves, the [optimal Ate pairing](https://datatracker.ietf.org/doc/html/draft-yonezawa-pairing-friendly-curves-02#appendix-A) $e : \mathbb G_1 \times \mathbb G_2 \to \mathbb G_T$, with $\mathbb G_T = \mu_r \subset \mathbb F_{p^{12}}^\times$ the $r$th roots of unity, is defined by
$$
e(P,Q) = (f_{6x+2, Q}(P) \cdot l_{[6x+2]Q, \phi_p(Q)}(P) \cdot l_{[6x+2]Q + \phi_p(Q), -\phi_p^2(Q)}(P))^{\frac{p^{12}-1}r}
$$ where
- $f_{i,Q}$ for $i \in \mathbb N, Q\in \mathbb G_2$ is a $\mathbb F_{p^{12}}$ rational function on $E$ with $i$ zeros at $\Psi(Q)$, a pole at $[i]\Psi(Q)$, and $i-1$ poles at the origin $O$.
- $f_{i,Q}$ is computed recursively using Miller's algorithm
$$
f_{i + j,Q} = f_{i,Q} \cdot f_{j,Q} \cdot \frac{l_{[i]\Psi(Q), [j]\Psi(Q)}}{v_{[i+j]\Psi(Q)}}.$$ Here $l_{P_1, P_2}$ denotes the equation for a line passing through $P_1, P_2$, while $v_{P}$ 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]\Psi(Q)}$ in the equation above.
- $x$ is the parameter of the curve
- $\phi_p(x,y) = (x^p, y^p)$ is Frobenius operator

## Subgroup checks
### Subgroup check for $\mathbb G_1$
Given a pair $(x, y) \in \mathbb F_p^2$, it is easy to check if $(x,y)$ is a point on the curve $E(\mathbb F_p)$. We need to further check whether it belongs to the subgroup $\mathbb G_1 = E(\mathbb F_p)[r]$. Fortunately, for BN curves we have $\mathbb G_1 = E(\mathbb F_p)$ so no further check is required.

One way to see this is that the Weil conjectures [Theorem 2.3.1, [Silverman](https://link.springer.com/book/10.1007/978-0-387-09494-6)] imply
$$
\# E(\mathbb F_p) = p + 1 - t.
$$ One can check that for BN curves generated by a parameter $x$, we have $p(x) + 1 - t(x) = r(x)$ using the formulas [above](#Barreto-Naehrig-curves). We conclude that $\#E(\mathbb F_p) = r$.

The Weil conjectures also tell us that if $\alpha,\beta \in \mathbb C$ are the roots of the characteristic polynomial $X^2 - t X + p$ of the [Frobenius morphism](#Frobenius-morphism), then $\alpha,\beta$ have absolute values $\sqrt p$ (so $\beta = \overline \alpha$) and
$$\tag{1}
\# E(\mathbb F_{p^k}) = p^k + 1 - \alpha^k - \overline\alpha{}^k.
$$

### Subgroup check for $\mathbb G_2$
Given a pair $P = (x,y) \in \mathbb F_{p^2}^2$, it is easy to check if $P$ is a point on the twisted curve $E'(\mathbb F_{p^2}).$ However we need to further check if $P$ lies in the subgroup $\mathbb G_2 = E'(\mathbb F_{p^2})[r]$. Let $\# E'(\mathbb F_{p^2}) = c_2 r$. Unfortunately in our case $c_2 \ne 1$. This number $c_2$ is known as the $\mathbb G_2$ **cofactor**.

#### $\mathbb G_2$ order
We can compute $\# E'(\mathbb F_{p^2})$ from [Proposition 2, [HSV](https://eprint.iacr.org/2006/110.pdf)] *with some modifications*:
:::info
The CM method for constructing curves produces integers $D, V$ such that
$$
D V^2 = 4 p - t^2
$$ where $-D$ is the discriminant and the resulting curve $E$ has $\operatorname{End}(E) \subset \mathbb Q(\sqrt{-D})$. For BN curves, $D = 3$ so $\operatorname{End}(E)$ is an order in $\mathbb Q(\sqrt{-3})$. Since $E'$ is a sextic twist of $E$, we know that the sixth roots of unity $\mu_6 \subset \operatorname{Aut}(E)$. The only order for which this is true is $\mathbb Z[\omega]$ with $\omega = \frac{-1 + i \sqrt{3}}2$. We conclude that any BN curve has complex multiplication by $\operatorname{End}(E) = \mathbb Z[\omega]$.

The roots of $X^2 - t X + p$ equals $\frac{t \pm \sqrt{t^2 - 4p}}2 = \frac{t \pm V\sqrt{-3}}2$ by quadratic formula, so we can take $\alpha = \frac{t + V \sqrt{-3}}2$. Now the twist $E'$ is defined over $\mathbb F_{p^2}$ so we can consider the Frobenius map $\phi'_{p^2}$ on $E'(\overline{\mathbb F}_p)$. Let $\alpha'$ be one of the roots of the characteristic polynomial of $\phi'_{p^2}$. Since $E$ and $E'$ are isomorphic over $\mathbb F_{p^{12}}$ we have
$$
\# E(\mathbb F_{p^{12}}) = p^{12} + 1 - \alpha^{12} - \overline \alpha{}^{12} = p^{12} + 1 - \alpha'^6 - \overline{\alpha}{}'^6 = \# E'(\mathbb F_{p^{12}}).
$$ We deduce that up to conjugation, $\alpha' = \zeta \alpha^2$ for some $\zeta \in \mu_6$. Moreover since $\mathbb F_{p^{12}}$ is the smallest field extension for which the above is true, $\zeta$ must be a primitive sixth root of unity $\zeta = \frac{1 \pm i\sqrt 3}2$. Some computation gives $\alpha' + \overline{\alpha}{}' = \frac{t^2 \mp 3 t V}2 - p$ where $V = \sqrt{(4p-t^2)/3}$. Therefore
$$
\# E'(\mathbb F_{p^2}) = p^2 + p + 1 - \frac{t^2 \mp 3 t V}2
$$
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 = 6x^2 + 4 + 1$ where $x$ is the parameter. Plugging in [formulas](#Barreto-Naehrig-curves) for $p$ and $t$ in terms of the parameter $x$, we find that the correct sign to make $\# E'(\mathbb F_{p^2})$ divisible by $r = p - t +1$ is $\# E'(F_{p^2}) = p^2 + p + 1 - \frac{t^2 + 3 t V}2$, which simplifies to
$$\begin{align}
\# E'(\mathbb F_{p^2}) &= (p-t+1)(p+t-1) \\
c_2 &= p + t - 1.
\end{align}$$ For the specific case of BN254, we get:

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

#### $\mathbb G_2$ membership check using efficient endomorphism
An easy, but slow, way to check if $P \in E'(\mathbb F_{p^2})[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 $\mathbb G_2$ 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](https://eprint.iacr.org/2022/352.pdf)] adapted from [Scott](https://eprint.iacr.org/2021/1130.pdf). This relies on the untwist-Frobenius-twist endomorphism $\psi : E'(\mathbb F_{p^2}) \to E'(\mathbb F_{p^2})$ introduced by [Galbraith-Scott](https://eprint.iacr.org/2008/117.pdf). It is defined by
$$
\psi = \Psi^{-1} \circ \phi_p \circ \Psi
$$ where $\Psi : E'(\mathbb F_{p^2}) \to E(\mathbb F_{p^{12}})$ is the twist map and $\phi_p(x,y) = (x^p, y^p)$ is the Frobenius morphism. Note that $\Psi$ is only injective but one can directly check that $\phi_p \circ \Psi$ lies in the image of $\Psi$. For a D-type sextic twist of a BN curve, we have
$$
\psi(x',y') = (\xi^{(p-1)/3} x'^p, \xi^{(p-1)/2} y'^p)
$$ (recall that $\xi = 9 + u$ for BN254).

By [Proposition 3, [HGP](https://eprint.iacr.org/2022/352.pdf)], we have
$$
P \in E'(\mathbb F_{p^2}) \text{ belongs to }\mathbb G_2\text{ if and only if } \psi(P) = [6x^2]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:
:::info
We have $r = p - t +1$ and given $P \in E'(\mathbb F_{p^2})$ we need to check if $[r]P = O$. This is equivalent to $[p]P = [t - 1]P$. On the other hand, $\psi$ satisfies the characteristic polynomial of the Frobenius operator, which means that $\psi^2 - [t]\psi + [p] = 0$. Thus $[p]P = [t-1]P$ is equivalent to $\psi^2(P) - [t]\psi(P) + [t-1]P = O$.

Write $\lambda = t-1 = 6x^2$. Then the above factors as $(\psi - [1])(\psi - [\lambda])(P) = O$. Clearly $\psi(P) = [\lambda](P)$ implies the equation holds. Conversely, suppose $[r]P=O$ so the equation holds. Let $Q = (\psi - [\lambda])P$. Then $\psi(Q) = Q$ implies that the twist $\Psi(Q) \in E(\mathbb F_p) = E(\mathbb F_p)[r]$. The intersection $\Psi(E'(\mathbb F_{p^2})) \cap E(\mathbb F_p)[r] = \{O\}$, so $Q = O$. In other words, $\psi(P) = [\lambda]P$.
:::

## Resources
* Barreto-Naehrig, Pairing-Friendly Elliptic Curves of Prime Order. https://www.cryptojedi.org/papers/pfcpo.pdf (more up to date than https://eprint.iacr.org/2005/133.pdf)
* Beuchat et al, High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves. https://eprint.iacr.org/2010/354.pdf
* Silverman, The Arithmetic of Elliptic Curves. https://link.springer.com/book/10.1007/978-0-387-09494-6