Let $E$ be an elliptic curve defined over a prime field $\mathbb{F}_p$. We assume points on $E/\mathbb{F}_p$ form a group of prime order $n$ generated by the point $G$.
The bottleneck of ECRECOVER in-circuit is in the scalar multiplications over $E$. One needs to verify an equation of the form:
\begin{align} [u_1]G + [u_2]R = P \quad\quad(1)
\end{align}
where $R \in E$ is the public key and $P \in E$ a reconstructed point from an $x$-coordinate $r$. The scalars are $u_1=m/r \mod n$ and $u_2=s/r \mod n$ with $(r,s)$ the ECDSA signature tuple and $m$ the signed message.
In a BN254 PLONK circuit, an ECRECOVER (where $E=\texttt{secp256k1}$) costs *mainly* a variable-base scalar multiplication $[u_2]R$ ($\texttt{881041 scs}$) and a fixed-base scalar multiplication $[u_1]G$ ($\texttt{604534 scs}$).
*N.B.*: a joint scalar multiplication that scans $u_1$ and $u_2$ simultanously is not efficient in-circuit for short Weierstrass curves when one of the points is fixed, becayse $u_1$ is scanned right-to-left (to precompute doubles of $G$) and $u_2$ is scanned left-to-right.
## A silly idea [SAC:ABGL+05] ?
One can re-write the equation by multiplying it by some scalar $v$:
$$ [v\cdot u_1]G + [v\cdot u_2]R - [v]P = \mathcal{O}$$
This results in one more variable-base scalar multiplication, but if we choose $v$ to be $u\cdot r/s \mod n$ such that both $v$ and $u$ are half-size of $n$, then we get:
\begin{align} [u\cdot m/s]G + [u]R - [v]P = \mathcal{O} \quad\quad(2)
\end{align}
One can find a suitable value for $v$ by writing $x = s/r \mod n$ as $x = u/v \mod n$, where $u$ and $v$ are integers of approximately half the bit-size of $n$ or, more generally, of $1 - \epsilon$ and $\epsilon$ times the bit-size of $n$, respectively, where $0 < \epsilon < 1$.
#### Maybe not too silly
Let $n$ be a prime number. Any integer $x \in \mathbb{F}_n$ can be written as $x = u/v \mod n$, where $u$ and $v$ are integers such that $|u| < n^{1-\epsilon}$ and $1 \leq v \leq n^\epsilon$. In particular, one may have $|u| < \sqrt{n}$ and $1 \leq v \leq \sqrt{n}$ for $\epsilon = 1/2$. This looks like finding good solutions to the *simultaneous Diophantine approximation problem* which is equivalent to the problem of *finding short vectors in a particular lattice*.
**TODO**: more one that + sagecode
### In-circuit optimization
| | Total cost | constraints |
----------|------|---|
|(1) | 1 full fbSM + 1 full vbSM | |
|(2) | 1 full fbSM + 1 half-sized vbSM + 1 half-sized vbSM |
It results a priori in the same cost, but now we can implement $[u]R - [v]P$ efficiently using Strauss-Strassen trick thanks to the endomorphism [[PR 949]](https://github.com/Consensys/gnark/pull/949).

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/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/2023Let $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/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