eWASM Precompile for general elliptic curve math

security

#1

(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


#2

Nice!

We do currently collect some precompile ideas under https://github.com/ewasm/ewasm-precompiles/issues, but since the above proposal doesn’t utilise any ewasm-specific behaviour (such as the potential to avoid using the current ABI encoding), I’d suggest the best would be proposing this as an EIP, which can be implemented and tested on ewasm. The other newly implemented precompiles in the ewasm repository all have a corresponding EIP.

What do you think?


#3

This seems to be an outline, if fleshed out it would become an EIP.

A (the?) major use case for this precompile, if I understand correctly, is for doing Pedersen commitments inside contracts, cheaply. So it would supersede a pedersen commitment precompile.