Introduction to Zero Knowledge Proof (1)

Original title: "Dry goods | Introduction to zero-knowledge proof (1)"

Original source: Nervos Chinese community

Following the last time Shor sent a response Comprehensive research on routing issues in payment networks After that, another person who loves research Cyte, a small partner of Nervos, has done a detailed research on zero-knowledge proofs.

In this article, Cyte  will introduce the definition of  Zero-Knowledge Proof (ZKP) , and combine Zero-Knowledge Proof with SNARK and Differentiate and analyze these two concepts of 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 used interchangeably. In fact, all these concepts belong to a broader category called Proof System(Proof System) , or called Cryptographic Proof(Cryptographic Proof) . There are overlaps between zero-knowledge proofs, SNARKs, and STARKs, but they do not include each other. The relationship between them can be represented by a graph.

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-interactivity. In particular, if a proof system is "zero-knowledge", it is called a "zero-knowledge proof". Finally, the article discusses the definitions of  SNARK  and  STARK and compares them.

Proof System

A Proof System is an interactive protocol that includes Two participants Prover and Verifier, and an algorithm Setup. The role of the proof system is to allow the Prover to convince the Verifier to believe one thing, which we call a Statement.

Before the protocol begins, 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, where the information learned by Verifier is denoted as , and the information learned by Prover is denoted as . The common part of and is called the Common Reference String (CRS). Who and when to call the Setup algorithm depends on the design of the proof system.

At the beginning of the protocol, Prover and Verifier get input statements at the same time. Compared with Verifier, Prover must have some additional advantages, such as more powerful computing power, or get some extra input .png">. In addition, Prover and Verifier also learned about respectively. The time to obtain Setup information depends on the design of the certification system. For example, it may be that Prover and Verifier have long been downloaded and stored in their respective hard drives for repeated use, or they may be input on the spot before the agreement starts.

Then Prover and Verifier start to execute the protocol stipulated by the proof system. If both Prover and Verifier are honest, then they both strictly abide by the protocol. However, it is also possible that a certain party is malicious and does not follow the agreement. What happens at this time depends on the security of the proof system. If both parties are malicious and they don't abide by the agreement, then it has nothing to do with this proof 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 true, and both Prover and Verifier adhere to this protocol, then Verifier must submit at least The probability output accept, here It is called the integrity error (Completeness error) of the proof system

-Soundness: If the statement is incorrect, at this time the Prover must be dishonest, and the Verifier abides by the agreement, so no Prover can Let the probability of Verifier output accept exceed , this It is called the reliability error of the proof system (Soundness error)

These two requirements are The most basic requirements for a proof system to work. With either requirement missing, we could all have a proof system that qualifies but is completely useless. For example, if we only require integrity, then no matter what Prover does, Verifier will always output only accept; if we only require reliability, let Verifier always output only reject. In addition, and No more than 1/2, and the sum is less than 2/3, otherwise this proves that the system error is too large, and it is almost useless.

If one proves the reliability of a system only for any computation A Prover with limited capabilities is established, that is to say, an adversary with unlimited computing capabilities may deceive the Verifier. At this time, the proof system only has computational soundness (Computational Soundness), and such a system is also called an argument system (Argument System). In contrast, a soundness 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 required) properties

-CRS model (CRS model): If the Setup information is open to everyone Visible, that is, Setup=Setup p=Setup v, it is said that this proof system is under the CRS model

-Interactive (Interactive) / Non-interactive (Non- interactive): If only the Prover sends a message to the Verifier during the entire interaction process, the system is called a non-interactive proof system; otherwise, the system is an interactive proof system

- Transferable/Deniable: If the statement is correct and the interaction process Sending to other Verifiers can also convince other Verifiers that the statement is correct. This proof system is transferable otherwise the proof system is repudiable

-Public Verifiable/Designated Verifier: If Setup v is valid for all It is publicly visible, that is, anyone can become a Verifier, and this zero-knowledge proof system is publicly verifiable. Otherwise, this system is specific to the verifier

-Public random (Public coin): If the selection of all the messages of the Verifier is uniformly random and independent of the messages of the Prover , the system is said to be openly random

-Zero-Knowledge: In the statement is the correct case if except correctness, the Verifier cannot obtain any other "knowledge" from the interaction, and the system is said to be zero-knowledge

-Succinctness: If This proof system is used to prove NP languages, and the communication volume of the proof system is smaller than the proof , then this proof system is concise

Example: Prove that the colors of two balls are different< /h4>

Setup info: There are two balls

Statement : These two balls are of different colors

< p>1. Verifier has limited computing power (blindfolded), and Prover has normal vision

2. Verifier holds a ball in each of his left and right hands and shows it to Prover. Verifier puts his hands behind his back, then (in his mind) flips a coin at random, and if it comes up heads, he swaps the balls in his left and right hands, otherwise he doesn't.

3. The Verifier shows the ball to the Prover.

4. Prover tells Verifier whether the two balls have been exchanged.

Result: If Prover guesses correctly, Verifier outputs accept, otherwise Verifier outputs reject.

Importance

< /p>

In the 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 to reveal the secret evidence needed for proof.

The zero-knowledge nature of the proof system has been mentioned above, and it is simply described as Verifier cannot obtain any "knowledge" from interaction ". This description is imprecise as it does not give a strict criterion for judging.

The definition of zero-knowledge itself is counterintuitive: Prover obviously sent some bits of data to Verifier, why is this system What about "zero knowledge"?

Actually, "information" is not the same as "knowledge". If Verifier obtains information, but obtaining this information does not allow Verifier to calculate more results, or if the information is calculated by Verifier itself, then Verifier has not acquired any "knowledge".

During the execution of a proof system, all the information obtained by Verifier includes: Setup v; Verifier's own random number r; All information sent by Prover to Verifier (marked as p). We call this information the Verifier's "field of view", denoted as . This information is the source of all uncertainty in the Verifier calculations. Once this information is determined, everything else can be calculated deterministically.

Note, is a random variable. After Verifier and Prover execute the proof system, Verifier will obtain a sample of this random variable. If the Verifier can sample on its own without the participation of the Prover, then the system is zero-knowledge.

We sampled The algorithm of this random variable is called Simulator. According to the different working methods of the simulator, there are different definitions as follows:

1. 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.

2. The black box simulator corresponds to the black box zero knowledge. This zero-knowledge definition requires the existence of a unique simulator, so that for all Verifiers, it can sample . It is impossible for this unique simulator to know all the specific implementation details of Verifier, so it can only access Verifier through black-box calls. However, the emulator has full control over Verifier. The simulator can determine the random number r of the Verifier, and input any Prover message or Setup v to the Verifier. Therefore, in the eyes of the simulator, Verifier is a black-box deterministic algorithm.

3. If the simulator is only for honest Verifier, it corresponds to Honest Verifier Zero Knowledge (Honest Verifier ZK). Because the behavior of the honest Verifier is completely expected, the simulator can naturally use this information, so the simulator's access to the Verifier is non-black box.

The non-black-box simulator has 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 implement.

About honest Verifier zero knowledge, the honest Verifier here is more precisely semi-honest (Semi-Honest), or "Honest but curious". Such a Verifier would ostensibly abide by the protocol, but would potentially secretly attempt to extract knowledge from the message.

In contrast, malicious Verifiers are completely unrestricted in their actions. Verifier may crash, send messages that do not conform to the format, sample out of the distribution specified by the protocol, and so on. To prove that a system is zero-knowledge-proof against a malicious Verifier, all these cases must be covered.

The simulator is a random algorithm, and its output value is also a random variable, recorded as . Zero knowledge required and These two random variables are indistinguishable. However, there are also many versions of the word "indistinguishable", from which various definitions of zero-knowledge proofs can be derived:

-If the distribution of two random variables It is statistically indistinguishable, that is, their statistical distance (Statistical Distance) is negligible, and the proof system is called Statistically Zero-Knowledge (Statistically Zero-Knowledge); if the statistical distance is 0, it is also called Perfect Zero-Knowledge (Perfect Zero-Knowledge). -Knowledge);

-If the distribution of two random variables is computationally indistinguishable, that is, any polynomial time random adversary cannot distinguish between the two distributions, the proof system is called Computationally Zero-Knowledge.

Note that in the definition of zero knowledge, only the correct statement is required,    distributions are indistinguishable. For false statements, we don't care what knowledge the Verifier can obtain, because in this case the Prover itself is dishonest, and there is no need to protect it. In other words, since the Prover does not abide by the agreement, no matter how well our agreement is designed Can't protect it either.

However, although Wrong case, zero knowledge pair The distribution is not Make no assumptions but if the input is wrong  sampled If there is a significant difference between the probability of being verified by Verifier and the correct case, we can use this to judge . This means that   can only come from a trivial NP language. So, for difficult NP problems, input the wrong   into the simulator and get  can also be verified with the same probability.

In this way, isn't zero knowledge and reliability contradictory? In other words, for false, why can't Prover call the simulator to fool Verifier? In fact, the Prover cannot control the Verifier, so it cannot provide the simulator with what it needs to sample  resource. Indeed, a malicious Prover can call the emulator, but this is useless to 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 by the simulator may also be the same as the   is different and the verification fails. However, the simulator invoked by Prover cannot obtain the random number of Verifier, which is enough to ensure security, so in the interactive proof  Even fixed constants are fine.

Proof of Knowledge

If Prover is required to "know" some information in order for Verifier to pass the verification, this system is called Proof of Knowledge. Proof of knowledge can be seen as an enhanced version of reliability. Proof of knowledge also has a computational version called Argument of Knowledge.

Knowledge proof systems are usually used to prove NP languages. An NP language is a set such that the element Saved by can be created by A proof   to prove that there is a polynomial time algorithm that can determine Is it belongs to  legal evidence.

The common proof system enables Prover to prove to Verifier . The knowledge proof system allows Prover to prove to Verifier not only , but also proves that Prover "knows"< img src="https://image.theblockbeats.com/upload/2020-11-06/c098b56b5a7858ad2616c414d48f31c8e3c68cf8.png">. That is to say, even if , if Prover does not know the corresponding , also difficult to verify.

Similar to the zero-knowledge discussed in the previous section, "knowledge" also requires a strict definition. A program P "knows" data , how to define it? Imagine running this program in a virtual machine, its random number can be specified by us at will. During its entire running process, the complete history of the CPU state, as well as all memory read and write operations, can be recorded by the virtual machine. If this program "knows" , we should extract from these records  information. In fact, this is an intuitive way to understand the Extractor. An extractor is an algorithm that runs concurrently with the extracted program and has access to 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 has access to the internal state of the program being extracted. Algorithms of non-black-box extractors necessarily vary from program to program to be extracted. Therefore, a proof system is a proof of knowledge, which is defined as follows: "For any Prover  An extractor , which works with  At the same time, and can access  internal state. If  After interaction Output accept, then   will output . "

similar to zero knowledge Simulators in definitions, extractors can also be defined in a black-box fashion. Extractors do not have access to the program's internal state, but can call the program, control the program's random numbers, and read the program's output. We introduce such a mark , indicating that the extractor accesses the interaction between a pair of Prover and Verifier through a black box process. It is enough to have only one black-box extractor for all Prover, so the proof of knowledge can be defined as follows: "There is an extractor for any Prover , if   and After interaction output accept, then  will output ."

Simplicity

Use Indicates an instance of NP language, means Evidence exists in language. Succinctness refers to a linear function that demonstrates that the amount of communication required by the system is less than  . In other words, Prover and Verifier implement this proof system, than Prover directly sends   to Verifier, It also saves communication bandwidth. Sometimes, simplicity may also require Verifier to be less computationally intensive than Verification in the proof system. In summary, simplicity requires proving that the system has an advantage in terms of efficiency.

We may wish to have a compact proof system with logarithmic communication or less, i.e. . However, such a simplicity requirement will bring about a loss of security. Because if the communication volume is as low as the logarithmic level, then the entire space where Prover's message combination p is located can be found in Exhaustive in time. However, the reliability requirements of the system, for the wrong statement , Prover cannot find the p .

If there is no such thing that can be verified, this can indeed guarantee reliability. But in this way, the legality of  can be judged by exhaustive p, then  is not a difficult problem, which rules out general NP languages. If we want proof systems for NP languages in general, we must allow that even for wrong A small number of p that can be verified.

In this case, we can only introduce an additional security parameter , relax the traffic size to , so that the complexity of exhaustive p reaches , which at least achieves reliability in the sense of calculation. At the same time, the communication volume is still logarithmic relative to , so the simplicity is satisfied.

In summary, for general NP languages, (logarithmic level) concise proof systems can only be argument systems.

Non-interactive

Non-Interactivity means that all interactions of the proof system are only a message sent by the Prover to the Verifier. This message is called a proof and is recorded as . Non-interactivity can bring a lot of convenience and bring more application scenarios to the proof system. For example, in a blockchain system, a non-interactive zero-knowledge proof can be attached to a transaction for anyone to verify 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, the Prover directly sends the proof to the Verifier, and this proof is a knowledge proof. Therefore, it is of little significance to construct a purely non-interactive proof system. Non-interactivity is only interesting in combination with the two previously discussed properties, zero-knowledge or brevity.

Non-interactive + zero-knowledge

Combining zero-knowledge and non-interactivity , there is Non-Interactive Zero-Knowledge (NIZK).

When we discussed zero-knowledge before, the reason why zero-knowledge is not inconsistent with reliability is because  is different from the random number of Verifier interacting with Prover. However, for non-interactive zero-knowledge, we have to re-examine this reasoning process.

In interactive proof, a Verifier whose random number is r1 can verify the passed Prover message p, and it is very possible to move it directly to the Verifier whose random number is r2 Verification failed. So, in an interactive proof, the correctness of p is not global, but depends on r.

In non-interactive proof, Prover does not receive any message from Verifier, so the random number r of Verifier is not used in the calculation process of Prover. Therefore, in order to achieve the integrity of the proof system, the p outputted by the honest Prover can be verified for most of the Verifier random number r. Therefore, the correctness of p in a non-interactive proof is global and does not depend on any r.

Zero-knowledge requirements, Verifier's vision  and the output of the simulator Indistinguishable. This means that their partial components are also indistinguishable if viewed individually. That is   and   3aa9.png">  are also indistinguishable. So, a malicious Prover can invoke the emulator to output . This is not a problem in interactive proofs, the malicious Prover just gets the correct p for some r. But in non-interactive proof, the correctness of p does not depend on r, which will bring security problems.

At this time, it will be It works. Although the correctness of p no longer depends on r, it still depends on  For reliability, we hope, given  and stated It is difficult to calculate p that can pass the verification. Although the simulator can output a pair of , but it is difficult to calculate the former and then the latter. Specifically, how to do this will be explained in detail when the specific solution is introduced in the follow-up article.

Non-interactive + Simplicity

As mentioned above, the proof system of simplicity It must be an argument system. Combined with non-interactive, you have Succinct Non-interactive ARGument (SNARG). In fact, systems satisfying the SNARG definition were constructed by Micali as early as 2000, and the name came later.

If a SNARG is also an argument of knowledge, it is called a Succinct Non-interactive ARgument of Knowledge (SNARK). The name SNARK was coined by the paper BCCT12 and has now become one of the hottest concepts in the field of zero-knowledge proofs. In fact, SNARK is only concise and non-interactive, not necessarily zero-knowledge. If there is zero knowledge, it should be called zkSNARK.

Analysis of STARK and SNARK

Another concept that is often mentioned together with SNARK is STARK . It is only one word different from SNARK, but there are many differences. Let's compare the two concepts.

Common point:

- Both are Arguments of Knowledge (ARK), namely Reliability in the computational sense only, and the proof is intellectual

Difference:

-SNARK's "S" is simplicity (Succintness), and STARK's "S" is scalability (Scalability). It also requires Prover complexity to be quasi-linear at most on the basis of simplicity. Namely , and the computational complexity of Setup is at most logarithmic

-Transparent: STARK does not require a trusted third-party Setup; SNARK does not have this limitation

-Non-interactive (Non-Interactivity): SNARK must be non-interactive, but STARK does not have this limitation

It can be seen that the only limitation of SNARK over STARK is non-interaction sex. Nevertheless, through the Fiat-Shamir transformation that will be introduced in subsequent articles, STARK can generally be converted into a non-interactive proof, and the result of the conversion 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 two nouns broad meaning. In a narrow sense, they respectively refer to two specific construction schemes. Among them, SNARK refers to a series of zkSNARK construction schemes based on QAP and bilinear pairing represented by the Groth16 scheme. In a narrow sense, STARK specifically refers to the scheme based on AIR and FRI proposed by Ben-Sasson et al. in 2018.

Summary

This paper introduces the definition of a proof system and discusses the various aspects of a proof system. Class properties, focusing on "zero-knowledge", "proof of knowledge", "succinctness" and "non-interactive", explaining how to define zero-knowledge with simulators and proof-of-knowledge with extractors. Finally, the article discusses and compares SNARKs and STARKs.

References

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/

< a href="https://mp.weixin.qq.com/s/pG1rWN8WKWyghhl7myUZJA" target="_blank" rel="nofollow">Original link

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia