In this module, we will "look under the hood" of zkSNARKs and acquire an understanding of how zkSNARKs are constructed. To set the stage, we will introduce the concepts of homomorphic hiding and blind evaluation.
Then we will go through the process of converting a computation into a zkSNARK, starting from arithmetic circuits, to R1CS and QAP. Finally, we will explore some common proof systems like Groth16 and Plonk.
Let's start by looking into the concepts of homomorphic hiding and blind evaluation. Although not directly related to zkSNARKs, it is one of the main ingredients or concepts that make zkSNARKs possible.
This blog series from Electric Coin is a good start:
- Explaining SNARKs Part I: Homomorphic Hidings by Electric Coin Co.
- Explaining SNARKs Part II: Blind Evaluation of Polynomials
ASecuritySite.com also has some helpful interactive examples that go along with these two blog posts:
Now that you have a general idea of the topics above, let's turn to the "pipeline" of a zkSNARK construction.
The goal of our construction is to be able to create a proof that a particular computation was properly executed. In order to do that, we must first transform it into a special form.
First, we need to convert our problem into something called an arithmetic circuit. This allows us to take an equation and "flatten" it into a series of simpler equations. Read the following:
- The Arithmetic Circuits section of this Electric Coin article
- The Flattening section of this 0xParc article
- The following two posts in this series by Maurizio Binello:
Once we have this arithmetic circuit in the form as explained above, we can proceed to convert it into a representation of matrices and vertices known as the Rank-1 Constraint System (R1CS).
To understand how it works, read the following resources:
- R1CS: A Day in the Life of a few Equations - This 0xParc article was mentioned above, ensure you read this in full as it is a very friendly introduction to R1CS.
- R1CS by Maurizio Binello - This is a continuation of Maurizio Binello's series of blog posts mentioned above. You might want to revisit the other pages in this series.
R1CS helped to reduce our computation into a set of matrices and vertices. But now, we need to convert it into a format called QAP.
For understanding this, we turn to the following resources:
- Explaining SNARKs Part V: From Computations to Polynomials - A continuation of the Electric Coin blog series.
- QAP by Maurizio Binello - A continuation of Maurizio Binello's blog series.
- Quadratic Arithmetic Programs: from Zero to Hero - Vitalik Buterin's article on getting to a QAP representation. Feel free to start from the "R1CS to QAP" section.
The Pinocchio Protocol was first described in a paper in 2013, Pinocchio: Nearly Practical Verifiable Computation. As the name suggests, it was a big step towards the practical construction of zkSNARKs that we know today. It builds upon the QAP representations we described above and it is also here where elliptic curve pairings become relevant again.
Admittedly, the details from here get even more technical than before. So it is important to start with a focused article before moving onwards.
Therefore, read Vitalik's article, zk-SNARKs: Under the Hood. This article was designed to follow his two other blog posts (on QAP and Pairings), so feel free to revisit those articles if you need to.
Once you have done this, check out Maurizio Binello's page on the history of the Pinocchio paper. You can then jump back into the series by reading the page on Hiding (which follows after the page on QAP) and continue by clicking "Next" at the bottom of each page.
Finally, Part VI of the Electric Coin series provides a brief sketch of the protocol. While Part VII ties it all up with elliptic curve pairing concepts. Both of these are worth a read:
- Explaining SNARKs Part VI: The Pinocchio Protocol
- Explaining SNARKs Part VII: Pairings of Elliptic Curves
Two common proof systems you should know about are Groth16 and PLONK. They are significant improvements over the Pinocchio proving system. Here is a very brief overview of the two and their tradeoffs.
The efficiency of Groth16 is very hard to beat, and as such it has become a de-facto standard in many blockchain technologies that require an efficient proof system. However, the requirement of a circuit-specific trusted setup is a significant downside for some use-cases.
Here are a couple articles to understand how Groth16 works:
- Groth16 by Remco Bloemen - A very light article that covers the full life cycle of the Groth16 proving system.
- Groth16 by Maurizio Binello - A continuation of the blog series above that you should be well acquainted with.
PLONK has fast become one of the favourite proof systems because of its "universal and updateable" trusted setup, eliminating the need to have a new trusted setup for every circuit.
Here are a couple resources to understand how PLONK works:
- Understanding PLONK by Vitalik Buterin
- How does PLONK work? by David Wong
- How PLONK Works: Part 1 by CoinGeek
- How PLONK Works: Part 2 by CoinGeek
In the above, we have drawn very heavily from blog posts written by Vitalik Buterin, Electric Coin, and Maurizio Binello. However, these are only some of the many pathways towards understanding zkSNARK construction.
Since it is always helpful to take a look at the same problem from different angles, we recommend you visit the following resources:
- Why and How zk-SNARK Works (highly recommended) - Originally a paper by Maksym Petkus, it dives into the specifics of how a zkSNARK is constructed, it has been converted to a series of blog posts for easy consumption.
- ZK Whiteboard Sessions - There are three videos by Dan Boneh (he's the B in BLS Signatures) providing a very compelling introduction to zkSNARKs. I highly recommend at least watching What is a SNARK? and Building a SNARK (Part I).
- The MoonMath Manual to zkSNARKs - This is a free online textbook PDF that explains many of the necessary concepts. It is an excellent reference guide whenever you need to dive into specific topics.
Answer the following questions (in as much detail as you like).
- Explain homomorphic hiding in your own words.
- What is the primary purpose of converting a problem into an arithmetic circuit?
- What are the main components of an arithmetic circuit?
- Describe the Rank-1 Constraint System (R1CS) in your own words.
- Why is R1CS essential in the zkSNARK construction pipeline?
- What is the primary goal of converting R1CS into a QAP?
- How does QAP aid in the zkSNARK proof generation process?
- Why are polynomials central to the QAP representation?
- Why is the Pinocchio Protocol considered a significant step towards practical zkSNARK construction?
- How does the Pinocchio Protocol utilize QAP representations?
- What role do elliptic curve pairings play in the Pinocchio Protocol?
- What makes Groth16 a popular choice for zkSNARK constructions in blockchain technologies?
- Describe the main advantage and disadvantage of the Groth16 proof system.
- How does Groth16 differ from the original Pinocchio Protocol?
- What are the advantages of PLONK over Groth16? What are the disadvantages?
- How does PLONK eliminate the need for a new trusted setup for every circuit?