# EdDSA gadget
- Twisted 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$
- public key: point $A$
- signature $\{R,s\}$ where $R$ is point and $s$ a scalar.
- signature verification
$$ [s]\cdot G = R + [H(R, A, M)]\cdot A$$ where $H(R, A, M)$ is the (MiMC) hash of the concatenation of $R$, $A$ and the message $M$.
## gnark circuit
| computation | operation | number of constraints (R1CS) for BN254 |
|-------------|-----------|-----------------------|
| $H(R, A, M)$| MiMC hash | 1365
| $[s]\cdot G$| fixed-base scalar multiplication| 3038|
| $[s]\cdot G$ is on curve| curve equation verification | 4
| $[H(R, A, M)]\cdot A$ | variable-base scalar multiplication | 4055
| $[H(R, A, M)]\cdot A$ is on curve| curve equation verification | 4
| $R + [H(R, A, M)]\cdot A$ | variable-point addition | 7
| $[s]\cdot G - (R + [H(R, A, M)]\cdot A)$| point negation and variable-point addition | 7
| $h\cdot([s]\cdot G - (R + [H(R, A, M)]\cdot A))$ | two (or three) variable-point doublings| 18
| $h\cdot([s]\cdot G - (R + [H(R, A, M)]\cdot A) =^? 0_{\text{curve}}$ | check $(x,y)=(0,1)$ | 2
:::info
Total: 8500 constraints.
Total without hash: 7135 constraints.
:::
The hash computation is done through GKR in Sumo.
## Optimisations
- [x] rearrange doubling formula (saves 1C per bit)
\begin{align*}
(\frac{2xy}{1+d x^2y^2}, \frac{y^2+x^2}{1-dx^2y^2}) \rightarrow (\frac{2xy}{-x^2+y^2}, \frac{y^2+x^2}{2+x^2-y^2})
\end{align*}
- [x] scalar multiplication:
- [x] handle first bit seperately (no need to double/add the zero point. 2C instead of 14C)
- [x] 2-bit windowed method with `Lookup2`select
:::info
**up to these**
Total: 7222 constraints.
Total without hash: 5857 constraints.
:::
- [x] double-base scalar multiplication
- instead of computing $[s]G$ and $[h]A$ seperately and then subtract them, we compute simultaneously $[s]G-[h]A$ by sharing the doubling and using a lookup table of 4 points to add ($0, G, -A$ or $G-A$).
- Out-circuit we would do this with a windowed method (precomputations) and/or with a Joint-Sparse Form (JSF) of scalars. In-circuit this requires a bigger conditional lookup table.
:::info
**up to this (naive double-base scalar mul)**
Total: 6451 constraints.
Total without hash: 5086 constraints.
:::
- [x] rearrange addition (saves 1C. I missed this trick ^^)
:::info
Total: 6212 constraints.
Total without hash: 4847 constraints.
:::
- [ ] base-3 (ternary) instead of binary. A naive double-and-add algorithm requires
- in binary $(1 \texttt{ADD} + 1 \texttt{DOUBLE} + 2 \texttt{SELECT}) \times N_2$ where $N_2$ is the max size of binary bits (e.g. BN254 $N_2=253$). This costs naively $(6+5+2)\times253=3289$ constraints.
- in ternary $(1 \texttt{ADD} + 1 \texttt{TRIPLE} + 2 \texttt{LOOKUP2}) \times N_3$ where $N_3$ is the max size of ternary bits (e.g. BN254 $N_3=109$). This costs naively $(6+8+6)\times109=2180$ constraints.
- [ ] double-base number system (2, 3 or 2, 3, 5).
- Didn't analyse the saving yet but a tripling in affine coordinates cost **4C** less that a doubling+addition. We can write the scalars in the double-base number system instead of binary.
- currently writing code to find optimal chains of 2,3 double-base.
- [ ] batch verification of many EdDSA signatures
- [ ] same public key
- [ ] different public key
Sumo verifies $n$ EdDSA signatures seperately as
$$ [s_i]G = R_i + [h_i]A_i $$ for $i \in \{0,\cdots,n-1\}$. It costs $n$ fixed-based scalar multiplication, $n$ variable-base scalar multiplication, $2n$ variable-point addition, $2n$ variable-point doubling and $2n$ curve equation. The total is $8500\cdot n$ constraints (or $6212$). We can write the batch verification as
$$
[\sum_{i=0}^{n-1}s_i]\cdot G = (\sum_{i=0}^{n-1}R_i) + (\sum_{i=0}^{n-1}[h_i]A_i)
$$
this costs 1 fixed-base scalar multiplication, $n$ variable-base scalar multiplication, $2n$ variable-point addition and $n$ addition of `frontend.Variable`.
:::info
This would save $2644\cdot (n -1)$ constraints (e.g. $n=2850$ saves ~$7.5$M constraints).
:::
$\rightarrow$ More optimisations:
- variable-point addition in twisted Edwards (affine) costs 7C. We can convert $R_i$ to Montgomery form ($n\times$ 2C) and do the addition there ($(n-1)\times$ 4C) and then convert back a single point (2C). This would save ~$n$ constraints. We might also save the $R_i$ (from the signatures) already in Montgomery form.
- $\sum_{i=0}^{n-1}[h_i]A_i$ can be performed with some SNARK-friendly MSM. I don't know yet but a bucket method in Montgomery form would be appropiate as the cost is dominated by additions.
- if the signatures are provided from the same signer it becomes
$$
[\sum_{i=0}^{n-1}s_i]\cdot G = (\sum_{i=0}^{n-1}R_i) + [\sum_{i=0}^{n-1}h_i]A
$$
which trades off $n$ variable-base scalar multiplication for $1$ fixed-based scalar multiplication and $n-1$ `frontend.Variable` additions. This saves ~$1000n$ more contraints.
The batch algorithms should be randomised (mul by $\alpha_i$). This doesn't change the constraints count of $[\sum_{i=0}^{n-1} \alpha_i s_i]\cdot G$ and $\sum_{i=0}^{n-1}\alpha_i [h_i]A_i$ but would change the cost of $\sum_{i=0}^{n-1}\alpha_i R_i$ from $n-1$ additions to $n$ variable-base scalar multiplication (maybe we can omit to randomize $R_i$? Also is it possible to derive sparse randomizers? security?).
$$
[\sum_{i=0}^{n-1} \alpha_i s_i]\cdot G = (\sum_{i=0}^{n-1}\alpha_i R_i) + (\sum_{i=0}^{n-1}\alpha_i [h_i]A_i)
$$
This would make the batch technique not worthwhile unless the 2 MSMs are implemented efficiently constraint-wise.

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