(A version with formated math is available here eWASM Precompile for general elliptic curve math I have requested the admins to enable Latex formating like in Ethresearch.)

# Precompile for Elliptic Curve math

**Problem.** Currently the EVM only supports `secp261k1`

natively and `bn254`

through two pre-compiles. There are many more elliptic curve that have useful application for integration with existing systems or newly developed curves for zero-knownledge proofs.

## Proposal

Given integers $m, α$ and $β$, scalars $s_i$, and curve points $A_i$ construct the elliptic curve

$$

y^2 = x^3 + α ⋅ x + β \mod m

$$

and compute

$$

C = s_0 ⋅ A_0 + s_1 ⋅ A_1 + \cdots + s_n ⋅ A_n

$$

```
(Cx, Cy) := ecmul(m, α, β, s0, Ax0, As0, s1, Ax1, As1, ...)
```

## Gas cost

```
BASE_GAS = ...
ADD_GAS = ...
MUL_GAS = ...
```

The total gas cost is `BASE_GAS`

plus `ADD_GAS`

for each $s_i$ that is $1$ and `MUL_GAS`

for each $s_i > 1$ ($s_0 = 0$ is free).

## Encoding of points

Encode as $(x, y’)$ where $s$ is the indicates the wheter $y$ or $-y$ is to be taken. It follows SEC 1 v 1.9 2.3.4, except uncompressed points (`y' = 0x04`

) are not supported.

$y’$ | $(x, y)$ |
---|---|

`0x00` |
Point at infinity |

`0x02` |
Solution with $y$ even |

`0x03` |
Solution with $y$ odd |

Conversion from affine coordinates to compressed coordinates is trivial: `y' = 0x02 | (y & 0x01)`

.

## Special cases

**Coordinate recovery.** Set $s_0 = 1$. The output will be the recovered coordinates of $A_0$.

**On-curve checking.** Do coordinate recovery and compare $y$ coordinate.

**Addition.** Set $s_0 = s_1 = 1$, the output will be $A_0 + A_1$.

**Doubling.** Set $s_0 = 2$. The output will be $2 ⋅ A_0$. (Note: under current gas model this may be more costly than self-addition!)

**Scalar multiplication.** Set only $s_0$ and $A_0$.

**Modular square root.** Set $α = s_0 = A = 0$ the output will have $\mathtt{Cy}^2 = β \mod m$.

## Rationale

**Compressed Coordinates.** Compressed coordinates allow contract to work with only $x$ coordinates and sign bytes. It also prevents errors around points not being on-curve. Conversion to compressed coordinates is trivial.

**Linear Combination.** We could instead have a simple multiply $C = r ⋅ A$. In this case we would need a separate pre-compile for addition. In addtion, a linear combination allows for optimizations that like Shamir’s trick that are not available in a single scalar multiplication. ECDSA requires $s_0 ⋅ A_0 + s_1 ⋅ A_1$ and would benfit from this. Weistrudel shows that this is an important optimization.

**Variable Time Math.** When called during a transaction, there is no assumption of privacy and no mittigations for side-channel attacks are necessary.

## Edge cases

- Non-prime moduli or too small modulus
- Field elements larger than modulus
- Curve has singular points ($4 α^3 + 27 β^2 = 0$)
- Invalid sign bytes
- Returning the point at infinity
- (Please add if you spot more)

## Implementation

- Implement 256 field addition and multilpication
- Benchmark native, wasm-v8 and wasm-interpreter
- Generate test vectors
- Implement field inversion
- Implement field square root (Shanks & Tonelli)
- Implement curve point y computation
- Implement Jacobian to/from conversion
- Implement Jacobian curve point addition and doubling formulas
- Implement GLV?, Shamir’s trick, wNAF, etc.
- Try Montgomery reduction in the field
- Try using five 64-bit words and have carry spill bits
- Try both

## Questions

**Q1.** The curve is specified in short Weierstrass form. Some curves like Curve25519 and Ed25519 have a different specification (Montgomery, Edwards, etc). While any curve can be converted to short Weierstrass form, this requires a complex subtitution of variables. Should we expect the caller to do this transformation? Should we support more performant curves like Edwards?

**Q2.** There are more optimal addition formulas for curves where $α

∈ {-3, -1, 0}$ or $β = 0$. Most common curves fall in one of these cases. Should we support this?

**Q3.** Some curves have moduli larger than 256 bit. Should we support this? A double-word 512 bit contract would support all curves on Safecurves except M-511 and E-521.

**Q4.** Accepting points in compressed form adds extra overhead to every call, but allows caller to work with compressed coordinates. Is it worth it?

**Q5.** Cleverness allows you to use this precompile for modular square root. Is it possible to extract a modular inversion?

**Q6.** While a transaction has no assumption of privacy, this could be an issue when used in `eth_call`

. A constant time implementation also allows more code-reuse with applications that require more side-channel protection such as wallets. Should we implement constant time algorithms?

**Q7.** Beside prime fields, there are Galois fields for any $p^k$ for prime $p$. When $k ≥ 2$ this requires an irreducable polynomial to be supplied and the math is more complex. The special case where $p=2$ are the binary fields wich have nice properties. Should we support them?

**Q8.** Is it worth exploring some hash to a curve point function?

## References

- List of elliptic curve parameters.

https://safecurves.cr.yp.to/index.html - Database of optimal addition formulas.

http://www.hyperelliptic.org/EFD/index.html - Mater Inc. Rust Finite Field implementation.

https://github.com/matterinc/ff/blob/master/src/lib.rs - And Elliptic Curve.

https://github.com/matterinc/pairing/blob/master/src/bn256/ec.rs - Parity Finite Field Implementation.

https://github.com/paritytech/bigint/blob/master/src/uint.rs - Standards for Efficient Cryptography 1 (SEC 1).

http://www.secg.org/sec1-v2.pdf - Weierstrudel implementation of BN254.

https://medium.com/aztec-protocol/huffing-for-crypto-with-weierstrudel-9c9568c06901