ZKPs to ZK-Snarks for Dummies by a Dummie

10 min readAug 26, 2024

Zero knowledge Proofs are the brainchild of mathematicians, mothered by cryptographers, & put into the world by computer scientist. In this article we will talk about how ZKPs are brought into reality.

In a previous article I talked about what zero-knowledge proofs are and how they work, however that article followed more of the theory and math behind zero-knowledge proofs. Putting zero-knowledge proofs (ZKPs) into practice is a whole different process to actually convert the theory into code. There are two types of functional ZKPs: Zero-Knowledge Succinct Non-Interactive Argument of Knowledge or ZK-Snarks, and Zero-Knowledge Scalable transparent argument of knowledge or ZK-Starks. ZK-Starks are notably more complex than ZK-Snarks & the technology is not as flushed out. Which is why in this article I will run through how ZKPs are converted into ZK-Snarks & abstracting away some of the complex lingo that might confuse people.

Before getting into the details of converting ZKPs to ZK-snarks we will briefly explain some important pre-topics that make the conversion possible. These will include polynomials & polynomial commitments, & finite fields. If you feel somewhat familiar to these feel free to skip to the section talking about the actual conversion.

ZK-Snarks very generally work using mathematical tricks to manipulate polynomials or math functions and combine this with encryption to be able to hide these values. What makes ZK-Snarks special is that they use a secret input to produce these polynomials which are created by a trusted party. This trusted party must destroy this secret once it is created or else someone could game the system and break our math trickery. We will go into how all these processes work but first there are some technologies that make this possible.

Dummied Down:

ZK-Snarks are math games like pretty much all cryptography. If you’ve ever tried to create a secret language as a kid you would usually have a rule to follow, say switch the first and last letters, Oellh yodat si yeallr eicn (Hello today is really nice). A ZK-Snark is basically this on steroids and they use a secret rule as well, but snarks require someone to make the secret rule then destroy it, so no one finds out. Doing this makes generating & verifying ZK-Snarks faster.

Polynomial Commitments:

Polynomial commitments allow a prover to prove properties about the polynomial, like what an output of the polynomial would be at a certain point without revealing what the polynomial is. Polynomial commitments are essentially a way to encrypt a polynomial while still being able to run logic on it. This makes the polynomial a black box in a way where you don’t know what the polynomial is, but you can put in a point into this black box and get an output out of it. With this commitment a prover can generate a proof of an output, which usually involves dividing our polynomial by another, & give the commitment to the verifier & the verifier can check if it is correct without ever knowing what the actual polynomial was. Polynomial Commitment create “succinctness” — the S in snarks — which means it makes these polynomials small, so they don’t take up a lot of space & computing power.

Dummied Down:

Remember the goal of what we are trying to do with ZKs are prove a fact without revealing what it is. To do this we have to turn our word problems — when were you born?, did you pay taxes?, Do you have a dog? — into number problems. But if we reveal these number problems someone could game the system, plus to do our math tricks they are too big & spit out scary numbers. So, we hide them & make them more compact. I.E. polynomial commitments help compact and hide our number problems.

Finite Fields:

The boundaries of math are limitless, literally. In the scope of mathematics, the upper and lower bounds go to positive and negative infinity. This can get out of hand as results can go way into the ether and have a hard time coming back. With ZK-Snarks the polynomials (Number problems) that are used need to be very big in order to work. To contain these numbers, we use a finite field which is self-explanatory, but the words together might be confusing. A finite field sets a range that our polynomials can work in, and this helps to make sure they don’t go crazy into the ether. Using a finite field makes ZK-Snarks operations well-defined and secure while also making them more efficient to run.

Finite fields are put into practice using modular Arithmetic. In a previous article we explained that a modulus just gives the remaining number after dividing. EX: 16 mod 3 = 1 because 3 can fit in 16, 5 times which is 15 leaving a remainder of 1. Using Mods are how we are able to create a finite field around our computations.

Dummied Down:

Finite fields put up a barrier around the proofs and math tricks we are trying to use so our proving and verifying don’t get out of hand and can’t be comprehended. Also makes them more speedy.

Elliptic Curve Pairing:

There are two main components that make ZK-Snarks work: Elliptic curve pairing & Quadratic Arithmetic Programs. An elliptic curve is created when there is an equation where the x component highest degree of 3 or x³ & y component has highest degree 2 or y². An example of what one looks like is below. This curve is used a lot in cryptography by picking points on the line and then drawing lines to see where other points on the line intersect. Elliptic curve pairing is a special type of bilinear map, in general pairings in cryptography are bilinear maps.

With ZK-Snarks the elliptic curve pairing is usually a map given the function:

e : G1 ×G2 →GT

Where:

G1 and G2 are elliptic curves, or the same curve with different properties
GT is the result of the pairing function e; GT is actually represented as a single number like 5 or –3. It is not a line, equation, vector, etc. It is a single value.

Why do we care?

If you remember earlier, we talked about polynomial commitments — hiding functions so people cannot game the system but still wanting to run logic on top of them. Well, how do we know that the functions being hidden by our commitment are the ones we are looking for? That’s where elliptic curve pairing comes in. In ZK-Snarks, the elliptic curve pairing is used to efficiently verify that certain algebraic relationships hold true without revealing the underlying data. These elliptic curves allow us to do proof generation & verification.

Proof generation:

To prove we know s (a secret) without revealing it, the prover computes a point Qs on the elliptic curve G2 (from above) & a point Ps on the elliptic curve G1 (from above). The prover then sends the two points to the verifier.

Verification:

The verifier checks whether the relationship between points Ps & Qs match up with our result GT. It does this by pairing Ps with another point on the same curve (G1 — notice big G) g & checks if it equals the pairing of our point Qs and another point on the same curve (G2 — notice again big G) g1. Formally it checks:

e(Ps ,g) = e(g1 ,Qs )

Where e is our pairing function.

The equation checks that for a point (Ps, g) they satisfy that Ps * k = g, and for point (Qs, g1) Qs * k = g1. K is our secret value that it created by our trusted set-up & is our determining factor to verify the statement given. This is where the concept of a “trusted setup” comes into play since you must trust that whoever generates this secret value deletes it afterwards, else they could break the system.

Desmos Visualization of Elliptic Curve Pairing

Dummied Down:

Elliptic Curve pairings are the math games that make ZK-Snarks possible, they are the ones that can create a proof and verify. This math trick uses a pairing function e, which is a long scary math problem, what e does is takes 2 points on 2 different elliptic curves & outputs a number. To verify a fact is correct a person will take a different point on the curves and use the same function to see if they get the same output. This tests the relationship of the two variables and shows if they come from the same place.

Quadratic Arithmetic Circuits (QAPs):

In use ZK-Snarks aren’t just a bunch of math problems written out and strung together. For a ZK-Snark to work it must be in the correct form to run the calculations on, this form is what Quadratic Arithmetic Circuits are. An Arithmetic Circuit is a way to express equations or polynomials. These circuits are a series of gates that perform basic operations on their inputs and each gate represents a polynomial. QAPs convert the problem of checking whether a computation was done correctly into checking whether certain quadratic equations are satisfied (checking with our elliptic curve pairings). In a QAP, you have a set of polynomials v(x), w(x), and y(x) as inputs and try to satisfy v(x) * w(x) = y(x).

Creating a QAP involves 3 processes:

Flattening
Convert flattening to rank-1 constraint system (R1CS)
Convert R1CS to a QAP

Flattening involves the first part of an Arithmetic circuit, using logic gates to break up a polynomial into its parts.

R1CS stands for rank-1 constraint system. The goal of this system is to find the coefficients of the polynomials we are going to use. The goal of the R1CS is to express a computation as a set of linear constraints, these constraints ensure that a given computation is performed correctly. There are 3 components of a R1CS: Vectors, Variables, and constraints.

Example of R1CS:

Let’s say you have a simple computation: z = x × y

Define the vectors:

A might correspond to x, so A⋅X=x
B might correspond to y, so B⋅X=y
C corresponds to the result z, so C⋅X=z

The constraint would be:

(A⋅X) × (B⋅X) = C⋅X

Which represents: x × y = z

An R1CS output would look like this

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]
B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

R1CS to QAP:

Turning R1CS into QAPs involves turning our constraints into polynomials. Formally tunring A*X, B*X, and C*X into a polynomial v(x), w(x), & y(x). We then put these polynomials into a form:

v(x) * w(x) — y(x) = 0

Finally, in a QAP there is a special equation Z which is defined as a function designed so that when you divide v(x) * w(x) — y(x) you will get a “quotient polynomial” if the calculation was correct. The “quotient polynomial” is just the result of dividing by Z, Z is the simplest polynomial that is equal to zero at all points of the logic gate flattening.

For Example:

Polynomial: x³ + x + 5

Z: (x-1) * (x — 2) * (x — 3) * (x-4)

The quotient is just another way to check/verify that the computation was done correctly. If our equations when divided by Z yield the correct quotient polynomial than we can be sure the proof is valid.

Dummies Down:

QAPs are the form that or ZK-Snark problem turns into. You basically take an equation — your number problem — break it into its parts and then create 3 equations so that they equal 0, specifically:

v(x) * w(x) — y(x) = 0

From there you take the simplest form and divide by that equation to get an output H(x). With this we can check that our proofs are correct. QAPs are basically the way we are able to create our polynomial commitments before. They help prove equations work together without revealing what they are and make them small enough to verify.

Vitalik in his article looking “under the hood” gives a great outline of how this process works all together:

Summary from Vitaliks article “ZK-SNARKS: Under the Hood”

You can go to Vitaliks article (link below) for his definition but here’s a dummied down version.

A succinct summary:

You see here to make one of them ZK-Snarks get yer problem, turn it to numbers, flatten that thing out & bake those flat functions in an R1CS. Take out your fresh R1CS vector & multiply by yeer constraints to get the coefficients for your polynomials. Run those things on an elliptic curve with a finite field, slap a point on the curve, then get yourself another point. Check that those 4 points line up, run through it again to make double sure. Take your trusted set-up values out back & dispose of them, check your QAP divided by your simplest polynomial form with no remainder and boom you got yourself a:

Zero-Knowledge –> Secret is Destroyed

Succinct –> Small Size

Non-Interactive –> Verifier only has to check once

Argument -> Make sure to points line up

Of Knowledge -> The statement is indeed valid

Thanks for reading

[1] https://vitalik.eth.limo/general/2021/01/26/snarks.html

[2] https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627

[3] https://medium.com/@VitalikButerin/zk-snarks-under-the-hood-b33151a013f6

[4] https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

[5] https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell

[6] https://tokenminds.co/blog/knowledge-base/zk-snarks-in-practice