ERC-2494: Baby Jubjub Elliptic Curve

Simple Summary

This proposal defines Baby Jubjub, an elliptic curve designed to work inside zk-SNARK circuits in Ethereum.

Abstract

Two of the main issues behind why blockchain technology is not broadly used by individuals and industry are scalability and privacy guarantees. With a set of cryptographic tools called zero-knowledge proofs (ZKP) it is possible to address both of these problems. More specifically, the most suitable protocols for blockchain are called zk-SNARKs (zero-knowledge Succinct Non-interactive ARguments of Knowledge), as they are non-interactive, have succinct proof size and sublinear verification time. These types of protocols allow proving generic computational statements that can be modelled with arithmetic circuits defined over a finite field (also called zk-SNARK circuits).

To verify a zk-SNARK proof, it is necessary to use an elliptic curve. In Ethereum, the curve is alt_bn128 (also referred as BN254), which has primer order r. With this curve, it is possible to generate and validate proofs of any F_r-arithmetic circuit. This EIP describes Baby Jubjub, an elliptic curve defined over the finite field F_r which can be used inside any zk-SNARK circuit, allowing for the implementation of cryptographic primitives that make use of elliptic curves, such as the Pedersen Hash or the Edwards Digital Signature Algorithm (EdDSA).

Motivation

A zero knowledge proof (ZKP) is a protocol that enables one party, the prover, to convince another, the verifier, that a statement is true without revealing any information beyond the veracity of the statement. Non-Interactive ZKPs (NIZK) are a particular type of zero-knowledge proofs in which the prover can generate the proof without interaction with the verifier. NIZK protocols are very suitable for Ethereum applications, because they allow a smart contract to act as a verifier. This way, anyone can generate a proof and send it as part of a transaction to the smart contract, which can perform some action depending on whether the proof is valid or not. In this context, the most preferable NIZK are zk-SNARK (Zero-knowledge Succinct Non Interactive ARgument of Knowledge), a set of non-interactive zero-knowledge protocols that have succinct proof size and sublinear verification time. The importance of these protocols is double: on the one hand, they help improve privacy guarantees, and on the other, they are a possible solution to scalability issues (e.g. see zk-Rollup project).

Like most ZKPs, zk-SNARKs permit proving computational statements. For example, one can prove things like: the knowledge of a private key associated with a certain public key, the correct computation of a transaction, or the knowledge of the preimage of a particular hash. Importantly, one can do these things without leaking any information about the statements in question. In other words, without leaking any information about the private key, the transaction details, or the value of the preimage. More specifically, zk-SNARKs permit proving any computational statement that can be modelled with an F_r-arithmetic circuit, a circuit consisting of set of wires that carry values from the field F_r and connect them to addition and multiplication gates mod r. This type of circuits are often called zk-SNARK circuits.

The implementation of most zk-SNARK protocols (e.g. [Pinnochio] and [Groth16]) make use of an elliptic curve for validating a proof. In Ethereum, the curve used is alt_bn128 (also referred as BN254), which has prime order r. While it is possible to generate and validate proofs of F_r-arithmetic circuits with BN254, it is not possible to use BN254 to implement elliptic-curve cryptography within these circuits. To implement functions that require the use of elliptic curves inside a zk-SNARK circuit – such as the Pedersen Hash or the Edwards Digital Signature Algorithm (EdDSA) – a new curve with coordinates in F_r is needed. To this end, we propose in this EIP Baby Jubjub, an elliptic curve defined over F_r that can be used inside any F_r-arithmetic circuit. In the next sections we describe in detail the characteristics of the curve, how it was generated, and which security considerations were taken.

    inputs                zk-SNARK (alt_bn128)             output
            +--------------------------------------------+
            |   +--------------------+                   |
        --->|   | EdDSA (Baby Jubjub)|                   |
            |   +--------------------+                   | 
        --->|                                            |--->
            |          +-----------------------------+   |
        --->|          | Pedersen Hash (Baby Jubjub) |   |
            |          +-----------------------------+   |
            +--------------------------------------------+

Specification

Definitions

Let F_r be the prime finite field with r elements, where

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617

Let E be the twisted Edwards elliptic curve defined over F_r described by equation

ax^2 + y^2 = 1 + dx^2y^2

with parameters

a = 168700
d = 168696

We call Baby Jubjub the curve E(F_r), that is, the subgroup of F_r-rational points of E.

Order

Baby Jubjub has order

n = 21888242871839275222246405745257275088614511777268538073601725287587578984328

which factors in

n = h x l

where

h = 8
l = 2736030358979909402780800718157159386076813972158567259200215660948447373041

The parameter h is called cofactor and l is a prime number of 251 bits.

Generator Point

The point G = (x,y) with coordinates

x = 995203441582195749578291179787384436505546430278305826713579947235728471134
y = 5472060717959818805561601436314318772137091100104008585924551046643952123905

generates all n points of the curve.

Base Point

The point B = (x,y) with coordinates

x = 5299619240641551281634865583518297030282874472190772894086521144482721001553
y = 16950150798460657717958625567821834550301663161624707787222815936182638968203

generates the subgroup of points P of Baby Jubjub satisfying l * P = O. That is, it generates the set of points of order l and origin O.

Arithmetic

Let P1 = (x1, y1) and P2 = (x2, y2) be two arbitrary points of Baby Jubjub. Then P1 + P2 = (x3, y3) is calculated in the following way:

x3 = (x1*y2 + y1*x2)/(1 + d*x1*x2*y1*y2)
y3 = (y1*y2 - a*x1*x2)/(1 - d*x1*x2*y1*y2)

Note that both addition and doubling of points can be computed using a single formula.

Rationale

The search for Baby Jubjub was motivated by the need for an elliptic curve that allows the implementation of elliptic-curve cryptography in F_r-arithmetic circuits. The curve choice was based on three main factors: type of curve, generation process and security criteria. This section describes how these factors were addressed.

Form of the Curve

Baby Jubjub is a twisted Edwards curve birationally equivalent to a Montgomery curve. The choice of this form of curve was based on the following facts:

1. The Edwards-curve Digital Signature Scheme is based on twisted Edwards curves.
2. Twisted Edwards curves have a single complete formula for addition of points, which makes the implementation of the group law inside circuits very efficient [Crypto08/013, Section 6].
3. As a twisted Edwards curve is generally birationally equivalent to a Montgomery curve [Crypto08/13,Theorem 3.2], the curve can be easily converted from one form to another. As addition and doubling of points in a Montgomery curve can be performed very efficiently, computations outside the circuit can be done faster using this form and sped up inside circuits by combining it with twisted Edwards form (see here) for more details).

Generation of the Curve

Baby Jubjub was conceived as a solution to the circuit implementation of cryptographic schemes that require elliptic curves. As with any cryptographic protocol, it is important to reduce the possibility of a backdoor being present. As a result, we designed the generation process to be transparent and deterministic – in order to make it clear that no external considerations were taken into account, and to ensure that the process can be reproduced and followed by anyone who wishes to do so.

The algorithm chosen for generating Baby Jubjub is based in the criteria defined in [RFC7748, Appendix A.1] and can be found in this github repository. Essentially, the algorithm takes a prime number p = 1 mod 4 and returns the lowest A>0 such that A-2 is a multiple of 4 and such that the set of solutions in F_p of y^2 = x^3 + Ax^2 + x defines a Montgomery curve with cofactor 8.

Baby Jubjub was generated by running the algorithm with the prime

r = 21888242871839275222246405745257275088548364400416034343698204186575808495617,

which is the order of alt_bn128, the curve used to verify zk-SNARK proofs in Ethereum. The output of the algorithm was A=168698. Afterwards, the corresponding Montgomery curve was transformed into twisted Edwards form. Using SAGE libraries for curves, the order n of the curve and its factorization n = 8*l was calculated.

• Choice of generator : the generator point G is the point of order n with smallest positive x-coordinate in F_r.
• Choice of base point: the base point B is chosen to be B = 8*G, which has order l.

Security Criteria

It is crucial that Baby Jubjub be safe against well-known attacks. To that end, we decided that the curve should pass SafeCurves security tests, as they are known for gathering the best known attacks against elliptic curves. Supporting evidence that Baby Jubjub satisfies the SafeCurves criteria can be found here.

Backwards Compatibility

Baby Jubjub is a twisted Edwards elliptic curve birational to different curves. So far, the curve has mainly been used in its original form, in Montomgery form, and in another (different representation) twisted Edwards form – which we call the reduced twisted Edwards form.

Below are the three representations and the birational maps that make it possible to map points from one form of the curve to another. In all cases, the generator and base points are written in the form (x,y).

Forms of the Curve

All generators and base points are written in the form (x,y).

Twisted Edwards Form (standard)

• Equation: ax^2 + y^2 = 1 + dx^2y^2
• Parameters: a = 168700, d = 168696
• Generator point:

    (995203441582195749578291179787384436505546430278305826713579947235728471134, 5472060717959818805561601436314318772137091100104008585924551046643952123905)
  

• Base point:

    (5299619240641551281634865583518297030282874472190772894086521144482721001553, 16950150798460657717958625567821834550301663161624707787222815936182638968203)
  

Montgomery Form

• Equation: By^2 = x^3 + A x^2 + x
• Parameters: A = 168698, B = 1
• Generator point:

    (7, 4258727773875940690362607550498304598101071202821725296872974770776423442226)
  

• Base point:

    (7117928050407583618111176421555214756675765419608405867398403713213306743542, 14577268218881899420966779687690205425227431577728659819975198491127179315626)
  

Reduced Twisted Edwards Form

• Equation: a' x^2 + y^2 = 1 + d' x^2y^2
• Parameters:

    a' = -1 
    d' = 12181644023421730124874158521699555681764249180949974110617291017600649128846
  

• Generator point:

    (4986949742063700372957640167352107234059678269330781000560194578601267663727, 5472060717959818805561601436314318772137091100104008585924551046643952123905)
  

• Base point:

    (9671717474070082183213120605117400219616337014328744928644933853176787189663, 16950150798460657717958625567821834550301663161624707787222815936182638968203)
  

Conversion of Points

Following formulas allow to convert points from one form of the curve to another. We will denote the coordinates

• (u, v) for points in the Montomgery form,
• (x, y) for points in the Twisted Edwards form and
• (x', y') for points in reduced Twisted Edwards form.

Note that in the last conversion – from Twisted Edwards to Reduced Twisted Edwards and back – we also use the scaling factor f, where:

f = 6360561867910373094066688120553762416144456282423235903351243436111059670888

In the expressions one can also use directly -f, where:

-f = 15527681003928902128179717624703512672403908117992798440346960750464748824729

Montgomery –> Twisted Edwards

(u, v) --> (x, y)

x = u/v
y = (u-1)/(u+1)

Twisted Edwards –> Montgomery

(x, y) --> (u, v)

u = (1+y)/(1-y) 
v = (1+y)/((1-y)x)

Montgomery –> Reduced Twisted Edwards

(u, v) --> (x', y')

x' = u*(-f)/v 
y' = (u-1)/(u+1) 

Reduced Twisted Edwards –> Montgomery

(x', y') --> (u, v)

u = (1+y')/(1-y')
v = (-f)*(1+y')/((1-y')*x')

Twisted Edwards –> Reduced Twisted Edwards

(x, y) --> (x', y')

x' = x*(-f)
y' = y

Reduced Twisted Edwards –> Twisted Edwards

(x', y') --> (x, y)

x = x'/(-f)
y = y'

Security Considerations

This section specifies the safety checks done on Baby Jubjub. The choices of security parameters are based on SafeCurves criteria, and supporting evidence that Baby Jubjub satisfies the following requisites can be found here.

Curve Parameters

Check that all parameters in the specification of the curve describe a well-defined elliptic curve over a prime finite field.

• The number r is prime.
• Parameters a and d define an equation that corresponds to an elliptic curve.
• The product of h and l results into the order of the curve and the G point is a generator.
• The number l is prime and the B point has order l.

Elliptic Curve Discrete Logarithm Problem

Check that the discrete logarithm problem remains difficult in the given curve. We checked Baby Jubjub is resistant to the following known attacks.

• Rho method [Blake-Seroussi-Smart, Section V.1]: we require the cost for the rho method, which takes on average around 0.886*sqrt(l) additions, to be above 2^100.
• Additive and multiplicative transfers [Blake-Seroussi-Smart, Section V.2]: we require the embedding degree to be at least (l − 1)/100.
• High discriminant [Blake-Seroussi-Smart, Section IX.3]: we require the complex-multiplication field discriminant D to be larger than 2^100.

Elliptic Curve Cryptography

• Ladders [Montgomery]: check the curve supports the Montgomery ladder.
• Twists [SafeCurves, twist]: check it is secure against the small-subgroup attack, invalid-curve attacks and twisted-attacks.
• Completeness [SafeCurves, complete]: check if the curve has complete single-scalar and multiple-scalar formulas.
• Indistinguishability [IACR2013/325]: check availability of maps that turn elliptic-curve points indistinguishable from uniform random strings.

Test Cases

Test 1 (Addition)

Consider the points P1 = (x1, y1) and P2 = (x2, y2) with the following coordinates:

x1 = 17777552123799933955779906779655732241715742912184938656739573121738514868268
y1 = 2626589144620713026669568689430873010625803728049924121243784502389097019475

x2 = 16540640123574156134436876038791482806971768689494387082833631921987005038935
y2 = 20819045374670962167435360035096875258406992893633759881276124905556507972311

Then their sum P1+P2 = (x3, y3) is equal to:

x3 = 7916061937171219682591368294088513039687205273691143098332585753343424131937
y3 = 14035240266687799601661095864649209771790948434046947201833777492504781204499

Test 2 (Doubling)

Consider the points P1 = (x1, y1) and P2 = (x2, y2) with the following coordinates:

x1 = 17777552123799933955779906779655732241715742912184938656739573121738514868268,
y1 = 2626589144620713026669568689430873010625803728049924121243784502389097019475

x2 = 17777552123799933955779906779655732241715742912184938656739573121738514868268
y2 = 2626589144620713026669568689430873010625803728049924121243784502389097019475

Then their sum P1+P2 = (x3, y3) is equal to:

x3 = 6890855772600357754907169075114257697580319025794532037257385534741338397365
y3 = 4338620300185947561074059802482547481416142213883829469920100239455078257889

Test 3 (Doubling the identity)

Consider the points P1 = (x1, y1) and P2 = (x2, y2) with the following coordinates:

x1 = 0
y1 = 1

x2 = 0
y2 = 1

Then their sum P1+P2 = (x3, y3) results in the same point:

x3 = 0
y3 = 1

Test 4 (Curve membership)

Point (0,1) is a point on Baby Jubjub.

Point (1,0) is not a point on Baby Jubjub.

Test 5 (Base point choice)

Check that the base point B = (Bx, By) with coordinates

Bx = 5299619240641551281634865583518297030282874472190772894086521144482721001553
By = 16950150798460657717958625567821834550301663161624707787222815936182638968203

is 8 times the generator point G = (Gx, Gy), where

Gx = 995203441582195749578291179787384436505546430278305826713579947235728471134
Gy = 5472060717959818805561601436314318772137091100104008585924551046643952123905

That is, check that B = 8 x G.

Test 6 (Base point order)

Check that the base point B = (Bx, By) with coordinates

Bx = 5299619240641551281634865583518297030282874472190772894086521144482721001553
By = 16950150798460657717958625567821834550301663161624707787222815936182638968203

multiplied by l, where

l = 2736030358979909402780800718157159386076813972158567259200215660948447373041

results in the origin point O = (0, 1). This test checks that the base point B has order l.

Implementation

Arithmetic of Baby Jubjub and some cryptographic primitives using the curve have already been implemented in different languages. Here are a few such implementations:

• Python: https://github.com/barryWhiteHat/baby_jubjub_ecc
• JavaScript: https://github.com/iden3/circomlib/blob/master/src/babyjub.js
• Circuit (circom): https://github.com/iden3/circomlib/blob/master/circuits/babyjub.circom
• Rust: https://github.com/arnaucube/babyjubjub-rs
• Solidity: https://github.com/yondonfu/sol-baby-jubjub
• Go: https://github.com/iden3/go-iden3-crypto/tree/master/babyjub

Copyright

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Barry WhiteHat (@barryWhiteHat), Marta Bellés (@bellesmarta), Jordi Baylina (@jbaylina), "ERC-2494: Baby Jubjub Elliptic Curve [DRAFT]," Ethereum Improvement Proposals, no. 2494, January 2020. [Online serial]. Available: https://eips.ethereum.org/EIPS/eip-2494.