Deeply understand some basic principles of constructing a universal, concise, non-interactive, publicly verifiable zero-knowledge proof zkSNARK.
Original title: “Introduction to Zero Knowledge Proof (2)”
Written by: Cyte
In the last article ” Introduction to Zero Knowledge Proof (1) “, we introduced the proof system and the definition of ZKP. Starting from this article, we focus on how to construct ZKP. We only discuss the construction of a universal, concise, non-interactive, publicly verifiable zero-knowledge proof , referred to as zkSNARK. This article will outline some basic principles of constructing zkSNARK and some commonly used tools for constructing zkSNARK. The specific zkSNARK construction scheme will be introduced one by one in subsequent articles.
NP language coding
According to the above definition, NP language is determined by its standard verification process, and its verification process is a piece of calculation logic. Coded NP language is essentially looking for a way to describe “computation”. Turing machine is a way of describing calculation, and another way is circuit. Of course, you can also use more advanced programming languages.
If you use a high-level programming language, the advantage is that it is relatively easy to write programs, but it is very complicated to deal with when constructing ZKP. The execution process of a Turing machine is very simple. It is easier to construct a ZKP for a Turing machine than a high-level language, but the experience of programming with a Turing machine is not very friendly. Therefore, we have to choose a balance between “easy to write programs” and “easy to construct ZKP”.
One option is the circuit. In terms of writing programs with circuits, it is relatively mature. For example, CPUs, various chips, embedded devices, and ASIC mining machines are all circuit designs. At the same time, the circuit structure is simple enough to not cause too much trouble to construct ZKP.
Another option is a slightly more complicated model than the Turing machine, called the Random Access Machine (RAM) model, which is also a good balance point. The RAM model can be seen as a simple modern computer, including a CPU and a memory. The CPU supports some simple instruction sets, and the memory can be accessed randomly.
In terms of expressiveness, RAM is actually more advantageous than circuits because it is closer to modern computers. Using RAM model to describe the calculation process is like writing a program in assembly. Compiling a high-level language into an assembler is more convenient than compiling into a circuit. However, it may be because the RAM model is more complicated to process than the circuit. At present, most zkSNARKs are based on circuit models, and very few are based on RAM models. STARK is one of the representatives, and the structure of STARK is extremely complicated.
When constructing zkSNARK, the arithmetic circuit (Arithmetic Circuit) is commonly used instead of the common Boolean circuit in hardware. The main differences are:
- Boolean circuits deal with Boolean values, and arithmetic circuits deal with elements in the finite field F;
- The gates of Boolean circuits are logic gates, and the gates of arithmetic circuits are addition gates and multiplication gates;
- Arithmetic circuits are more friendly to calculation logic involving algebraic operations
Arithmetic circuits can be further transformed into mathematical models. This process is called Arithmetization . Here are some common mathematical models transformed from circuits.
R1CS
By taking different matrices, R1CS problems can represent all NP problems. To encode an NP problem as R1CS, first express its verification process with arithmetic circuit C, and then further transform it into R1CS problem (A, B, C).
QAP
Suppose polynomial
Hadamard product problem
The following summarizes the calculation model used by the existing zkSNARK:
- QAP: Mainly a series of zkSNARKs based on bilinear pairs represented by the Groth16 scheme in use
- Hadamard relationship: programs that use it include BulletProof, Sonic
- R1CS: Almost all circuit-based zkSNARKs use R1CS, such as Groth16, Marlin, Spartan, Fractal, Aurora
- Layered circuit: GKR and Libra are based on layered circuit
- RAM: STARK is based on RAM. In fact, it has also been arithmeticized and constructed a mathematical problem called AIR. After a very complex conversion, a problem called ACSP is obtained.
- Others: For example, some zkSNARKs such as PLONK have developed an arithmetic solution by themselves. We will introduce the corresponding zkSNARK solution in a follow-up article.
Achieve simplicity
We just mentioned that there is a standard verification process for NP problems. Compared with this standard verification, zkSNARK has two advantages:
- Zero knowledge (ZK): Standard verification requires evidence, but zkSNARK verification does not, and zkSNARK certification does not reveal any information
- Succinct: There are two requirements: a) zkSNARK proof is smaller than the evidence b) and/or Verifier verifies that zkSNAKR proof is faster than standard verification
These two advantages are very meaningful when taken separately. Needless to say the meaning of ZK. Even if there is only conciseness, that is, SNARK (not zkSNARK), there are some very important application scenarios, such as proxy computing. For example, a mobile phone can perform a large number of calculations with the help of a cloud server, and only a small amount of calculations can be performed locally to verify the calculation results. In this scenario, the cloud server does not need privacy, and ZK is not needed, but it needs simplicity.
Note that among the two requirements for simplicity, there is a natural obstacle to the point of “verification faster”: As mentioned above, the general zkSNARK system does not contain any NP language information, and Verifier needs to verify an NP Language, it is necessary to input the code of this NP language, which may be recorded as C. C needs to include a complete calculation process, so the scale of C is actually equivalent to the amount of calculation. Then, Verifier is already slower than the standard verification of this NP language by just reading C.
There are two solutions to this problem:
- It is assumed that the standard verification of NP language can be described with a short message. The general circuit cannot be done, because the circuit size is equivalent to the calculation amount. With Turing machine, RAM or high-level language, it is possible to describe a large amount of calculation with very little information. The key reason is that the code can be reused. For example, a simple loop in a high-level language code may not exceed 100 bytes when written down, which may represent a much larger amount of calculation. This calculation process is called “uniform” calculation, because most calculations perform similar logic. However, if there is a restriction on uniform calculation, a large part of NP language will be excluded.
- Preprocess C. Compress C into a small string, let’s denote it as c. Verifier only enter c. Of course, in this way, Verifier does not have direct access to the calculation process that needs to be verified, and some cryptographic tools are needed to prevent Prover from doing evil. For example, c can be C’s cryptographic promise.
Essentially, these two solutions are the same, that is, to compress C. If C represents a uniform calculation, it can be compressed losslessly, otherwise it can only be compressed with cryptographic tools.
Ideal model
Our goal is to construct zkSNARK. In our target scenario, Prover only needs to send a short proof string to Verifier, and Verifier does not need to send any message to Prover.
It may be difficult to directly construct a zkSNARK that satisfies this scenario. A more flexible way is to first construct the proof system under the ideal model, and then use a general conversion to convert this system that can only work in an ideal scenario into a zkSNARK that can work in a real scenario.
In the ideal model, it means that the model uses functions that do not exist in the scene, which is called the ideal function. The existence of ideal functions makes the construction proof more convenient. After it is constructed, use cryptographic tools to simulate this non-existent function to achieve this ideal model.
The figure below is the ideal model commonly used by ZKP and the conversion relationship between them. Next we will introduce these models and the specific implementation of the conversion between them.
IP
We introduced the interactive proof system in the previous article. Looking at the scene of zkSNARK, the interactive system is an ideal model, because it provides an ideal function that does not exist in the scene, that is, Verifier can send messages to Prover.
The above method is called Fiat-Shamir transformation. Fiat-Shamir transformation can only convert interactive proofs of public random numbers into non-interactive proofs. Therefore, in the next ideal model, only ZKPs of public random numbers can be considered.
PCP
Babai et al. proposed a Probabilistically Checkable Proof (PCP) in 1991. In the PCP model, Prover constructs a proof string called PCP proof. The length of the PCP certificate can be very long, far exceeding Verifier’s computing power. Therefore, Prover does not directly send the PCP proof to Verifier, but sends an Oracle to Verifier, called the PCP Oracle. Verifier can query the PCP oracle at will to obtain bits at any position of the PCP string.
In order to understand the relationship between IP and PCP, let’s give a realistic example. We invite our familiar protagonists Alice and Bob. Suppose Alice is a graduate student who is about to graduate, and Bob’s task is to assess whether Alice’s subject is qualified. The IP model is a defense. Alice and Bob have a direct conversation. If Alice can successfully answer all of Bob’s questions, Alice will successfully graduate. In the PCP model, there is no defense. Alice just sends the graduation thesis to Bob, and the graduation thesis is super long. Bob can’t finish reading the thesis, so he can only randomly select a few paragraphs in the thesis to read. If none of these paragraphs are selected The problem is logically fluent, and Bob believes that Alice’s project is qualified.
The PCP oracle machine provides such a function: it is very short, and only a small amount of communication is required to transmit it; the amount of information it transmits is large, and a long string of characters can be randomly accessed through it. Obviously, there is no real PCP oracle, and PCP is an idealized model.
The Merkle-Tree in the above process can be replaced by a more general cryptographic component Vector Commitment (VC) . VC allows Prover to send a short string to Verifier, representing a commitment to a vector, and Verifier can enable Prover to display the value at any position in the vector and provide a proof of legality. The length of the proof is much less than the length of the vector . In fact, Merkle-Tree is a simple VC implementation.
IPCP
The IPCP (Interactive PCP) model can be regarded as the addition of the IP model and the PCP model. In the IPCP model, after Prover sends the PCP oracle to Verifier, Prover and Verifier continue to interact. During the interaction, Verifier can access the PCP oracle from time to time.
Continue to use the example of Alice and Bob in the previous section. If the IP model only has a defense, and the PCP model only has a graduation thesis, then the IPCP model is to send the graduation thesis to Bob before Alice’s defense. During the defense process, Bob can ask Alice questions while reading the graduation thesis.
The proof system constructed based on the IPCP model can also be transformed into a proof system under the IP model through Merkle-Tree or a general VC scheme. The process is exactly the same as the conversion of the PCP model. The only difference is that Verifier may be mixed in the request to query the PCP proof Ordinary interaction.
Both the IP model and the PCP model can be regarded as special IPCP models. Among them, the IP model is equivalent to Prover in the IPCP model sending an empty oracle to Verifier. The PCP model is equivalent to omitting the dialogue link between Prover and Verifier in IPCP.
IOP
If the IPCP model is the addition of IP and PCP, then the IOP (Interactive Oracle Proof) model is the multiplication of IP and PCP. In the IOP model, Verifier sends a message to Prover, and Prover sends a PCP oracle to Verifier. Verifier can freely query any PCP oracle that Prover has sent.
Continue to use the previous examples of Alice and Bob to explain the IOP model. Alice sends the graduation thesis to Bob, and Bob responds to Alice with a short comment, then Alice writes another thesis and sends it to Bob, and Bob responds again, doing so many times. In this process, Bob can read any paper that Alice has sent him at any time. Of course, Bob still doesn’t have enough time. Bob can still only select a small part of the paper at random. Finally, Bob judges whether Alice’s project is qualified.
Like PCP and IPCP, the proof system constructed under the IOP model can also be similarly transformed into the proof system under the IP model.
The IPCP model can be regarded as a special IOP model. In the IPCP model, the Prover message in the dialogue link is regarded as a PCP oracle, then a protocol under the IPCP model can be regarded as a protocol under the IOP model.
PIOP
The polynomial IOP (Polynomial IOP, PIOP) model is a further generalization of the IOP model. Similar to the IOP model, in the PIOP model, Verifier sends a message to Prover, and Prover sends an oracle to Verifier, but this time the difference is that Prover sends a polynomial oracle.
Because the polynomial oracle can realize the function of the PCP oracle, the IOP model can be regarded as a special PIOP model.
Converting the proof system constructed under the PIOP model to the system under the IP model, the basic idea is the same as that of PCP, IPCP and IOP, that is, let Prover replace the role of polynomial oracle, but the required cryptographic tools are different . Simple Merkle-Tree or VC cannot simulate polynomial oracles. We need to use a more powerful cryptographic tool called Polynomial Commitment (PC).
Next we introduce two other models, LIP and LPCP. The existing Verifier complexity and the zkSNARK whose proof size is a constant level are constructed based on these two models.
LIP
In the Linear IP (LIP) model, Prover and Verifier talk to each other. However, compared to the IP model, some restrictions are added: Prover can only be linear.
In this way, not only Prover but also Verifier can only perform linear operations. In this way, the system doesn’t make much sense. In order to allow Verifier to do at least one nonlinear operation, one method is to introduce bilinear pairs. Bilinear pairing allows multiplication of ciphertext, but the calculation result of multiplication is in another ciphertext space, so it does not affect security.
LPCP
summary
This article introduces the basic principles and commonly used tools for constructing a general concise zero-knowledge proof (zkSNARK). Firstly, the description of NP is discussed, including mathematical problems such as Turing machine, circuit and R1CS. Then discussed the necessary ways to achieve simplicity: either assume that the calculation is uniform, or use preprocessing. Finally, it is more convenient to construct a zero-knowledge proof in an ideal model than directly in a non-interactive scene. This article introduces several ideal models and how to transform the zero-knowledge proof in the ideal model into zkSNARK.
references
S. Arora, B. Barak, “Computational Complexity: A Modern Approach”
L. Babai, L. Fortnow, L. Levin, M. Szegedy, “Checking Computations in Polylogarithmic Time”
