03 The core value of zero-knowledge proof： eliminating the need for a trusted third party

If it is just to answer the title question, two words are enough:It is not.

But I still want to mention by the way,What is zero-knowledge proof (ZKP)?

Although both the terms 'zero-knowledge proof' and 'zero-trust' contain the word 'zero' and are related to 'trust', they are not the same thing. Both essentially requireenhance‘trust’, but in the process of enhancing ‘trust’，zero-knowledge proof emphasizes not to leak knowledge; zero trust emphasizes not to over-authorize. In short,Zero knowledge is to hide knowledge; Zero trust is to control trust. For more information about Zero Trust Architecture, refer toThe NIST draft standard for Zero Trust Architecture.

Zero-knowledge proof solves the contradiction between trust and privacy: it improves ‘trust’ through ‘proof’ and protects ‘privacy’ through ‘zero knowledge’. It is a win-win solution.

The point I really want to express in this article is:The process of exploring zero-knowledge proof can explore the essence of security.

As of my current understanding,the ultimate definition of security，not heuristic CIA three attributes, butAdopted formal verification to prove security - a perfect combination of the divine (‘simulator’) and the scientific (mathematics, computational complexity) process.

First, understand zero-knowledge proof

01The definition of zero-knowledge proof

Zero-knowledge Proof (ZKP, Zero-Knowledge Proof)is defined as:Prover (prover)can verify withoutVerifier (verifier)make the verifier (verifier) believe that a certain assertion is correct without providing any useful information.

According to the definition, zero-knowledge proof has the following three important properties:

Completeness（Completeness）：

As long as the prover has the corresponding knowledge, he can pass the verification of the verifier, that is, the prover has a high probability of making the verifier believe him.

（about the “probability”，see the following “Color Blind Game”）

Reliability（Soundness）：

If the prover does not have the corresponding knowledge, he cannot pass the verification of the verifier, that is, the probability that the prover deceives the verifier can be ignored.

Zero-knowledge（Zero-Knowledge）：

The prover makes statements to the verifier whether he possesses the corresponding knowledge during the interactive process,it will not leak any additional information about knowledge.

From the definition, we can also extract two key words: “do not leak information”+“prove the validity of the assertion”。To summarize it further is:hide+Proof.

Therefore, the core purpose of zero-knowledge proof is:hideandProofIt needs to hide all kinds of secrets. (Don't you feel contradictory?)

02the origin of zero-knowledge proof.

Zero-knowledge proof is1984was proposed by Goldwasser, Micali, and Rackoff in the year《The Knowledge Complextiy of Interactive Proof Systems》（The Knowledge Complexity of Interactive Proof Systems）。

As can be seen from the upper left corner of the figure above, this paper actuallypublished in 1989. The reason lies in the thought of this paperit was too ahead of its time, to the extent thatFrom the initial draft written in 1984 to its formal adoption and publication in 1989，experiencedExactly five yearsTime. It was due to this pioneering work of zero-knowledge proof that Goldwasser and Micali shared the prize in 2012Turing Award——The highest award in the field of computer science, also known as the 'Nobel Prize of the computer world'.

03The core value of zero-knowledge proof: eliminating the trusted third party

With the rapid development of Internet e-commerce and online transactions today,Trusted Third Party (TTP, Trusted Third Party)is almost indispensable. But the fact that everyone does not feel is that,TrustedThe introduction of the third party introduces a huge 'trust cost'. Over-reliance on the third party will bring serious problems such as 'privacy leakage', 'single point of failure', and 'personal information abuse'. Although the academic community has also proposed “Semi-trusted third party”（Semi-trusted Third Party）to relax the conditions, but 'semi-trusted' does not solve the fundamental problem.The fundamental question is whether the third party can be canceled.

Then,If the trusted third party is canceled, can the fairness of the transaction still be guaranteed?Imagine this transaction scenario: one buyer carries a cash box, and the other seller also carries a box containing some valuable goods. In the plot of a movie, both buyers and sellers will sit on opposite sides of a table, counting down 3-2-1 simultaneously, and then push the boxes to each other at the same time. Of course, both parties had better carry weapons to prevent the other party from cheating. Apart from the buyer and seller, there is no third party present, and neither party trusts each other. It is easy to understand that neither party wants to take the initiative, hand over their own box to the other party, because they are worried that the other party will run away after getting the box, resulting in the outcome of losing both money and goods.

Time went to 2008,Bitcoin emergedIn a P2P network that can be accessed without any permission, Satoshi Nakamoto proposed a genius design:BlockchainTechnology, in a very fair way, to carry out decentralized accounting.

We can understand Satoshi Nakamoto's innovation from another perspective:Bitcoin has realized a distributed protocol, which 'simulates' a 'virtual' 'trusted third party' in a decentralized manner..

And the zero-knowledge proof can also be understood in this way:Zero-knowledge proof has realized a class of cryptographic theoretical technology,}It is based on some security assumptions,‘Simulation’ has produced a virtual trustworthy third party.

As can be seen,One of the important roles of 'zero-knowledge proof' is to eliminate the trusted third party.In other words,The 'trust' provided by zero-knowledge proof can replace a 'trusted third party'.

It should be noted that:The 'zero-knowledge proof' replacesIt is not the 'third party', but the 'Trusted Third Party».

」A classic example of zero-knowledge proof: the color blind game

The logic behind zero-knowledge proof is not complex. Below isInteractive Zero-Knowledge ProofA classic example ofColor Blind Game, to help understand the concept of zero-knowledge proof. See reference [1] for details.

Color Blind Game:

Participants: Alice is color blind, and Bob is not color blind.

Bob has two balls of the same size and shape in his hand, butDifferent colorsOne is blue, the other is red.

Since Alice is colorblind,Alice cannot distinguishwhether these two balls are the same.

andBob needs to prove to Alice that the two balls are different.

In this game:

Alice is calledVerifier: he needs to verify whether Bob's statement is correct or not;

Bob is calledProver: he needs to prove his statement (there are two balls of different colors).

AdoptZero-knowledge proofMethod: Bob needs to prove to Alice that the two balls are different in color, which is consistent with the definition of zero-knowledge proof.

The method of zero-knowledge proof is as follows:

Alice picks up two balls in front of Bob, holding the blue ball in her left hand and the red ball in her right hand (of course, Alice does not know which one is the blue ball or the red ball because she is colorblind);

Alice then puts her hands behind her back, so Bob cannot see the balls on Alice's hands;

Alice is behindRandom exchangethe balls in the left and right hands, and silently remember her way of exchange;

After the exchange is completed, Alice will extend her hand and ask Bob “Have the two balls been exchanged in position?

If Bob can see the colors of the balls, then every time Alice changes the position of the balls, Bob can correctly answer Alice's question.

The analysis and reasoning process is as follows:

Firstly: suppose Alice indeed exchanged the positions of the two balls in her hands.

If Bob answers correctly, Alice will still not completely believe that Bob can distinguish the two balls, because Bob has a 50% chance of guessing correctly;

So, even if Bob answers correctly, Alice still needs to conduct the second test;

If Bob answers incorrectly, then Alice can be sure that Bob cannot distinguish the colors of the two balls. This test can be terminated.

Secondly: suppose Alice did not exchange the positions of the two balls in her hands this time, and then Alice asks Bob if he exchanged the positions of the balls.

If Bob answers correctly, then Alice has a 75% chance of believing that Bob can distinguish the colors of the two balls;

Of course, Alice can also conduct a third test;

If Bob answers incorrectly, then Alice can be sure that Bob cannot distinguish the colors of the two balls.

This test is terminated here.

The following figure shows the probability tree for the above situation:

The probability calculation results are as follows:

When Bob answers correctly for the first time, Alice can say that the probability of Bob's statement being true is 50％;

If Bob answers correctly again for the second time, Alice can say that the probability of Bob's statement being true is 75％;

If he gets it right for the third time, the probability will reach 87.5％;...

If Bob passes the test continuously for n times, Alice believes Bob to be telling the truth with a probability of 1-(1/2)^n, that the two balls indeed have red and blue colors.

This example of zero-knowledge proof is aBased on probabilistic verification methods (i.e., probabilistic proof, not deterministic proof)The verifier (verifier) proposes questions to the prover (prover) based on certain randomness, and if the prover can always give the correct answer, then it indicates that the prover probably has the 'knowledge' he claims.

Let's see how this example meets the definition of zero-knowledge proof:Three properties:

Completeness: If Bob has the knowledge to distinguish the colors of the balls, then Bob will always answer correctly.

Reliability: If Bob does not have the knowledge to distinguish the colors of the balls, then Bob cannot always answer correctly.

Zero-knowledge: In the end, Alice also cannot know the specific colors of the two balls because Bob never revealed this information.

Second, insight into trust and security

01The mechanism of trust generation

How does zero-knowledge proof 'create trust out of thin air'?

The trust of zero-knowledge proof is based on a relatively objective theory:

One type is basic theory:

Such as 'number theory and algebra', 'mathematical logic', 'computational theory', etc.;

Another type is security assumptions:

Such as 'discrete logarithm problem' and so on.

If we trust these basic theories (mathematics, logic), and trust that the security assumptions have not been broken, then we can indeed draw the following conclusion:Zero-knowledge proof implements a class of cryptographic theoretical technology, which 'simulates' a virtual trusted third party based on some security assumptions.

In 2016, The Economist proposed that 'blockchain is a trust machine'. Carefully thinking about the derivation mechanism of trust, we can find out:

Blockchain: Solves the 'trust of distributed computing';

Zero-knowledge proof: Solves the 'trust of data';

Formal verification: Solves the 'trust of logic'.

The above three points: logic <-> calculation <-> data, together constitute a closed loop, perhaps truly realizing the concept of 'trust machine'.

In short,Any 'trust' needs to be based on certain trust foundations (such as Trusted Computing Base), and any 'security' has security assumptions..

The last link of trust isFormalized Verification. Formalized verification is actually for logic, process, or business.Formalized ModelingYou can understand it as a description in a mathematical language, where the model is some mathematical concepts (or mathematical objects), such as sets, algebra, categories, etc. Then all formal verification uses 'explicit' or 'implicit' methods to 'strictly prove' some conclusion (or called a theorem).

The core of understanding the theory of zero-knowledge proof is to understand the concept of 'simulation'.. We mentioned two 'simulations' above: one is the blockchain, and the other is zero-knowledge proof. Let's take a look back:

Bitcoin has implemented a distributed protocol that, in a decentralized manner, 'simulates' a 'virtual' 'trusted third party'..

Zero-knowledge proof has realized a class of cryptographic theoretical technology,}It is based on some security assumptions,‘Simulation’ has produced a virtual trustworthy third party.

They are credible because they can 'Simulationa trustworthy third party». This simulation process is allformalizedand it isprovable. Now,Simulation (Simulation)andSecurity proofIt has become a consensus in the field of cryptography and is a basic formal tool. Simulations without proof/verification are unacceptable to everyone.

Theoretically, all objective standards can beVerification, from a large-scale security protocol to a line of code, can be adoptedFormal verificationmethods. The author has studied provable security and has experienced the magical concepts expressed in 'simulation' and 'provable security' from those cryptographic security proofs. To some extent, one can understand the essence of 'security'.

If you are interested in formal verification methods such as simulation, security, and indistinguishability, please refer to reference [6], which will take you to another 'parallel world' with 'God', spanning scientific and philosophical issues.

02Proof vs. Verification

Zero-knowledge proof implementationCan be realized throughThree journeysTo describe: (see reference [3])

Hiding secretsJourney:One-way function;

Proofing secretJourney:Homomorphic mapping;

Building a universal zero-knowledge proofJourney:Polynomial proof of NP-complete problems.

What is the relationship between the 'proof' in 'Zero-knowledge Proof' and the 'verification' in its definition? This involves the meaning of the existence of proof. All proofs reflect the 'asymmetry' of 'proof' and 'verification'.

Proof: may be a very resource-intensive activity, or a brain-intensive activityWhether it is the 'Fermat's Last Theorem' that took hundreds of years or the POW proof in Bitcoin, these proofs all condense the energy consumed in the search for proof.

The proof process may be extraordinarily complex, and occasionally requires the emergence of genius.

Verification: should be very simplemechanical, within the effective time (polynomial complexity) and able to terminate activities.

In a sense,‘Proof’ and ‘Verification’ofThis asymmetry truly reflects the meaning of proof and shows the value of zero-knowledge proof. For this part, see the reference [2].

03Trust vs. Privacy

In essence, trust is a good thing. We have createdCredit system; we can provide credit to people and organizations we trust; relying on reputation, credit records, and so on,we can also conduct business with people we do not trust.

However,Trust is usually established at the expense of privacy. In order to trust each other, one must usually give up some privacy. Moreover, trust is usually closely related to your identity information.

Zero-knowledge proof is just a kind ofProtectiona win-win situation「The scheme: through 'proof' to enhance the 'Trust」，and again」，and thenThrough 'zero-knowledge'ProtectionPrivacy「.

」04

Anonymous vs. PseudonymousPrivacyUnderstanding of

The first isAnonymous, which means that users do not need to disclose any information related to themselves, just like a schoolConfession wall, you will never know who wrote it, anyway, the words are written there.

The second isPseudonymous, which means that users can post information through the pseudonyms they create, just like a forum. If you don't know this user, you can't establish a connection between the pseudonym and the real name, and you don't know who posted the message.

Currently, most currentBlockchain technology is just pseudonymous. As in Bitcoin, each user will randomly generate their ownPublic key (pseudonym)address to receive payments. This kind ofPublic keyAddressIn fact, it is a kind ofPseudonym, once somewhereReal-name system authenticationOnce that happens, the pseudonym and the real name can be associated, and there is no privacy to speak of.

If hackers or the government can associate the real name with the network address, then it is possible to trace back to the identity of the user at the time of the transaction through the blockchain transaction. Although the blockchain is praised as a perfect security solution, those in the know are aware of this weakness. In fact, law enforcement agencies around the world have been taking advantage of this vulnerability to catch criminals.

This is just like someone posting messages on a forum under a pseudonym and cursing, and then being found by the secret protection to get the phone number, and then finding the real name registered with the phone number, and being doxxed in this way.

Zero-knowledge proof can make up for this anonymous defect. Creating a society of trust using zero-knowledge proof is a society that pays more attention to personal privacy. It will truly transfer the control of privacy to the hands of consumers, rather than giving it to the government or organizations.

Third, the application of zero-knowledge proof

There are two key words in the definition of zero-knowledge proof: 'non-disclosure of information' and 'validating the assertion'. Based on these two features, we can directly extend out two major application scenarios of zero-knowledge proof on the blockchain (see reference materials [1]).

PrivacyIn the privacy scenario, we can make use of the 'non-disclosure of information' feature of zero-knowledge proof to prove that the asset transfer on the blockchain is effective without leaking transaction details (receiver, sender, transaction balance).

ExpansionIn the expansion scenario, we are not very concerned about the 'non-disclosure of information' feature of zero-knowledge proof technology, but more concerned about the feature of 'validating the assertion'. Since the resources on the chain are limited, we need to transfer a large amount of computation to off-chain, so we need a technology that can prove that these actions that occur off-chain are credible, and zero-knowledge proof can exactly help us with the endorsement of off-chain credible computation.

End-to-end communication encryptionUsers can send messages to each other, but need not worry that the server gets all the message records. At the same time, messages can also be presented with the corresponding zero-knowledge proofs as required by the server, such as the source of the message and the destination of the transmission.

Identity authentication: The user can prove to the website that they possess the private key or know a secret answer that only they know, and the website does not need to know this private key and secret. However, the website can verify this zero-knowledge proof to confirm the user's identity.

Decentralized storage: The server can prove to the user that their data is properly stored and that no content of the data is leaked.

Credit records: Credit records are another field where zero-knowledge proof can be fully utilized. Users can selectively show their credit records to the other party while proving the authenticity of the credit records.

More examples can beAny form of data sharing, data processing, and data transmission.

In July 2019, the Defense Advanced Research Projects Agency (DARPA) of the United States Department of Defense issued a broad institutional announcement (HR001119S0076) for the Cryptographic Verification and Evaluation of Information Security Assurance (SIEVE) project.Zero-knowledge proofthe most advanced technology, aiming to verify military capabilities without leaking secret information.Zero-knowledge proof for verifying military capabilitiesincluding large and complex proofs that involve probabilistic and uncertain branching conditions. The project research is divided into three technical fields: constructing useful zero-knowledge statements; constructing efficient zero-knowledge proof generation compilers; post-quantum zero-knowledge research.

References

[1]Introduction to Zero-Knowledge Proof, Wu Shouhe;

[2]Initial Understanding of 'Zero Knowledge' and 'Proof';

[3]Understanding the Simple Logic Behind Zero-Knowledge Proof, Li Hua;

[4]zkPoD: Blockchain, Zero-Knowledge Proof, and Formal Verification, Realizing Fair Transactions without Intermediaries or Trust, Guo Yu;

[5]A Brief Introduction to Zero-Knowledge Proof: Background and Origin, Dong Ze;

[6]Understanding Zero-Knowledge Proof from 'Simulation': Parallel Universe and Time Travel, Guo Yu;

Author: Ke Shanxue, Editor; Source: Public account Network Security View