Following the last time Shor issued a comprehensive research on routing issues in payment networks , another Nervos partner Cyte who loves research did a detailed research on zero-knowledge proofs.
In this article, Cyte will introduce to you the definition of zero-knowledge proof (ZKP) , and distinguish zero-knowledge proof from the two concepts of SNARK and STARK.
These cryptographic concepts such as ZKP, SNARK and STARK have become popular with the recent rise of blockchain. However, they are often misunderstood and mixed. In fact, all these concepts belong to a broader category, called Proof System , or Cryptographic Proof . Zero-knowledge proof and SNARK and STARK have overlapping parts, but they do not contain each other. The relationship between them can be represented by a diagram.
This article will first introduce the definition of the proof system and discuss the various properties of the proof system, focusing on “zero knowledge”, “knowledge proof”, “simplicity” and “non-interactive”. In particular, if a proof system has “zero-knowledge”, then it is called a “zero-knowledge proof”. Finally, the article will discuss the definition of SNARK and STARK and compare them.
Proof system
A proof system (Proof System) is an interactive protocol that includes two participants, Prover and Verifier, and an algorithm Setup. The function of the proof system is to allow Prover to persuade Verifier to believe in one thing, which we call a statement .
Before the protocol starts, someone needs to call the Setup algorithm. The Setup algorithm accepts some public parameters as input and outputs the Setup information required by Prover and Verifier. The information learned by Verifier is recorded as, and the information learned by Prover is recorded as. The common part of and is called Common Reference String (CRS) . Who calls the Setup algorithm and when it depends on the design of the proof system. At the beginning of the agreement, Prover and Verifier received input statements at the same time. Prover must have some additional advantages over Verifier, such as more powerful computing power, or some additional input. In addition, Prover and Verifier also learned and respectively. The time to obtain the Setup information depends on the design of the certification system. For example, it is possible that Prover and Verifier have already been downloaded and stored in their respective hard drives for repeated use, or they may have been entered on the spot before the start of the agreement. Then Prover and Verifier start to implement the protocol stipulated by the certification system. If Prover and Verifier are both honest, then they both strictly abide by the agreement. However, it is also possible that one party is malicious and does not execute in accordance with the agreement. What happens at this time depends on the security of the certification system. If both parties are malicious and neither follow the agreement, then it has nothing to do with this certification system. Finally, Verifier outputs accept or reject, indicating whether to believe the statement. A proof system needs to satisfy two properties:
- Completeness : If the statement is correct and both Prover and Verifier comply with this agreement, then Verifier outputs accept with a probability of at least, which is called the completeness error of the proof system here .
- Reliability (Soundness) : If the statement is incorrect, then Prover must be dishonest, and Verifier abides by the agreement, then any Prover cannot let the probability of Verifier output accept exceed. This is called the reliability error of the proof system (Soundness error)
These two requirements are the most basic requirements for a certification system to be established. Without any requirement, we can get a certification system that meets the conditions but is completely useless. For example, if we only require integrity, then no matter what Prover does, Verifier will always output accept only; if we only require reliability, then let Verifier always output reject only. In addition, it is generally hoped that and do not exceed, and the sum is less than, otherwise this proves that the system error is too large and it is almost useless. If the reliability of a proof system is only valid for any Prover with limited computing power , that is, an adversary with unlimited computing power is likely to deceive Verifier. At this time, the proof system has only computational reliability (Computational Soundness) , so The system is also called the Argument System (Argument System) . In contrast, the reliability that is safe for any Prover is called Statistical Soundness .
Prove other properties of the system
A proof system can also satisfy some other (not necessary) properties
- CRS model (CRS model) : If the Setup information is publicly visible to everyone, namely Setup=Setup=Setup, it is said that this certification system is under the CRS model
- Interactive/Non-interactive : If only the Prover sends a message to Verifier during the entire interactive process, the system is called a non-interactive certification system; otherwise, the system is an interactive certification system
- Transferable/Deniable : If the statement is correct and the interaction process is sent to other Verifiers, it can also convince other Verifiers that the statement is correct. This certification system is transferable; otherwise this certification system Is denial
- Public Verifiable / Designated Verifier : If the Setup is publicly visible to everyone, that is, anyone can become a Verifier, this zero-knowledge proof system is publicly verifiable. Otherwise this system is for specific verifiers
- Public coin : If the selection of all messages of Verifier are uniformly random and independent of Prover’s messages, the system is said to be publicly random
- Zero-Knowledge : If the statement is correct, if Verifier cannot obtain any other “knowledge” from the interaction except for the correctness, the system is said to be zero-knowledge
- Succinctness : If the proof system is used to prove NP language, and the communication volume of the proof system is smaller than the proof, then the proof system is concise
Example: Prove that the colors of the two balls are different
Setup message: There are two balls
Statement: The two balls are of different colors. Verifier has limited computing power (blindfolded) and Prover has normal vision
- Verifier holds a ball in each hand and shows it to Prover.
- Verifier puts his hands behind his back, and then (in his heart) randomly toss a coin. If it is heads up, swap the balls in the left and right hands, otherwise, don’t swap.
- Verifier took the ball out and showed it to Prover.
- Prover tells Verifier if the two balls have been exchanged.
Result: If Prover guesses correctly, Verifier outputs accept, otherwise Verifier outputs reject. Completeness of nature discussion If the colors of the two balls are different, it is obvious that Prover will be able to guess whether Verifier has exchanged the ball with a 100% probability. If the colors of the two balls are the same, then Prover can only guess blindly, with only 1/2 probability of guessing. The reliability error of this system is 1/2 CRS. This proves that the system is under the CRS model, because the Setup information is publicly interactive. This is an interactive system, because Prover and Verifier send more than one piece of information to each other. This system is not transferable. The ones that migrate can be denied. Even if Verifier records the interaction process and shows it to other blindfolded people, they cannot be sure that the two balls are of different colors. Public verifiability. This system is publicly verifiable. Any Verifier can conduct this agreement with Prover to disclose randomness. The system is not openly random, because the information Verifier sends to Prover is not uniformly random with zero knowledge. This system is zero knowledge, because when the colors of the two balls are indeed different, Prover’s guess is what Verifier expected, except Indicates that there is no additional knowledge other than the correctness of the statement x
importance
Above we have given the definition, examples and properties of the proof system. Next we discuss several important properties of the proof system.
Zero knowledge
Zero-knowledge is used to protect the honest Prover from being deceived by the malicious Verifier and reveal the secret evidence needed for the proof.
The zero-knowledge nature of the proof system has already been mentioned above, which simply means that Verifier cannot obtain any “knowledge” from the interaction. This description is inaccurate because it does not give a strict criterion. The definition of zero-knowledge itself is counterintuitive: Prover clearly sends some bits of data to Verifier, why is this system “zero-knowledge”? In fact, “information” is not the same as “knowledge.” If Verifier obtains the information, but obtaining the information does not allow Verifier to calculate more results, or the information can be calculated by Verifier itself, then Verifier has not obtained any “knowledge”. During the execution of a certification system, all information obtained by Verifier includes: Verifier’s own random number; all information sent by Prover to Verifier (denoted as ). We call this information Verifier’s “field of view”, denoted as. This information is the source of all uncertainties in the Verifier calculation process. After confirming this information, everything else can be calculated deterministically. Note that is a random variable. After Verifier and Prover execute the proof system, Verifier will obtain a sample of this random variable. If Verifier can sample independently without Prover’s participation, then this system is zero-knowledge. We call the algorithm for sampling this random variable the Simulator . Depending on how the simulator works, there are different definitions as follows:
- Non-black box simulator, the corresponding zero knowledge is called non-black box zero knowledge. This zero-knowledge definition allows each Verifier to have an “exclusively customized” simulator. This definition allows the simulator to customize different sampling processes for different Verifier implementation details.
- The black box simulator corresponds to the black box zero knowledge. This zero-knowledge definition requires the existence of a unique simulator, so that it can sample all Verifiers. It is impossible for this only simulator to know all the specific implementation details of Verifier, so it can only access Verifier through black box calls. However, the simulator has complete control over Verifier. The simulator can determine the random number of Verifier and input any Prover message or to Verifier. Therefore, in the eyes of the simulator, Verifier is a black box deterministic algorithm.
- If the simulator is only for honest Verifier, it corresponds to Honest Verifier ZK. Because the honest Verifier’s behavior is completely expected, the simulator can naturally use this information, so this simulator’s access to Verifier is not a black box.
Non-black box simulators have access to more information, so non-black box zero knowledge is easier to establish than black box zero knowledge. And honest Verifier zero knowledge is the easiest to achieve. Regarding zero knowledge of honest Verifier, the honest Verifier here is more accurately semi-honest, or “honest but curious”. Such a Verifier will obey the agreement on the surface, but may try to extract knowledge from the message in private. In contrast, malicious Verifier’s behavior is completely unrestricted. Verifier may crash, send messages that do not conform to the format, sample distributions that do not follow the protocol, and so on. To prove that a system satisfies zero knowledge of malicious Verifier, it is necessary to cover all these situations. The simulator is a random algorithm, and its output value is also a random variable, denoted by. The zero knowledge requirement and these two random variables are difficult to distinguish. However, there are many versions of the word “indistinguishable”, from which various definitions of zero-knowledge proof can be derived:
- If the distribution of two random variables is statistically indistinguishable, that is, their statistical distance (Statistical Distance) is negligible, the proof system is said to be statistically zero-knowledge (Statistically Zero-Knowledge) ; if the statistical distance is 0, then It is called Perfect Zero-Knowledge ;
- If the distributions of two random variables are computationally indistinguishable, that is, no random adversary in polynomial time can distinguish the two distributions, then the proof system is said to be Computationally Zero-Knowledge .
Note that in the definition of zero-knowledge, only correct statements are required , and the distribution of and is difficult to distinguish. Regarding false statements, we don’t care what knowledge Verifier can acquire, because in this case Prover itself is dishonest and there is no need to protect it. In other words, since Prover does not comply with the agreement, then our agreement is well designed It cannot be protected. However, although the distribution of zero-knowledge pairs does not make any assumptions in the case of errors, if the probability of passing the verification by Verifier obtained from the wrong sampling is significantly different from that in the correct case, we can use this to judge The correctness. This means it can only come from an ordinary NP language. Therefore, for difficult NP problems, if you input the wrong input to the simulator, the result can be verified with the same probability. In this way, zero knowledge and reliability are not contradictory? In other words, why can’t Prover call the emulator to cheat Verifier for wrong? In fact, Prover cannot control Verifier, and it cannot provide the simulator with the resources needed for sampling. Indeed, a malicious Prover can call the emulator, but this is useless for it, because the output of the emulator is not the random number of the Verifier that is interacting with the Prover. In addition, the output of the simulator may be different from the one received by Verifier, which may cause the verification to fail. However, the simulator tuned by Prover cannot get the random number of Verifier, which is enough to ensure security, so even fixed constants in interactive proof are fine.
Proof of knowledge
If Prover is required to “know” some information in order for Verifier to pass verification, this system is called Proof of Knowledge . Proof of knowledge can be seen as an enhanced version of reliability. Knowledge proof also has a computational version called Argument of Knowledge .
Knowledge proof system is usually used to prove NP language. An NP language refers to a set, so that the element belonging to can be proved by a piece of evidence, that is, there is a polynomial time algorithm that can determine whether it belongs to legal evidence. Ordinary certification system allows Prover to prove to Verifier. The knowledge proof system allows Prover to prove to Verifier not only that, it can also prove that Prover “knows”. In other words, even if Prover does not know the corresponding, it is difficult to pass the verification. Similar to the zero-knowledge discussed in the previous section, “knowledge” also needs a strict definition. A program P “knows” the data, how should it be defined? Imagine running this program in a virtual machine, and its random number can be arbitrarily specified by us. During its entire operation, the complete history of the CPU state and all memory read and write operations can be recorded by the virtual machine. If this program “knows”, we should always extract information from these records. In fact, this is the Extractor An intuitive way of understanding. The extractor is an algorithm that can run simultaneously with the extracted program and can access the internal state of the extracted program. Finally, it can output the extracted results. The extractor described above is a non-black box extractor because it can access the internal state of the extracted program. The algorithm of a non-black box extractor must vary with the extracted program. Therefore, a proof system is a knowledge proof, which is defined as follows: “For any Prover, there is an extractor that executes at the same time and can access the internal state. If it outputs accept after interacting with it, it will output satisfy Conditional.” Similar to the simulator in the zero-knowledge definition, the extractor can also be defined in a black box. The extractor cannot access the internal state of the program, but it can call this program, control the random number of this program, and read the output of this program. We introduce such a notation to indicate that the extractor accesses the interaction process of a pair of Prover and Verifier through a black box. The black box extractor only needs one for all Prover, so the knowledge proof can be defined as follows: “There is an extractor for any Prover, if it outputs accept after interacting with it, then it will output the one that meets the conditions. “
Simplicity
Use to represent an instance of NP language, and to represent evidence in the language. Succinctness is a linear function that proves that the amount of communication required by the system is less than. In other words, Prover and Verifier implement this certification system, which saves communication bandwidth than Prover sends directly to Verifier. Sometimes, conciseness may also require Verifier’s calculations in the proof system to be lower than verification. In short, simplicity requires proof that the system has advantages in terms of efficiency.
We may want a concise proof that the communication volume of the system is logarithmic or lower, that is,. However, such succinctness requirements will bring safety losses. Because if the communication volume is as low as logarithmic level, the entire space where Prover’s message combination is located can be exhausted in time. However, the reliability of the system requires that Prover cannot find a way to pass Verifier’s verification for false statements. If it can be verified that the pass does not exist at all, this can indeed ensure reliability. But in this way, the legitimacy of can be judged by exhaustive enumeration, then it is not a difficult problem, which excludes general NP language. If we want a general NP language proof system, we must allow a small number of can be verified even for wrong. In this case, we can only introduce an additional security parameter and relax the size of the communication to make the complexity of the exhaustion reach, so that at least the reliability in the sense of calculation is achieved. At the same time, the communication volume is still logarithmic relative to, so it satisfies the simplicity. In summary, for the general NP language, the concise proof system (logarithmic level) can only be an argument system.
Non-interactive
Non-Interactivity (Non-Interactivity) refers to the proof that all interactions of the system are only a message sent by Prover to Verifier. This message is called a proof and is recorded as. Non-interactivity can bring a lot of convenience and bring more application scenarios for the proof system. For example, in the blockchain system, non-interactive zero-knowledge proofs can be attached to transactions for anyone to check at any time, without requiring the author of the transaction to interact with the verifier online at any time.
Any NP language naturally has a non-interactive proof protocol, that is, Prover sends proof directly to Verifier, and this proof is proof of knowledge. Therefore, it is of little significance to construct a proof system that is purely non-interactive. Non-interactivity is only interesting when combined with the two properties discussed above, namely zero knowledge or simplicity. Non-interactive + zero-knowledge combines zero-knowledge and non-interactive, and there is a non-interactive zero-knowledge (Non-Interactive Zero-Knowledge, NIZK). When we discussed zero-knowledge before, we mentioned that the reason why zero-knowledge is not inconsistent with reliability is that the probability of calling the simulator sample is different from the random number of the Verifier interacting with Prover. However, for non-interactive zero knowledge, we have to re-examine this reasoning process. In the interactive proof, a Verifier with a random number can verify the passed Prover message, and it is likely to fail the verification if it is directly moved to the Verifier with a random number. Therefore, in interactive proof, the correctness of is not global, but dependent. In the non-interactive proof, Prover did not receive any message from Verifier, so Verifier’s random number was not used in Prover’s calculation process. Therefore, in order to prove the integrity of the system, the honest Prover output can be verified for most of the Verifier random numbers. Therefore, the correctness of non-interactive proof is global and does not depend on anything. Zero knowledge requirements, Verifier’s field of view and simulator output are indistinguishable. This means that if these partial components are observed individually, they are also indistinguishable. Even and in are indistinguishable. Therefore, a malicious Prover can call the emulator to output. This is not a problem in interactive proofs, the malicious Prover just got the correct one. But in non-interactive proof, the correctness of is not dependent on, which will bring security problems. At this time, it is time to play a role. Although the correctness of is no longer dependent on, it still depends on. For reliability, we hope that given and statements are difficult to calculate that can be verified. Although the simulator can output a pair of at the same time when given, it is difficult to calculate the former first and then the latter. How to do this will be explained in detail when we introduce specific solutions in subsequent articles. Non-interactive + Simplicity As mentioned above, the proof system for simplicity must be an argumentation system. Combined with non-interactivity, there is a succinct non-interactive argument (Succinct Non-interactive ARGument, SNARG). In fact, the system that satisfies the definition of SNARG was constructed by Micali as early as 2000, and the name appeared later. If a SNARG is also a knowledge argument, it is called a Succinct Non-interactive ARgument of Knowledge (SNARK) . The name SNARK was pioneered by the paper BCCT12, and has now become one of the most popular concepts in the field of zero-knowledge proof. In fact, SNARK is only concise and non-interactive, not necessarily zero knowledge. If there is zero knowledge, it should be called zkSNARK. STARK and SNARK distinguish another concept often mentioned with SNARK is STARK. It is only one word from SNARK, but there are many differences. Let’s compare these two concepts below. Common points:
- All are argumentation of knowledge (ARK), that is, only the reliability in the sense of calculation, and the proof is knowledge
the difference:
- The “S” of SNARK is Succintness, and the “S” of STARK is Scalability . On the basis of simplicity, it also requires that the Prover complexity is at most Quasi-linear, that is , And the computational complexity of Setup is logarithmic at most
- Transparent: STARK does not require a trusted third party Setup; SNARK does not have this restriction
- Non-Interactivity: SNARK must be non-interactive, while STARK does not have this restriction
It can be seen that the only restriction that SNARK has more than STARK is non-interactivity. Nevertheless, through the Fiat-Shamir transformation that will be introduced in subsequent articles, STARK can generally be transformed into non-interactive proof, and the result of the transformation must be a SNARK. In this sense, STARK can be regarded as a subset of SNARK. The above definitions of SNARK and STARK are the broad meanings of these two terms. In a narrow sense, they respectively refer to two specific structural schemes. SNARK refers to a series of zkSNARK construction schemes based on QAP and bilinear pairs represented by the Groth16 scheme. In a narrow sense, STARK specifically refers to the AIR and FRI-based solution proposed by Ben-Sasson and others in 2018.
summary
This article introduces the definition of the proof system and discusses the various properties of the proof system, focusing on “zero knowledge”, “knowledge proof”, “simplicity” and “non-interactive”, and explains how to use the simulator Define zero knowledge, and use extractors to define knowledge proof. Finally, the article discusses and compares SNARK and STARK.
Reference resources
- Goldreich. Foundations of Cryptography, Volume 1. Basic Tools. 2001.
- ZKProof Community. ZKProof Community Reference. 2019. https://docs.zkproof.org/reference.pdf
- Yehuda Lindell. How To Simulate It – A Tutorial on the Simulation Proof Technique. 2018.
- Eli Ben-Sasson. A Cambrian Explosion of Crypto Proofs. https://nakamoto.com/cambrian-explosion-of-crypto-proofs/
