EIP 1895: Support for an Elliptic Curve Cycle

Author	Alexandre Belling
Discussions-To	https://ethresear.ch/t/reducing-the-verification-cost-of-a-snark-through-hierarchical-aggregation/5128
Status	Draft
Type	Standards Track
Category	Core
Created	2018-31-03

Simple Summary

The EVM currently supports elliptic curves operations for curve alt-bn128 thanks to precompiles ecadd and ecmul and ecpairing. The classes MNT4 and 6 contain cycles of curves. Those cycles enable doing operations on one curve inside a SNARK on the other curve (and reversely). This EIP suggests adding support for those curves.

Abstract

Adds supports for the following operations through precompiles:

ecadd on MNT4
ecmul on MNT4
ecpairing on MNT4

Motivation

Elliptic curve is the basic block of recursive SNARKs (ie: verifying a SNARK inside a SNARK) and this addresses the issue of scalable zero-knowledge. More generally this addresses partly the scalability issue as SNARKs verification are constant time in the size of the circuit being verified.

More concretely, today if the EVM has to deal with 1000s of SNARK verification it would take around 1.5 billion gas and would be impractical for Ethereum. Recursive SNARKs for instance make it possible to aggregate multiple proofs into a single one that can be verified like any other SNARK. It results in a massive cost reduction for the verification.

However, this is impossible using alt-bn128 and in my knowledge, the only family of pairing-friendly curves known to produce cycles are MNT4 and MNT6. A complete characterization of the cycles existing between those two families is proposed in On cycles of pairing-friendly elliptic curves

Specification

The curve

The proposed cycle has been introduced in Scalable Zero Knowledge via Cycles of Elliptic Curves.

MNT4 definition

The groups G_1 and G_2 are cyclic groups of prime order :

q = 475922286169261325753349249653048451545124878552823515553267735739164647307408490559963137

G_1 is defined over the field F_p of prime order :

p = 475922286169261325753349249653048451545124879242694725395555128576210262817955800483758081

with generator P:

P = (
    60760244141852568949126569781626075788424196370144486719385562369396875346601926534016838,
    363732850702582978263902770815145784459747722357071843971107674179038674942891694705904306
)

Both p and q can be written in 298 bits.

The group G_1 is defined on the curve defined by the equation Y² = X³ + aX + b where:

    a = 2
    b = 423894536526684178289416011533888240029318103673896002803341544124054745019340795360841685

The twisted group G_2 is defined over the field F_p^2 = F_p / <<To be completed>>

The twisted group G_2 is defined on the curve defined by the equation Y² = X² + aX + b where :

    a = 34 + i * 0
    b = 0 + i * 67372828414711144619833451280373307321534573815811166723479321465776723059456513877937430

G_2 generator is generated by :

    P2 = (
        438374926219350099854919100077809681842783509163790991847867546339851681564223481322252708 +
        i * 37620953615500480110935514360923278605464476459712393277679280819942849043649216370485641,
        37437409008528968268352521034936931842973546441370663118543015118291998305624025037512482 +
        i * 424621479598893882672393190337420680597584695892317197646113820787463109735345923009077489
    )

The operations and gas cost

The following operations and their gas cost would be implemented

MNT_X_ADD = <<To be estimated>>
MNT_X_MUL = <<To be estimated>>
MNT_X_PAIRING = <<To be estimated>>

Where X is either 4.

Encoding

The curves points P(X, Y) over F_p are represented in their compressed form C(X, Y):

    C = X | s

where s represents Y as follow:

    |  `s'`  | `Y`                      |
    |--------|--------------------------|
    | `0x00` | Point at infinity        |
    | `0x02` | Solution with `y` even   |
    | `0x03` | Solution with `y` odd    |

Compression operation from affine coordinate is trivial:

    s = 0x02 | (s & 0x01)

In the EVM the compressed form allows us to represents curve points with 2 uint256 instead of 3.

Edge cases

Several acceptable representations for the point at infinity

Rationale

The curve has 80 bits of security (whereas MNT6 has 120 bits) which might not be considered enough for critical security level, (for instance transfering several billions), but enough for others. If it turns out this is not enough security for adoption, there is another option : another cycle is being used by Coda but is defined over a 753 bits sized field which might also be prohibitively low (no reference to this curve from Coda’s publications found).

Independently of the cycle chosen, the groups and field elements are represented with integers larger than 256 bits (even for the 80 bits of security), therefore it might be necessary to also add support for larger field size operations.

We currently don’t know more efficient pairing-friendly cycles and don’t know if there are. It might be possible to circumvent this problem though by relaxing the constraint that all the curves of the cycle must be pairing friendly). If we had a cycle with only one pairing friendly curve we would still be able to compose proofs by alternating between SNARKs and any other general purpose zero-knowledge cryptosystems.

Assuming we find a convenient cycle, we don’t need to implement support for all the curves it contains, only one. The best choice would be the fastest one as the overall security of the recursive snark do not depends on which curve the verification is made.

Proper benchmarks will be done in order to make this choice and to price the operations in gas.

Test Cases

References

Eli-Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza, [BCTV14], April 28, 2015, Scalable Zero Knowledge via Cycles of Elliptic Curves : https://eprint.iacr.org/2014/595.pdf
Alessandro Chiesa, Lynn Chua, Matthew Weidner, [CCW18], November 5, 2018, On cycles of pairing-friendly elliptic curves : https://arxiv.org/pdf/1803.02067.pdf

Implementation

go-boojum : A PoC demo of an application of recursive SNARKs
libff : a C++ library for finite fields and elliptic curves
coda : a new cryptocurrency protocol with a lightweight, constant sized blockchain.

EIP 1895: Support for an Elliptic Curve Cycle Source