The Incredible Zero-Knowledge Proof

Cryptography is the cornerstone of blockchain and has gradually become a distinguished school with the development of blockchain. Peoples who know little about history cryptography should know that cryptography used to be considered as military products for quite a long time and was listed in the “export ban” list. Modern cryptography had to start with the publication of a revolutionary paper in 1976. Diffie and Hellman’s New Directions in Cryptography came out in 1976, which announced the emergence of a new paradigm of cryptography.

In 2008, Nakamoto Satoshi published a paper called Bitcoin: a peer-to-peer electronic cash system, bringing the Cypherpunk movement to a new height. In the next 10 years, the slogan “not your keys, not your coins” became popular. From the protection of information security to property security, obscure cryptography is not only brilliant in the process of the information technology revolution but also become more and more closely related to the average joe. So Vitalik once joked on twitter that human beings should use gene-editing technology to precompile hash and elliptic curve operations into the brains of future generations.

Modern cryptography, like alchemy, is based on mathematical problems and Turing machine models, which are melted and cast into something inconceivable. In the 1970s and 1980s, the titles of many academic cryptography papers contained the words “impossible” or “paradoxical”. Maybe we can have a glimpse of the excitement of scientists at that time when they found this alchemy.

In this cryptographer’s magic toolbox, there is an esoteric concept that seems to be under the limelight recently. It is the protagonist of this article — zero-knowledge proof. How to prove a proposition is true without revealing any other information than the fact that the statement is true? This indeed sounds like a paradox.

Review the classic proof model

Since the Euclidean era dated back thousands of years ago, the basic form of proof is the process of deducing some propositions based on some predefined theorems and deduction rules.

Once a proposition is proved, one can rest assured that it can serve as a solid building grounds for any future theorems. The process of developing proof can be an Odyssey of human intelligence, such as the famous Fermat theorem. After more than 300 years, the first proof was completed by Andrew Wiles, a British mathematician in 1995.

It seems to be a lot easier to verify a proof than to prove it, the latter needs to put in more mental force to reach the goal. Later, we will find that the asymmetry of Prove-Verify has a more general connotation.

Since we have a classic proof concept that has last for thousands of years, what makes people rethink the concept itself?

“Heroes” of Cryptography: Adversaries

Cryptography is a discipline that grows stronger in the battles with its adversary. If there is no adversary, no eavesdropping or tampering with the transmitted information, no identity forging, no spying on personal privacy — if this is an ideal friendly and harmless world, we don’t need cryptographers. But I’m sorry that we live in a world where all aspects of information transmission, storage, and use can be attacked. All the great inventions and discoveries of cryptography come from than worthy adversary.

Back to the proof itself, the traditional proof will give a theoretical derivation process that is necessary for the statement to be true. Consider this, when you give proof and convince the other party that the proposition is true, the other party will also obtain the knowledge needed for proof.

Cryptographers are naturally a victim of paranoia. The prover asks a question: the purpose of the proof is to convince the verifier that my claim is correct. Can I not disclose any other information, that is, nothing but validity? The verifier, who happens to be a Cryptographer, can understand the ideas of his peers, but he asks another question: how can I be sure that you didn’t cheat without showing the proof itself?

Cryptographers are smart. They upgrade the classic prove-verify model, add two new elements, randomness and interaction, and thus reach a new proof system that can achieve the above purpose. Here are a few intuitive examples to demonstrate how this new proof system can be built.

Game of red-green colorblindness: Interaction and Randomness

This game is like this. Bob is red and green color blind. One day Alice took a piece of paper and told Bob that there are two colors of red and green on it. Maybe what Alice said is true, or maybe she just holds a piece of paper that is pure yellow (assuming that the red and green seen by the red and green color blindness are all yellow), how can Bob judge whether Alice is true or not?

Bob is very clever. He has a way:

1. First, he asked Alice to put the paper on the table, with red on the top and green on the bottom;
2. Ask Alice to turn around. He tosses a coin. If it’s tail, he keeps the paper still. Otherwise, he turns the paper 180 degrees, that is, it turns green at the top and red at the bottom;
3. Ask Alice to turn around and ask her the color of the paper and check whether it is consistent with her own operation;
4. Repeat steps 2 to 3 N times;

Through this method, if Alice has passed the check n times, there is a probability of 1 — (1 / 2) ^ n that Alice is true. This paper does have red and green colors. This simple agreement contains two important concepts:

1. Interactive: unlike the classic prove-verify model, this proof is completed by multiple interactions between the prover and the verifier;
2. Randomness: Bob can get the real random number by flipping coins;

In addition, this interaction protocol also contains three properties:

1. If the paper is indeed red and green, Alice must be able to convince Bob of this, which is called completeness.
2. If the paper is yellow, Alice, no matter what strategy she adopts, will be rejected by Bob with a great probability because she can’t extract and predict the result of Bob’s coin toss, which is called “soundness”, that is, Alice can’t cheat. This is a huge difference between the interactive proof system and the classical proof. The classical proof is deterministic and the interactive proof is probabilistic. The wonderful thing is that interactive proof also achieves the purpose of persuading the verifier, which actually expands the connotation of the ancient concept of proof.
3. Bob didn’t get any other knowledge than the fact that there are two colors of red and green on the paper (what’s interesting here is that Bob himself is color blind, and he can’t get the actual information about color), which is called zero-knowledge.

The completeness and soundness are easy to prove, but zero knowledge is an intuitive feeling. To prove it, we need to borrow a simulator. Here is another example to introduce the concept of simulation.

Alibaba’s Cave: Simulation Paradigm

“Alibaba and the Forty Thieves” is a well-known story in China. Alibaba, the Internet giant in China, can see many traces of this ancient fable. In addition to the company name, there is a branch of credit scoring system named as sesame credit (from the mantra of “sesame opens the door”).

The cryptographer Quisquater adapted this story in 1989, called “how to explain zero-knowledge proof to your children”, to explain the concept of zero-knowledge proof just emerging in the academic world. This new story is as follows:

Ali Baba is a market businessman. His goods are often stolen by a thief. In the process of chasing after the thief, he found a cave as shown in the figure below. There are two branches at the entrance of the cave. No matter which branch you enter, you will go to the dead end.

In the process of chasing the thief for nearly 40 times, he saw the thief go into the cave but didn’t know which direction. He chose a direction at random every time and never caught the thief. He thought that the thief would never be so lucky which can choose a direction different from him every time. Eventually, he found that the exit was actually a door which can be opened by the mantra of “sesame open door” from the thief. Ali Baba caught the thief and knew the secret of the door.

A few centuries later, manuscripts left by Alibaba were found, recording the story of the cave and clues the mantra. According to the information in the manuscripts, people found this cave in Baghdad. A scholar named Mick Ali claimed that he knew the mantra, and the TV station found him and won the exclusive report. But Mick didn’t want to reveal information about the mantra, so he used the above zero-knowledge proof to prove:

The cameraman of the TV station is standing at the cave entrance. Mick randomly selects A or B direction to enter by flipping coins. Then the cameraman also randomly throws coins at the cave entrance and shouts “come out from A”, “come out from B”. This experiment was repeated 40 times, and Mick was able to come out as required each time. Like the red and green color blind game, he convinced the photographer with great probability. These are recorded and broadcast as programs.

Another TV reporter also wanted to cover the mysterious cave. He found Mick, but Mick has signed an exclusive deal with the previous TV station. The jealous reporter was very upset, but Mick hinted that you don’t need a mantra to shoot the show. The reporter was smart enough to understand. He found a substitute similar to Mick and made such a video:

The cameraman of the TV station is also standing at the entrance of the cave. The substitute guy enters through the direction A or B randomly by flipping coins. The cameraman also throws coins randomly at the entrance of the cave and shouts “come out from A”, or “come out from B”. But when the result of the substitute are different from that of the cameraman’s coin toss, the substitute can’t open the door without the mantra, and can’t come out as required. The reporter cut off these failed fragments and left a complete 40 successful experiments as the material of the program.

The program, which was broadcast by two TV stations at the same time, caused a lawsuit. The former TV station sued the latter to the court. The two videos are submitted to the court as evidence, but neither judge nor expert can distinguish them (without considering other pieces of evidence and testimonies). In the end, the lawsuit is over without any result of the sentence.

Mick Ali achieved his real goal. The photographer did know that he had a curse, but even if there was a video, he couldn’t persuade other people who were not present at the experiment to “Mick knew the mantra” because anyone could fake the video.

The above example is the basic idea to prove that a protocol has the nature of “zero-knowledge”. By constructing a simulation program, a record is generated and can be compared with the record generated by the real zero-knowledge protocol implementation process. If it is impossible for a computer to distinguish these two, it is proved that the verifier cannot get any information from the proof that he cannot execute by himself, except that the proposition is true.

Mathematicians in travel: Non-Interactive and Publicly Verifiable

In the third story, the protagonists are Arthur and Merlin, both mathematicians. One day Arthur began to travel and thought about mathematics during the journey. Whenever he finds a new proposition, he will write a postcard to Merlin, and he also doesn’t want to disclose any information except that the proposition is true. Merlin, on the other hand, can verify the truth of the proposition only by postcards.

This small example actually reflects the disadvantages of the zero-knowledge proof mentioned above, although it is cool in theory, in the actual project:

1. There are many interactions between the prover and the verifier, which undoubtedly requires a lot of communication overhead;
2. Each prover needs to run the interaction protocol independently with a specific verifier, so as to confirm the true and false of the proposition, which cannot be publicly verifiable.

The basic idea is to find a random way to replace Merlin in the interactive proof process and to prevent Arthur from using this randomness to cheat. Using the Fiat-Shamir hypothesis and one-way hash function, cryptographers have successfully designed the non-interactive zero-knowledge (NIZK) protocol. Non-interactive and public verifiability is the necessary condition for the ZKP system to be widely adopted.

The above three stories demonstrate the basic ideas and important concepts of zero-knowledge proof. The interested readers are referred to academic materials on the specifics of ZKP

The transcendence of theory

ZKP has been developed for 35 years since it was proposed in 1985. For the first time, it decouples the correctness of proof and the knowledge of proof from cognition. This transformation of the thought paradigm contains great potential for innovation. Until now, it is still a dynamic research field, with new progress each passing day. You can find in below a ZKP family tree, which the root is the cryptography hypothesis it is based on, some of which can be traced back to more than 40 years ago, but most of the fruits on this tree have “grown” in the last 10 years, from the laboratory into the industry.

zkp family trees: by StarkWare

They offer wonderful solutions to many of the problems that the world is facing today:

1. Nuclear warhead detection: scholars of Princeton and MIT use ZKP to design a nuclear warhead verification system for nuclear control, non-proliferation and nuclear disarmament. Due to the sensitivity of nuclear facilities, international inspectors need to be convinced of the authenticity of the submitted items and are not allowed to obtain any confidential information. This goal can only be achieved by using ZKP;
2. Privacy protection of cryptocurrency: Zcash uses zk-SNARK to provide privacy protection for cryptocurrency transactions, which can guarantee the legitimacy of transactions when the sender, receiver and the number of transactions are hidden on the blockchain;
3. Secure machine learning: big data and machine learning promote a new wave of artificial intelligence, using ZKP and other cryptography tools to ensure the privacy and correctness of computing;
4. ……

Just as the list will continue to grow, so will be the impact zero-knowledge proof has on the real world. To understand the zero-knowledge proof is not only to better understand this technology, but also to better understand the intellectual boundary that human beings can expand through their own efforts, and this may be a proof that human beings can provide on their own existence.

Reference

1. Shafi Goldwasser, Silvio Micali, Charles Rackoff: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). STOC 1985: 291–304