Editor's Note: This article comes from Ambi Labs (ID: secbitlabs), Author: Guo Yu, reproduced by Odaily with authorization.
I know that I know nothing
Editor's Note: This article comes from
Ambi Labs (ID: secbitlabs)
— SocratesFirst understanding of "zero knowledge" and "proof"I believe that many people have heard of zero-knowledge proofs, but only a few people have heard of simulation, but simulation is the key to understanding zero-knowledge.
Our first article "
』[1] introduces a simple zero-knowledge interactive system: the map three-coloring problem. So is this system really zero-knowledge? Why should we believe this conclusion? Is there proof? During the conversation between Alice and Bob, if there is no zero knowledge, Alice will be cheated. The designer "I" of the interactive system needs to convince Alice that this dialogue is indeed zero-knowledge.
If you explain it from the perspective of intuitionism, to prove that there is information leakage in an interactive system, then you only need to prove: which bit causes information leakage; but if you want to prove that there is no information leakage, then you have to face all information flows All the bits in say, the bits numbered from 1, 2, 3, 4, 5, ... don't reveal any information. Judges, is this difficult?
This article is about 8,000 words, a little brain-burning.
secondary title
Security Definition and Indistinguishability
First of all, an interactive system, that is, a dialogue, its "zero knowledge" needs to be proved. After all, modern cryptography is built upon rigorous formal systems. Before the proof, it is necessary to clarify what the "safety assumptions" are. The so-called security assumption, for example, we say that the authority isolation of a system is extremely precise, and each user can only see authorized information, but this is based on a security assumption: the administrator account has not been cracked. Another example is that in the mobile banking software, the transfer function can only be completed through the SMS authentication code. This is also based on a security assumption: your mobile phone SIM card has not been cloned. If we drill down into every system we feel is secure, there are a large number of security assumptions that don't seem so solid. Are Bitcoin Private Keys Safe? There are also many security assumptions for Bitcoin accounts: first of all, your mnemonic cannot be known to others, the encryption algorithm for storing the private key in the mobile wallet is strong enough, the key derivation algorithm is regular, you cannot forget the mnemonic, and so on.
Talking about security without security assumptions is hooliganism. Everything is safe. Only after mathematical proof can everyone be sure that the security of this algorithm/scheme is based on some very clear "security assumptions".
Before the proof, there is still one thing missing, that is "safety definition". In the cognitive system of most people, security is a box into which everything can be installed. Everyone should remind themselves well, when talking about the word safety, have you ever thought about what safety is? How is it considered safe?
"Security" needs to have a strict definition in the mathematical sense
The great scientist Claude Shannon gave a very reliable definition of security from the perspective of information theory [2]:
Perfect security: Assuming you are an attacker, you cannot get any valuable information through the ciphertext, and the only way to crack it is to rely on blindness.
Think about it, everyone, this definition is very interesting. You can’t get information through ciphertext, which means you don’t get any extra computing power, which can help you calculate plaintext in a shorter time.
But this definition is so perfect that it is difficult for the encryption algorithm used to meet this security definition. Later, Goldwasser, Micali and others wrote another classic "probabilistic encryption" [2] that was recorded in history.
In this paper, such a concept is defined: semantic security. The so-called semantic security relaxes some requirements on the definition of perfect security.
Semantic security: Assuming you are an attacker, you cannot calculate any valuable information through the ciphertext in polynomial time.
We introduce another concept - "indistinguishability" to redefine the security of encryption algorithms: Suppose you are an attacker, and I have an encryption algorithm:
OK, after understanding "indistinguishability", let's go back to "zero knowledge". How to prove that an interactive system is "zero knowledge"? First, we need to define the concept of zero knowledge
Note: Indistinguishability is indistinguishability in the sense of probability; academically, it can be divided into "completely indistinguishable", "statistically indistinguishable", and "computationally indistinguishable". In this article, we don't need to understand the difference between these concepts for the time being.
secondary title
meet the simulator
Let’s start with a brain hole, imagine that in the parallel universe, there are two parallel worlds, one is called "Ideal World" (Ideal World) and the other is called "Real World" (Real World). Each of us can play happily in two parallel worlds, but ordinary people in the two worlds cannot perceive or communicate with each other.
Suppose "you" is a very powerful code cracker, and "you" is not an ordinary person, with the ability to travel between parallel universes. And Alice has an answer to the map three-coloring. Your goal is to get the answer to the map three-coloring by talking to Alice. For the conversation process, refer to the "map three-coloring problem" protocol in the previous article.
Continuing with the imagination, Alice only exists in the "real world"; in the "ideal world", Alice is "replaced" with an individual who looks and sounds exactly the same, and we call the double Zlice. Next, put "you" in both worlds at the same time, but don't let you know which world you are currently in. Both of your doubles are facing someone who looks like "Alice".
Repeat again, in the "real world", the person talking to you is a real and honest Alice; while in the "ideal world", the person talking to you is Zlice (fake Alice), although Zlice has the same appearance and language as Alice It's the same, but the difference is that Zlice doesn't know "knowledge", that is, doesn't know the answer to a three-color problem.
Then in both worlds, your two doubles will talk to real and fake Alice at the same time. A miraculous thing happened. Finally, in the two worlds, both of your avatars were convinced, and after n rounds of challenges, no one was found to be cheating, that is, the two avatars of "you" believed that the other party really knew the "answer" . In other words, "you" do not have the ability to "distinguish" whether you are in the "real world" or the "ideal world", and of course you do not have the ability to "distinguish" whether you are talking to Alice or Zlice. Not only that, but for the people who eat melons, if I put "I" as an observer in any world, I will be "indistinguishable" like you from whether the person who looks like "Alice" in front of me is real or not. Fake.
Here are the brain-burning conclusions:
Why is this interactive system "zero knowledge"?
Because Zlice is without any knowledge, and she is indistinguishable from Alice.
Let me explain it in another way: because neither you nor I can distinguish which world we are in, the interaction process between the two worlds is almost indistinguishable, and there is no knowledge in one of the worlds, so we say that this interaction Agreement - "map three-coloring problem" is "zero-knowledge".
There is also a premise here, the ideal world must be algorithmically constructable. Then, there is a "god" who "simulates" an "ideal world" through an algorithm, and constructs an algorithm called Zlice. She has no "knowledge" as input, that is, "zero knowledge"; in addition, " The "ideal world" is exactly the same as the "real world".
Imagine that during your conversation, if the real Alice leaks information, then you can immediately distinguish whether the person in front of you is real Alice or Zlice. It is impossible for Zlice to pretend to leak information. Therefore it can be concluded that:
This god is called a "simulator", and in the ideal world, the Zlice phantom talking to you is actually a "simulator". In the ideal world, everything you can perceive is a simulator "Simulated" out.
Well, here, we use the concept of "simulator" to define "zero knowledge".
Save World State as Snapshot X
Next, we begin to enter the link of proving zero knowledge.
secondary title
separate the two worlds
The zero-knowledge process of the proof is equivalent to constructing (finding) a "simulation" algorithm that allows the simulator to simulate an ideal world with "no knowledge". If this algorithm exists and the two worlds are indistinguishable, then the proof is complete.
If such an algorithm really exists, and it can fool me without knowledge, then in the "real world", it is not ruled out that the real Alice also uses such an algorithm to deceive me. In this way, have I not been deceived in both worlds. Then this interaction agreement loses its meaning.
In fact, there is a key point here. Borrowing the stills from the movie "Inception", there are some things in the "ideal world" that are fundamentally different from the "real world". This thing is the key to distinguishing the two worlds, and it makes us "unperceivable". This thing is not the spinning top in the dream, it is a kind of "superpower", the superpower possessed by the simulator Simulator.
For example, such a superpower: "back in time".
image description
(The picture above is a still from the movie "Groundhog Day". Every time the protagonist wakes up, he will return to the morning of February 2, so that he will always live on the same day)
Wait, readers, haven't we been discussing indistinguishability just now? Why do the two worlds need to be distinguished again? "I'm confused". Don't panic, the so-called indistinguishability is aimed at individual cognition in an ideal world. And "differentiability" is for the gods who are outside the world.
So far, the "zero knowledge" of the interactive protocol has been proved. Do you already understand? Let me sort out the proof ideas again for you:
First of all, "zero knowledge" is to protect Alice's interests, because Alice does not want to disclose more information to Bob during the interaction process, does not want Bob to know her secret w, and even does not want Bob to analyze even A morsel of information. So how to ensure this? The "simulator" comes on the stage at this time, it can simulate an "ideal world" that looks exactly the same as the real world, and then the "simulator" can easily fool any opponent in this world, making it impossible for the opponent to tell whether they are in In the real world, or in the ideal world. Because the "simulator" does not have the secret w in its hands, the "ideal world" is zero-knowledge. And because of the indistinguishability of the two worlds, we can conclude that Alice's interaction protocol is "zero-knowledge".
Let's look at a specific example, the map 3 coloring problem mentioned in the previous article [1].
secondary title
Zero-Knowledge Proof of Map Triple Coloring Problem
Recall the "Map Three Coloring Problem Interactive System":
Step 1: Alice makes a complete replacement of the map coloring answer, then covers all the vertices with paper, and gives it to Bob
Step 2: Bob randomly picks an edge
Step 3: Alice opens the piece of paper at the vertices at both ends of the specified edge, Bob checks whether the colors of the two vertices are the same, if they are different, they pass, and if they are the same, they fail
Go back to the first step and repeat n times
Next, we will prove that the above interaction is zero-knowledge. Here we assume that the verifier Bob is honest, which will help everyone understand the proof process. Then we discuss the proof method if Bob is dishonest.
In the "ideal world", what Bob talks to is a "simulator", which simulates the appearance of the whole world. Bob interacts according to the interaction protocol for the three-color problem. The simulator doesn't have a three-color answer, it simply colors all vertices gray.
First, the simulator imitates Alice and covers each vertex with a piece of paper. Then send it to Bob.
Bob picks an edge at random and challenges the prover.
The simulator cannot open the paper at this time, because the color at both ends of this edge is gray.
At this time, the simulator is about to exert its "super power". He uses the skill of turning back time and returns to the first step of the dialogue.
The simulator is now in the first step, where he dyes the ends of the bottom edge any different color, re-covers the paper, and sends it to Bob.
At this time, Bob can't perceive that time has gone back to the first step. For him, everything is new, and he "honestly" chooses the bottom edge again.
So in the ideal world, the simulator does not have any "knowledge" of the three-color answer, but it can also fool Bob, and from the perspective of probability, it is highly consistent with the observed interaction process in the "real world" (exactly the same probability distribution). So the above process shows the existence of the algorithm of the simulator, which is equivalent to proving the "zero-knowledge nature" of the interactive system.
dishonest bob
In the above proof process, there is a fairly strong assumption that Bob will choose the same edge every time the time goes backwards. What if Bob switched to a different side each time? It doesn't matter, if Bob chooses a different side after the simulator implements time reversal for the first time, then the simulator can mess up the colors and run time reversal again. After multiple times of time reversal, Bob has a great probability The edge that the simulator will dye will be selected at one time, and then the simulator will go to the third step and open the paper.
secondary title
Ali Baba, Caves and Open Sesame
Among the many Chinese popular science articles explaining "zero-knowledge proof" on the Internet, there is an example that has been widely circulated. This is the story of Alibaba and the robbers. Unfortunately, these different versions of the story are only half told. Then I will tell a different story about "Alibaba" and "Forty Thieves":
A long time ago, in a city called Baghdad, there lived a man named Ali Baba. Every day Alibaba will go to the market to buy things.
One day, Ali Baba was robbed of his wallet by a thief, so he chased the thief all the way to the entrance of a cave, and then the thief disappeared. Alibaba found two forks in the entrance of the cave, as shown in the figure below.
Ali Baba didn't know which way the thieves were going, so he decided to take a look at the "left" fork. Soon Ali Baba found that this was a dead end and there was no trace of the thieves. Then he went to the "right" fork to check again. It was also a dead end, and there was no trace of the thief. Ali Baba said to himself, "Where did the damn thief go?"
The next day, Ali Baba went to the market to buy things again. This time another thief robbed his basket, and then Ali Baba chased the thief to the same cave entrance as yesterday, and then the thief disappeared again. Go to the "right" fork to see, no thieves are found, and then go to the left to see, also no thieves. This is very strange.
On the third day, the fourth day, ..., the fortieth day, the same story unfolded. Ali Baba chased the fortieth thief to the mysterious cave, and the thief disappeared. Ali Baba thought that there must be a mechanism in this cave, so he hid at the end of the "right" fork and waited patiently for a long time. ". At this time, the wall opened. After the thieves ran in, the wall closed again. At this time, another victim chased in. After searching for a long time, they found nothing.
Ali Baba then tried the spell after they were gone, and it was very effective, and Ali Baba found that the wall led to the "left" side road. Later, Ali Baba found a way to replace the spell, and wrote a new spell and the location of the cave on a piece of parchment.
Note: At this point, the story does not end.... (subtitles) After a long, long time
Many years later, in the 1980s, Ali Baba's parchment fell into the hands of a few cryptographers. They went to Baghdad and found the location of the cave. Even after centuries, the spell still works. These few The cryptographer excitedly opened the wall and ran back and forth between the two forks.
The program was very successful. But soon, another TV station was jealous and wanted to shoot a similar program, but Mick Ali couldn't participate in this new program because he signed an exclusive agreement. How to do it? The host of the second TV station had a plan. He found an actor who was very similar to Mick Ali. He imitated Mick Ali in dress, posture and speaking accent. Then they started filming, and every time the host flipped a coin, the actor ran out, but obviously, the actor didn't know the spell and couldn't open that wall. So sometimes the actor happens to be successful, and sometimes he fails, so the actor worked very hard, repeated nearly a hundred times, and only succeeded forty times. In the end, the cunning new show host edited the recorded video, keeping only the successful clips, and deleting the wrong clips. Then this new show and Mick Ali's show were broadcast on different channels at the same time. Viewers are then completely unable to tell which video is real and which is fake. The host of the first TV station fully understands that Mick Ali is the one who really knows the spell of the wall, but he can't pass this fact on to the innocent viewers.
Seeing this, do you gradually have a feeling for "simulation"? Here the host of the second TV station cuts the video instead of "reversing time". His external intervention in the "ideal world", that is, the world where the content broadcast on TV, has achieved the same effect. In an ideal world, editing is essentially a superpower
This story actually comes from a paper "How to Explain Zero-Knowledge Protocols to Your Children" (How to Explain Zero-Knowledge Protocols to Your Children) [3], which was published at the 1989 Mimi Conference.
secondary title
Simulation and Turing Machines
When it comes to superpowers, do you think this stuff is unscientific? Yes, if we mindlessly use "superpowers" to explain anything, then our logic will not be consistent (Consistent). In an ideal world, the simulator cannot be opened casually. For example, the simulator must not directly modify Bob’s internal state. For example, Bob obviously failed the verification step in the verification step, but the simulator insists on changing the verification result to "accept". It will lead us to prove: "Any interactive system is zero-knowledge", this wrong conclusion.
Simulators are not almighty gods in an ideal world.
So what exactly can an emulator be? The simulator is really just a Turing machine. The so-called superpowers such as "rewinding time" and "editing video" are not mysterious supernatural abilities, but functions that can be realized by Turing machines. Friends who are computer professionals must have used VMWare, virtual machine and other software. The "simulator" mentioned in this article can be imagined as a "virtual machine" software, which can virtualize a computer environment. The "ideal world" mentioned in the text. How to explain "back in time"? I don't know if you have used the "snapshot" function (Snapshot) of the virtual machine software. When using the snapshot, the virtual machine software can save all the states of the entire virtual computer, and then at any time, the virtual machine software can be restored. Go to where you saved the snapshot and continue running.
Note: In fact, the so-called time reversal is a basic operation in the computer. There is a concept called Continuation in the programming language theory. Abstractly speaking, a Continuation represents computation from now to the future. Continuation is an explicit abstraction of control flow, and goto, call-with-current-continuation, and even thread scheduling can be regarded as operators for operating Continuation. For example, call/cc, that is, call-with-current-continuation, can easily implement the "backtracking" function. Saving a snapshot can be understood as saving the current continuation, and returning to a certain moment in the past is to apply this continuation.
Is everyone enlightened again, let me emphasize again:
The process of proving zero-knowledge is to find an algorithm, or more generally, to write a piece of code that runs on an external computer system, but realizes the function of a virtual machine. And in the virtual machine, there needs to be a Zlice without "knowledge" as input, which can fool Bob who is put into the virtual machine to run.
If you haven't understood my sentence above, please go back to the section "Distinguishing the Two Worlds" and rethink the simulation. :P (Load World State from Snapshot X)
secondary title
Plato's Allegory of the Cave
Simulation is everywhere, and Gödel's incompleteness theorem uses the concept of simulation to simulate formal arithmetic with Godel Numbers. Turing proposed the concept of "Universal Turing Machine", which can simulate itself.
But the earliest concept of "simulation" comes from the seventh volume of the book "Utopia" [4]. The ancient Greek philosopher Plato told such a fable-Allegory of Cave:
Imagine that in a dark cave, there is a row of chained prisoners who have been brought up to see only the wall in front of them. Behind these prisoners is a wall, and behind them there is a pile of fire. Between the fire and the wall, some people walk back and forth holding props and puppets, so that the props and puppets will cast shadows on the wall under the reflection of the fire. And these prisoners can only look at these shadows all day long. Because these prisoners have heard and seen all kinds of shadows on the cave wall in front of them since they were born, and they will think that these shadows they see are the real world.
Plato hypothesized that if the prisoner was dragged out of the cave forcibly and went outside to see the real world, at first the prisoner would not adapt to the light of the real world and feel dazzling and dizzy, and he would be angry because of this. But when he got used to this world slowly, seeing the sun, trees, rivers, and starry sky, he gradually understood that this world was superior and advanced than the world in the cave. He never wanted to go back to the dark cave life ever again.
to be continued
After a while, he felt compassion for the prisoners in the cave, and thought of bringing them all out. But when he returned to the cave again, he couldn't see clearly because he had adapted to the bright world outside. Instead, the locked prisoners thought he was blind, talking nonsense, and a lunatic. Finally, when he tried his best to get the group of prisoners out of the cave, he was killed by the prisoners.
This is an allegory of human destiny, similar to the row of prisoners chained in chains. We think that what we see with our eyes is the truth of the world, but in fact, it may be an illusion, just like the shadow cast on the cave wall. .
to be continued
Two methodologies are crucial in computer science, the first is "abstraction" and the second is "simulation".
references
Look back at Bob's dialogue between the "ideal world" and the "real world" in the map three-color problem. Although Bob cannot distinguish between the two worlds, there is one thing he can be sure of: in the real world, Alice has no superpowers.
[2] Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.
[3]Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G. and Guillou, S., 1989, August. How to explain zero-knowledge protocols to your children. In Conference on the Theory and Application of Cryptology (pp. 628-631). Springer, New York, NY.
references
[5] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.
[6] Oded, Goldreich. "Foundations of cryptography basic tools." (2001).
[7] Rackoff, Charles, and Daniel R. Simon. "Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1991.
[8] Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems." Journal of the ACM (JACM) 38.3 (1991): 690-728.
