Intuition about ZK

One sentence for ZK: ZK is a way for a prover to convince a verifier that some statement is true but reveals no additional information except that the statement is true. ZK is designed for anonymity. Imagine that we can prove we have a valid ID without verifiers knowing our real name or ID.

Here is a more vivid example. Alice and Bob are playing Sudoku. Alice would like to show Bob that she found the answer. However, she did not want to reveal any information about the answer since Bob was still working on it. How will you design this proof?

The answer is simple. We write down the Sudoku into cards, facing down. Bob can randomly choose one column, row, or block. Alice takes that column, row, or block of cards and shuffles it. Bob can verify the correctness by checking cards with 1-9. By constantly performing this step, Bob can say that Alice knows the answer, but Bob does not know the answer after the verification.

If you still can’t get the idea, view this video. The UCLA CS professor will explain ZK on five different levels. You will definitely get it.

Common ZK Proof System

Before examining the ZK Proof System comprehensively, notice that ZK-SNARK is a name of a class of schemes, and ZK-STARK is the name of a specific scheme.

Let’s start with ZK-SNARK. SNARK stands for Succinct Non-Interactive Arguments of Knowledge. SNARK is unique from other ZK proof systems because of its trust setup phase, what ‘N’ stands for.

• Succinct: The proof size and verification time are smaller than the original computation (statement).
• Non-interactive: The provers and verifiers do not need to communicate back and forth for each round. Instead, the provers and verifiers need to finish the initial setup phase. Even if they miss the setup phase, public verifiers can also join the verification later.
• Arguments: Provers with extremely large computation power can cheat the verifiers by generating wrong proofs. When this happens, the public/private key encryption is also broken.
• Knowledge: The prover needs to know something secret to make the proof.

The problem with ZK-SNARK is the trust setup phase. The trust setup phase generates a reference string. If the reference string is leaked, anyone can make the fake proof. Also, coordinating such a trust setup phase between multiparty is complex. The reference string can only be used in one program (Circuit). Thus it is impossible to have ZK-SNARK with a single trust setup for general computation. Another problem is that the reference string is not upgradable. If we upgrade the program, we need to rerun the trust setup phase.

To solve the problem, there are two approaches:

• Transparent Setup: The trust setup phase sets a CRS (Common Reference String). If the CRS is leaked, the ZK proof system will not be hurt. Fractal, Halo, SuperSonic and ZK-STARK use this approach. The problem with this approach is that the size of the proofs may be in kBs. This would be too large for the blockchain area.
• Universal Setup: The setup creates a secret reference string, but it is structured. Thus it can be used in not only one program. Marlin, SuperSonic-RSA, and Plonk use this approach.