HomeEIPs
EIPsEIP-1895
EIP-1895

Support for an Elliptic Curve Cycle

StagnantStandards Track: Core
Created: 2018-03-31
Alexandre Belling <alexandrebelling8@gmail.com>
DiscussionsOriginal linkEdit
1 min read

EIP-1895 proposes the implementation of support for an elliptic curve cycle in Ethereum. The idea is to use a cycle of elliptic curves to improve the efficiency of recursive SNARKs, which are used for privacy-preserving transactions. The proposal suggests that only one curve from the cycle needs to be implemented, and the choice should be based on speed rather than security, as the overall security of the SNARK does not depend on the curve used for verification. Proper benchmarks will be conducted to determine the best curve and to price the operations in gas. The proposal references two papers on cycles of elliptic curves and suggests using the go-boojum and libff libraries for implementation. The proposal also mentions the coda cryptocurrency protocol, which uses a lightweight, constant-sized blockchain. The document includes a waiver of copyright and related rights via CC0.

Video
Anyone may contribute to propose contents.
Go propose
Original

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

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.

Copyright and related rights waived via CC0.

Further reading
Anyone may contribute to propose contents.
Go propose
Adopted by projects
Anyone may contribute to propose contents.
Go propose

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
Serve EIP builders, scale Ethereum.
Resources
GitHub
Supported by