Understand zero-knowledge proof

It is based on zero-knowledge proof that the blockchain realizes peer-to-peer trust without relying on third parties to provide credible verification.

Does it sound fantastic, what is the trust basis of zero-knowledge proof? And how do we trust zero-knowledge proofs? Today we will talk about this underlying problem.

1. What is a zero-knowledge proof

In this article, we take the Merkle tree structure as an example. Realizing zero-knowledge proof means how to prove that someone owns the original data of L1-L4 without making the data public?

Step 1: The prover can create the Merkle tree structure as shown in the figure, and then publish Hash0-1, Hash1 and Top Hash (in the hash algorithm chapter, we have introduced that only the hash value cannot be deduced Raw data).

Step 2: Generate Hash0-0 through the hash algorithm through the data L1, then generate Hash0 according to the published Hash0-1, and then generate Top Hash according to the published Hash1. If the final generated Top Hash value is consistent with the published Top Hash value , it can be proved that he has L1 - L4 data, and there is no need to publish this series of original data. This also realizes zero-knowledge proof.

It can be seen that zero-knowledge proof is based on a series of basic theories of mathematics and computers. If we trust mathematics, logic, and these basic theories , then we can understand that zero-knowledge proof is a technology that realizes the theory of cryptography , and "simulated" a virtual trusted third party based on security assumptions.

In fact, the research on Zero Knowledge Proof (Zero Knowledge Proof) first began in 1985 , and was proposed by MIT professors Shafi Goldwasser, Silvio Micali and cryptography master Charles in the paper "The Knowledge Complexity of Interactive Proof-Systems". It was this article that proposed the great concept of zero-knowledge proof, and gradually became one of the foundations of modern cryptography theory. Shafi Goldwasser and Silvio Micali also won the "Nobel Prize in Computer Science" in 2012.

In simple terms, zero-knowledge proof describes a process in which the prover can convince the verifier that a statement (Statement) is correct without providing any useful information to the verifier .

The theory sounds convoluted, but as early as the Renaissance in the 16th century, two Italian mathematicians used zero-knowledge proofs when they were competing for the crown of the discoverer of the formula for finding the root of the cubic equation in one variable .

Mathematicians Tartaria and Fio both claimed to have mastered the root-finding formula . In order to prove that they were not lying and did not disclose the specific content of the formula, they set up a challenge: each side presented 30 one-dimensional cubic equations Give the solution to the other party, and whoever can solve all of them means that whoever has mastered the formula. The results of the competition showed that Tartaglia had solved all 30 of Fio's equations, and Fio could not solve any of them. So people believed that Tartaria was the real discoverer of the formula for finding the root of the cubic equation in one variable , although no one except Tartaria knew what the formula was.

2. Key attributes of zero-knowledge proofs

As can be seen from the brief description above, there are three key properties that any zero-knowledge proof must satisfy:

Completeness : If the prover is honest, then he will eventually convince the verifier.

Soundness : The prover can only convince the verifier whether the statement is true.

Zero -knowledgeness: In addition to knowing that the statement is true, the verifier cannot (or hardly) know anything other than the information it proves. Therefore, it is impossible for the verifier to prove to a third party that he owns the secret.

The real challenge comes from the third point: zero-knowledge

Prior to this, the research work in this field mainly focused on strengthening the reliability (Soundness) of the proof system. That is to say, everyone originally assumed that there would be malicious provers trying to play tricks to mislead the verifiers into accepting wrong statements.

But Goldwasser et al. think about this problem from another angle: what if we don't trust the verifier at all? More specifically, it is concerned with the issue of information leakage: "During the verification process of the verifier, how much additional information will be obtained that does not need to be known simply to verify the truth of the statement."

Therefore, scholars have proposed the existence of a "simulator" algorithm. Mechanistically, the simulator acts like a special prover. But unlike a real prover, which starts with some specific information that can prove the truth of the statement, the simulator does not, it must be able to "fool" each verifier into believing that the statement is true, and at the same time produce the same A statistically identical (or indistinguishable) copy of the true prover's output. But since the emulator has no "knowledge" to be extracted, it is clear that the verifier cannot gain any valuable information after interacting with it .

For example, it is like the prover Alice proves to the verifier Bob that there is a difference between two pictures that look the same, and can recognize the difference by herself. Bob replaces or maintains the order of the two pictures when Alice cannot see them, and asks Alice to recognize whether to adjust the order again. If Alice can correctly identify whether the order changes every time, Bob will approve Alice's proof with a high probability.

During this process, apart from knowing that Alice can indeed recognize the difference, Bob cannot obtain or infer any additional information (including the difference itself), nor can he use Alice's proof (such as a video of the proof process) to prove to others that he knows this difference.

3. Application of zero-knowledge proof

Since the concept of zero-knowledge proof was proposed, people have continuously improved and developed its theory, and applied it to various fields, such as identity authentication system, certificate storage system, data sharing, etc. Today, privacy is getting more and more attention , zero-knowledge proof shines in the application of privacy data protection

Privacy data protection : In our daily life, such as transcripts, we only want to prove to others that I have passed the test, but I don’t want others to know how many points I have scored; for example, when buying insurance, I only want to prove to the insurance company that I have no heart disease. However, there is no need to expose all the information of the medical record. Whether it is a report card, medical record, account book, etc., any part of it can be deducted and replaced with a zero-knowledge proof that is similar to a random number, which can prove the sensitivity of the deducted The data is still credible and real.

Calculation compression and blockchain expansion : In the traditional blockchain architecture, the same calculation is repeated many times, such as signature verification, transaction validity verification, smart contract execution, etc. Because of the proof of calculation, there is no need to repeat the same calculation many times, and these calculation processes can be compressed by zero-knowledge proof technology.

Authentication : The user can prove to the website that he has a private key, or knows a secret answer that only he knows. The website does not need to know this key, but can confirm the user's identity through zero-knowledge proof. Decentralized storage: the server can prove to the user that their data is properly stored and does not disclose any content of the data.

Credit history : Credit history is another field that can give full play to the advantages of zero-knowledge proofs. Users can selectively show their own credit history to the other party and at the same time prove the authenticity of the credit history.

As a result, zero-knowledge proof has truly solved the "trust of data" , realized the "protection of private data" , and made the blockchain truly realize the concept of "trust machine" .