# 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)
Last changed by  
 
Youssef El Housni
Applied researcher @ConsenSys. I do crytography and zk-stuff @gnark and @Linea.
1211

Read more

Faster in-circuit ECRECOVER

The bottleneck of ECRECOVER in-circuit is in the scalar multiplications. One needs to verify an equation of the form:

1/31/2024
Notes about optimizing emulated pairing (part 2)

This note focuses on the techniques used for optimizing the emulated bilinear pairing circuit in gnark library. This is the part 2 of the part 1 by @ivokub.

7/4/2023
BN254 pairing in gnark vs. google and cloudflare

A "potential security issue" in gnark-crypto was mentioned in the EF security call and was later reported to the gnark team by Besu, geth and EF teams. It was about a BN254 pairing value not consistant with google and cloudflare implementations discovered by the geth fuzzer. :::info TL;DR there is no bug. Starting from v0.8.0, gnark-crypto uses a different algorithm for the final exponentiation that outputs different (correct) results compared to google and cloudflare. ::: Example of a failing test vector: bn256.G1(192c207ae0491ac1b74673d0f05126dc5a3c4fa0e6d277492fe6f3f6ebb4880c, 168b043bbbd7ae8e60606a7adf85c3602d0cd195af875ad061b5a6b1ef19b645) bn256.G2((07caa9e61fc843cf2f3769884e7467dd341a07fac1374f901d6e0da3f47fd2ec, 2b31ee53ccd0449de5b996cb8159066ba398078ec282102f016265ddec59c354), (1b38870e413a29c6b0b709e0705b55ab61ccc2ce24bbee322f97bb40b1732a4b, 28d255308f12e81dc16363f0f4f1410e1e9dd297ccc79032c0379aeb707822f9))

5/15/2023
Elliptic nets

Let $E$ be an elliptic curve $y^2 = x^3 + ax +b$ over some finite field $\mathbb{F}_p$, where $p$ is a prime $\ne 2, 3$. For simplicity, let's focus on $j$-invariant $0$ i.e. $y^2=x^3+b$. With division polynomials, one can come up with the following formulas due to Katherine E. Stange. input: $P = (x_1,y_1)$ output: $[n]P = (x_n, y_n)$ where $x_n=x_1−\frac{W(n-1, 0)\cdot W(n+ 1, 0)}{W(n, 0)^2}$ $y_n=\frac{W(n− 1, 0)^2 \cdot W(n+ 2, 0) −W(n+1, 0)^2 \cdot W(n− 2, 0)}{4y_1 \cdot W(n, 0)^3}$ With:

4/26/2023
Read more from Youssef El Housni
Published on HackMD