Zero-Knowledge Proofs: A Layman’s Introduction

Alex has dedicated more of his time to create an article where he is giving an introduction to what ZK-SNARKs are. We encourage you to have a read and leave a comment if you find it useful.

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 twoposts 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 a person learns nothing about your secret except that you have it. To give it a worldly 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 relationship 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 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 somegood 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 an 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 set up 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 knew 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 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 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).

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
• BCTV14a: 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 Gro16Sonic (refs to each): a new and different approach of SNARK, that avoids the vulnerability recently found in BCTV14a.

• Sonic (MBKM19): a very recent SNARK that does not require a trusted setup.

Pairing-friendly elliptic curves:

• BN254 / BN_128: the Elliptic Curve chose 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. 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 Protocol 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!

Alexandre Pinto — Blockchain developer at Artos (Aventus Ecosystem Party)

Alex is a software engineer at Artos, our ecosystem partner, working on the blockchain engineering team. He has 20 years of experience working in technology, completing a PhD in Computer Science as well as a post-doctorate in Cryptography. As part of his research, Alex has published papers on Kolmogorov Complexity, Cryptography, Database Anonymization and Code Obfuscation.

Pinto also spent seven years lecturing at the University Institute of Maia, including directing the degree programmes for BSc Computer Science and Information Systems and Software.

This article was originally posted on his blog. Also, you can follow Alex’s Twitter account — @alexMirPinto.

Since you are here, we would love if you connected with us on Telegram, Reddit, Twitter, Facebook, Youtube, Instagram and LinkedIn.

We have also created a group for open-source developers/ ticketing developers and ticketing professionals and invite you to join it here — Ticketing on Blockchain.