Zero-Knowledge Proofs: A Layman’s Introduction

For the past months, I’ve been immersed daily in a thrilling and cutting-edge world: that of Zero-Knowledge (ZK) proofs. It is a challenging field, and because of that, one I explore with great enjoyment. Today, I will talk a bit more about this quest of mine. The end goal is to implement a practical prototype that Artos (my employer) can use in their ticketing solutions for the Aventus protocol. I am not concerned with the final usage, for now, only with the ZK technology itself: what it is, what we can do with it and some of the tools available out there.

Zero-Knowledge Proofs

In my experience, people smile when they hear this name. Maybe I did too, I don’t remember, that was a long time ago. But it is not uncommon to hear jibes like this “I’m an expert at Zero-Knowledge, I know nothing about it”. Zero-Knowledge proofs are an amazing and counter-intuitive cryptographic concept, first proposed by Goldwasser, Micali and Rackoff in a paper that introduced the idea of interactive proof systems. The literature is extensive and if you want to know about the more modern and practical references and implementations, you’ll find ZKP Science very useful. In this post, I will stay at a very high level and ignore most of it. Although I have previously written two posts about SNARKs in Ethereum, I felt I needed to properly introduce the concept.

So what are ZK Proofs, and what can you do with them?

A Zero-Knowledge proof is a means by which you convince another person that you know something without showing it. More than that, such person learns nothing about your secret except that you have it. To give it a wordly flair, suppose you knew for sure that carrot juice in a certain specific formula would stop hair loss. With a Zero-Knowledge proof (if it could be applied in such circumstances) you would absolutely convince someone else that you knew that to be a fact, but that person would not know anything about how to make such a formula. To be fair, you might not know either, all you prove to know is that that relation exists and you can convince someone else of that. And because you made that proof in a Zero-Knowledge way, the next person cannot make use of the same proof to convince someone else (this may be different in a non-interactive proof, where the ability to prove may be transferred to the Verifier): you don’t give any knowledge about the proof, only that the proven statement is true. This is called a Zero-Knowledge Proof (of a statement). You could go one step further. You could prove to anyone else that you actually know the formula and it works, without revealing anything about the it. Now, not only that person is convinced of the truth of your statement, s/he is convinced as well that you know why, and that you probably can make lots of money with it if you wish, but they will still not know anything about that miraculous secret formula. This would be a Zero-Knowledge Proof of Knowledge.

Use Cases

There are several use cases for this, for example proving knowledge of a secret password; or possession of secret items that you don’t want to reveal or give to anyone (eg compromising photographs, secret legal documents). In cryptocurrencies, ZCash is using them to prove a private transaction of ZEC has correctly occurred without revealing any of the particulars (involved addresses and quantities). It is quite a powerful concept, but of course, you can’t use it to prove anything. There is a precise class of statements for which you can develop a ZK proof, mathematically described by the complexity class NP. I will not explain what that means in this post, but I can recommend some good books on Computational Complexity.

How does it work?

There are 3 roles that users can take in a Zero-Knowledge system. I will call them the Creator, the Prover and the Verifier. Some types of ZK systems don’t require a trusted Creator. ZCash does, and because there are important security considerations relating to this role, I will use these systems as example.

Creator

The Creator is the entity (it could be a single person or a group of them, for example), who sets up the system. It decides first of all what the system is designed to prove. A single instance of a Zero-Knowledge system only makes proofs of this specific kind. For example, in ZCash, this amounts to defining the criteria that establish a single transaction has been correctly formed. ZCash Proofs only prove that a transaction is correct. The important thing about these systems is that in creating this system some randomness is generated which should be kept secret forever. If a misbehaving person would take hold of that randomness, they could create forgeries of proofs and undermine the validity of the whole system. That is why ZCash has made it a point of creating a very public, very visible ceremony, to convince the whole world they have destroyed the randomness used to setup the ZK system for ZCash. The outcome of the system-setup is the creation of two keys: the proving key and the verification key, which are distributed to users according to their role.

Prover and Verifier

The two main roles in everyday functioning are the other two. Provers receive the proving key, and are able to create particular proofs of the type defined in the setup. Verifiers receive the verification key, and can validate that a certain proof is correct. You could have a user be simultaneously a Prover and a Verifier, if they use each of these roles with different keys: the point of ZK is, after all, for a Prover to convince a Verifier of something the Prover knows and the Verifier doesn’t. Note that all provers known the same proving key and all Verifiers know the same verification key. The system’s security is not impacted by this. ZCash, and the use case we are exploring in Artos, actually uses ZK Proofs of Knowledge (technically, Arguments instead of Proofs, but that is not relevant for this discussion). The Prover proves possession of some secret information. It is also typical that each proof relates to some information that is publicly known (certainly known by the Verifier) which differs from proof to proof. A single proof, then, is defined by this public information and the private information known only to the prover (and just that prover). The example given in the introduction is an instance of a proof, and perhaps the more general kind of statement that supports this proof would be “A certain formula of natural ingredients can cure this given ailment”.

Proofs and Verification

Now the magic begins: the Prover creates a proof with the use of the proving key and its instance parameters (the public and private inputs). This process is random: repeating it with the same inputs would create a different proof. The SNARK expands these parameters into a witness, that adds a specification of all the intermediate steps of the computation between the public and private inputs. The Verifier then takes this proof and the verification key, adds the public inputs and feeds everything to a verifier algorithm, to decide whether the proof is valid or not for that input. There is no randomness in this process: the result will always be the same (or as is typical in cryptographic proofs, it could be random but fail with negligible probability). I’d like to point out something that, although implicitly assumed, may not be obvious. The Prover and the Verifier have to agree on what they’re proving. This means that both know the statement that is to be proven and what the inputs to this statement represent. They both must know that the proof includes a specification of a unique type of computation, the only one chosen in the SNARK setup, and agree on what that computation represents. Without such an agreement, the proof would be an exercise in futility. The Verifier would confirm that the Prover knew an instance and a proving key that matched the verifier’s verification key, but without more information, those would be just a sequence of some numbers corresponding to public inputs plus some numbers corresponding to private inputs. There can be several statements that will have the same number of inputs in each of these categories, and without knowledge of the computation steps these would have no meaning. A second point to note is that SNARKs are non-interactive, and thas has a problem. Anyone can grab a proof and present it as if they had created it. The proof makes no statement about who presents it, it is not tied to any identity. The only thing it shows is that the Prover, whoever that was, knew a valid instance and a certain proving key. Whoever has the matching verification key can attest to that, but they can’t know if that is the same person that is giving them the proof. If the Verifier wants to have assurances about that person, they must request that they create a new proof for a new set of keys.

The ZK-SNARK Landscape

These systems are cryptographic constructions supported by Elliptic Curve Pairings. There are many kinds of different elliptic curves, some can be used with pairings others can’t, and each type of curve can be parameterized in different ways, leading to specific choices that get their own names. There are also different constructions of ZK systems, and in particular the type we want to use at Artos: ZK-SNARKs. Finally, there are also several tools being developed to produce these systems in different environments. Since I began this research, I came in contact with the following (for an extensive list, check ZKP Science or the references here or here):

SNARKs:

• PGHR13: one of the earliest and most fundamental SNARKs, that has inspired several variants
• BCTV14: an improvement of PGHR13 that optimizes for efficiency. The version originally implemented in ZCash. A vulnerability has been revealed this month, but found by ZCash last June. This paper has since been corrected to avoid it.
• Gro16: a different design of SNARK that is not inspired by PGHR13. Achieves smaller proofs and faster verification.
• GM17: an evolution of Gro16
• Sonic (MBKM19): a very recent SNARK that requires a different kind of trusted setup, which can continue indefinitely by accepting new randomness contributions. This improves security since an attack is thwarted if at least one user destroys their contribution.

Pairing-friendly elliptic curves:

• BN254 / BN_128: the Elliptic Curve chosen by the Ethereum Alliance to support ZK-SNARKs. It is a Barreto-Naehrig curve, for a long time the most efficient kind of pairing-friendly curve. The 128 in the name refers to the nominal security level of this curve. Recent improvements in attacks have reduced it to about 100 bits of security, but this is still good enough. The 254 in the other name refers to the number of bits necessary to represent each of the coordinates of points in this curve.
• BLS12-381: a new curve designed by the ZCash team to target the 128-bit security level, in response to BN254’s downgrading.

Tools:

• Libsnark: a C++ library that can produce an almost end-to-end ZK journey, from encoding the statement to be proved to generating keys and proofs.
• Libff: a C++ library for fast computation in large algebraic groups and fields, and specific kinds of pairing-friendly Elliptic Curves. Used by libsnark.
• py_ecc: a Python library by the Ethereum Foundation supporting the BN128 and BLS12-381 for SNARKs, and also the secp256k1 for cryptographic signatures.
• Milagro: a complete cryptographic library covering several platforms, including JavaScript, Go, Swift, C and Java. Not specialized for SNARKs.
• DIZK: a Java library for SNARKs, mirroring libsnark but supporting only Gro16.
• ZoKrates: a Rust/C++ tool providing the best end to end experience to produce SNARKs, since it provides an easy high-level language to specify the statement to prove. Uses libsnark as a backend. Currently, only supports the BCTV14a and GM17 Snarks. More are coming.

Our goal at Artos is to investigate what we can use for the Aventus use case. We are targeting several types of platforms, including verification on-chain and in the back-end, and proof generation server-side, and in Android and iOS DApps. This creates a wide array of challenges, and covers a broad gamut of languages and techniques. Our goal is to create an end-to-end product that can easily allow for the choice of different SNARKs, different curves and maybe different libraries. It’s an ambitious project, and not all of these requirements are written in stone, but it is also extremely motivating and satisfying. It is a pleasure to work with such cutting-edge technology. This is the beginning of a long series, in which I will tell you of our team’s successes, the “blood, sweat and tears”, but also all the cheers. Stay tuned for more info. Share in the comments if you’re going through the same difficulties, if you have insight and even if you learn something from these posts. And if you like this, hit the buttons below and share with your network. Thank you! See you next time.