A few days ago I wrote about the Jubjub elliptic curve that takes its name from Lewis Carroll’s poem Jabberwocky. I’ve also written about a slightly smaller but still enormous curve named Baby Jubjub.
This post introduces Tiny Jubjub, an elliptic curve with 20 elements, one designed to have some properties in common with its gargantuan counterparts, but small enough to work with by hand. As far as I know, the curve was created for the book The Moon Math Manual to zk-SNARKs and may not be known anywhwere outside that book.
First, a word about the book. The math behind zero-knowledge proofs is complicated and unfamiliar to most, and has been called “moon math.” The “zk” in the title stands for zero-knowledge. SNARK stands for “succinct non-interactive argument of knowledge.” The book is an introduction to some of the mathematics and computer science used in the Zcash privacy coin.
Equation and size
The Tiny Jubjub curve, abbreviated TJJ, has Weierstrass form
y² = x³ + 8x + 8
and is defined over the field F13, the integers mod 13. As mentioned above, it has 20 points. This is interesting because it is close to Hesse’s upper bound on the number of points on an elliptic curve as a function of the field size. In all the examples in my post from a couple days ago the number of points on each curve was equal to slightly below the middle of the possible range.
Here’s a checkerboard plot of TJJ, like the plots given here.
Note that there are 19 blue squares above. Elliptic curves always have an extra point at infinity not shown.
Montgomery form
One thing Tiny Jubjub has in common with the better known Jubjub curves is that it has a Montgomery form. That is, there is a change of variables that puts the curve in the form
By² = x³ + Ax + b
with B(A² − 4) ≠ 0. Every elliptic curve in Montgomery form can be put in Weierstrass form, but not vice versa; Montgomery curves are special.
TJJ can be put in Montgomery form with A = 6 and B = 7.
Twisted Edwards form
Every elliptic curve that can be put into Montgomery form can also be put into twisted Edwards form
a x² + y² = 1 + d x² y²
with a ≠ 0 ≠ d.
TJJ can be put into Montgomery form with a = 3 and d = 8.
It’s useful when a curve can be put in twisted Edwards form because elliptic curve arithmetic can be implemented without branching logic for special cases.
SNARK friendly
TJJ is a SNARK-friendly curve, which is why it appears often in a book on zk-SNARKs. A curve is said to be SNARK friendly if in its twisted Edwards form a is a quadratic residue and d is not. In our case, that means
x² = 3 mod 13
has a solution but
x² = 8 mod 13
does not. We can verify this with the following Python code.
>>> [x**2 % 13 for x in range(13)]
[0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1]
Notice that 3 is in the output and 8 is not.
Related posts
The post Tiny Jubjub first appeared on John D. Cook.