EIP-1962: EC arithmetic and pairings with runtime definitions

Metadata

Status: StagnantStandards Track: CoreCreated: 2019-04-22

Authors

Alex Vlasov (@shamatar)

Requires

EIP-1109

Links

GitHub page Discussion on Ethereum Magicians

Simple summary

This proposal is an extension and formalization of EIP-1829 with an inclusion of pairings. EIP-1109 is required due to low cost of some operations compared to the STATICCALL opcode (more information in the corresponding section below).

Abstract

This EIP proposes a new precompile to bring cryptographic functionality desired for privacy and scaling solutions. Functionality of such precompile will require the following:

Implementation the following operations over elliptic curves in the Weierstrass form with curve parameters such as base field, A, B coefficients defined in runtime:
- Point addition
- Multiplication of a single point over a scalar
- Multiexponentiation
Implementation pairing operation over elliptic curves from the following "families" with parameters such as base field, extension tower structure, coefficients defined in runtime:
- BLS12
- BN
- MNT4/6 (Ate pairing)

Full functionality of the precompile is described below in Specification section.

Motivation

There is a pending proposal to implement base elliptic curve arithmetic is covered by EIP-1829 and will allow to implement various privacy-preserving protocols with a reasonable gas costs per operation.
Pairings are an important extension for basic arithmetic and so this new precompile is proposed with the following benefits:
- Extended set of curves will be available to allow Ethereum users to choose their security parameters and required functionality.
- Generic approach of this precompile will allow Ethereum users to experiment with newly found curves of their choice and new constructions constructions without waiting for new forks.
- EC arithmetic is indeed re-implemented in this precompile, but it's strictly required. Most of the pairing-based protocols still need to perform standard EC multiplications or additions and thus such operations must be available on generic set of curves.
Gas costs - this EIP is designed to estimate gas-cost of performed operation as early as possible during the call and base if solely on specified parameters and operation type. This is a strict requirement for any precompile to allow Ethereum nodes to efficiently reject transactions and operations as early as possible.

Functionality of this newly proposed precompile is different from EIP-1829 in the following aspects:

Operation on arbitrary-length modulus (up to some upper-limit) for a base field and scalar field of the curve
Pairing operations are introduced
Different ABI due to variable parameter length

Specification

If block.number >= XXXXX, define a set of 10 new precompiles with an addresses [0x.., 0x.., ...] and the following functionality.

Addition of points on the curve defined over base field
Multiplication of a point on the curve defined over base field
Multiexponentiation for N pairs of (scalar, point) on the curve defined over base field
Addition of points on the curve defined over quadratic or cubic extension of the base field
Multiplication of a point on the curve defined over quadratic or cubic extension of the base field
Multiexponentiation for N pairs of (scalar, point) on the curve defined over quadratic or cubic extension of the base field
Pairing operation on the curve of BLS12 family
Pairing operation on the curve of BN family
Pairing operation on the curve of MNT4 family
Pairing operation on the curve of MNT6 family

Due to actuve development of the precompile and a lot of ongoing changes there is a single source of truth. It covers binary interface, gas schedule, integration guide for existing implementations.

Possible simplifications

Due to high complexity of the proposed operations in the aspects of implementation, debugging and evaluation of the factors for gas costs it may be appropriate to either limit the set of curves at the moment of acceptance to some list and then extend it. Another approach (if it's technically possible) would be to have the "whilelist" contract that can be updated without consensus changes (w/o fork).

In the case of limited set of curve the following set is proposed as a minimal:

BN254 curve from the current version of Ethereum
BN curve from DIZK with 2^32 roots of unity
BLS12-381
BLS12-377 from ZEXE with large number of roots of unity
MNT4/6 cycle from the original paper. It's not too secure, but may give some freedom for experiments.
MNT4/6 cycle from Coda if performance allows
Set of CP generated curves that would allow embedding of BLS12-377 and may be some BN curve that would have large power of two divisor for both base field and scalar field modulus (example of CP curve for BLS12-377 can be found in ZEXE).

Rationale

Only the largest design decisions will be covered:

While there is no arithmetic over the scalar field (which is modulo size of the main group) of the curve, it's required for gas estimation purposes.
Multiexponentiation is a separate operation due to large cost saving
There are no point decompressions due to impossibility to get universal gas estimation of square root operation. For a limited number of "good" cases prices would be too different, so specifying the "worst case" is expensive and inefficient, while introduction of another level if complexity into already complicated gas costs formula is not worth is.

This precompile and EIP 1109

While there is no strict requirement of EIP 1109 for functionality, here is an example why it would be desired:

BLS12-381 curve, 381 bit modulus, 255 bit scalar field, no native arithmetic is available in EVM for this
Point addition would take 5000ns (quite overestimated)
Point multiplication would take roughly 150000ns
Crude gas schedule 15 Mgas/second from ECRecover precompile
Point addition would cost 75 gas, with STATICCALL adding another 700
Point multiplication would cost 2250 gas
One should also add the cost of memory allocation that is at least 1 + 1 + 48 + 48 + 48 + 1 + 32 + 2*48 + 2*48 = 371 byte that is around 12 native Ethereum "words" and will require extra 36 gas (with negligible price for memory extension)

Based on these quite crude estimations one can see that STATICCALL price will dominate the total cost (in case of addition) or bring significant overhead (in case of multiplication operation) in case of calls to this precompile.

Backwards Compatibility

This change is not backwards compatible and requires hard fork to be activated.

Functionality of the new precompile itself does not affect any existing functionality of Ethereum or EVM.

This precompile may serve as a complete replacement of the current set of ECADD, ECMUL and pairing check precompiles (0x06, 0x07, 0x08)

Test Cases

Test cases are the part of the implementation with a link below.

Implementation

There is an ongoing implementation effort here. Right now:

Non-pairing operations are implemented and tested.
BLS12 family is completed and tested for BLS12-381 and BLS12-377 curves.
BN family is completed and tested with BN254 curve.
Cocks-Pinch method curve is tested for k=6 curve from ZEXE.

Preliminary benchmarks

cp6 in benchmarks is a Cocks-Pinch method curve that embeds BLS12-377. Machine: Core i7, 2.9 GHz.

Multiexponentiation benchmarks take 100 pairs (generator, random scalar) as input. Due to the same "base" it may be not too representative benchmark and will be updated.

Copyright