Zippy

A Basic Zero-Knowledge Protocol to Build Intuition on the Popular Proving Systems

In this guide, we’re going to build a toy zero-knowledge proving system called Zippy. It can only do one thing: prove that you know the 4th root of a number, without revealing what that 4th root is. It should not require anything more than middle school math to understand, and by the end you’ll have a foundational intuition for how the real proving systems work.

Why this guide?

There is no shortage of great guides on the basics of zero-knowledge proofs^[1], but there is a chasm between those guides — which mainly focus on the concept of a zero-knowledge proof — and actually understanding how today’s proving systems verify computation. The learning curve goes from basic logical arguments straight to advanced algebra and number theory.

The proving systems of today bring together a few highly technical concepts: execution traces, arithmetization, polynomial interpolation, constraints, and commitment schemes. Zippy uses all of these, in a simplified form. Some aspects of Zippy are closest to a STARK^[2], but the general steps are the same ones followed by both SNARKs and STARKs. If you understand this guide, you will be able to use that understanding to tackle the much more complicated, more specific system of your choice.

Step 1. Execute the computation and convert the results to data points

In zero-knowledge proving systems, the two parties involved are usually called the prover and the verifier. The prover is trying to convince the verifier about some fact. This fact may be something like the following: “I know a secret that has some property you care about.” In our case, the fact that the prover wants to prove is “I know the 4th root of some number.” In other cases, it might be: “I have an identification card that proves I am 18 or older.” The main purpose of a zero-knowledge protocol is to prove that fact without revealing anything else: the prover doesn’t need to reveal the 4th root to prove that they know it. I don’t need to show my ID card to prove I’m 18.

Moving away from the very general concept of what zk is, we can now target how it is implemented for real developer systems. The model that deployed zk platforms use, such as Noir, Circom, Cairo, and others, is one of computation: the prover executes a computer program, and then uses a zero-knowledge proof to convince a verifier that this computer program ran on some unknown secret inputs, and then produced outputs that are shared with them. The computer program may be anything! It can be a program that squares numbers, like we’ll be using in this guide, or a machine learning system that can detect features from images. Whatever the program is, the zero-knowledge proof ensures that the inputs and execution trace of that program are private, and only the results of that program are shared.

For this guide, the program we will be using can do one thing: calculate $x^4$ for some input $x$, by squaring $x$ and then squaring $x^2$. It’s a very simple program. Our input to this program will be 2, and as you could guess, our output will be $2^4 = 16$.

The first step in a proving system is to execute the program to get your outputs from your secret inputs. There’s nothing special here, just do the math:

We have our secret input 2, an intermediate value 4, and our final output $2^4 = 16$. The combination of all these values is known as the execution trace. While in this simple proving system, the execution trace is just a few multiplication results, in real proving systems it is often the execution of actual machine code: registers, memory addresses, and instructions from the computer’s instruction set being executed!

Next, we line up our execution trace into a table — a process known as arithmetization:

Finally, we convert each cell into a coordinate, with the row number as the x-coordinate and the value as the y-coordinate:

The important intuition here is that any set of data can be turned into points. If you have some list of values, say 1, 10, 100, 1000, 10000, those items can be represented as points: (1, 1), (2, 10), (3, 100), (4, 1000), (5, 10000). The x-value is just the index and the y-value is the original value. The idea of converting data into points and then doing things with those points was originally pioneered in Reed-Solomon encoding^[3] — a technique present in DVDs, Blu-ray, QR codes, barcodes, text messages, video streaming, and more. It also happens to be very useful for cryptography and zk proofs, as we’ll see.

Step 2. Convert the data points to a function

This is where we start to do weird things. But don’t worry! It will all be explained in relatively plain terms.

Now that our table is a single column with 3 points, we can treat those points like they are points on a curve, and our column becomes a function. We can call the function we are creating from our column $f$. For $f(x)$, our values for $f$ are $f(1) = 2$, $f(2) = 4$, and $f(3) = 16$. This matches with the points in our column: (1, 2), (2, 4), (3, 16).

Since our function has some points, we can actually plot it on a graph!

For our use case, when we pick what kind of function we want to plot through our points, we use a quadratic equation. You might have flinched there. If I can resuscitate the 14 year old out of your cerebellum, I’ll remind you that the quadratic equation is just a second-degree polynomial. In other words:

The reason why we like to use a quadratic equation to describe our function, is because our column has 3 points. As it turns out, there is 1 unique polynomial with degree $d$ that passes through $d+1$ points. In other words, there is one unique quadratic equation (our function $f$) that can be used to represent our data points (1, 2), (2, 4), (3, 16). If that doesn’t yet make sense, no worries, let’s use a simpler example and move up from there.

We can express this concept with simpler functions than the quadratic equation: namely, polynomials of highest-degree 1. These are also just called lines: $f(x) = mx + b$. An example of a line is $f(x) = x + 1$. I’m not overloading that term “line” with something more complicated, I’m literally just talking about lines. A line is a degree-1 polynomial, because it could also be written as $f(x) = x^1 + 1$. Here’s our line plotted on a graph:

Okay, now we can explain everything we need to with lines. The main thing we need to understand is that in order to know which line we are drawing, we need two points. If we just have one point, we could draw infinitely many lines through that point. See this plot below to understand that:

As you can see, just writing down the point (0, 1) isn’t enough to know that we are dealing with the line $f(x) = x + 1$. In fact, it reveals nothing to us. We don’t have a clue which line we are supposed to draw! Once we add a second point, though, we go from infinitely many lines to only 1 single possible line. See below:

As the visual shows, 2 points is enough to represent a single unique line. This rule scales to all degrees of polynomials: for degree 2 functions, or quadratic equations, 3 points is enough to represent a unique quadratic equation, and for degree 3 functions, 4 points is enough, and so on… In our case, our table’s column has 3 points, so we can represent it with a unique quadratic equation (i.e. a degree-2 polynomial):

Values Column = (1, 2), (2, 4), (3, 16)

Verification:

These evaluations line up perfectly with our original table. You might be asking, how did you get that equation from our points? Good question! The answer is that I asked AI:

“Give me the unique quadratic equation that fits points (1, 2), (2, 4), (3, 16).”

Easy! Seriously, though, there are a couple of methods by which you can do this by hand:

1. Polynomial interpolation. This is the way the zk pros actually create their unique polynomials from their data points. It is a mathematical technique that allows you to turn any set of $n$ points into a unique $n-1$ degree polynomial.

2. Create a system of equations. This is another basic math concept that you may have learned long ago. Effectively, you turn your points into equations, and solve for your coefficients, i.e.:

   $a(1)^2 + b(1) + c = 2$

   $a(2)^2 + b(2) + c = 4$

   $a(3)^2 + b(3) + c = 16$

At any rate, you don’t need to know exactly how to construct these functions from the data points, but you should come out of this section with the understanding that once we have a table that represents the execution trace from our program, each column in that table can be converted to points, and all of the points in a column can then converted to a single unique function using polynomial interpolation.

Step 3. Establish and Prove our Constraints

Now that we have a function $f(x)$ that uniquely fits our original points (1, 2), (2, 4), (3, 16), and therefore uniquely represents our original execution trace, we can get to the meat of our zk proving system.

Here’s the main part: the way by which we prove that our computation is valid (i.e., the 4th root of 16 = 2), is by convincing someone that our unique $f(x)$ function satisfies certain properties. We do this by using points on our polynomial other than our original data. The result is that the person we are proving to is convinced that the original data points are valid, and represent a valid execution trace, without ever being shown the original data points! Very zero-knowledge, indeed.

Our dataset, and consequently $f(x)$, has two important properties:

1. For the rows in our original table, the value in a row is equal to the square of the value in the previous row. For example, $f(2) = 4 = 2 \times 2 = f(1) \times f(1)$.
2. The value of the third row is 16 (our output). In other words, $f(3) = 16$.

We express these as constraints — equations that must hold at specific points on our function:

The first is called a “transition constraint” — it represents the relationship between consecutive rows, specifically that $f(x+1)$ equals the square of $f(x)$. The second is a “boundary constraint” — it asserts the output of our program, that $f(3) = 16$.

If we can convince someone that these constraints hold, they can follow these logical steps:

1. I am convinced that this person knows a unique degree-2 polynomial function $f(x)$, where for $x = 1$ and $x = 2$, $f(x+1) = f(x) \cdot f(x)$, and also where for $x = 3$, $f(3) = 16$.
2. Because I am convinced that for $x = 1$ and $x = 2$, $f(x+1) = f(x) \cdot f(x)$, I am convinced that $f(3) = f(2) \cdot f(2) = f(1) \cdot f(1) \cdot f(1) \cdot f(1) = f(1)^4$. Therefore, I am convinced that $f(1)$ is the 4th root of $f(3)$.
3. Because I am convinced that for $x = 3$, $f(3) = 16$, I am convinced that $f(1)$ is the 4th root of 16.
4. Because I am convinced that the prover knows what the polynomial function $f$ is, I am convinced that they can use this function to compute any of its points, including $f(1)$, and therefore they know $f(1)$.
5. Since I am convinced this person knows $f(1)$, I am convinced this person knows the fourth root of $f(3) = 16$.

This logical deduction does not require the verifier to ever see the value of $f(1)$ or $f(2)$. They just need to be convinced that these constraints hold.

What does a zk proof actually look like? The proof is just a handful of numbers — evaluations of polynomials at a single random point $z$. The verifier never sees the original data points, never learns $f(1)$ or $f(2)$, and never touches the execution trace. They just check a few arithmetic relationships between the numbers they receive, and that’s enough.

So how do we actually convince them? This is the hardest part, even if it is all still middle school math, so bear with me.

Convincing them that f(x+1) = f(x) * f(x)

We’ll work on the transition constraint first. Within our original data points, we can see that $f(x+1) = f(x) \cdot f(x)$. For example, $f(2) = 4 = 2 \times 2 = f(1) \cdot f(1)$, and $f(3) = 16 = 4 \times 4 = f(2) \cdot f(2)$. Restating this, we can say that $f(x+1) - f(x) \cdot f(x)$ is zero when $x = 1$ and $x = 2$.

Well, this pattern holds for a couple of our points, but it doesn’t hold for every point. If we calculated $f(4)$ on our function $f(x)$, it wouldn’t equal $f(3)^2$ (you can verify this yourself with $f(x)$, if you’d like). So how can we use that statement to prove something about every point on our function, not just those two? The answer is this: if we define a new function $c(x)$, and say that $c(x) = f(x+1) - f(x) \cdot f(x)$, we can say that $c(1) = 0$, and $c(2) = 0$. This should make sense, since we know that when $x = 1$, $c(1) = f(2) - f(1) \cdot f(1) = 4 - 2 \times 2 = 0$, and when $x = 2$, $c(2) = f(3) - f(2) \cdot f(2) = 16 - 4 \times 4 = 0$. And if we know that $c(1) = 0$ and $c(2) = 0$, then we can say that 1 & 2 are zeroes of $c(x)$.

What does it mean when a polynomial has zeroes? Once again, this should be dormant knowledge that we can extract from your brain. To do so, we can remind ourselves of a simple example. Let’s take the quadratic equation:

If we factor this polynomial, we get $e(x) = (x - 3)(x - 2)$ as the factors of our polynomial. You can probably verify this yourself, or ask AI for a refresher. If $(x - 3)$ is a factor of the polynomial, that means that 3 is a zero for that polynomial, and the same goes for $(x - 2).$ Let’s try it out:

Ok, now let’s steer things back to our $c(x)$ function that we actually care about.

$c(x)$ is a more complicated equation than the ones we’ve seen so far. This is because it contains the product of two polynomials, namely the $f(x) \cdot f(x)$ part within $c(x) = f(x+1) - f(x) \cdot f(x)$. If we tried to write out what $c(x)$ is by plugging in the quadratic equation form of $f(x)$, we would get:

And the evaluation of that expression ends up being:

That polynomial is too complicated for my liking, and I don’t want you to have to think about something like that either. We just need to understand a very simple thing about $c(x)$:

It’s true! You’re free to verify this yourself by plugging in 1 & 2 as x-values to the fully-written form of $c(x)$. Remember that even though $c(x)$ looks ugly and complicated in its fully written-out form, it really is still just $c(x) = f(x+1) - f(x) \cdot f(x)$, which we know is zero for our $x = 1$ and $x = 2$. Now, since we know that $c(1) = 0$ and $c(2) = 0$, we know that $(x - 1)$ and $(x - 2)$ are both factors of $c(x)$. So, we could re-write $c(x)$ in a more simple form:

Where the … represents the rest of the factors of $c(x)$. We don’t care about those other factors, so let’s just use a polynomial to represent them, called $h(x)$.

$h(x)$ just represents all the factors in $c(x)$ besides $(x - 1)$ and $(x - 2)$ multiplied together. In modern zk proving systems, $h(x)$ is called the quotient polynomial.

At this point we have our original $f(x)$ function, plus a $c(x)$ function that represents $c(x) = f(x+1) - f(x) \cdot f(x)$, and finally a new $h(x)$ function that represents all the factors of $c(x)$ besides $(x - 1)$ and $(x - 2)$. Using these three things, we can actually prove what we need to prove! And here’s how:

1. Our verifier picks a random large $x$ value, we’ll call it $z$, that isn’t from any of our known x values $x = 1$, $x = 2$, or $x = 3$. As we mentioned earlier in the guide, this is the part where we use points outside of our original dataset.
2. The prover calculates $f(z)$, $f(z+1)$, $c(z)$ and $h(z)$ and gives those evaluations to the verifier.
3. The verifier validates that $c(z) = f(z+1) - f(z) \cdot f(z)$.
4. The verifier validates that $h(z) \cdot (z - 1)(z - 2) = c(z)$.
5. The verifier is convinced that $f(x + 1) = f(x) \cdot f(x)$ for $x = 1, 2$.

Wait, what? How? Why would checking a single random point be convincing at all?

In order to answer this question, we have to use something called the Schwartz-Zippel lemma^[4][5]. This may sound scary, but the result of this lemma that we care about is very simple: if two polynomials $a(x)$ and $b(x)$ are not equal to each other, then for a large enough random $z$ the probability that $a(z) = b(z)$ is extremely small.

What does that mean for us? It means that if the prover used their polynomials $c$ and $f$ to calculate $c(z) = f(z+1) - f(z) \cdot f(z)$, and if $c(x)$ and $f(x+1) - f(x) \cdot f(x)$ were not actually equal polynomials, then due to the Schwartz-Zippel lemma the probability that the equation holds at random $z$ is extremely small. Conversely, the opposite holds: if $c(z) = f(z+1) - f(z) \cdot f(z)$ does check out at a random $z$, then it is overwhelmingly likely that $c(x) = f(x+1) - f(x) \cdot f(x)$ everywhere. The same logic applies to every equation the verifier checks. This is why we say that the verifier is “convinced,” because they understand that the probability of the prover being able to cheat is extremely small.

Now, we can use that fact to re-examine those evaluations at z:

Step 3 convinces the verifier that $c(x) = f(x+1) - f(x) \cdot f(x)$, due to the Schwartz-Zippel Lemma. However, it doesn’t tell us anything useful about $f(x)$ yet.

For Step 4: Now that we’ve validated that $c(z) = f(z+1) - f(z) \cdot f(z)$, we then validate that $c(z) = h(z) \cdot (z - 1)(z - 2)$. Why do we do this? Remember that if a polynomial contains a factor like $(x - 1)$, it evaluates to zero at $x = 1$. So by saying that $c(z) = h(z) \cdot (z - 1)(z - 2)$, we are saying that $c(x)$ has factors $(x - 1)$ and $(x - 2).$ Further, by saying that $c(x)$ has factors $(x - 1)$ and $(x - 2)$, we are saying that $c(x) = 0$ for $x = 1$ and $c(x) = 0$ for $x = 2$.

For Step 5: finally, put these two steps together! We have shown that $c(x) = f(x+1) - f(x) \cdot f(x)$, and we have shown that $c(x) = 0$ for $x = 1$ and $x = 2$. The corollary of this is that $f(x+1) - f(x) \cdot f(x) = 0$, for $x = 1$ and $x = 2$. In other words, we have convinced the verifier that $f(2) = f(1) \cdot f(1)$, and $f(3) = f(2) \cdot f(2)$, which was the first property that we were trying to prove about $f$!!

And there we have it. We’ve used a random point $z$, evaluations of $f(z)$, $c(z)$, and $h(z)$, and the values $(z - 1)$ and $(z - 2)$ to prove that $f(x+1) = f(x) \cdot f(x)$ for $x = 1$ & $x = 2$, without having ever revealed $f(1)$ or $f(2)$. If you’ve understood this part, you’ve understood the most important bit of modern zk proving systems.

Convincing the verifier that f(3) = 16

The same idea applies here, but simpler. We define $d(x) = f(x) - 16$. Since $f(3) = 16$, we know $d(3) = 0$, which means $(x - 3)$ is a factor of $d(x)$. So we can write:

Where $g(x)$ is another quotient polynomial. Using the same random $z$, the verifier checks:

1. That $d(z) = f(z) - 16$ (confirming the definition of $d$).
2. That $g(z) \cdot (z - 3) = d(z)$ (confirming that $(x - 3)$ is a factor, and therefore $d(3) = 0$).

Since $d(x) = f(x) - 16$ and $d(3) = 0$, it follows that $f(3) = 16$. That’s our boundary constraint, proven!

Now that we have convinced our verifier of both constraints, they can follow the logical deduction we outlined earlier to conclude that the prover knows the fourth root of 16 — without ever seeing $f(1)$ or $f(2)$.

At this point, we have gone through the entire proving and verifying flow. Our prover has converted their execution trace of the computation $2^4 = 16$, generated a proof (the proof is all the requested evaluations for $z$: $f(z), f(z+1), c(z), d(z), h(z), g(z), (z-1), (z-2), (z-3)$), and had that proof verified to convince someone that they know the 4th root of 16.

In the real proving systems, we aren’t just proving a couple of tiny constraints like this. We would be proving thousands, or millions, (or billions) of constraints. And all those constraints would add up to convince a verifier that we ran a complicated program on some secret inputs and produced some public outputs that we claim are valid. In Zippy, all we did was prove we knew the 4th root of 16. But the system we used to do this scales from that teeny tiny little use case to much more complicated secret inputs and public outputs, like:

• I can prove that when I run my ID (the secret input) through a machine learning program, it will detect that my age is 18 or above (the output).
• I can prove that my bank account statement (secret input) contains a valid balance (the output) to take out a loan.
• I can prove that my vote for the newest government elections (secret input), is a valid, unique vote (output), and in doing so I complete my civic duty in an incorruptible, anonymous way.

This simple system that we defined here can be scaled to handle some of the most important and interesting problems in privacy and governance, and if you understand this system, you now understand one of the best solutions to these problems.

Epilogue: Commitment Schemes, and Where to Go from Here

There is one final unresolved issue with our system: our $f(x)$ function was supposed to be a degree-2 polynomial, because there is only one unique degree-2 polynomial that satisfies our constraints: $f(x) = 5x^2 - 13x + 10$.

But what if our prover tried using a degree-3 polynomial? It turns out there are infinitely many degree-3 polynomials that can falsely satisfy our constraints. A couple valid examples:

It’s just like that analogy we had with drawing infinitely many lines through a single point. Once we add an extra degree to our function, we can no longer uniquely identify a polynomial with our current constraints.

To address this problem, the solution used by all popular proving systems is a polynomial commitment scheme — a mathematical technique that ensures the points the prover hands over really come from a polynomial of the expected degree. You can think of it like a secret box: the prover locks their polynomial inside, and the box only accepts polynomials of the right degree. When the verifier asks for a point, they pull it out of the box, and therefore know it came from a valid polynomial.

The actual commitment schemes — FRI^[6] (used in STARKs) and KZG^[7] (used in many SNARKs) — are mathematically involved and well beyond middle school math. Understanding how they work is a great next step once you’re comfortable with everything covered here.

All done!