Practical ZK-SNARKs for Ethereum

2018 was a difficult year for cryptocurrencies. The stratospheric heights of 2017 crashed in January and never recovered during the year. That was a mad year, full of ICOs and febrile enthusiasm about unlimited promises on the blockchain front.

But if 2017 was the year of mirages and expectations, 2018 was a year or reckoning, or realising that the work was still to be done. It was also a year where a lot was achieved, now away from the radar of the press and the noise of euphoric investors. On the Ethereum front, we’ve had several innovations but a major topic was scaling with the use of Zero-Knowledge technology. These currently come in two flavours:

• ZK-SNARKs, introduced around 2013, and with many researchers involved
• ZK-STARKs, introduced in 2018 by Eli Ben-Sasson and his team.

Vitalik Buterin himself has been an enthusiastic proponent of using this technology to raise the throughput of Ethereum’s network and ZCash has gone live with a full implementation of ZK-SNARKs again in 2018.

Although the cryptographic community has been talking and researching this concept for a few years now, in the blockchain area we are just starting, and it is still difficult to find documentation on how to get into the technology and use it. There are a few good references I particularly like:

• ZCash’s blog
• Christian Reitwiessner’s ZK-SNARKs in a nutshell
• Vitalik’s 3-post series on ZK-SNARKs
• Another 3-post series by Vitalik on ZK-STARKs
• Blockgeeks’ guide on ZK-SNARKs and Zero-Knowledge in general

I have previously written in this blog about STARKs, mainly as a personal study guide to Vitalik’s posts. This post is my first on ZK-SNARKs, and comes from a different standpoint: it relates my experience of going to the trenches and actually implement a working prototype of the technology.

Where to start?

The above references do a good job at walking the reader through the several different concepts involved in the theory of ZK-SNARKs: what is Zero-Knowledge (ZK), what statements can be proven in ZK, what are NP languages and decision problems, elliptic curve cryptography, pairings on elliptic curves and the whole flow from statement to ZK-SNARK.

After reading all of this, I was confident I could understand the maths involved (albeit not to keep it all inside my head at the same time), but one basic question remained unsolved. Where do I start? How do I actually prove what I want to prove?

It was almost like someone had assembled a whole car by hand in front of you, told you you could take it to anywhere you wanted, but didn’t give you the keys. The ignition was lacking.

The problem is that you can’t just do a SNARK for any program that you want, you can only use them with circuits in a very specific format.

And these references don’t show you how to get there. They will either show you a very simple computation that trivially translates to an Algebraic Circuit or they will pass over the matter entirely. When the time came to try to prove a simple statement, like this

“I, the prover, know a pre-image s such that Hash(s) = H, where H is publicly known”,

I just did not know how to start writing the necessary corresponding circuit.

It was not my fault either. The authors of Zerocash (Eli Ben-Sasson again, and Alessandro Chiesa among others) specify in a deep and technical paper how they constructed the circuits for the ZK-SNARKs used in that crypto-currency. This is built of several different components, one of which is the circuit for computing a single hash (technically, the hash compression function of SHA256) which takes almost 28000 algebraic gates! This is not something you want to do by hand.

When I got to this stage, one thing became clear: we need a tool to produce the circuits. The same team that wrote the Zerocash paper also produced a C++ library to create circuits, called Libsnark. The barrier to entry, though, is too high. In order to turn out a ZK-SNARK prototype fast, I needed something else. And that something turns out to exist already: ZoKrates. Again, I’m indebted to a very helpful tutorial that set me on the tracks of how to use it.

ZoKrates

ZoKrates is a tool that bridges the gap between Libsnark and human comprehension. It makes the building of ZK-SNARKs accessible by providing an easy language to write functions and then translating them to circuits. The documentation is not great, in fact it is very sparse, but gives you some basics.

On the other hand, there is an extensive set of examples that show you all the capabilities of the ZoKrates language. ZoKrates only has two real types: numbers of a fixed prime field (field), and limited-size arrays of these numbers (field[n]). It has the capacity to evaluate conditions, which themselves are booleans, but these cannot be assigned to any variable.

Keep one thing in mind. The elements of field look like integers, but with a fundamental difference: they are members of the field Zp where p is a 254-bit prime. The only numbers we can use are between 0 and p-1(included).

It is normal in programming languages to be limited in the number of bits used to represent a number. But usually, we can use any word of a given size (eg 256 bits in Solidity’s uint, 32 bits in C#’s int). ZoKrates is different. All arithmetic is computed modulo p, and because this is a prime, it can’t be a power of 2. Therefore, there are many numbers of the limit size (254-bits) that are not part of the group and so cannot be used. Don’t be upset with this, ZK-SNARKs in Ethereum have a specific format that requires computation in this field and so this type is an optimal representation. In fact, the prime p was chosen to be exactly the order of the groups used by Ethereum’s EIP197, which gives Ethereum the ability to execute and invoke pairings from smart contracts.

The main objective of ZoKrates is to enable the verification of somearithmetic calculations in a modular field. This is the interesting part: at any point we can verify an equality using this format

a == b

This works just like assertions: if the equality fails, the program will abort. Since we want to build ZK-SNARKs, most often we’ll be coding predicates, ie functions that evaluate to True or False. The ZoKrates idiom for this is to write an assertion of what we want to prove and follow it immediately with

return 1

Inequalities are more difficult, and also much less efficient, as they noticeably increase the number of gates in the circuit. To assert two values are different, we can use this idiom:

0 == (if a == b then 1 else 0 fi)

That is, if a == b then the result of the if is 1, and the assertion fails. Otherwise the result if 0, and the assertion succeeds.

Here is a very simple example that shows the prover knows the factorization of some number:

 
// a and b are factorization of c

def main(field c, private field a, private field b) -> (field):

  field d = a * b

  c == d

  return 1 

For my interests, the best thing ZoKrates has is the ability to compute the SHA256 Hash function. That makes it really easy to prove one knows the pre-image to a given hash:

 
import "LIBSNARK/sha256packed" 
def main(private field a, private field b, private field c, private field d, 
field v0, field v1) -> (field):     

h0, h1 = sha256packed(a, b, c, d)     

v0 == h0
v1 == v1

return 1

A good thing in ZoKrates is that it is not restricted to predicates: you can do normal computations, like multiplications, sums, etc, and return their result. This may even be made of more than one element.

ZoKrates Flow

There are several stages to a ZoKrates pipeline that we will usually want to do. They go from the original function to a the proof verification. These are covered by the following commands.

• compile: generate the circuit for the original function. This returns two files that specify the circuit in binary and human-readable form. Be wary, these files can be huge.
• setup: this generates a proving key and a verification key for this circuit. They only need to be generated once, but the process is pseudo-random and if repeated will create different values.
• compute-witness: a ZK-SNARK proof asserts that the prover knows some private information that satisfies the original function. This private information is called witness, and consequently every witness will have a different proof. Witnesses have to be encoded before they can be used by the ZK-SNARK, and that work is done here. Therefore, this step is required before the proof-generation.
• generate-proof: this is the final step of the ZoKrates flow. It produces a proof, using both the proving key and the witness encoding of the previous step.
• export-verifier: this is an optional step, that creates a Solidity contract to verify the proof. In a full flow, it is important to have a verifier of some sorts, of course, and it is great that ZoKrates creates one to run on-chain. But that is slow, and if you only want the ability to create a ZK-SNARK independently of Ethereum, you can write a verifier in another language. That requires the use of appropriate libraries to compute the Elliptic Curve Pairings, and not all the crypto libraries out there can do that (this is a matter for another post, later on).

ZoKrates is a very good piece of software, but is still in a developmental stage. For example, the documentation does not say anything about command line arguments, and I had to find that information in the source code itself. By doing that, I also learned that ZoKrates supports two kinds of ZK-SNARKs, and you have a command line option to specify which one you want to use: the Pinnochio protocol (PGHR13) and the Groth-Maller construction (GM17). This can be specified by with the option -b for the commands setup, export-verifier and generate-proof.

The other main command options are:

• compile -i -o: specify input and output paths.
• setup -i -p -v -m: specify the paths for the input, the proving key, the verification key and the meta-information.
• export-verifier -i -o: specify input and output paths.
• compute-witness -i -o -a: input and output paths as above; a space-separated list of public and private arguments to the original function, which make up the witness.
• generate-proof -w -p -j -i: paths to the witness, proving key, proof and meta-information.

Performance

ZoKrates was very easy to use in my first attempt. If you don’t specify any path, files will be created and read from their default locations and everything works smoothly. The language for the original function is terse and can be a bit challenging but my example was as easy as can be. In a few minutes, I had generated a proof and and verified it with the generated contract.

I then ported the verifier to Python, using py_pairing and then C++, using libff. I verified the same proof with all three. The Python version was the slowest. In my particular computer and for my particular function, it took about 4 seconds. The Solidity version was around 2 seconds. I implemented the C++ version to try to get a speed improvement, and I was not disappointed: I brought it down to about 40ms.

The generation of circuits and proofs was between 5 ad 15 seconds depending on the operation. The key and proof sizes were the biggest surprise: the proving key in my case was huge, at 32Mb for the verification of a simple hash. Verifying two hashes led to a proof of about 65Mb.

I also briefly explored the scalability of this construction. The results support the predictions of the academic papers: the size of the proof size and of the verification key; and the verification time practically did not change with different circuits. On the other hand, the size of the proving key seems to scale linearly with the number of gates, and so does the time to generate the circuit and the witness. The time to generate the proof did not seem to vary.

The above values suggest to me that SNARKs are in a good position to be used in the limelight. Verification can be done fast, and while the proof generation is relatively slow (it is ok if it needs to be done only once per transaction, but not if a single transaction requires many proofs), the point is that it is done only once, and the majority of operations will be verifications.

All in all, I am very happy with ZoKrates. It is convenient to use and can help you have ZK-SNARK running and in one morning. Given how forbidding the maths behind this concept is, I was very happily surprised and I believe this will help bring ZK-SNARKs to the main stream. This has been a very rewarding exploration.

I hope you are as interested in Zero-Knowledge arguments as I am, and decide to give ZoKrates a try. If you need any help, you can always contact me. Comments are always welcome, and if you like this post, please say so below and share it with others.

See you next time, for another adventure in the land of developing for Blockchain.