Introduction

Zero-knowledge Proofs (ZKP) have picked up a whole ton of interest in the last couple of years. We are super early in ZKP applications and yet we are already met with exciting use-cases that will only continue to grow in order to provide privacy-saving mechanisms for our digital lives. This guide is targeted at software developers who are ZKP curious by clarifying what ZKPs are while using the least math possible and still explaining how it works and how teams can get started with their ZKP projects. Needless to say, a lot more further reading is required to get fully up to speed with ZKPs but the goal here is to show you how you can use Circom to get started and shed some light on some known unknowns on your ZK journey.

Circom, is a circuit programming language and a compiler that allows programmers to design and create their own arithmetic circuits for ZKP. We’ll discuss common pitfalls in using Circom, the most important paradigm to have when developing in Circom and ways you can write and extend your own Circom circuits using existing Circom libraries.

This guide will gloss over very key points about ZKPs in order to get readers coding with Circom as soon as possible. The “Further Reading'' section will provide useful links.

This article is broken down into 4 sections, we will cover only section 1 and 2 in this instalment.

• What are Zero-Knowledge Proofs and how do they intersect with Web3 (Theory)
• Key Paradigms (Theory)
• Circom and Solidity (Coding)
• Full-stack React application using Next.js (Coding)

What are Zero-Knowledge Proofs and How Do They Intersect with Web3

Zero-Knowledge Proofs can simply be defined as the ability to prove you know something without revealing what you know. Think, for example, that you have to prove to a travel website, say an airline, that you are indeed a citizen of a given country without having to show them your passport and that the website will verifiably know that what you are saying is true. Sounds wild? I know but this ZKP accuracy and reliability is really high. This, and many other scenarios, are why ZKPs are all the rage right now. ZKP’s privacy-preserving properties are changing the fundamentals of how the Web works.

Components of a ZKP

ZKPs can either be interactive—where a prover convinces a specific verifier but needs to repeat this process for each individual verifier—or non-interactive—where a prover generates a proof that can be verified by anyone using the same proof.

The three fundamental characteristics that define a ZKP include:

• Completeness: if the statement is true, an honest verifier will be convinced of this fact by an honest prover.
• Soundness: if the statement is false, no cheating prover can convince an honest verifier that it is true, except with some small probability.
• Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret.

Important note: ZKPs don’t necessarily equate to privacy, they equate to honest computation. The honest computation can be the foundation of a privacy tool, product or protocol. ZKP is a cryptographic standard not a privacy panacea in and of itself.

History of ZKPs

In 1985, an MIT paper by Shafi Goldwasser and Silvio Micali titled “The Knowledge Complexity of Interactive Proof-Systems” introduced the concept of ZKP which defined protocols in which interactive proofs that involve two kinds of entities: a prover and a verifier, interact over a number of rounds by sending messages.

Prior to their paper, there was a lot of focus on interactive proof systems and the concept of Soundness, where a malicious prover attempts to trick a verifier. The concept of Soundness in which a mathematical statement is defined as sound if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system. Goldwasser, Micali and Rackoff changed the fundamentals of interactive proofs by asking “what if you don’t trust the verifier?” They asked, how much extra information is the verifier going to learn during the course of this proof, beyond the mere fact that the statement is true?

By limiting this exposure of information, their proposed proving system provided the least amount of information to either party. While the approach was novel, a key limitation of this system was the requirement for interactivity. This meant that both prover and verifier had to send each other multiple messages of varying mathematical complexity in order to complete the verification process.

What has since emerged are a number of proving systems, like STARKs, SNARKs, BulletProofs etc that, broadly speaking, remove the need for interaction between prover and verifier by using a secret key. These proving systems have different benefits, drawbacks and value propositions but you can find out more about them here.

Applications in Web3

There are a number of exciting applications of ZKPs in Blockchain technology. I’ll highlight two that relate to technology that I interact with in my role at Polygon.

• zkEVM: The zkEVM wars are upon us and Vitalik’s blog post defines the parameters of different zkEVM types. The endgame for zkEVM is providing a scaling solution for Ethereum. You can learn more about Polygon zkEVM here.
• Polygon ID: Self-Sovereign Identity (SSI) is an exciting development of the internet that seeks to provide an identity layer to the internet. The core contention being that the internet should end with you, not your IP address. Polygon ID is a blockchain-native identity system with programmable privacy that empowers people and enables the creation of trusted interactions with web3 services.

Key Paradigms

This guide is intended to provide hands-on instructions on getting started with Circom and we will be focusing on using the Snark tool that uses zk-SNARK under the hood but we have to define what zk-SNARKS are.

zk-SNARKS

zk-SNARK stands for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”, let’s break this down:

• “zk”: Zero-Knowledge, this was defined above
• “Succinct”: the proof that is generated is short. This is ideal because it means that our proofs can be stored on a blockchain, inside of a single transaction. This is particularly useful if we are looking at different applications of ZK such as Polygon ID.
• “Non-interactive”: This non-interactive component allows the verification to occur without having to send messages between the prover and the verifier. Gross oversimplification but think of this as a driving license being verified without having to hit the DMV’s API.
• “Argument” : we don’t quite use mathematical proofs but we do provide a form of them for ZKPs to work
• “Knowledge”: the information that the prover has

zk-SNARKs are just one protocol that has various proving systems. I’d recommend further reading on ZK proving systems such as Pinocchio, Groth16, Plonk, Plonky2. Also, the guide “Why and How zk-SNARK Works: Definitive Explanation” is seminal text in understanding zk-SNARKs.

There is a general criticism of zk-SNARKS that in the generation of it’s key, there is still a requirement of a trusted setup in order to generate a witness, we’ll delve more into that in the coding section of this guide.

Arithmetic and ZKPs

If I was to choose the most crucial piece in understanding ZKP, it would be this, how do you convert your computations into algebraic expressions? This is by far the part of Circom that gives new developers the most grief. Let me attempt to break it down for you.

The goal of ZK is to verify computations and according to Kineret Segal & Shir Peled here, the first step “... is the translation (often referred to as ‘reduction’) of the problem of verifying a computation to the problem of checking that a certain polynomial, which can be evaluated efficiently on the verifier’s side (this is the ‘succinctly’ part), is of low degree.”

Polynomials are fundamental to understanding ZKPs given that we can present a polynomial with arguments that essentially verifies the computation. There are entire domains of study dedicated to explaining ZK math, such as the absolutely awesome ZK Hack Whiteboard Series which I highly recommend. This guide is purposefully light on this subject.

In its most simplest form, the biggest change a developer needs to make is learning how to write traditional control structures as quadratic constraints. To borrow from Vitalik’s example, we can see how this changes in arithmetic circuit programming.

Traditional control structure:

if x < 5: y = 7; else: y = 9) 

To Quadratic Control Structure

y = 7 * (x < 5) + 9 * (x >= 5);

The key to understanding how to shift in thinking is by noting how the value of y changes in both statements depending on the value of x. This is the main difference in arithmetic circuit programming, well, this and understanding logic gates but if it still doesn’t make sense, don’t worry. In the next section, we delve into a Circom example that illustrates this difference even better.

In the next section, we’ll get up and running with Circom and get you writing your first ZKP Dapp. I hope this theory section provides sufficient clarity about ZKPs.

Further Reading

ZK Hack Whiteboard Series
Quadratic Arithmetic Programs: from Zero to Hero
Why and How zk-SNARK Works: Definitive Explanation