Efficient ECC in zkSNARKs using ZoKrates

Elliptic Curve Cryptography (ECC) is a powerful tool that has many applications in the blockchain space and cryptography in general. With one of the last releases, we added support for efficient ECC-based cryptographic primitives inside a zkSNARK construction.

ZoKrates is a toolbox for zkSNARKs on Ethereum. It includes an easy-to-use  domain-specific language for developers to leverage the power of  zero-knowledge proofs in their decentralized applications.

Elliptic Curve Cryptography (ECC) is a powerful tool that has many  applications in the blockchain space and cryptography in general. With one of the last releases, we added support for efficient ECC-based cryptographic primitives inside a zkSNARK construction. We outlined how to use these primitives in this previous blog post.

In  this blog post, we provide theoretical background with regards to this  process. We explain how to construct an elliptic curve, which is  efficient in zkSNARKs. We start by understanding the zkSNARK prime field  arithmetics programming model before providing an introduction to  elliptic curves. We then describe how to construct an efficient elliptic  curve on top of this abstraction and how to use this curve within  ZoKrates.

In a followup blog post, we will dig deeper into the applications of  elliptic curve cryptography in zkSNARKs, e.g., more efficient hashing  and digital signature schemes.

While we try to provide all the information necessary to follow along,  this blog post assumes some knowledge of zkSNARKs and the underlying  mathematics. If you are interested in learning more about the  mathematical foundations of zkSNARKs, you may find the following blog  posts by the community helpful: [1], [2], [3].

Disclaimer: The goal of this document is to be an  introduction to the matter and hence not all theory is covered  rigorously. Perfect fidelity could interfere with the understanding of  the main concepts when dealing with a complex new topic.

zkSNARK Programming — Arithmetics in prime fields

Before diving into elliptic curves and their construction, let’s quickly recap the programming model of zkSNARKs.

Any computation that you want to prove with a zkSNARK has to be  expressed as arithmetic operations on a finite field. More specifically,  this finite field is a prime field. You can think of it as a set of  natural numbers smaller than a huge prime:

$\mathbb{F}_p = \mathbb{Z}\\,mod\\, p$

This set has two basic arithmetic operations, addition and multiplication, which are commutative and associative and together fulfill the distributive law:

$$a + b = c,(mod\\, p), \quad a,b \in \mathbb{F}_p \\ a * b = c,(mod\\, p), \quad a,b \in \mathbb{F}_p.$$

This  may look complex, but it simply says that you can add and multiply  numbers as you’re used to; however, you need to apply the mod operation afterwards. The operations of a field always have an inverse:  Hence, you can also subtract and divide. Note, however, that the division may behave unlike you’d expect.

Fortunately,  when working with ZoKrates, you do not need to take care of the  translation into prime field arithmetics. ZoKrates does all the magic  for you as part of the compilation process in the background and  provides an easy to use programming abstraction. Hence, the following  ZoKrates DSL code

def f(x):
def main(field a, field b) -> (field):
    field result = a + b
    return result

is actually computing a+b (mod p).

The important takeaway of this section is that in zkSNARK programming all variables are field elements and we perform all arithmetic operations modulo a large prime number p.

The prime field we work in when programming zkSNARKs is defined by the elliptic curve chosen to implement a zkSNARK proving system. To be more precise, the prime p which represents the field modulus is defined by the group order r of the elliptic curve. This will become clearer after elliptic curves have been introduced in the following section.

Ethereum provides pre-compiled contracts for the BN128 (also known as BN254) curve, which enable cheap curve operation on the blockchain. Operations inside a zkSNARK program, constructed using that curve, will wrap around the prime:

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

Elliptic Curves in 5 Minutes

Now, that we know which operations are available to us in zKSNARKs, let’s brielfy look at the core properties of elliptic curves, so we know what we need to implement.

From a high-level perspective, an elliptic curve is something very simple: A finite cyclic group. A group is a set with only one operation that fulfills closure, associativity, identity and invertibility. That’s just a fancy way of saying we have an “addition” operation which obeys all the basic arithmetic rules we’re intuitively used to. A finite group is a group with a finite number of elements. We refer to this finite number of elements in the group as the group’s order r.

What’s peculiar about elliptic curves is the way the elements in this group look and how the “addition” operation is defined: An element of an elliptic curve is a pair of prime field elements (remember, we know those from before!). Fun math fact: Since the prime field is finite, the set of pairs is also finite, which directly implies finiteness of the group constructed on top.

To be elements of the group, i.e., the elliptic curve, these pairs need to satisfy an elliptic curve equation that looks like this:

$y^{2}=x^{3}+ax+b$

However, for the purpose of this post, we do not need to bother about this too much. What is important to understand is that given an elliptic curve the points of that curve are the elements of the corresponding finite group. It’s size is defined by the number of points that satisfy the equation above. Furthermore, the addition of two points for the chosen curve-family is a well-defined operation, for which an exceptionless closed-form formula exists. The addition of two points on the curve always results in a new point on the curve. As an example, here is the closed-form formula for adding two points on a particular type of curve:

$\left(x_{1}, y_{1}\right)+\left(x_{1}, x_{2}\right)=\left(\frac{x_{1} y_{2}+y_{1} x_{2}}{1+d x_{1} x_{2} y_{1} y_{2}}, \frac{y_{1} y_{2}-a x_{1} x_{2}}{1-d x_{1} x_{2} y_{1} y_{2}}\right) \quad(\bmod p)$

Since the elliptic curve is defined over the prime field $\mathbb{F}_p$ , i.e., the curve points (x,y) consist of field elements, the curve addition inherits the mod p operation. Unfortunately, modulo operations are costly in zkSNARKs as they rely on operations (comparisons, …) which are very inefficient. Is this game over for elliptic curves in zkSNARKS, or is there a way to get around this costly modulo operation?

Constructing an Embedded Curve

In the elliptic curve addition, we need to apply the modulo operation by the order of the field the curve is defined over, which we referred to as p. The alert reader might have spotted already that we can apply a nifty trick here: Wouldn’t it be convenient if the order of the field our elliptic curve is defined over would exactly match the modulus in our zkSNARK arithmetics? In other words, can we make sure the fields share the same p?

This is the rationale behind the sampling of an embedded curve. An embedded curve is an elliptic curve where the parameters have been sampled such that the underlying prime field 𝔽_p matches the group order of a host curve and hence the modulus in the arithmetic field.

Thus, EC operations on the embedded curve boil down to prime field arithmetics using the field-native mod p operations. In other words — we get the modulo operations during elliptic curve computations “for free”: With the matching moduli the formula for point addition is reduced to a couple of multiplications and additions. This makes embedded curve operations very efficient inside a SNARK.

An example of an embedded curve and the one we also use in ZoKrates is the so-called baby_JubJub elliptic curve. Here, curve parameters have been sampled such that the prime field 𝔽_p the baby_JubJub curve is defined over matches the group order of the BN128 curve used in Ethereum.

More details on baby_JubJub can be found here. Zcash also published a nice article describing the motivation behind the original JubJub curve, which follows the same rationale as baby_JubJub but is designed for a different modulus p (Zcash is not using the BN128 curve in the zkSNARK proof system anymore).

One important takeaway we want to highlight is that the baby_JubJub curve is just another program that is programmed in ZoKrates and then compiled as a zkSNARK. In case you don’t believe us feel free to have a look at the standard library of ZoKrates. Unsurprisingly, the point addition formula mentioned above is also there:

def f(x):
import "ecc/babyjubjubParams.code" as context
# Add two points on a twisted Edwards curve
# Curve parameters are defined with the last argument
# https://en.wikipedia.org/wiki/Twisted_Edwards_curve#Addition_on_twisted_Edwards_curves
def main(field[2] pt1, field[2] pt2, field[10] context) -> (field[2]):

    field a = context[0]
    field d = context[1]

    field u1 = pt1[0]
    field v1 = pt1[1]
    field u2 = pt2[0]
    field v2 = pt2[1]

    field uOut = (u1*v2 + v1*u2) / (1 + d*u1*u2*v1*v2)
    field vOut = (v1*v2 - a*u1*u2) / (1 - d*u1*u2*v1*v2)

    return [uOut, vOut]

Following this small detour, we now have access to efficient elliptic curve computations inside the zkSNARK and can leverage this for elliptic curve based constructions like Pedersen hashes and signatures inside a zkSNARK program.

Why secp256k1 and other curves don’t work

Ethereum uses a curve called secp256k1 for its signature scheme ECDSA (Elliptic Curve Digital Signature Algorithm). As the preceding link shows, the curve is defined over the finite field with the following order:

$r=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1$

Unsurprisingly, in this case, the order, r, does not match the modulo p we have in our zkSNARK construction.

In contrast to baby_JubJub, the field order, in that case, is way larger ( r > p), hence we can not map all values to elements on the given BN128 curve. There is a way to represent these values in their binary format, also called binary expansion, but this clearly is a very inefficient representation. Note that in this case we also wouldn’t get the modulo operation “for free” as the moduli don’t match.

The resulting constraint system would be so large that it makes it impractical to use Secp256k1 inside zkSNARKs, but fortunately, we now have baby_JubJub 🚀.

Conclusion

In  the first post of this series, we discussed some of the high-level  properties of elliptic-curve cryptography and showed how we can  construct efficient curves zkSNARKs.

Next  time, we will extend our zkSNARK Swiss army knife with the tools  necessary to compute efficient hashes in zkSNARKs. Until then!

Acknowledgment

We’d like to thank the following contributors and reviewers of the blog post: JacobEberhardt and Schaeff from the ZoKrates team, as well as sanchopansa and kobigurk. 🍻

In addition big thanks to all the people in the ZKP community. In particular to BarryWhitehat and HarryR for their work on integrating SNARKs into Ethereum. Also folks like Sean Bowe and the whole ECC and Zcash foundation team for their advancements and amazing implementations.