The magical zero knowledge proof can not only keep secrets, but also make others believe you!

Someone claimed that he had solved the Goldbach conjecture , But I am afraid that others will copy , Do not expose details , How can we convince everyone that he has proved Goldbach's conjecture without releasing the details ？

It seems impossible , But there is a way , be called “ Proof of zero knowledge ”, To solve the problem of trust .

The definition of zero knowledge proof is ： Certifier （prover） Be able to do this without telling the verifier （verifier） Provide any useful information , Make the verifier （verifier） Believe that an assertion is correct .

Define dry , It's so boring , Take two examples to digest （ See the link at the end of the article for the source of the example ）.

1

If you have such a picture in your hand , There are hundreds of penguins inside ：

however , among There is a sea parrot that looks like a Penguin ：

You know this sea parrot is hiding somewhere else , But you don't want to tell people where they are .

So here comes the question ： How can you without revealing the exact location , Prove to others that you do know the location of the sea parrot ？

A very simple way is , You take a board , Leave a hole in it , Put the picture behind the board , And let the sea parrot aim at the hole .

So when people look through the hole , He'll see the sea parrot .

But the point is ： You didn't reveal the location of the sea parrot , Others know that there is a sea parrot in the picture .

This is zero knowledge proof .

2

The above example is a little simple , Let's watch a more complicated Sudoku game .

Sudoku rules are very simple , Players need to 9×9 Known on the disk Prompt number , Infer the number of all remaining spaces , And meet every line 、 Each column 、 Every thick line Palace （3*3） All numbers in 1~9, No repetition .

Suppose zhangdapang and hexiaohe both like to play Sudoku , They often ask each other Sudoku puzzles to test each other .

one day , Zhangdafan gives hexiaohe a Sudoku puzzle , Hexiaohe couldn't do it , So he found zhangdafang .

Hexiaohe ： Fat brother , Did you cheat , A Sudoku without solution ？

Da Pang Zhang ： ha-ha , It's your level , This Sudoku has a solution .

Hexiaohe ： I don't believe it , Tell me the answer .

Da Pang Zhang ： I won't tell you the answer , But I will prove with zero knowledge that I do know the answer .

How does zhangdafun prove it with zero knowledge ？

He asked hexiaoheng to turn around , Then I made 9981 cards , The card says 1~9, Put it on the table in the right way .

For those prompt numbers , He put the card number up , For places that need to be filled in , He put the card number down , Let hexiaohe not see the correct answer .

Hexiaohe turned around , He was disappointed to find , Zhangdachun didn't give him the answer .

Da Pang Zhang ： The answer is on the table , You can check if it is correct , It can be in the form of lines 、 In columns , Or with 3*3 Block mode .

Hexiaohe chose to use the line .

Zhangdafun put each row of cards into an opaque bag , Shake... Shake , Ensure complete mixing , Then give it to hexiaohe .

Hexiaoheng opened each bag for inspection , Sure enough , The cards in each bag are 1~9 , Completely comply with Sudoku rules .

Hexiaohe ： What can this prove ？ I can also put 1~9 Put these lines , This will also happen .

Da Pang Zhang ： But , I can't read my mind , I didn't know in advance that you had to choose the line method to verify ？

Hexiaohe asked for a retest , This time he chose column validation , Still right .

use 3*3 Square verification , Still can't find fault .

Hexiaohe thought ： Is this boy lucky , You can guess my verification method every time , So as to put the appropriate number ？ It's impossible ！ that Zhangdachun does have a very high probability （ That's important ） Know the right answer ！

In the process of verification , He didn't get any knowledge about the answer , Zhangdachun successfully implemented the zero knowledge proof .

3

There are many examples of zero knowledge proof , Such as Alibaba and the forty thieves 、 Map coloring verification 、 Color blind games and so on , If you are interested, you can search the Internet .

Zero knowledge proof is made up of S.Goldwasser、S.Micali And C.Rackoff stay 20 century 80 Put forward in the early s , It has a 30 For many years , What's the use of it ？ We can imagine ：

I want a loan , The bank requires monthly income 5000 above , But I don't want to disclose my salary , At this time, zero knowledge proof comes in handy .

For nuclear control 、 Non proliferation and nuclear disarmament , International inspection agencies need a way , It can confirm the authenticity of the nuclear weapon information submitted by a certain country , Without exposing sensitive information about nuclear facilities , It is just the place where zero knowledge proof can be used .

In the security field and blockchain , Zero knowledge proof has been applied ：

Than me （ Liu Xin ） There is a public key and a private key , You got my public key safely , But never met me , One day we met .

I said, ： I am Liu Xin

You may not believe it , What if someone pretends ？

I can generate a random string , Encrypt with my private key , And send it to you .

You decrypt with public key , If you get the same string , You know I must be Liu Xin .

Every transaction on bitcoin is transparent , Who transferred how much money to whom is publicly available . however , Privacy coin realized by zero knowledge proof technology , for example Zcash You can achieve hidden transaction information , But at the same time, it can make the whole network verify the validity of transactions .

All in all , Zero knowledge proof for the first time The correctness of the proof is decoupled from the knowledge of the proof , This paradigm shift is a huge innovation , It expands the intellectual boundary of human beings .

Reference material ：

1. Computer Scientist Explains One Concept in 5 Levels of Difficulty

https://www.youtube.com/watch?v=fOGdb1CTu5c

There are examples of penguin pictures . What is more interesting is that he spoke to the pupils separately 、 middle school student 、 College students' 、 Graduate student 、 Experts and other five levels of people talk about zero knowledge proof , very interesting , Strongly recommend .

2. The Incredible Machine

https://medium.com/qed-it/the-incredible-machine-4d1270d7363a

It not only tells the examples of Sudoku , A proof machine is also constructed , Those who are interested can have a deeper understanding of .

（ End ）

Click on the picture below , See more highlights