Lecture 22: Faster and Smaller ZK Proofs

Announcements

This week’s reading: Matt Green’s blog and Decentralized Thoughts blog
Due this Friday 4/18 at 10pm on Gradescope
- Homework 9
- Challenge 3-4 resubmissions
Please complete the course survey form
On Thursday 4/25, we have an in-person-only guest lecture by Prof. Andy Sellars

Learning outcomes

By the end of today’s lecture, you will learn:

How to build a fast ZK proof using the ideas we learned about MPC
How to build a succinct ZK proof using some fancier math

Review from last lecture

Secure multi-party computation (MPC) solves a seemingly-impossible problem:

Many people, each with their own private data that they do not wish to share, can still perform data analysis collaboratively and only reveal the result!

Zero knowledge solves another seemingly-impossible problem:

Can a prover convince a verifier that a statement is true, without revealing the evidence or reason why?

Prover Peggy\((x, w)\)		Verifier Victor\((x)\)
	\(\begin{array}{c} \underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\)
		output: Accept or Reject

In a ZK proof, there are a few items that are assumed to be common knowledge before the protocol begins:

A claimed statement \(x\) (i.e., a Sudoku puzzle)
An efficiently-computable check program \(C(x, w)\) that can can test whether a claimed solution \(w\) actually solves the statement. It has a boolean output: True or False.

The prover Peggy also has a witness \(w\) (i.e., the solution to the Sukodu puzzle).

By the end of the interactive conversation, the verifier should be convinced that:

The statement is true.
Optionally, Peggy knows why the statement is true (i.e., she has a witness that makes the check program return true). This is called a proof of knowledge.

Once the protocol ends: the verifier outputs its judgment about whether to Accept or Reject the claim that \(x\) is true.

A zero knowledge proof satisfies three properties.

Completeness: if both Peggy and Victor are honest, then every valid proof should be accepted.
Soundness: even if Peggy is dishonest, then every proof of an invalid statement (i.e., a Sudoku puzzle that has no solution) should be rejected.
Zero knowledge: even if Victor is dishonest, it is infeasible to learn anything from the proof beyond the fact that the statement \(x\) is true.

Last time, we designed a zero knowledge proof for Sudoku puzzles.

Amazingly, one can show using complexity theory that any problem can be converted into a Sudoku puzzle. So, there exists a zero knowledge proof for any statement! (Well at least: for any statement that can be efficiently checked, if someone gave you a potential solution.)

However, this approach is inefficient in at least three metrics.

Computation: the reduction from a general problem to a Sudoku puzzle is computationally intensive.
Interaction: the proof we constructed only convinces a single verifier Victor; if you want to convince someone else then you’ll have to start all over again.
Communication: the prover must send many kilobytes or megabytes of data to convince the verifier of a single Sudoku puzzle proof.

Today, we will discuss new kinds of ZK proofs that perform better in these metrics.

22.1 Zero knowledge from MPC

As a stepping stone toward today’s first construction, let’s imagine the following “hybrid” construction between ZK and MPC.

As with zero knowledge: there is a public statement \(x\), Peggy knows the solution \(w\), and Victor wants to be convinced that Peggy knows it.
As with MPC, Peggy and Victor have access to a collection of \(n\) outsourced cloud servers. Both of them trust that:
- none of the servers is actively malicious, and
- at most \(t\) of them would try to collude in order to recover any secret data.

Question. How could Peggy and Victor take advantage of the outsourced cloud servers?

Remember that Peggy’s ultimate goal is to convince Victor that she knows \(w\), but without the need for Peggy to share \(w\) with anyone (not Victor, nor the cloud servers).

Prover Peggy\((x, w)\)		Verifier Victor\((x)\)
	\(\begin{array}{c} \underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\)

Construction. Here is an idea:

Peggy acts as the data owner in the MPC protocol, and she provides secret shares of \(w\) to all cloud servers. She also sends \(x\) in the clear – remember that the statement \(x\) is not meant to be a secret.

Given their shares \(w_1, w_2, \ldots, w_n\): the cloud computing servers now perform a secure multi-party computation of the function \(C(x, w)\). Recall that \(C\) is the “check program”: it is the algorithm that tests whether a potential solution is correct. It has a boolean output \(y = C(x, w)\).

If this program is calculated using MPC, then the computing servers eventually obtain secret shares \(y_1, y_2, \ldots, y_n\) of the answer.

Victor acts as the data analyst: he wants to know the result of \(C(x, w)\). All of the outsourced servers send their shares of \(y\) to Victor; once he has them all, he can use them to reconstruct \(y\) itself. Remember that \(y\) is the bit that tells us whether the check program succeeded.

If \(y = \text{True}\) then he Accepts the proof, otherwise he Rejects the proof.

Security analysis

Let’s think about why this construction works. That is, why does MPC help us to achieve zero knowledge?

A general-purpose MPC protocol is secure against passive Eve (rather than active Mallory) if it satisfies the following two properties.

Correctness: if all servers act honestly, then the result of the computation is correct – in this case, the final shares \(y_1, y_2, \ldots, y_n\) really will be shares of \(y = C(x, w)\).
\(t\)-privacy: given fewer than \(t\) shares of any value (e.g., \(w\), or any intermediate variable during the computation), it is impossible to learn any data.

Let’s see how we can use the MPC properties in order to satisfy the three requirements of zero knowledge.

Completeness says that if everyone is honest, then valid statements will be accepted.

This follows from the correctness of the MPC protocol: if the statement \(x\) is true and Peggy has a valid witness \(w\), then the outsourced servers will jointly calculate \(y = C(x, w)\) correctly and give shares of \(y\) to Victor.
Soundness says that if the statement \(x\) is false, then Victor will reject the proof.

Once again this follows from the correctness of the MPC protocol. If the statement is false, then there is no witness \(w\) that will cause \(C(x, w) = \text{True}\). So no matter what value \(w^*\) that Peggy secret-shares with the outsourced servers, they will correctly compute \(C(x, w^*) = \text{False}\) and Victor will reject the proof.
Zero-knowledgeness says that Victor cannot learn anything from the proof, beyond the fact that the statement is true.

This follows from the \(t\)-privacy of the underlying MPC protocol. Even if Victor is colluding with \(t-1\) of the outsourced servers, those shares alone are insufficient to learn anything about the witness \(w\), or anything else. All of the shares that the \(t-1\) servers see are uniformly random, and Victor could have dreamed them up in his mind before the interaction with Peggy.

And that’s it! Let’s take a step back and admire what we’ve done here.

If Peggy and Victor have access to a collection of outsourced servers, then they can use any MPC protocol in order to build a zero knowledge proof!

This idea will work using any MPC protocol.

For example, we can use the 3-party MPC protocol that we designed in Lecture 19.
The prover can secret-share the witness – which might contain one number, or a vector of several numbers such as each cell of a Sudoku solution – and then the 3 compute parties can jointly calculate whether the check program returns true or false.

22.2 Zero knowledge from MPC-in-the-head

While the ZK proof we have built is elegant, it also suffers from a few drawbacks.

Peggy and Victor need to find a collection of outsourced servers to help them, and trust that they are not all colluding to reconstruct Peggy’s witness \(w\).
The cost of this protocol isn’t as low as it could be. Remember that the multiplication steps in MPC involve network communication between the parties, and that’s one of the more expensive actions to take in a commercial cloud.

So our next question is: can we do even better?

The insight

Here’s a wacky idea: what if Peggy just runs all of the MPC computing servers by herself!

Prover Peggy\((x, w)\)		Verifier Victor\((x)\)
	\(\begin{array}{c} \underset{\longleftarrow}{\pi} \\ \longrightarrow \\ \vdots \\ \longrightarrow \end{array}\)

This sounds strange! After all, MPC is about multiple parties computing together.

Remember that MPC only provided privacy if at most \(t-1\) of the computing parties are colluding together. If Peggy runs all \(n\) servers, we can’t provide privacy against Peggy anymore.

But that’s okay here because Peggy already knows all of the data involved in the calculation of \(C(x, w)\).

The statement \(x\) is public knowledge: everyone knows that.
The witness \(w\) is Peggy’s own data. Victor doesn’t contribute any inputs into the secure computation.

Put another way: in our analysis of the zero knowledge property in the earlier construction, we only needed the \(t\)-privacy guarantee to hold against Victor, not against Peggy.

So here is our current working plan:

Peggy is the data owner (she knows \(w\)). She acts as all computing parties, and performs the MPC calculation.
Peggy provides shares \(y_1, y_2, \ldots, y_n\) to Victor.
Victor reconstructs \(y = C(x, w)\) and he chooses to Accept the proof if \(y = \text{True}\).

Note that we have removed the need for the MPC compute parties to send data over a network, since they’re all running “in her head.”

Question. Is this a valid zero knowledge proof?

No. This satisfies completeness and zero-knowledgeness, but it does not satisfy soundness.

Remember that Peggy could be dishonest. Right now, there is nothing that forces her to execute an MPC protocol at all. She can just create shares of the boolean value \(\text{True}\) and send them to Victor.
We need something to bind the shares \(y_1, y_2, \ldots, y_n\) to the execution of the MPC protocol itself.

Fixing the construction

We can add two crucial steps to this plan, using a commitment scheme. The idea is for Peggy to commit to the view of each of the MPC parties.

The “view” of an MPC compute party contains all of the messages they send and receive throughout the execution of the interactive protocol.

MPC in the head (source: Trail of Bits blog)

So here is the new zero knowledge proof that Peggy and Victor can conduct, with changes from the previous version in italics.

Peggy is the data owner (she knows \(w\)). She acts as all computing parties, performs the MPC calculation, and commits to each message sent by some party \(i\) to some party \(j\) (note that there are a total of \(n \choose 2\) pairwise communication channels).
Peggy provides shares \(y_1, y_2, \ldots, y_n\) to Victor.
Victor challenges Peggy to open the state of up to \(t\) parties. If Victor selects to open party \(i\), then Peggy must decommit all messages sent or received by \(i\). Then, Victor verifies that all of their work was honestly performed and that party \(i\) reaches a final result of \(y_i\). If any of these checks fail, he Rejects the proof.
Victor reconstructs \(y = C(x, w)\) and he chooses to Accept the proof if \(y = \text{True}\).

This construction is called “MPC in the head,” because Peggy runs all of the compute parties herself rather than outsourcing it to external cloud providers.

The only messages that are actually sent over the Internet are the 3 rounds of communication between Peggy and Victor.

Security analysis

Let’s analyze whether this new construction achieves all of the goals of a ZK proof: completeness, soundness, and the zero knowledge property.

The nice part is that completeness is true for the same reasons as before! Let me quote what we said earlier in the class when Peggy and Victor were outsourcing the MPC computation to the outsourced servers.

Completeness says that if everyone is honest, then valid statements will be accepted. This follows from the correctness of the MPC protocol: if the statement \(x\) is true and Peggy has a valid witness \(w\), then the outsourced servers will jointly calculate \(y = C(x, w)\) correctly and give shares of \(y\) to Victor.

Even if Peggy runs all of the compute servers herself, as long as she is honest then everything we wrote before is still true.

Similarly, the zero knowledge property holds for nearly the same reasons as before. Let me again quote our analysis from earlier today, when the MPC computation was outsourced to external cloud providers.

Zero knowledge says that Victor cannot learn anything from the proof, beyond the fact that the statement is true. This follows from the \(t\)-privacy of the underlying MPC protocol. Even if Victor is colluding with up to \(t\) of the outsourced servers, those shares alone are insufficient to learn anything about the witness \(w\), or anything else. All of the shares that the \(t\) servers see are uniformly random, and Victor could have dreamed them up in his mind before the interaction with Peggy.

In this new construction, Victor is colluding with \(t\) of the servers… in the sense that Peggy intentionally allows Victor to view the internal state of \(t\) servers. Even so, the \(t\)-privacy of the underlying MPC protocol guarantees that viewing only \(t\) shares is insufficient to learn anything about any secret data.

We’re not going to be so lucky with soundness; it is more complicated to think about now.

As a reminder, here’s what we said before:

Soundness says that if the statement \(x\) is false, then Victor will reject the proof. Once again this follows from the correctness of the MPC protocol. If the statement is false, then there is no witness \(w\) that will cause \(C(x, w) = \text{True}\). So no matter what value \(w^*\) that Peggy secret-shares with the outsourced servers, they will correctly compute \(C(x, w^*) = \text{False}\) and Victor will reject the proof.

Question. Why doesn’t this analysis work now, in the setting where Peggy runs all of the compute servers?

The issue is that Peggy can be dishonest, and she controls the MPC compute parties so she can run them in a faulty manner.

We only used a semi-honest MPC protocol as a building block. It doesn’t tolerate any failures (i.e., \(f = 0\)). But Peggy can make all \(n\) of them faulty!

Here’s the good news.

If the statement \(x\) is false, then in order to run an MPC protocol that results in \(y = \text{True}\), then Peggy actually must have at least one compute party act in a faulty manner. If they were all honest, the result would be \(y = \text{False}\) as desired.
Victor inspects the state of \(t\) of the compute parties, and can verify if they are acting in an honest or faulty manner.

Therefore, if Peggy has constructed a faulty party, then Victor has probability \(t/n\) of catching her in this deceit. (And if Peggy only constructed honest parties, then Victor definitely won’t be fooled since the honest answer is \(\text{False}\).)

So: if the statement is false, then Victor is fooled by Peggy with probability at most \(\varepsilon = 1 - t/n\).

We can reduce the soundness error in the same way as the last lecture – by repeating the protocol many times in parallel.

If we run this procedure \(k\) different times (with Peggy executing independent MPC instances each time, i.e., with fresh secret shares of the witness \(w\)) then the overall soundness error is \(\left( 1 - \frac{t}{n}\right)^k\).
For instance, if we use the replicated secret sharing protocol from earlier with \(t = 1\) and \(n = 3\), then after \(k = 219\) repetitions the overall soundness error becomes smaller than \(2^{-128}\).

And that’s it! This proof is also a proof of knowledge: that is, it convinces Victor both that the statement is true and that Peggy knows a valid witness \(w\).

Overall, what we have done today is to show how to convert – or compile – any MPC protocol and commitment scheme into a zero knowledge proof system. This transformation is called the IKOS compiler, named after its creators Ishai, Kushilevitz, Ostrovsky, and Sahai.

IKOS compiler (source: Trail of Bits blog)

Any proof constructed from the IKOS compiler requires 3 rounds of communication between Peggy and Victor, and the total amount of data sent is about \(k\) times the communication for the underlying MPC protocol (which you should think of as proportional to the size of the check program \(C\)).

22.3 Non-interactive proofs from the Fiat-Shamir transform

Next, let’s make a slight modification to the proof from above, in order to transform it into a 1-round protocol – that is, a single message sent from Peggy to Victor.

This is powerful, because if we can make the proof non-interactive then Peggy can post the proof for anyone to verify! That is: the proof no longer is targeted toward a designated verifier, but instead becomes publicly verifiable.

The key insight here comes from inspecting Victor’s message in round 2 of the protocol in more detail.

Note that Victor’s message has the following properties:

All it contains is a uniformly random selection of which party/parties to open. Whereas Peggy’s messages have lots of structure (i.e., commitments, or views of parties), Victor’s messages have essentially no structure.
There is nothing that Victor keeps secret from Peggy after his message is revealed. In other words, Victor is stateless.

As a result, Victor’s algorithm is so simple that we would like to ask Peggy to perform this action on Victor’s behalf. This would eliminate Victor’s need to interact in the ZK proof at all; he only needs to perform the final verification step at the end.

Question. What could go wrong if we ask Peggy to create the challenge (of which parties to open) rather than Victor?

Answer. The concern is that Peggy could choose them dishonestly, rather than randomly.

Specifically, Peggy might have executed some of the MPC parties in a faulty manner. If we allow Peggy to control which parties are opened, then she might choose always to avoid the faulty parties so that she is never caught in a lie.
So: we want Peggy to select the challenge uniformly at random, but in a way that is outside her control to tamper with.

Amos Fiat and Adi Shamir came up with a clever way to do this: use a cryptographic hash function! Namely, remember that one strong assumption we can make about a hash function \(H\) is that it acts like a random oracle, i.e., as if it is a randomly-generated truth table.

If an adversary [Mallory] has not explicitly queried the oracle on some point \(x\), then the value of \(H(x)\) is completely random… at least as far as [Mallory] is concerned.

– Jon Katz and Yehuda Lindell, Introduction to Modern Cryptography

The Fiat-Shamir transform converts an interactive proof into a non-interactive one, by telling the prover Peggy to compute Victor’s challenge as a cryptographic hash function applied to the statement \(x\) and her first message of the protocol.

In this way, Peggy’s own commitments end up selecting the challenge message, but in a way that is difficult for her to predict or control.

In detail, Peggy performs the following:

Run the MPC parties and form commitments \(\vec{c}\) to all of the views.
Compute \(r = H(x, \vec{c})\) and treat this random value as Victor’s challenge.
Open the corresponding views in response to Victor’s challenge.
Send everything to Victor in one round of communication.

This construction can be proved to satisfy all of the ZK properties, although I won’t show that here.

Remember that one advantage of a non-interactive zero knowledge proof is that we can post it to a blockchain, in order to convince the whole world that (for instance) a financial transaction is sound. We’ll discuss ZK in the context of blockchains next time.

An aside: From ZK to digital signatures

When they proposed this transformation, Fiat and Shamir’s original goal wasn’t to build non-interactive ZK. Actually, they wanted to build digital signatures!

If you think about it, a digital signature is just a special case of a zero knowledge proof.

Recall the definition of a digital signature.

Definition. A digital signature contains three algorithms:

KeyGen: takes no input, produces a secret key \(sk\) and a public key \(pk\)
Sign(sk, M): produces a signature \(\sigma\)
Verify(pk, M, \(\sigma\)): returns true or false

All three algorithms should be efficiently computable. Moreover, the digital signature must satisfy two guarantees: correctness and unforgeability.

Here’s how we can use a ZK proof to build a signature.

KeyGen: the secret key is a random bitstring \(sk\), and the public key \(pk = H(sk)\) is a hash of that string
Sign(sk, M): create a ZK proof \(\sigma\) for the statement “I know a value \(sk\) that is the preimage to \(pk\), and I approve the message \(M\)”
Verify(pk, M, \(\sigma\)): check the validity of the proof

Using this approach, one can build a digital signature scheme purely using a hash function \(H\) and a zero knowledge proof… which, using the MPC-in-the-head approach, also only needs a hash function to construct the commitment scheme.

So, this is a new type of signature that doesn’t rely on a discrete log or factoring-type assumption!

That’s helpful because discrete logs and factoring are known to be breakable if someone ever builds a sufficiently-large quantum computer.

To plan ahead for this potential problem, the U.S. National Institute of Standards and Technology (NIST) have been running a post-quantum cryptography competition for the past decade to study and standardize replacements for the current systems that we use for public-key cryptography. The idea that I described above is just one of many proposals they considered.

22.4 zk-SNARKs

Switching gears, for the rest of today’s lecture I will show you a different way to construct a zero knowledge proof. This new system prioritizes smaller proof sizes at the expense of longer time to generate a proof.

This new proof system is called a zero knowledge succinct non-interactive argument of knowledge, or zk-SNARK.

The word “snark” comes from a poem by Lewis Carroll, in which several people are hunting a fictional animal that he calls a snark.

That is, the proof that we construct will be:

zero knowledge
succinct: in other words, it will be short!
non-interactive: using the Fiat-Shamir transform, the proof contains just a single message that the prover sends to the verifier, rather than an interactive challenge-response protocol.
argument of knowledge: this means that the verifier will be convinced that the statement has a solution and that the prover knows one solution. (Also: for the purposes of this class, you should think of the words “proof” and “argument” as synonyms.)

Fair warning upfront:

Constructing a SNARK requires a lot of math… more than we have time to discuss in this course. So, I will give only an overview of the ideas, but won’t show all the details.
The most important thing to take away from today’s lecture is that all of this is even possible – that I can send you a really short message (think: a few hundred bytes of data) that will convince you that I performed a data science analysis correctly.

Importantly, the message is short even if:

the analysis involves a large volume of data (say, gigabytes or terabytes), and/or
the analysis itself is computationally intensive (say, a high-performance machine learning algorithm).

Here are some potential applications of zk-SNARKs:

A bank can prove that from all of their transactions over the past year, they did not transact with some entity \(Y\)… but without revealing their full transaction log.
A person or company can publicly show that you have paid the correct amount of taxes, without revealing their finances.
You outsource a large computation to a cloud computing server, and then can validate that the result is correct without redoing the execution.

Why this is hard

In today’s lecture, I’m not going to worry about the zero knowledge property of hiding the actual data. It turns out that this is the easy part.

The hardest part of building a zk-SNARK is to provide succinctness and soundness together.

To see why this is hard, let’s think about what you might do to verify a computation done by someone else, if ZK and succinctness were not needed. Here is one approach:

When the untrusted cloud performs the computation, you can also ask them to write down their work at each step.
After they’re done, you can review all of their work and check that they’ve done it correctly.

For example, suppose that you outsource to the cloud the act of calculating \(2^{20}\). For now, let’s pretend that the only way to calculate this number is to multiply a register by 2 a total of \(20\) times.

Suppose the cloud messes up in one step of the calculation, and here is the work that they show you.
Rather than calculating \(8192 \times 2 = 16,384\) the cloud instead produces the cell \(15,625\).
As a consequence, the cloud tells you that \(2^{20} = 1\) million.

Transcript of an erroneous computation (source: Vitalik Buterin’s blog)

If you can see the entire working state of the cloud computer, then you can catch this bug!

But what if the cloud can only send you a small amount of data, of your choice. What should you request?

One seemingly-natural answer is to ask the cloud to send over just a portion of its working state, so that you can spot-check a subset of its work.

But this approach is likely to miss the bug. Even worse: a malicious/faulty cloud provider could be careful only on the part of the calculation that you ask for, and spend its time making sure that this part is correct even if the computer is incredibly buggy elsewhere!

What you need is some way to bind together all of the numbers \(1, 2, 4, 8, \ldots\) into some object that is:

Succinct, but also
Brittle, in the sense that if you tamper with even a single number then the object will be wildly different most of the time.

Question. Can you think of a mathematical object with these properties?

Answer. One common choice that many zk-SNARKs adopt is to use polynomials. They have the property that if you change a polynomial at even one point, then you end up changing it at nearly every point.

Or in other words:

Two different polynomials \(P\) and \(Q\), each of degree \(d\), intersect in at most \(d\) points.

Two polynomials (source: Why and How zk-SNARK Works)

Does this solve the problem?

The bad news: polynomials aren’t succinct. If you want to describe a polynomial of a large degree \(d\), you need to write \(d+1\) coefficients.
The good news: polynomial commitments are succinct.

A polynomial commitment is a special case of a commitment scheme. It allows the prover to create a short message that binds the prover to a specific polynomial, without needing to reveal it (since that would be both privacy-destroying and space-consuming).

Furthermore, given the commitment to polynomials \(\operatorname{com}(P)\) and \(\operatorname{com}(Q)\), we can do a few operations over these commitments.

Evaluation at a point: the prover can open \(P(w)\) at some point \(w\), and convince the verifier that this opening is correct.
Addition of commitments: the verifier can compute on their own \(\operatorname{com}(R)\) for \(R = P + Q\).
Multiplication of commitments: the verifier can compute on their own \(\operatorname{com}(S)\) for \(S = P Q\).

(Constructions of polynomial commitments are based on the same math as we already used to construct Feldman and Pedersen commitments.)

The punchline here is:

If we can transform the action of “verifying an arbitrary program outsourced to the cloud” into “verifying some polynomial arithmetic,” we would be done!
And this is possible to do! Just like any computer program can be translated into a circuit of addition and multiplication gates via Turing-completness, there is a way to convert the act of verifying a computer program into verifying polynomial arithmetic.

In the interest of time, I will not describe how to perform this transformation in class today; instead, I’ll post the details in the lecture notes.

Fortunately, there are ZK computer programs that handle the strange “moon math” of polynomials and R1CS behind the scenes.

Next Tuesday, we will use zk-SNARKs to build private cryptocurrencies. Then, we have a special guest lecture on Thursday.

Appendix: Converting programs into polynomials

[This part of the lecture notes largely follows the contents of Vitalik Buterin’s blog post Quadratic Arithmetic Programs: from Zero to Hero.]

Amazingly, there is a generic way to compile an arbitrary computer program (say, written in Python or Circom) into a polynomial. The details are complicated, so I’ll show you an overview today by walking through an example.

In our example, the prover wants to convince verifier of the following statement: it knows some value \(x\) such that \(x^3 + x + 5 = 35\).

(Admittedly, this is not a very impressive claim. It’s not hard to solve this cubic equation for yourself. Hint: the answer is \(x = 3\). But let’s pretend that the verifier does not know this, and wants to be convinced that the solution is correct.)

Or to cast the question in another way: both the prover and verifier know the code of the following Python function. The prover wants to prove that she knows an input that will cause this function output to equal \(35\).

def qeval(x):
    y = x**3
    return x + y + 5

Step 1: Flattening

The first step is to re-write the computer program in a new way, so that each individual line only contains a single addition and/or a single multiplication.

(Thanks to Turing-completeness, this is always possible, but may not always be easy to do.)

def qeval(x): one = 1 sym_1 = x * x y = sym_1 * x sym_2 = y + x out = sym_2 + 5*one return out

The prover knows that an input of \(x = 3\) will result in a result of \(\operatorname{out} = 35\).

Actually we can make a stronger statement: the prover knows the value of all variables throughout the calculation.

\(\operatorname{one} = 1\)
\(x = 3\)
\(\operatorname{out} = 35\)
\(\operatorname{sym}_1 = 9\)
\(y = 27\)
\(\operatorname{sym}_2 = 30\)

Let’s think of the entire working state of the prover as a vector \(\vec{s} = [1, 3, 35, 9, 27, 30]\).

This working state is analogous to the prover’s running calculation of \(2^{20}\) from earlier. If the prover showed the entirety of \(\vec{s}\) to the verifier, then they could check each step and become convinced that the prover’s work is correct. But that would be neither succinct nor confidential.

Instead, we need some way to encode all of these variables into a polynomial, since that is both succinct and brittle (if the prover is cheating then we want the lie to be easy to detect).

Step 2: A Rank-1 Constraint System (R1CS)

Next, we convert each step of the program into a series of vector equations.

Specifically, we want to construct three (public) vectors \(\vec{a}, \vec{b}\), and \(\vec{c}\) corresponding to our computation, such that any solution vector \(\vec{s}\) known by the prover satisfies the vector equation

\[ (\vec{s} \cdot \vec{a}) * (\vec{s} \cdot \vec{b}) - \vec{s} \cdot \vec{c} = 0,\]

where \(\cdot\) denotes a dot product and \(*\) denotes taking the component-wise product of two vectors. (Reminder: the multiplication of two vectors is typically not defined… just add that to the stack of ways that this construction is unorthodox.)

Once again it is easiest to think about this using an example. Here is the R1CS equation corresponding to the final step of our function qeval, which checks that out = sym_2 + 5*one.

def qeval(x):
    one = 1
    sym_1 = x * x
    y = sym_1 * x
    sym_2 = y + x
    out = sym_2 + 5*one
    return out

R1CS corresponding to qeval (source: Quadratic Arithmetic Programs: from Zero to Hero)

Question. How would you construct vector equations corresponding to sym_1 = x * x or y = sym_1 * x?

Answer. We can check the calculation sym_1 = x * x using:

\[\begin{align*} \vec{a} &= [0, 1, 0, 0, 0, 0] \\ \vec{b} &= [0, 1, 0, 0, 0, 0] \\ \vec{c} &= [0, 0, 0, 1, 0, 0]. \end{align*}\]

We can check the calculation y = sym_1 * x using:

\[\begin{align*} \vec{a} &= [0, 0, 0, 1, 0, 0] \\ \vec{b} &= [0, 1, 0, 0, 0, 0] \\ \vec{c} &= [0, 0, 0, 0, 1, 0]. \end{align*}\]

Don’t worry too much about the math details here. The important part to remember is that:

We can convert each line of the program qeval into a vector equation \((\vec{s} \cdot \vec{a}) * (\vec{s} \cdot \vec{b}) = \vec{s} \cdot \vec{c},\) where \(\vec{a}, \vec{b}, \vec{c}\) are publicly known and the prover knows the secret \(\vec{s}\).

As a result, in order to check the entire program, we must verify a system of vector equations.

Step 3: Quadratic equation on polynomials

The next step is to convert a system of vector equations into a single equation involving polynomials.

This is actually straightforward to do using polynomial interpolation. We take the constants from each of the equations and turn them into vectors of polynomials:

\(\vec{A} = A_1, A_2, \ldots, A_6\)
\(\vec{B} = B_1, B_2, \ldots, B_6\), and
\(\vec{C} = C_1, C_2, \ldots, C_6\).

Once again, don’t worry too much about the math involved here. The important thing is that we can represent any computer program as a series of public constants, with the property that any solution \(\vec{s}\) has the property that:

Quadratic arithmetic program corresponding to the constraint system (source: Quadratic Arithmetic Programs: from Zero to Hero)

In other words, multiplying the scalars within \(\vec{s}\) times each of the polynomials in turn will lead to a polynomial that is zero everywhere. In this way, we can convert a system of vector equations into a single (admittedly more complicated) equation.

(Nitpicky detail: sometimes the result of this calculation won’t be zero everywhere, but just on a large fraction of the space. Let’s not worry about this.)

Why did we do all of this? The major benefit of this approach 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.”

– Vitalik Buterin, Quadratic Arithmetic Programs: from Zero to Hero

Concretely, we have converted the prover’s claim into a new format.

We started with “I know an input x that causes qeval(x) = 35”
Our new claim is a polynomial equation of the form “I know a vector \(\vec{s}\) such that \((\vec{s} \cdot \vec{A}) * (\vec{s} \cdot \vec{B}) - \vec{s} \vec{C} = 0\)” (where all of the polynomials in \(\vec{A}, \vec{B}, \vec{C}\) are publicly known).

Here’s the punchline: checking a polynomial equation is easy, because it suffices to check it at a single point!

Suppose I have a polynomial \(P\) in my head, and I claim that \(P\) is the zero polynomial. You can check whether I’m telling the truth just by challenging me to reveal the value \(P(r)\) on a random value of your choice.

If \(P\) really was the zero polynomial, then clearly \(P(r) = 0\).
Otherwise, \(P\) has at most \(d\) roots (if it is of degree \(d\)), and there is a very small chance that you happened to pick one of the roots.

So once we have done this (strange) transformation of a computer program into a polynomial equation, there’s actually a simple three-step zero knowledge proof system.

The prover commits to its secret vector \(\vec{s}\) containing the state of the program at all times.
The verifier chooses a challenge point \(r\).
The prover uses the magic of polynomial commitments to reveal the value of the polynomial equation \((\vec{s} \cdot \vec{A}) * (\vec{s} \cdot \vec{B}) - \vec{s} \vec{C}\) when all polynomials are evaluated at \(r\). The verifier accepts if and only if the answer is 0.

Also, this proof can be made non-interactive using the Fiat-Shamir transformation from earlier in the lecture. This is how succinct proof systems work, behind the scenes.