First principles is a series of articles diving into bleeding-edge technology on the frontiers of blockchain and crypto. It breaks down the most advanced topics into the most digestible content for the average reader. The future belongs to everyone, so everyone should understand the future.

Scaling solutions are needed more than ever in this accelerated pace of blockchain technology. L1s are bloated by transactions, resulting in high gas fees that ruin user experience. We are in need of a solution that can efficiently execute transactions in a secure, decentralized way.

“ZK-SNARKs” or “Rollups” are the most recent solutions. If these terms seem foreign to you, check out this blog. We will deep dive into how SNARKs work.

This topic will be about how to produce arithmetic circuits and produce a mathematical structure (hint: polynomial) that can be efficiently verified by the verifier. The biggest misconception is that there is nothing zero-knowledgey about this process. There are “SNARKs” which perform efficient computation. Then there’s “ZK” which preserves privacy. Zero-knowledge is another juicy topic with more math, but that will be for another section.

The goal of this article is to deep dive into a very complex subject, SNARKs, and explain most of the math in the most intuitive way possible. I used this article from Vitalik as inspiration. The biggest frustration I had understanding Vitalik’s post was the sheer moving parts of this complex field. So, I hope to reduce headache by giving definitions of what, where, and when everything is happening.

NOTE: Bolded words indicate a new definition.

Before we dive into SNARKs, we must understand the use cases that make SNARKs necessary. Here is a brief description of it, but refer to this resource for a better understanding.

Trust is a huge part of our society. In order to cooperate, we must establish trust so we can cooperate and benefit from each other in a more efficient manner. If you pay someone to perform some work, how can you know that they will do it? Well, you can either trust them, or you can actually watch them do the work and make sure it is done correctly.

Based on the above example, you are the verifier, and the worker is the prover. These two parties establish the foundation of how interactive proofs work. The goal of the prover is to do the work and prove they did it correctly. The verifier’s job is to ensure the prover did the work correctly.

Now let’s take this back into the blockchain context. The prover is some user or program that executed some code and wants to submit this as a transaction on the blockchain. The verifier is a node that is in charge of accepting or rejecting transactions. Great! The perfect use case for SNARKs.

The naive approach is to:

1. have the prover run the code and get the output

2. send the code and output to the verifier

3. the verifier has to run the ENTIRE code again and compare the verifier’s output with the prover’s output.

This is super inefficient. Literally every line of code must be executed twice in order to accept that one transaction.

That’s where rollup solutions come in. They compute transactions off-chain and submit them to the blockchain after. What used to be an n-line program to verify now is just a succinct hash that can be verified with ease.

Alas, let’s create a SNARK.

We are starting with a program and spreading it into multiple, logic gate steps.

def qeval(x):

    y = x**3

    return x + y + 5

will turn into

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

A logic gate represents a line in the above flattening. It is atomic, with only two inputs, and an output. We must represent every output as an individual variable.

For example: if we have x^3, it will flatten to

1. y = x * x,

2. z = y * x

We will call each element in the flattening as constraint variables. We place every variable on a vector, so their positions represent that variable. Later during the mathematical calculations, their positions serve to show whether a variable is turned on or not. For example, x=3 is in position 2 in the vector, so any vector that turns “on” in position 2 will use that variable.

Okay, let’s take logic gates and constraint variables and put them side by side.

Now we are turning each logic gate from the flattening process into a group (a * b - c =0), where a, b, c are vectors that represent the constraint variable vectors. A group is just a representation of a logic gate during circuit execution (another term describing the sequence of computation). a, b, c are subgroups or vectors that turn on specific constraint variables used for this logic gate.

For example, based on the first logic gate in the above example,

• A represents x in vector form

• B represents x in vector form

• C represents sym_1 in vector form

Think of this as breaking each logic gate down, showing the specific variables that are turned on during this step. For example, in Figure 2, A= [0, 1, 0, 0, 0, 0] means we are turning on x bc variable mapping is '~one', 'x', '~out', 'sym_1', 'y', 'sym_2', where ‘x’ is the second position in vector

There is also a solution vector s (in yellow) that references what the true values are in each variable at that logic gate. This is what the prover has and wants to show during verification.

If there are 4 groups, that means there are 4 logic gates, so each row will represent a subgroup for a logic gate.

This is called the R1CS (Rank-1 Constraint System). I actually don’t know why its called that, some linear algebra definitions, nor do I understand intuitively how we got here, but trust me (ironically) it will make sense in the end.

The next step is taking this R1CS and converting it into QAP form. Just think of QAP as a polynomial which is much better than the mess that we call R1CS. Why? Because polynomials are more efficient to verify. In the end, we are making the verifier’s job much easier. In the R1CS above you had to multiply EVERY element in the subgroup to the solution vector. With polynomials, we will see how efficient it is.

The transformation goes like this. We are basically flipping the rows and columns of the R1CS matrix. R1CS’s rows will represent columns in QAP (each column represents a logic gate), and R1CS’s columns will represent rows in QAP (each row represents a constraint variable like sym_1). The transformation should look like this:

Confused? Well, let’s go through the pseudocode for the transformation.

Before we dive in, we need to understand Lagrange interpolation. It’s simply described like this: Given a list of pairs of coordinates (x, y), it outputs a polynomial that passes through all those points. Refer to Vitalik’s post for an example demo.

Here’s some pseudocode from R1CS → QAP:

For each a->c
        For each column x in R1CS (contraint variables)
        Take first value out of R1CS vector
        Do langragian interpolation to make polynomial

Let’s try this on our first column in subgroup A (shown in red in Figure 3)

for each a->c (start at a)
        grab first column vector [0, 0, 0, 5] (red in Figure 3)
    Take first value of vector = 0
        Do lagrangian interpolation on these coordinates:
        1. (x=1,0)
        2. (x=2,0)
        3. (x=3,0)
        4. (x=4,5)

Waittttt hol up. Where did x=1,2,3,4 come from? First, we must understand commitment schemes. Here’s a brief definition:

“Roughly speaking, a commitment scheme enables a party, called the committer, to commit itself to a value to another party, the receiver. At first the value is hidden from the receiver; this property is called hiding. At a later stage when the commitment is opened, it can only reveal a single value as determined in the committing phase; this property is called binding*”*

The term binding indicates that the QAP is uniquely configured as a set of polynomials based on the program code and solution input (aka the witness, aka the solution vector s). So when the commit is opened, we have already set the QAP in stone, and it can’t be changed.

We are binding from 1 to N, where N is the number of constraints/equations in your circuit. In this case, N=4 because there are 4 logic gates. To summarize, we are defining the structure of the commitment scheme to prevent the prover from changing their answer.

This creates an elegant polynomial that will represent the computation for subgroup A

Try it yourself by entering the inputs: https://www.dcode.fr/lagrange-interpolating-polynomial

Result:

The QAP after 1 run in the for loop is now:

[-5.0, 9.166, -5.0, 0.833]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0]

After a few runs, the final result is:

A polynomials
A1 = [-5.0, 9.166, -5.0, 0.833]
A2 = [8.0, -11.333, 5.0, -0.666]
A3 = [0.0, 0.0, 0.0, 0.0]
A4 = [-6.0, 9.5, -4.0, 0.5]
A5 = [4.0, -7.0, 3.5, -0.5]
A6 = [-1.0, 1.833, -1.0, 0.166]

B polynomials
B1 = [3.0, -5.166, 2.5, -0.333]
B2 = [-2.0, 5.166, -2.5, 0.333]
B3 = [0.0, 0.0, 0.0, 0.0]
B4 = [0.0, 0.0, 0.0, 0.0]
B5 = [0.0, 0.0, 0.0, 0.0]
B6 = [0.0, 0.0, 0.0, 0.0]

C polynomials
C1 = [0.0, 0.0, 0.0, 0.0]
C2 = [0.0, 0.0, 0.0, 0.0]
C3 = [-1.0, 1.833, -1.0, 0.166]
C4 = [4.0, -4.333, 1.5, -0.166]
C5 = [-6.0, 9.5, -4.0, 0.5]
C6 = [4.0, -7.0, 3.5, -0.5]

The polynomials are now the parameters for this QAP instance. In most layman's terms, we have done the computation that shows EVERY step of how the logic was done. Congrats! Let’s summarize what we did:

By flattening we defined all variables and logic gates, forming our R1CS dimensions (rows = logic gates, cols = # variables). Then we transformed into QAP, making sure every logic gate in each subgroup (A0, B0, C0) is done sequentially (we used lagrangian for each x coordinate). This creates a polynomial that is now part of QAP.

Ok, the whole point of creating the QAP is to make verifying easier.

“The answer is that instead of checking the constraints in the R1CS individually, we can now check all of the constraints at the same time by doing the dot product check on the polynomials.”

Here is the rule when evaluating the QAP:

1. If the result is 0 at every x coordinate, all checks have passed, meaning the logic has been executed exactly how it was supposed to.

2. If the result is nonzero for at least 1 x coordinate, the logic has not been executed exactly how it was supposed to. Input variables are found to be inconsistent with how the logic was executed.

Let’s break this computation into steps:

1. Referring to Figure 2, we had s (in yellow), solution R1CS vector of length n where the ith element represents the solution value for a constraint variable.

2. Remember we performed lagrangian interpolation from 1 to N? For each ith binding element (i=0, 1, ….. N), we will input into our new QAP polynomials:

   1. i = 1, so we have polynomial A1 = .8333(1)^3 - 5(1)^2 + 9.166(1) - 5 = 0.

   2. i = 2, so we have polynomial A2 = -0.666(2)^3 - 5.0(2)^2 + -11.333(2) - 8.0 = 0.

3. If we repeat until N, we will always get 0, meaning the polynomial is valid and corresponds to an execution trace that correctly steps through the logic gates.

What’s another term for a value that evaluates a polynomial to 0? A factor!

If we take all the factors and multiply them together: Z = (x - 1) * (x - 2) * (x - 3) .. * (x - n), we will get a polynomial that is equal to 0 at all the logic gates. Therefore, if we divide our QAP polynomials with Z, it means we have satisfied all the logic gates!

Let’s take the A, B, and C from QAP and take the dot product of the solution vector. Let’s try A * s:

And fill out the rest:

A . s = [43.0, -73.333, 38.5, -5.166]

B . s = [-3.0, 10.333, -5.0, 0.666]

C . s = [-41.0, 71.666, -24.5, 2.833]

We then treat these vectors as a polynomial by turning them into A . s * B . s - C . s. By placing the coefficients in the vector, the solution is:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

Since we have 4 logic gates, Z will be (x - 1) * (x - 2) * (x - 3) * (x - 4). By placing the coefficients in the vector, the solution is:

Z = [24, -50, 35, -10, 1]

Then we do t / Z, creating:

[-3.666, 17.055, -3.444]

And leaving no remainder.

This is essentially how we can use elegant polynomials to simplify verification. We just take polynomial P and divide it by a factor (x - i), to get no remainder.

If we divide the polynomial for every binding variable from i = 1, 2, 3, ...., N, we get a polynomial with no remainder.

And I hope I was this much closer to demystifying the complexities of ZK proofs. The next part of the series will deep dive into the “zero-knowledge” side of things.

Special thanks to Haichen Shen, co-founder of Scroll, for helping me understand the intricacies of ZK tech.