From Zero to Hero in Zero Knowledge Proofs [Part 10]
This is the tenth part of the series that takes you from absolute ground zero in ZKPs to a fairly advanced level. We will start from the absolute basics and then move onward and upward. Subscribe to get regular updates!
In the previous post, we discussed an example program covering the structure of zk-snarks. In today’s post, we will cover the internal steps required to create a snark proof. So without further ado, let’s dive into it.
Creation and verification of a SNARK Proof
There are four main steps in the creation and verification of zkSNARK proofs:
1. Encoding as a polynomial problem
The program C that is to be checked is compiled into a quadratic equation of polynomials:
t(x)h(x)=w(x)v(x)
In this equation, the equality holds if and only if the program is computed correctly. The prover wants to convince the verifier that this equality holds.
2. Succinctness by random sampling
The verifier chooses a secret evaluation point s to reduce the problem from multiplying polynomials and verifying polynomial function equality to simple multiplication and equality checks on numbers:
t(s)h(s)=w(s)v(s)
This reduces both the proof size and the verification time tremendously
3. Homomorphic encoding/encryption
An encoding/encryption function E is used that has some homomorphic properties (but is not fully homomorphic, something that is not yet practical). This allows the prover to compute E(t(s)), E(h(s)), E(w(s)), E(v(s)) without knowing s, she only knows E(s) and some other helpful encrypted values.
4. Zero Knowledge
The prover obfuscates the values E(t(s)), E(h(s)), E(w(s)), E(v(s)) by multiplying with a number so that the verifier can still check their correct structure without knowing the actual encoded values. The very rough idea is that checking t(s)h(s) = w(s)v(s) is identical to checking t(s)h(s)k = w(s)v(s)k for a random secret number k (which is not zero), with the difference that if you are sent only the numbers (t(s)h(s)k) and (w(s)v(s)k), it is impossible to derive t(s)h(s) or w(s)v(s).
This was a basic explanation of the four steps involved in the creation of a zk-SNARK proof.
Converting the zk-SNARK program into quadratic polynomials
This section provides further details about the first step explained above i.e. how the zk-SNARK program can be encoded into a polynomial problem.
This section is optional and contains details about how to convert the program into polynomials.
zk-SNARK works by first turning what you want to prove into an equivalent form about knowing a solution to some algebraic equations
The following are the steps taken to do this:
Computation→ArithmeticCircuit→R1CS→QAP→ zk−SNARK
In the first step, the creator of the zkSNARK uses a high-level language to specify the algorithm that constitutes and tests the proof. This proof is then compiled into an arithmetic circuit.
Converting a program into an arithmetic circuit means it’s broken down into single steps consisting of the basic arithmetic operations of addition, subtraction, multiplication, and division.
To further explain the concept of arithmetic circuits, here is an example of what an arithmetic circuit looks like for computing the expression(a+b)*(b*c):
Looking at such a circuit, we can think of the input values a, b, and c as “traveling” left-to-right on the wires toward the output wire.
Our next step is to build what is called a Rank 1 Constraint System, or R1CS, to check that the values are “traveling correctly”. In this example, the R1CS will confirm, for instance, that the value coming out of the multiplication gate where b and c went in is b*c.
In this R1CS representation, the verifier has to check many constraints — one for almost every wire of the circuit.
In a 2012 paper, “Quadratic Span Programs and Succinct NIZKs without PCPs”, Gennaro, Gentry, Parno, and Raykova presented a nice way to “bundle all these constraints into one”. This method uses a representation of the circuit called a Quadratic Arithmetic Program (QAP). The single constraint that needs to be checked is now between polynomials rather than between numbers. At this point, we have the polynomials we require.
Appendix
The explanation of the steps involved in a zk-SNARK is taken from this paper.
The paper that shows how to bundle R1CS constraints: https://eprint.iacr.org/2012/215.pdf
This marks the end of our zk-snark journey. We will do a quick recap in the next lesson and then move on to more hands-on stuff.
Hey there, thanks for reading this far. If you liked this article, don’t forget to follow and leave a clap.
I am building Plurality Network, the user context layer on web3. Join our discord to get alpha!
Follow me here, on LinkedIn, on X, or on Farcaster to get the latest blockchain technical content in simple, bite-sized reads.
