## BN254 Specifics The curve BN254 is specified by the following parameters. ##### Curve generator $z = 2^{62} - 2^{54} + 2^{44}$ ##### Prime $$ p = 36z^4 + 36z^3 + 24z^2 + 6z + 1$$ $$=21888242871839275222246405745257275088696311157297823662689037894645226208583$$ ##### Curve equation $$y^2 = x^3 + 3$$ ##### Order $$r = 36z^4 + 36z^3 + 18z^2 + 6z + 1$$ $$=21888242871839275222246405745257275088548364400416034343698204186575808495617$$ ##### Embedding degree $k=12$ ### Security In theory, the curve has $L=128$ bit security, but [it was shown](https://eprint.iacr.org/2015/1027.pdf) to now be closer to ~100. The curve also has a prime base field of 254-bits, which is huge by our conception of what a large number is, but there are curves with bigger primes (and thus higher security in a real way). Also, the curve as we show below has a cofactor decomposition that require subgroup checks to avoid invalid curve or small subgroup attacks. And as always, operations should run constant time to avoid side channel attacks. --- ### Torsions Let $G$ be a group. The $r$-torsion of the group is defined by $\{x\in G\,|\, rX=\mathcal{O}\}$, where $\mathcal{O}$ is the identity element (we use the notation $\mathcal{O}$ to be consistent with the notation that an $r$-torsion on an elliptic curve group is the point at infinity $\mathcal{O}$). A great example is an analog clock, where the 12-torsion of the clock group is every hour on the clock, since adding an hour 12 times to any hour brings you to the same time on the clock. --- ### $\mathbb{G}_1$ In order to use this curve for cryptography, we need two different versions of the curve, which are then manipulated / used by the pairings discussed earlier. The first version of the curve is the naive expectation you have, namely the pairs of points $\{(x,y)\in\mathbb{F}_p\times\mathbb{F}_p\,|\, y^2=x^3+3\}$. This is almost right what we need! We add one more condition though that the group we want to deal with is actually the smallest prime cyclic subgroup of order $r$. Therefore, the group we want to deal with is actually the $r$-torsion of this elliptic curve group: > $\mathbb{G}_1\triangleq E(\mathbb{F}_p)[r]$ is the only subgroup of the $r$-torsion of $E$ on $\mathbb{F}_p$ of order $r$ #### Membership check for $\mathbb{G}_1$ In our scheme, to hash a message to $E$, we use `hash_to_field` and `field_to_curve`, and then multiply the mapped curve point by the generator of the curve to create a point in $\mathbb{G}_1$. Fortunately, by [Theorem 2.3.1 of Silverman](https://link.springer.com/book/10.1007/978-0-387-09494-6), we have $$ |E(\mathbb{F}_p)|=p+1-t$$ and for BN curves generated by a value $z=2^{62}-2^{54}+2^{44}$, we have $p(z)+1-t(z)=r(z)$, implying that $|E(\mathbb{F}_p)|=r\implies \mathbb{G}_1 = E(\mathbb{F}_p)[r]=E(\mathbb{F}_p)$! In this way, since $r$-torsions give us some notion of structure, this means that the "prime factorization" of the curve is simply the curve itself, so its smallest possible prime order subgroup is just the group, no extra structure to be found. We therefore only need to check if a pair $(x,y)\in\mathbb{F}_r\times\mathbb{F}_r$ is on the curve $E(\mathbb{F}_p)$ for membership in $\mathbb{G}_1$. --- ### $\mathbb{G}_2$ We now need a second version of the curve $\mathbb{G}_2$ such that $|\mathbb{G}_1|=|\mathbb{G}_2|=r$, which requires us to now go to $\mathbb{F}_{p^{12}}$. Why? Well, we're technically dealing with not the entire EC group, but the cyclic subgroup $\langle X\rangle$ generated by the point $X$ which is the base of our DL problem (ie $X^d\equiv Y\implies [d]X = Y$). The embedding process (aka taking points from $\mathbb{G}_1$ and map them into $\mathbb{F}_{p^m}$) is done by the pairing $e(x, y)$ which, for a point $x$ in the n-order subgroup of the curve, will be an n-th root of unity for some $y$, required by the condition that $e(ax, by)=e(x,y)^{ab}$. In order for this to hold, there must be enough roots of unity in the field, which happens when $p^k\equiv 1\mod \ell$, where $\ell$ is the order of the cyclic subgroup. For us, this is $k=12$, so the embedding must go from the curve to $\mathbb{F}_{p^{12}}$. We need to deal with this massive extension for the pairing operation because the curve defined over this extension is the smallest extension which contains subgroups of order $r$ that we can use for pairings, one subgroup in which contains only points with zero trace, which we choose to be $\mathbb{G}_2$. So we have $\mathbb{G}_1\subset E(\mathbb{F}_p)$ with $|\mathbb{G}_1|=r$, and $\mathbb{G}_2\subset E(\mathbb{F}_{p^{12}})$ with $|\mathbb{G}_2|=r$ which we want to use for our pairing. Recall that given an irreducible polynomial $N \in \mathbb{F}_p[x]$ of degree $m=12$, the elements of this extension are those given by $\{a_{m-1}x^{m-1}+\cdots+a_1x+a_0 \,|\, a_i\in \mathbb{F}_p\}$ Multiplication is defined by multiplying the two polynomials, then using polynomial long division on the polynomial $N$ to get the remainder, and inverses are defined via the extended euclidean algorithm. You can "tower" extensions if the order of one divides the order of the other, so if $m_j | m_{j+1}$, then $\mathbb{F}_p \subset \mathbb{F}_{p^{m_1}}\subset\cdots\subset \mathbb{F}_{p^{m_k}}$. The [standard tower](https://eprint.iacr.org/2010/354.pdf) for BN254 is given by the following (see [here](https://github.com/ethereum/py_pairing/blob/master/py_ecc/bn128/bn128_field_elements.py) or [here](https://github.com/arkworks-rs/algebra/tree/master/curves/bn254/src/fields)): $$\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)$$ where $\beta$ is a quadratic nonresidue in $\mathbb{F}_p$ and $\xi$ neither a quadratic or cubic residue in $\mathbb{F_{p^2}}$, which amounts to saying that $X^6-\xi$ is irreducible in the ring $\mathbb{F}_{p^2}[X]$. Here, $\beta=-1,\xi=9+u$, which brings about $u^2=-1, w^2=v, v^3=9+u$, and therefore: $$\mathbb{F}_{p^{12}} = \mathbb{F}_{p^2}[w]/(w^6-(9+u))$$ This brings about the following nice points - any element in this extension can be written as $g+hw$ with $g,h\in\mathbb{F}_{p^6}$, which means that the $p^6$-th power of any element in the extension $x^{p^6}=g-hw$ is free to compute - Likewise writing each $g,h$ in terms of coefficients from $\mathbb{F}_{p^2}$ lets you compute the $p$-th, $p^2$-th, and $p^3$-th powers easily as well Dealing with elements directly in $\mathbb{F}_{p^{12}}$ is very unruly and inefficient, but it is possible to define a coordinate transformation such that such that the curve in the 12-th order extension is mapped to a lower degree field. For BN254, we define a sextic twist (aka drops the degree of extension by 6) such that the twisted curve is defined on $\mathbb{F}_{p^2}$ instead of $\mathbb{F}_{p^{12}}$. Defining $u^6=(1+i)^{-1}$, the twist performs $(x,y)\to(x/u^2,y/u^3)$ to produce our new curve $E^\prime(\mathbb{F}_{p^2})$: $$ y'^2 = x'^3 + \frac{3}{9+i}$$ Very nice. Note though that points in $E(\mathbb{F}_p)$ are pairs of ints, while points on the twist are pairs of complex ints, so points in $\mathbb{G}_2$ take more storage despite them being also valid as the domain for keys and signatures. See [this](https://eips.ethereum.org/EIPS/eip-197) for industry definition of this twist. Since $X^6-\xi$ is irreducible, with roots $w\in\mathbb{F}_{p^{12}}$, we therefore have a homomorphism $$\Psi:E^\prime(\mathbb{F}_{p^2})\to E(\mathbb{F}_{p^{12}})\,;\,(x',y') = (w^2x', w^3y')$$ which is injective, but not surjective, and defines the twist mapping! Recalling that the $r$-torsion points of a curve are all the points $X$ such that $rX=\mathcal{O}$, with $\mathcal{O}$ the point at infinity, ie these are all points of order dividing r, we finally define - $\mathbb{G}_2\triangleq E^\prime(\mathbb{F}_{p^2})[r]$ is the only subgroup of the $r$-torsion of $E^\prime$ on $\mathbb{F}_{p^2}$ of order $r$ ### membership check in $\mathbb{G}_2$ First, recall that there is a mapping $\phi_p:E(\overline{\mathbb{F}}_p)\to E(\overline{\mathbb{F}}_p); (x,y)\to(x^p,y^p)$ called the Frobenius morphism. It can [can be shown](https://link.springer.com/book/10.1007/978-0-387-09494-6) that the set of points fixed by $\phi$ are *exactly* the finite group $E(\mathbb{F}_p)$, so application of this mapping to the curve defined on the base field will leave things structurally unchanged. This mapping will crop back up later in our definition of optimal ate pairing. Now, actually checking membership is a bit trickier. You can check easily if the point $(x,y)\in\mathbb{F}_{p^2}\times\mathbb{F}_{p^2}$ lies on $E^\prime(\mathbb{F}_{p^2})$, but unfortunately the order of the twist curve is not given by the order of the $r$-torsion, ie $|E^\prime(\mathbb{F}_{p^2})|=c_2r$, where $c_2$ is the $\mathbb{G}_2$ cofactor. [You can show](https://hackmd.io/@jpw/bn254#mathbb-G_2-order) that $c_2=p+t-1$. Thinking about $r$-torsions as structure again, it makes sense that this is the case even just from the consideration of the total number of elements in the preimage of $\mathbb{G}_2$ ($\mathbb{F}_{p^2}\times\mathbb{F}_{p^2}$) vs $\mathbb{G}_1$ ($\mathbb{F}_p$); with that many more elements to consider, it makes sense that there is additional structure in the group to now deal with. You can just rely on the definition of the $r$-torsion if you want to check if $[r](x,y)=\mathcal{O}$, but with 254 bits of r, this is slooooooow. Faster algorithms exist. For instance, defined the untwist-Frobenius-twist endomorphism of [Galbraith-Scott](https://eprint.iacr.org/2008/117.pdf): $$\psi:E^\prime(\mathbb{F}_{p^2})\to E^\prime(\mathbb{F}_{p^2}) = \Psi^{-1}\circ\phi_p\circ \Psi\,;\, (x^\prime, y^\prime)\to (\xi^{(p-1)/3}x^{\prime p}, \xi^{(p-1)/2}y^{\prime p})$$ where $\Psi$ is the twist mapping, and recall $\xi=9+u$. Membership in $\mathbb{G}_2$ therefore [boils down to verifying](https://eprint.iacr.org/2022/352.pdf) if the following holds: $Q=(x^\prime, y^\prime); \psi(Q)=[6x^2]Q$, and [more recent work](https://eprint.iacr.org/2022/348.pdf) improves this to the following: $$[x+1]Q + \psi([x]Q) + \psi([x]Q) = \psi^3([2x]Q)$$ [You can go even further too](https://eprint.iacr.org/2022/352.pdf).