EIPs

EIP1895 - Support for an Elliptic Curve Cycle

# 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 (opens new window)

# Specification

# The curve

The proposed cycle has been introduced in Scalable Zero Knowledge via Cycles of Elliptic Curves (opens new window).

# MNT4 definition

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

q = 475922286169261325753349249653048451545124878552823515553267735739164647307408490559963137
1

G_1 is defined over the field F_p of prime order :

p = 475922286169261325753349249653048451545124879242694725395555128576210262817955800483758081
1

with generator P:

P = (
    60760244141852568949126569781626075788424196370144486719385562369396875346601926534016838,
    363732850702582978263902770815145784459747722357071843971107674179038674942891694705904306
)
1
2
3
4

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
1
2

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
1
2

G_2 generator is generated by :

    P2 = (
        438374926219350099854919100077809681842783509163790991847867546339851681564223481322252708 +
        i * 37620953615500480110935514360923278605464476459712393277679280819942849043649216370485641,
        37437409008528968268352521034936931842973546441370663118543015118291998305624025037512482 +
        i * 424621479598893882672393190337420680597584695892317197646113820787463109735345923009077489
    )
1
2
3
4
5
6

# 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>>
1
2
3

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
1

where s represents Y as follow:

    |  `s'`  | `Y`                      |
    |--------|--------------------------|
    | `0x00` | Point at infinity        |
    | `0x02` | Solution with `y` even   |
    | `0x03` | Solution with `y` odd    |
1
2
3
4
5

Compression operation from affine coordinate is trivial:

    s = 0x02 | (s & 0x01)
1

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 transferring 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

Copyright and related rights waived via CC0 (opens new window).

▲ Powered by Vercel