Zero-Knowledge Proofs

Today, we focus on how to construct ZKPs. We will discuss the construction of general, succinct, non-interactive, publicly verifiable zero-knowledge proofs, abbreviated as zkSNARKs. This article will outline some basic principles for constructing zkSNARKs and some commonly used tools for their construction. Specific zkSNARK construction schemes will be introduced in subsequent articles.

According to the above definition, NP languages are determined by their standard verification process, which is a computation logic. Encoding NP languages essentially involves finding a way to describe "computation." A Turing machine is one way to describe computation, and another way is through circuits. Of course, higher-level programming languages can also be used.

Using high-level programming languages makes writing programs relatively easy, but handling them in ZKP construction is very complex. The execution process of a Turing machine is simple, making it easier to construct ZKPs for a Turing machine, but programming with a Turing machine is not user-friendly. Therefore, we need to choose a balance between "ease of programming" and "ease of constructing ZKPs."

One choice is circuits. Writing programs with circuits is already quite mature, for example, CPUs and various chips, embedded devices, ASIC miners, etc., are all designed with circuits. At the same time, the structure of circuits is simple enough not to bring too much trouble to ZKP construction.

Another option is a model slightly more complex than a Turing machine, called the Random Access Machine (RAM) model, which is also a good balance. The RAM model can be considered a simple modern computer, including a CPU and memory. The CPU supports a simple instruction set, and the memory can be randomly accessed.

In terms of expressiveness, the RAM is more advantageous than circuits because it is closer to modern computers. Describing the computation process using the RAM model is like programming in assembly language. Compiling high-level language into assembly is more convenient than compiling into circuits. However, possibly due to the complexity of handling the RAM model, most zkSNARKs are based on circuit models, with very few based on the RAM model. STARK is one such example, and its construction is extremely complex.

In zkSNARK construction, arithmetic circuits are commonly used rather than the boolean circuits seen in hardware. The main difference is that arithmetic circuits can be further converted into mathematical models. This process is called arithmetization. Below are some common mathematical models converted from circuits.

By taking different matrices, the R1CS problem can represent all NP problems. Encoding an NP problem into R1CS involves first representing its verification process with an arithmetic circuit CCC, then further converting it into the R1CS problem (A,B,C)(A, B, C)(A,B,C).
Here are some existing models used by zkSNARKs.

We've discussed that NP problems have a standard verification process. Compared to this standard verification, zkSNARKs have two advantages.

These two advantages are meaningful on their own. The significance of ZK (zero-knowledge) is evident. Even if there is only succinctness, i.e., SNARK (without ZK), there are important applications, such as delegated computation. For example, a mobile phone can utilize cloud servers for heavy computation while performing minimal local computations to verify the results. In this scenario, the cloud server doesn't need privacy, only succinctness is required.

Note that for succinctness, "faster verification" faces a natural obstacle: in a general zkSNARK system, without any information about the NP language, the verifier needs to input the encoding of the NP language, denoted as CCC. CCC needs to include the entire computation process, and its scale is comparable to the computation itself. Therefore, the verifier simply reading CCC would be slower than the standard verification of the NP language.

This problem can be solved in two ways:
Essentially, these two methods compress CCC. If CCC represents uniform computation, it can be losslessly compressed; otherwise, cryptographic tools must be used for compression.
Our goal is to construct zkSNARK. In our target scenario, the prover only needs to send a short proof string to the verifier, and the verifier doesn't need to send any messages back to the prover.

Directly constructing a zkSNARK for this scenario might be difficult. A more flexible approach is to first construct a proof system in an ideal model and then use a general transformation to convert this ideal model system into a zkSNARK that works in a real-world scenario.

In an ideal model, this model uses functionalities that don't exist in the real scenario, called ideal functionalities. These ideal functionalities make constructing proofs more convenient. After construction, cryptographic tools are used to simulate these non-existent functionalities to realize the ideal model.We will introduce these models and their transformations in detail next. From the perspective of zkSNARK, the interactive system is an ideal model because it provides an ideal functionality not present in the real scenario, i.e., the verifier can send messages to the prover.

The above method is called Fiat-Shamir transformation. Fiat-Shamir transformation can only convert public randomness interactive proofs into non-interactive proofs, so the next ideal model only considers constructing ZKPs with public randomness.

In 1991, Babai et al. proposed probabilistically checkable proofs (PCP). In the PCP model, the prover constructs a proof string called the PCP proof. The PCP proof can be very long, far exceeding the verifier's computational capacity. Therefore, the prover does not directly send the PCP proof to the verifier but sends an oracle called the PCP oracle. The verifier can query the PCP oracle at will to obtain any bit of the PCP string.

To understand the relationship between IP and PCP, let's take a real-world example. Suppose Alice is a graduate student about to defend her thesis, and Bob's task is to evaluate whether Alice's thesis is qualified. The IP model is akin to a defense: Alice and Bob directly converse, and if Alice can successfully answer all of Bob's questions, she passes. In the PCP model, there is no defense; Alice simply submits her thesis, which is extremely long. Bob cannot read it all and can only randomly select segments to read. If the selected segments are error-free and logically coherent, Bob believes Alice's thesis is qualified.

The PCP oracle provides this functionality: it is short and easy to transmit, yet it represents a large amount of information. Through it, one can randomly access a very long string. Clearly, a real PCP oracle doesn't exist; PCP is an idealized model.

In the above process, the Merkle-Tree can be replaced by a more general cryptographic component called Vector Commitment (VC). VC allows the prover to send a short string to the verifier, representing a commitment to a vector. The verifier can then request the prover to reveal any position within this vector and provide a validity proof, which is much shorter than the vector itself. In essence, a Merkle-Tree is a simple implementation of VC.

The IPCP (Interactive PCP) model can be seen as a combination of the IP and PCP models. In the IPCP model, after the prover sends the PCP oracle to the verifier, they continue interacting. During this interaction, the verifier can occasionally access the PCP oracle.

Continuing with the example of Alice and Bob: if the IP model is just a defense, and the PCP model is just the thesis, then the IPCP model is where Alice sends her thesis to Bob before the defense. During the defense, Bob can read the thesis while questioning Alice.

Proof systems based on the IPCP model can be transformed into proof systems in the IP model through Merkle-Tree or general VC schemes, in the same way as PCP model transformations. The difference is that in the IPCP model, the verifier's queries to the PCP proof might be mixed with ordinary interactions.

Both the IP and PCP models can be seen as special cases of the IPCP model. In the IP model, the prover sends an empty oracle to the verifier. In the PCP model, the prover-verifier interaction phase is omitted.

If the IPCP model combines the IP and PCP models additively, then the IOP (Interactive Oracle Proof) model multiplies them. In the IOP model, the verifier sends messages to the prover, and the prover responds with a PCP oracle. The verifier can query any PCP oracle sent by the prover.

Using the Alice and Bob example again: Alice sends her thesis to Bob, Bob responds with brief comments, Alice writes another thesis and sends it back, and this back-and-forth happens multiple times. During this process, Bob can read any of the theses sent by Alice, though his time is still limited, so he can only randomly read parts of them. Finally, Bob judges whether Alice's thesis is qualified.

Like PCP and IPCP, proof systems constructed in the IOP model can be transformed into IP model proof systems.

The IPCP model can be seen as a special case of the IOP model. In the IPCP model, viewing each message from the prover as a PCP oracle makes an IPCP protocol an IOP protocol.
The Polynomial IOP (PIOP) model further generalizes the IOP model. In the PIOP model, like in the IOP model, the verifier sends messages to the prover, and the prover responds with an oracle. However, this time, the prover sends a polynomial oracle.

Since a polynomial oracle can simulate a PCP oracle's functionality, the IOP model can be considered a special case of the PIOP model.

The basic idea of transforming proof systems constructed in the PIOP model into systems in the IP model is similar to that of PCP, IPCP, and IOP: the prover takes the role of the polynomial oracle. However, different cryptographic tools are required. Simple Merkle-Trees or VCs cannot simulate polynomial oracles. Instead, a more powerful cryptographic tool called Polynomial Commitment (PC) is needed.

Next, we introduce two other models, LIP and LPCP. The existing zkSNARKs with constant verifier complexity and proof size are based on these models.

In the Linear IP (LIP) model, the prover and verifier interact. However, compared to the IP model, there are additional constraints: the prover can only perform linear operations.
Thus, not only the prover but also the verifier can only perform linear operations. This limitation makes the system less meaningful. To allow the verifier to perform at least one nonlinear operation, a method is to introduce bilinear pairings. Bilinear pairings allow multiplication on ciphertexts, where the result remains in another ciphertext space, maintaining security.

This article introduces the basic principles and commonly used tools for constructing general succinct zero-knowledge proofs (zkSNARKs). We discussed characterizing NP, including Turing machines, circuits, and mathematical problems like R1CS. We then explored necessary methods to achieve succinctness: assuming uniform computation or using preprocessing. Finally, constructing zero-knowledge proofs in ideal models is more convenient than directly in non-interactive scenarios. Several ideal models and the transformation of zero-knowledge proofs into zkSNARKs were introduced.

References:

• S. Arora, B. Barak, "Computational Complexity: A Modern Approach"
• L. Babai, L. Fortnow, L. Levin, M. Szegedy, "Checking Computations in Polylogarithmic Time"