Precompile for Elliptic Curve Linear Combinations
EIP-1829 proposes a new precompile for elliptic curve linear combinations, which would allow for more efficient implementation of privacy-preserving protocols on the Ethereum blockchain. The precompile would support point addition, scalar multiplication, and multiexponentiation operations over elliptic curves in the Weierstrass form with curve parameters defined at runtime. The proposal also includes possible simplifications to the implementation and outlines the rationale for the precompile. Backwards compatibility and test cases are also discussed, and preliminary benchmarks are provided.
Video
Original
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.
Adopted by projects
Not miss a beat of EIPs' update?
Subscribe EIPs Fun to receive the latest updates of EIPs Good for Buidlers to follow up.
View all