# On subgroup checks for BLS12
Let $E$ be an elliptic curve from the BLS12 family. We denote by $r$ its prime subgroup order. Let $P(x,y) \in E$ a point of order $r$. The goal is to verify efficiently that $r\cdot P = \infty$.

## Notations
- $E$ is an elliptic curve defined over a finite field $\mathbb{F}_p$ with the short Weierstrass equation $y^2=x^3+ax+b$
- $r$ is a prime-order subgroup of $E(\mathbb{F}_p)$
- $k$ is the embedding degree, i.e. the smallest integer s.t. $r \mid p^k-1$
- A pairing is a map $e: \mathbb{G}_1 \times \mathbb{G}_2 \mapsto \mathbb{G}_T$, where $\mathbb{G}_1 \subset E[r](\mathbb{F}_p)$, $\mathbb{G}_2 \subset E[r](\mathbb{F}_{p^k})$ and $\mathbb{G}_T$ the group of $r$-th roots of unity in $\mathbb{F}_p$.

## BLS12
BLS12 is a complete family of pairing-friendly elliptic curves with an embedding degree $k=12$ (Construction 6.6 in [FST06](https://eprint.iacr.org/2006/372.pdf), case $k\equiv 0 \mod6$). It is defined over a finite field $\mathbb{F_p}$ of prime characteristic $p$ by the equation $y^2=x^3+b$. It has Complex Multiplication by discriminant $D=-3$ and parameters defined by the following polynomials:
Parameter | Polynomial |
--------- | ---------- |
field size $p(x)$ | $(x-1)^2/3\cdot r(x)+x$ |
subgroup order $r(x)$ | $x^4-x^2+1$ | 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 |
Frobenius trace $t(x)$ | $x+1$ |

$\rightarrow$ These polynomials are evaluated at some seed $z$ to derive a specific curve with the desired security and efficiency.

## Endomorphisms
BLS12 curves have CM discriminant $D=-3$, so there is an efficient endomorphism $\phi:(x,y)\mapsto (x\cdot \omega, y)$ with $\omega \in \mathbb{F}_p$ a primitive cube root of unity (i.e. $\omega^2+\omega+1 \equiv 0 \mod p$). The eigenvalue of this endomorphism is $\lambda=z^2-1$ which a cube root of unity in $\mathbb{F}_r$.

:::info
BLS12 has Complex Multiplication by $\frac{-1+\sqrt{-3}}{2}$. There is an endomorphism $\phi$ satisfying $\phi^2+\phi+1$ with eigenvalue $\lambda=\frac{-1+\sqrt{-3}}{2} \mod r$. Given BLS12 polynomials, one finds $\lambda(x)=x^2-1$.
:::

Given a twist of order $d$, $\mathbb{G}_2 \subset E[r](\mathbb{F}_{p^k})$ is isomorphic to $E'[r](\mathbb{F}_{p^{k/d}})$ with $\nu:E\mapsto E'$ the twisting isomorphism. On $E'(\mathbb{F}_{p^{k/d}})$, there is an efficient endomorphism $\psi$ called "untwist-Frobenius-twist" $\psi = \nu^{-1} \circ \pi_p \circ \nu$ where $\pi_p$ is the $p$-power Frobenius. It satisfies $\psi^2-t\psi+p=0$

:::info
BLS12 curves have a twist of degree 6. Associated with a choice of $\xi \in \mathbb{F}_{q^{k/6}}$ s.t. $x^6-\xi \in \mathbb{F}_{q^{k/6}}[X]$ is irreducible, the equation of $E'$ can be either
- $y^2=x^3+b/\xi$ and we call it a D-twist or
- $y^2=x^3+b.\xi$ and we call it a M-twist

For the D-type, $\nu^{-1}:(x,y)\mapsto(\xi^{1/3}x,\xi^{1/2}y)$,
and for the M-type $\nu^{-1}:(x,y)\mapsto(\xi^{2/3}x/\xi,\xi^{1/2}y/\xi)$

So given that $k=12$ and $d=6$, $\mathbb{G}_2$ is over $\mathbb{F}_{p^2}$ and $\pi_p:(x,y)\mapsto (x^p,y^p)=(\bar{x}, \bar{y})$ and $\psi$ is
$$
(x,y) \mapsto (\bar{x}\cdot c_1^{te}, \bar{y}\cdot c_2^{te})
$$
:::

## Related work
Using the endomorphism $\phi$ on $\mathbb{G_1}$ and $\psi$ on $\mathbb{G_2}$, Sean Bowe [[1]](https://eprint.iacr.org/2019/814.pdf) derived using LLL algorithm as in Fuentes et al.[[2]](https://eprint.iacr.org/2008/530.pdf) and Budroni and Pintore[[3]](https://eprint.iacr.org/2017/419.pdf) fast formulae to check that a point is on BLS12-381 $\mathbb{G_1}$ and $\mathbb{G_2}$. The formulae are

- $P \in \mathbb{G_1} \iff ((z^2 − 1)/3)\cdot (2\phi(P) − P − \phi^2(P)) − \phi^2(P) = \infty$
- $Q \in \mathbb{G_2} \iff z\cdot \psi^3(Q)-\psi^2(Q)+Q = \infty$
## Observations
- To derive $\mathbb{G_1}$ membership formula for BLS12, there is no need for LLL algorithm. Given the polynomials $r(x)$ and $\lambda(x)$, a simple formula can be derived
$$
r(z)\cdot P = (z^4-z^2+1)\cdot P = (z^2\cdot \lambda(z)+1)\cdot P = z^2\cdot \phi(P)+P
$$
The formula in [[1]](https://eprint.iacr.org/2019/814.pdf) can be simplified into this one by using the fact that $\phi^2+\phi+1=0$.

- For $\mathbb{G_2}$, the check can be done the same way: $z^2\cdot\phi(Q)+Q=\infty$ (note $\phi$ in $\mathbb{G_2}$ uses the other cube root of unity $-\omega-1$). However, the formula in [[1]](https://eprint.iacr.org/2019/814.pdf) is faster (multiplication by $z$ instead of $z^2$) but it can be simplified into $-z\cdot \psi(\phi(Q))+\phi(Q)+Q=0$ by remarking that $\psi^2=-\phi$.

:::info
$\rightarrow$ Why $\psi^2=-\phi$?
Let's take the example of D-twist, we have
$$
\nu^{-1}:(x,y)\mapsto(\xi^{1/3}x,\xi^{1/2}y) \\
\pi_p:(x,y)\mapsto(y^p,y^p)=(\bar{x}, \bar{y}) \\
\nu:(x,y)\mapsto(1/\xi^{1/3}x,1/\xi^{1/2}y) \\
\psi:(x,y)\mapsto(\xi^{(p-1)/3}\cdot\bar{x},\xi^{(p-1)/2}\cdot\bar{y})
$$
and,
$$
\psi^2:(x,y)\mapsto(\xi^{(p+1)(p-1)/3}\cdot x,\xi^{(p+1)(p-1)/2}\cdot y)
$$
Now, recal that $x \mapsto x^{p+1}$ is the trace $\mathbb{F}_{p^2}/\mathbb{F}_p$ hence $x^{p+1}\in\mathbb{F}_p$ and $(\xi^{(p-1)/6})^{p+1}$ is a primitive 6th root of unity. So, $\xi^{(p+1)(p-1)/3}$ is primitive 3rd root of unity. Now, $(\xi^{(p-1)/2})^{p+1}=(\xi^{p+1})^{(p-1)/2}$ and $\xi^{p+1} \in \mathbb{F}_p$, this is the trace. Finally, $(\xi^{p+1})^{(p-1)/2}=\begin{cases}1 \quad\text{if square} \\ -1\quad \text{otherwise}\end{cases}$, and because $\xi$ is not a square in $\mathbb{F}_{p^2}$, then $(\xi^{p+1})^{(p-1)/2}=-1$, which means
$$
\psi^2:(x,y)\mapsto(\omega\cdot x, -y)=-\phi
$$

:::

## [NEW] Scott eprint 2021/1130
- For $\mathbb{G_1}$, Scott proves by contradiction that checking the endorphism is sufficient: $\phi(P)=-z^2P$. In fact, $-z^6 \equiv \lambda \equiv 1 \mod r$ because $\lambda$ a third root of unity in $\mathbb{F_r}$. If the endomorphism was true for a point of order $c\cdot r$, then by CRT, $-z^6 \equiv 1 \mod c$ but $c\mid z-1$ for BLS curves and hence $u^6=1 \mod c$.
- For $\mathbb{G_2}$, he finds a simpler formula: $\psi(P)=zP$. In fact, given that $(p+1-t)Q=\infty$ and $t=z+1$ then $uP=pQ$. $\psi$ verifies $\psi^2(Q)-t\psi(Q)+pQ=\infty$ and this becomes $zQ=\psi(uQ)+\psi(Q)-\psi^2(Q)$ which has two solutions: $\psi(Q)=Q$ or $\psi(Q)=uQ$. Only the latter is valid sinc $\psi$ acts non-trivially on $\mathbb{G_2}$.

## Implementation
Example code for BLS12-381 (M-twist) with seed $z=-15132376222941642752$ and BLS12-377 (D-twist) with $z=9586122913090633729$ in [gnark-crypto](https://github.com/ConsenSys/gnark-crypto) library (golang).
- [BLS12-381 $\mathbb{G}_1$ membership test](https://github.com/ConsenSys/gnark-crypto/blob/ed8216091919174f8d578ef1f023ebcb649df7fa/ecc/bls12-381/g1.go#L375)
- [BLS12-381 $\mathbb{G}_2$ membership test](https://github.com/ConsenSys/gnark-crypto/blob/ed8216091919174f8d578ef1f023ebcb649df7fa/ecc/bls12-381/g2.go#L376)
- [BLS12-377 $\mathbb{G}_1$ membership test](https://github.com/ConsenSys/gnark-crypto/blob/develop/ecc/bls12-377/g1.go#L375)
- [BLS12-377 $\mathbb{G}_2$ membership test](https://github.com/ConsenSys/gnark-crypto/blob/develop/ecc/bls12-377/g2.go#L376)