This proposal defines Baby Jubjub, an elliptic curve designed to work inside zk-SNARK circuits in Ethereum.
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).
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.
Let F_r be the prime finite field with r elements, where
Let E be the twisted Edwards elliptic curve defined over F_r described by equation
with parameters
We call Baby Jubjub the curve E(F_r), that is, the subgroup of F_r-rational points of E.
Baby Jubjub has order
which factors in
where
The parameter h is called cofactor and l is a prime number of 251 bits.
The point G = (x,y) with coordinates
generates all n points of the curve.
The point B = (x,y) with coordinates
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.
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:
Note that both addition and doubling of points can be computed using a single formula.
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:
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.
G is the point of order n with smallest positive x-coordinate in F_r.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.
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).
All generators and base points are written in the form (x,y).
Twisted Edwards Form (standard)
ax^2 + y^2 = 1 + dx^2y^2a = 168700, d = 168696Montgomery Form
By^2 = x^3 + A x^2 + xA = 168698, B = 1Reduced Twisted Edwards Form
a' x^2 + y^2 = 1 + d' x^2y^2Following 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:
In the expressions one can also use directly -f, where:
Montgomery --> Twisted Edwards
Twisted Edwards --> Montgomery
Montgomery --> Reduced Twisted Edwards
Reduced Twisted Edwards --> Montgomery
Twisted Edwards --> Reduced Twisted Edwards
Reduced Twisted Edwards --> Twisted Edwards
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.
r is prime.a and d define an equation that corresponds to an elliptic curve.h and l results into the order of the curve and the G point is a generator.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.
0.886*sqrt(l) additions, to be above 2^100.(l − 1)/100.D to be larger than 2^100.Elliptic Curve Cryptography
Test 1 (Addition)
Consider the points P1 = (x1, y1) and P2 = (x2, y2) with the following coordinates:
Then their sum P1+P2 = (x3, y3) is equal to:
Test 2 (Doubling)
Consider the points P1 = (x1, y1) and P2 = (x2, y2) with the following coordinates:
Then their sum P1+P2 = (x3, y3) is equal to:
Test 3 (Doubling the identity)
Consider the points P1 = (x1, y1) and P2 = (x2, y2) with the following coordinates:
Then their sum P1+P2 = (x3, y3) results in the same point:
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
is 8 times the generator point G = (Gx, Gy), where
That is, check that B = 8 x G.
Test 6 (Base point order)
Check that the base point B = (Bx, By) with coordinates
multiplied by l, where
results in the origin point O = (0, 1). This test checks that the base point B has order l.
Arithmetic of Baby Jubjub and some cryptographic primitives using the curve have already been implemented in different languages. Here are a few such implementations:
Copyright and related rights waived via CC0.