# 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](https://en.wikipedia.org/wiki/Division_polynomials), one can come up with the following formulas due to [Katherine E. Stange](https://arxiv.org/pdf/0710.1316.pdf).
- *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:
\begin{align}
W(-2, 0) &= − 2y_1 \\
W( − 1, 0) &= − 1 \\
W(0, 0) &= 0 \\
W(1, 0)&= 1 \\
W(2, 0) &= 2y_1 \\
W(3, 0) &= 3x_1^3+12b \cdot x_1 \\
W(4, 0) &= 4y_1(x_1^6 + 20b \cdot x_1^3- 8b^2)\\
W(0, 1) &= 1\\
W(1, 1) &= 1\\
W(2, 1) &= 2x_1+x_2− (\frac{y_2−y_1}{x_2−x_1})^2\\
W( − 1, 1) &=x_1−x_2\\
W(2, − 1) &= (y_1+y_2)^2− (2x_1+x_2)(x_1−x_2)^2
\end{align}
When $i \geq 5$, $W(i, 0)$ and $W(i, 1)$ can be computed using some recursive formulas (cf. [[Stange07](https://arxiv.org/pdf/0710.1316.pdf)]). For example:
\begin{align}
W(2i− 1, 0) &=W(i+ 1, 0)W(i− 1, 0)^3−W(i− 2, 0)W(i, 0)^3 \\
W(2i, 0) &=\frac{W(i, 0)W(i+ 2, 0)W(i− 1, 0)^2}{W(2, 0)}−\frac{W(i, 0)W(i− 2, 0)W(i+ 1, 0)^2}{W(2, 0)}
\end{align}
---
Doubling ($n=2$):
\begin{align}
x_2&=x_1−\frac{W(1, 0)\cdot W(3, 0)}{W(2, 0)^2} \\
x_1-x_2&=\frac{W(3, 0)}{W(2, 0)^2}\\
y_2&=\frac{W(1, 0)^2 \cdot W(4, 0) −W(3, 0)^2 \cdot W(0, 0)}{4y_1 \cdot W(2, 0)^3} \\
4y_1\cdot y_2&=\frac{W(4, 0)}{W(2, 0)^3}
\end{align}
## More
Stange depicted two algorithms `Double` and `DoubleAdd` to compute Tate pairing. [Kanayama et al.](https://www.jstage.jst.go.jp/article/transfun/E97.A/1/E97.A_300/_article) adapted Stange's algorithm to compute scalar multiplication. [Chen et al.](https://eprint.iacr.org/2015/284) later improved on this.
If we denote the multiplication and squaring in the finite field under consideration by `M` and `S`, respectively, it can be seen that the number of operations for both the `Double` and `DoubleAdd` steps is `26M+ 6S` for Kanyama et al. and `18M+ 10S` for Chen et al.
It can be seen that these formulas are more expensive than the traditional double-and-add algorithms. For SNARKs (where an inverse costs almost as much as a multiplication), these formulas are even more expensive in comparison with double-and-add in affine coordinates. However, my point is to see if there is a verification-friendly shortcut of the division sequences which would make them SNARK-friendly.

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

1/31/2024This 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/2023A "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/2023Twisted Edwards curve: $-x^2+y^2=1+dx^2y^2$ over $\mathbb{F}_r$ (e.g. SNARK field of BN254) of order $n = h\cdot \texttt{prime}$ ($h=4$ or $h=8$) with generator point $G$. keys: secret key: scalar $a$

11/4/2022
Published on ** HackMD**

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up