#
EIP-1829: Precompile for Elliptic Curve Linear Combinations

Authors | Remco Bloemen <Recmo@0x.org> |
---|---|

Created | 2019-03-06 |

Discussion Link | https://ethereum-magicians.org/t/ewasm-precompile-for-general-elliptic-curve-math/2581 |

## Table of Contents

# Precompile for Elliptic Curve Linear Combinations

## Simple Summary

Currently the EVM only supports *secp256k1* in a limited way through `ecrecover`

and *altbn128* through two pre-compiles. There are draft proposals to add more curves. There are many more elliptic curve that have useful application for integration with existing systems or newly developed curves for zero-knowledge proofs.

This EIP adds a precompile that allows whole classes of curves to be used.

## Abstract

A precompile that takes a curve and computes a linear combination of curve points.

## Motivation

## Specification

Given integers `m, α`

and `β`

, scalars `s_i`

, and curve points `A_i`

construct the elliptic curve

```
y² = x³ + α ⋅ x + β mod m
```

and compute the following

```
C = s₀ ⋅ A₀ + s₁ ⋅ A₁ + ⋯ + s_n ⋅ A_n
```

aka *linear combination*, *inner product*, *multi-multiplication* or even *multi-exponentiation*.

```
(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_i = 0`

is free).

### Encoding of points

Encode as `(x, y')`

where `s`

indicates whether `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₀ = 1`

. The output will be the recovered coordinates of `A₀`

.

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

coordinate.

**Addition.** Set `s₀ = s₁ = 1`

, the output will be `A₀ + A₁`

.

**Doubling.** Set `s₀ = 2`

. The output will be `2 ⋅ A₀`

. (Note: under current gas model this may be more costly than self-addition!)

**Scalar multiplication.** Set only `s₀`

and `A₀`

.

**Modular square root.** Set `α = s₀ = A = 0`

the output will have `Cy² = β mod m`

.

### Edge cases

- Non-prime moduli or too small modulus
- Field elements larger than modulus
- Curve has singular points (
`4 α³ + 27 β² = 0`

) - Invalid sign bytes
- x coordinate not on curve
- Returning the point at infinity
- (Please add if you spot more)

## Rationale

**Generic Field and Curve.** Many important optimizations are independent of the field and curve used. Some missed specific optimizations are:

- Reductions specific to the binary structure of the field prime.
- Precomputation of Montgomery factors.
- Precomputation of multiples of certain popular points like the generator.
- Special point addition/doubling formulas for
`α = -3`

,`α = -1`

,`α = 0`

,`β = 0`

.

TODO: The special cases for `α`

and `β`

might be worth implementing and offered a gas discount.

**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 addition, a linear combination allows for optimizations that like Shamir’s trick that are not available in a single scalar multiplication. ECDSA requires `s₀ ⋅ A₀ + s₁ ⋅ A₁`

and would benefit from this.

The BN254 (aka alt_bn8) multiplication operation introduced by the EIP-196 precompile only handles a single scalar multiplication. The missed performance is such that for two or more points it is cheaper to use EVM, as practically demonstrated by Weierstrudel.

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

**Prime Fields.** This EIP is for fields of large characteristic. It does not cover Binary fields and other fields of non-prime characteristic.

**256-bit modulus.** This EIP is for field moduli less than `2^{256}`

. This covers many of the popular curves while still having all parameters fit in a single EVM word.

TODO: Consider a double-word version. 512 bits would cover all known curves except E-521. In particular it will cover the NIST P-384 curve used by the Estonian e-Identity and the BLS12-381 curve used by ZCash Sappling.

**Short Weierstrass Curves.** This EIP is for fields specified in short Weierstrass form. While any curve can be converted to short Weierstrass form through a substitution of variables, this misses out on the performance advantages of those specific forms.

## Backwards Compatibility

## Test Cases

## Implementation

There will be a reference implementation in Rust based on the existing libraries (in particular those by ZCash and The Matter Inc.).

The reference implementation will be production grade and compile to a native library with a C api and a webassembly version. Node developers are encouraged to use the reference implementation and can use either the rust library, the native C bindings or the webassembly module. Node developers can of course always decide to implement their own.

## References

This EIP overlaps in scope with

- EIP-196: ecadd, ecmul for altbn128
- EIP issue 603: ecadd, ecmul for SECP256k1.
- EIP-665: ECDSA verify for ED25519.
- EIP-1108: Optimize ecadd and ecmul for altbn128.

## Copyright

Copyright and related rights waived via CC0.

## Citation

Please cite this document as:

Remco Bloemen <Recmo@0x.org>, "EIP-1829: Precompile for Elliptic Curve Linear Combinations [DRAFT]," *Ethereum Improvement Proposals*, no. 1829, March 2019. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-1829.