EIP-1895: Support for an Elliptic Curve Cycle Ethereum Improvement Proposals AllCoreNetworkingInterfaceERCMetaInformational 🚧 Stagnant Standards Track: Core EIP-1895: Support for an Elliptic Curve Cycle Authors Alexandre Belling  Created 2018-03-31 Discussion Link https://ethresear.ch/t/reducing-the-verification-cost-of-a-snark-through-hierarchical-aggregation/5128 Table of Contents Simple Summary Abstract Motivation Specification The curve MNT4 definition The operations and gas cost Encoding Edge cases Rationale Test Cases References Implementation Copyright 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 / <> 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 = <> MNT_X_MUL = <> MNT_X_PAIRING = <> 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 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. Copyright Copyright and related rights waived via CC0. Citation Please cite this document as: Alexandre Belling , "EIP-1895: Support for an Elliptic Curve Cycle [DRAFT]," Ethereum Improvement Proposals, no. 1895, March 2018. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-1895. Ethereum Improvement Proposals Ethereum Improvement Proposals ethereum/EIPs Ethereum Improvement Proposals (EIPs) describe standards for the Ethereum platform, including core protocol specifications, client APIs, and contract standards.