Mind Reading: Extracting "Knowledge" from Zero Knowledge Proof

And what, Socrates, is the food of the soul? Surely, I said, knowledge is the food of the soul.

Socrates, what is the food of the soul? I said, of course, knowledge.

—— Plato

"zero knowledge" vs. "reliability"

• Academician Zhou Zhongyi of the Chinese Academy of Engineering: Blockchain application must first distinguish user-centric classification
• Financial giant Fidelity executives: In order to protect investors, we have not yet provided cryptocurrency trading services on retail trading platforms.
• Will the quantitative fund industry break out? Global mainstream investors will participate in 5 years

We can see these three properties in many articles that introduce zero-knowledge proof:

Completeness – completeness

Soundness – reliability

Zero-Knowledge – zero knowledge

But few articles explain in depth the deep meaning and insight behind this feature.

In the article "Series (2) Understanding "Simulation"", we introduced the concept of "simulator". Many introductory articles avoid talking about "simulation", but "simulation" can be said to be the core of the security protocol, because it is an important weapon to define "security."

In general, we define security in such a way that we first list some security events and then state that if a system is secure, then the listed security events will not occur.

Rather than giving a list of the events that are not allowed to occur, it (the definition of zero-knowledge proof) gives a maximalist simulation condition.

— Boaz Barak

Borrowing the cryptographer Boaz Barak, the translation, "zero knowledge proof" is not defined by giving a list of events that are not allowed to occur, but directly gives the most extreme "simulation conditions."

The so-called "simulation condition" refers to the realization of an "ideal world" through the "simulation" method, making it indistinguishable from the "real world"; and because there is no knowledge in the ideal world, it can be concluded that the real world is satisfied. "Zero knowledge."

We continue to analyze the three properties of the next interactive system (security protocol): "completeness", "reliability" and "zero knowledge."

Soundness: Alice cannot pass Bob's verification without knowledge.

Completeness: Alice can pass Bob's verification if he has knowledge.

Zero-knowledge: Alice does not reveal any information about knowledge during the interaction.

We can see that "reliability" and "completeness" have a "symmetry." Reliability guarantees that malicious Alice must fail, and completeness guarantees that honest Alice will succeed.

"Completeness" is easier to prove, as long as Alice is honest and Bob is honest, then everyone is happy. This is like writing a piece of code, feeding a test case, and finishing the work.

Let us think about how "reliability" should be defined? The inverse of this reliability proposition is: (in the real world) If Alice can pass Bob's validation, then Alice must have knowledge. Or say: Alice knows that… a "secret"!

The following question is how to prove that Alice knows a "secret"?

It seems to be difficult, right? If we need to prove that a machine knows a "secret", the easiest way is to find the "secret" in the hard disk of the machine or in the memory, but this reveals the secret. What if this machine is a black box? Or is it Alice? We didn't read the mind and couldn't guess the secret in her heart.

How to define "To Know"?

Zero Knowledge ensures that the certifier Bob does not have the (computing) ability to "extract" information related to "knowledge". "Knowledge" that cannot be extracted does not mean that it does not exist. "Reliability" guarantees the "existence" of knowledge.

Only when "knowledge" exists, it is meaningful to guarantee "zero knowledge."

This article will explore "reliability" and "To Know."

In order to further analyze "knowledge", we first introduce a very simple and versatile zero-knowledge proof system – the Schnorr protocol. This protocol represents a large class of security protocols, the so-called Σ-protocol, and the Schnorr protocol extension is also one of the core technologies of the zero-knowledge data exchange protocol zkPoD [1].

Simple Schnorr protocol

Alice has a secret number, a, we can think of this number as a "private key" and then "map" it to a point a*G on the elliptic curve group, abbreviated as aG. At this point we use it as a "public key."

Sk = a

PK = aG

Please pay attention to the word "mapping". Let us briefly introduce the concept of "homomorphism". There is a homomorphic mapping relationship between the finite field of elliptic curve groups. The finite field, we use the symbol Zq, where the prime number q refers to the size of the finite field, which refers to a set of integers from 0, 1, 2, …, q-1. On an elliptic curve, we can generate a "cyclic group" through a base point, G, labeled 0G, G, 2G, …, (q-1)G, which is exactly the set of q curve points. Any two curve points can be used to perform a "special binary operation", G + G = 2G, 2G + 3G = 5G. It seems that this binary operation seems to be similar to "addition", satisfying the commutative law and the conjunction law. So we use the + symbol to indicate. The reason why this group is called a cyclic group, because the last element (q-1)G of the group, plus a G, is rolled back to the first element 0G of the group.

Given an integer r on any finite field, we can find a corresponding point rG in the loop group, or use a scalar multiplication to represent r*G. But the calculation in turn is very "difficult". This is a "cryptographic problem" – called the discrete logarithm problem [2].

That is to say, if any point R on an elliptic curve cycle group is given, then which integer in the finite field corresponds to R, this calculation is very difficult. If the finite field is large enough, for example, 256bit is so large, we I can think that this reverse calculation is impossible.

The Schnorr protocol makes full use of the one-way mapping between finite fields and cyclic groups, and implements the simplest zero-knowledge proof security protocol: Alice proves to Bob that she has the private key sk corresponding to PK.

The first step: In order to ensure zero knowledge, Alice needs to first generate a random number, r, the purpose of this random number is to protect the private key can not be extracted by Bob. This random number also needs to be mapped to the elliptic curve group, rG.

Step 2: Bob wants to provide a random number to challenge, we call it c.

Step 3: Alice calculates z = r + a * c according to the number of challenges, and sends z to Bob. Bob tests by the following formula: z*G ?= R + c*PK = rG + c*(aG )

You can see that Bob tests the calculation process of z in the same way in the third step. If this formula is true, then it can be proved that Alice does have a private key a.

However, why is this?

The calculation and verification process for z is interesting and there are several key techniques:

First, Bob must give a "random" challenge number, and then Bob checks z in a homomorphic state on the elliptic curve. If we consider the challenge number c as an unknown number, then r+a*c=z can be thought of as a one-dimensional equation, where r and a are equation coefficients. Note that if c is unknown, if r + a*x = r' + a'*x is true, then according to Schwatz-Zippel's theorem [3], r=r', a=a' is the maximum probability. Established. That is to say, Alice wants to find another pair of different r', a' to calculate z. It is almost impossible to fool Bob if c is unknown. This random challenge number c implements the limits of r and a. Although Bob randomly selected a number, Alice had to use the private key a to calculate z because Alice didn't know it beforehand. The key here: c must be a random number.

Bob verification is done on an elliptic curve group. Bob doesn't know r, but he knows that r maps to point R on the curve; Bob doesn't know a, but he knows that a maps to point PK on the curve group, a*G. Through the homomorphic mapping and the Schwatz-Zippel theorem, Bob can verify that the calculation process of z is correct, so that Alice is indeed calculated by r and a, but does not expose the values ​​of r and a.

Also, the random number r generated in the first step of the protocol guarantees the confidentiality of a. Because any secret is summed with a random number that conforms to the "consistent distribution" and still conforms to the "consistent distribution".

Prove zero knowledge

Let's take a look at how the Schnorr protocol proves a weaker "zero knowledge" nature – "SHVZK":

Note: Here we only prove the Special Honest Verifier Zero-Knowledge (SHVZK). SHVZK requires Bob's behavior in the agreement to be unreasonable. For example, he must agree on the agreement. In the second step, take a fresh random number on the conveyor and use it immediately. In the usual sense, "zero knowledge" does not make any demands on Bob, so we say that this is a weaker nature. Although the current Schnorr protocol cannot prove complete "zero knowledge", after adding some protocol steps, the goal of complete zero knowledge can be achieved. The details are not developed here. For interested readers, please refer to the literature [4]. We will discuss this issue again later when we discuss the Fiat-Shamir transformation.

First, the "simulator" simulates an "ideal world", simulating a Zlice and Bob conversation in the ideal world, Zlice has no knowledge of the Schnorr protocol, sk, and Bob has the public key PK. Please take a look at the picture below. Bob needs to present a random number c in the second step of the Schnorr protocol. There is an additional requirement that Bob can only "honestly" take a random number from an external "random number conveyor". Each random number must be a one-time distributed random number in the range of 2^k generated by throwing "coins" in advance. Bob can't generate random numbers in any other way, which is why we ask Bob to be honest.

Here's how Zlice fools Bob:

Prologue: Please note that Zlice has no knowledge of sk, and Bob's random number conveyor has pre-placed some random numbers.

Step 1: Zlice produces a consistently distributed random number c and replaces the first random number on Bob's random number transfer with a new "super power". At this time, Bob could not detect it.

Step 2: Zlice again generates a random number z, then calculates R'=z*G – c*PK and sends R' to Bob.

Step 3: At this point Bob will get c from the random number conveyor and send c to Zlice. Please note that this c is exactly the c produced by Zlice in the first step.

Step 4: Zlice sends the random number z generated in the third step to Bob. Bob verifies according to the verification formula of Schnorr protocol. You can check that this formula is perfect.

You can compare the "real world" Schnorr protocol, and Bob can be verified in both worlds.

But the difference is:

In the "ideal world", Zlice has no sk; in the "real world", Alice has sk

In the "ideal world", z is a random number and does not involve sk; in "real world", the calculation process of z contains sk

In the "ideal world," Zlice used super powers to replace Bob's random numbers; in the "real world," Alice couldn't see Bob's random number conveyor, nor could she change the numbers on the conveyor.

Here, please think about it:

In the Schnorr protocol, can Bob challenge the number in the second step? That is to say, Bob can send the challenge number first, then Alice sends R = r*G.

(Two minutes later…)

The answer is no.

If Alice can know the random number in advance, Alice (in the real world) can trick Bob according to the simulator Zlice.

Re-experience simulator

In fact, the two properties of "reliability" and "zero knowledge" also have a symmetry in another dimension. Reliability guarantees that malicious Alice must fail, and zero knowledge guarantees that malicious Bob will not succeed. Interestingly, this symmetry will be reflected in the simulated "ideal world."

We analyze the definition of reliability: Alice has no knowledge that causes Bob validation to fail. Its inverse noun is: Bob's verification success leads Alice to have knowledge.

We once again turned to the simulator to test Alice's knowledge in the "ideal world" where super powers can be used.

Again, please imagine that in the parallel universe, there are two worlds, one called "ideal world" and the other called "real world." What's interesting about the ideal world is that it is simulated by the "simulator", and the simulator can put a superpowered NPC in the ideal world. This time, I put Alice's two avatars into the "ideal world" and the "real world."

Assuming that "you" plays the role of Bob, you want to know if Alice talking to you is really "reliable." So put you in the "ideal world", with a super-powerful NPC, you can "extract" the knowledge of Alice on the opposite side.

W…hat? We have not just proved: Is the agreement zero-knowledge? Zero knowledge means that Bob can't extract any "knowledge" fragments. Knocking on the blackboard here, "zero knowledge" is for the "real world." What we are discussing now is the magical "ideal world."

Repeat, in the "ideal world", you can extract Alice's knowledge with a super-powerful NPC, so that Alice in the "real world" can't cheat. Imagine a cheating Alice, she certainly has no knowledge, and without knowledge, it is impossible to let the NPC extract anything in the "ideal world."

However, in the "real world", you can't rely on NPC, and of course you can't see Alice's knowledge, and you won't conflict with the "zero knowledge" nature. Because the events in the two worlds are "indistinguishable", we can conclude that in the "real world", Alice must have knowledge.

Sort out the idea: How to prove that Alice can't cheat in an interactive session? We need to define a "simulation algorithm" for this interactive session. This algorithm can simulate an "ideal world". There is a special role called "Extractor", which is the NPC we mentioned earlier. "Super Power" to "extract" Alice's knowledge, but let the other party "not notice."

Note that super power is essential! This is explained in the series (2) Understanding "simulation". If the simulator has the ability to cheat without super power, it is equivalent to proving the agreement "Unsoudness". Similarly, if the "decimator" has the ability to extract information without super power, it is equivalent to proving that the protocol is not-zero-knowledge.

Finally, what is super power?

This depends on the proof of the specific interactive system, and we will start with the Schnorr protocol we just talked about.

Proof of Knowledge : " Proof of Knowledge "

Let's prove the "reliability" of the Schnorr protocol and see how this super-capable NPC extracts the Alice private key in the "ideal world." And this "super power" is still "time back."

Step 1: Alice chooses a random number r, and calculates R=r*G and sends R to the Extractor.

Step 2: The decimator also selects a random challenge number c and sends it to Alice.

Step 3: Alice calculates and responds to z, then the extractor checks if z is correct

Step 4: The decimator finds that z has no problem, launches the super power, and reverts the time back to the second step.

Step 5: The decimator sends a different random challenge number c' to Alice again. At this time, Alice returns to the second step and has a feeling of deja vu, but cannot perceive the fact that time is reversed.

Step 6: Alice calculates z' again and sends it to the extractor to check

Step 7: At this time, the extractor has z and z', and you can directly calculate the private key a owned by Alice to achieve "knowledge extraction".

At this point, "reliability" is basically proved. Do you feel a little bit about the "symmetry" of reliability and zero-knowledge?

To sum up: "Extractor" in the "ideal world", through the time-reversing super power, completely "extract" Alice's "knowledge", which ensures that Alice without knowledge can't make the extractor reach the goal. , thus proving "reliability."

Note: Not all reliability must require the presence of a decimator algorithm. A proof system that uses a decimator to prove reliability is called "Proof of Knowledge."

Interpreting ECDSA signature attacks

The ECDSA signature scheme, which is ubiquitous in the blockchain system, is also a simple zero-knowledge proof system. The elliptic curve digital signature scheme ECDSA is very close to the Schnorr protocol. The signature scheme based on the Schnorr protocol was published in the 1991 Journal of Cryptography [5]. In 1991, when the National Bureau of Standards (NIST) chose the digital signature algorithm, the elegant Schnorr signature scheme was patented. Therefore, NIST proposed another signature scheme, DSA (Digital Signature Algorithm), which subsequently supported the ellipse. The curve is then called ECDSA. In conceiving bitcoin, Satoshi Satoshi chose ECDSA as the signature algorithm, but the curve did not select the elliptic curve recommended by the NIST standard – secp256-r1, but secp256-k1. Because of the rumors of the rivers and lakes, NIST may have made the choice of elliptic curve parameters, which led some institutions to solve the discrete logarithm problem in an unknown way, so that they have the ability to have super power in the "real world." Many people are skeptical. Maybe Zhong Cong had this kind of consideration when designing Bitcoin. He deliberately chose a curve like secp256-k1 which looks like a slightly weaker security.

We disassemble the ECDSA signature and define an ECDSA-like authentication scheme interactively. See the figure below for interaction.

The first step: Alice still chooses a random number k, maps k to the elliptic curve, gets the point K, and sends it to Bob.

Step 2: Bob needs to generate two random numbers, c and e, and then hand it to Alice.

Step 3: Alice calculates s and sends it to Bob, who verifies that the calculation process of s is correct.

Note: For readers familiar with the ECDSA signature scheme, here is a brief explanation. The Bo generated by Bob corresponds to the hash value Hash(m) of the signed message, and e is generated by a conversion function F(K). Where F(.) is taken from the x coordinate of the point on the elliptic curve (mod q) to get [6].

There is a saying on the rivers and lakes: The ECDSA signature scheme has a serious security risk. If the same random number is used in two signatures, the signer's private key will be exposed. In fact, the Schnorr signature scheme has the same problem.

When the engineers of Sony PlayStation 3 called the ECDSA library function, they should have entered the parameter position of the random number, but passed a constant. Hackers familiar with cryptography have discovered this serious back door. In January 2011, the magical kid Geohot publicly released the main private key of the Sony PS3, which means that any user can easily get the root access of the game console. Sony is very angry… (Follow-up story, everyone can search online)

If Alice uses the same K in two interactions, Bob can get s and s' by sending two different c and c's, and then calculate the private key a by the following formula:

k = (c – c')/(s – s')

a = (k * s – c)/e

So how should we look at this "safe back door"? Think about it, this security back door is almost exactly the same as the proof of the Schnorr protocol we have proven before! This algorithm is the "decimator" algorithm in the "reliability" proof of the ECDSA authentication protocol. In the proof of reliability, in order for Alice to use the same random number k for authentication twice, the "decimator" needs to take advantage of the "time backflow" superpower.

However, in the Sony PS3 system, the random number is written to a fixed value by the engineer, which is equivalent to directly giving the hacker "super power", which is in the "real world." In other words, hackers can implement "decimators" without the need for "time backflow."

Reminder, not just the problem that random numbers cannot be repeated. Rather, the random number must be a random number with cryptographic security strength.

Imagine that if the random number r is generated by a pseudo-random number generator that uses the principle of "linear congruence", although the value of r is always changing, it still does not prevent "knowledge extraction." Assuming the linear congruence algorithm is r2=d*r1 + e (mod m), return to the third step of the Schnorr protocol:

1: z1 = r1 + c1*a

2: z2 = r2 + c2*a

If the attacker asks Alice to make two signatures in succession, then after r2 is substituted into r1, two linear equations arise for solving two unknowns (r1, a), z1, z2, c1, c2, d, e for the attack. It is known that this system of equations can be solved using only junior high school mathematics.

Please note that this is not a "design flaw" in the Schnorr protocol (or ECDSA protocol). On the contrary, this is where the Schnorr protocol is designed to be more sophisticated, which in principle guarantees the reliability of the protocol. Similar techniques occur frequently in cryptographic protocols, reaching a "simple" at a glance. However, it must be said that if the internal mechanism of the agreement is not clear, especially if the "ideal world" and the "real world" are not clearly defined, it is easy for users to introduce various "safety loopholes".

As a responsible code farmer who can write safe and reliable software, what do we need to know? It is certainly best to thoroughly understand the design mechanism of the security protocol, but in most cases this is unrealistic. Generally speaking, we use various cryptography tools as "black boxes", but this may not be enough. We better understand:

What is the "security definition"?

What exactly is the "safety assumption"?

What is the "super power" in the "ideal world"?

Brain hole: Do we live in the simulated world?

The first time I read the "simulator", the first thing I thought of was the movie "The Matrix." The "real world" in which we live may be the "ideal world" that a simulator simulates. Everything we see, hear, and perceive is "simulated." In the "real world," we live in a mother. However, we are not aware of this.

As early as the Spring and Autumn Period and the Warring States Period, Zhuangzi was also thinking about similar problems:

In the past, Zhuang Zhou Meng was Hu Die, and Hu Hu also. Self-worthy and ambition! I don't know Zhou. If you feel it, you will feel like Zhou. I do not know the dream of Zhou is Hu Die and? Hu Die's dream is Zhou? Zhou and Hu Die will have a split. This is called materialization.

– "Zhuangzi Qiwu Theory"

Explained in a common way: Zhuangzi fell asleep one day, dreaming that he had become a butterfly, dancing and waking up and found himself still a Zhuangzi. In his dream, the butterfly did not know that he was a Zhuangzi. So Zhuangzi’s contemplation is whether he has become a butterfly in his dream, or has it become a Zhuangzi in the butterfly dream? If the dream is true enough,…

"The Brain in the Cylinder" is an idea put forward by the American philosopher Gilbert Harman: a person's brain can be put into a container, and then plugged into a wire, by simulating various electrical signal inputs, so that the brain thinks that it is living in reality. In the world.

This idea is derived from the philosopher Descartes's "First Philosophical Contemplation" [7], in which he argues that we should doubt everything and examine all human knowledge, mathematics, geometry, and the world of perception. However, he found that all but the "I think so I am", all the knowledge may not be reliable, because our brain is likely to be deceived by a "super power" Evil Demon.

Nick Bostrom, a professor of philosophy at Oxford University in 2003, wrote a paper "Do we live in the computer simulation world?" "[8]. I believe that at least one of the following three facts is true:

Human civilization is completely extinct.

Human civilization has reached the level of technology that can fully simulate the real world, but for some reason, no one is willing to create a new simulated world that acts as a god.

Our current human civilization lives in a simulated world.

In a public interview, Silicon Valley entrepreneur Elon Musk said that the probability of "we live in the basic real world" is only "one billionth." In other words, he thinks we live in a computer game (the world of simulation). Outside the analog world, there is a programmer who develops and manipulates the world. Each of us is a game character (NPC).

After playing the jailbreak iPhone and autopilot, the magical kid Geohot gave a speech entitled "Jailbreaking the Simulation" at the "South-South-South" conference in March this year [9]. He believes that we are living in a simulated world. The so-called God is the alive farmers in the outside world. They have programmed to create our "real world". Of course, they may have started more than one copy of the world. However, they may also live in an outer "simulation world."

If we do live in the analog world, perhaps we can find a back door – "Simulation Trapdoor" somewhere on the planet, to get the "simulator" super power, extracting incredible "secret knowledge."

If our world is indeed simulated by the program, this program may have bugs. If there are bugs, maybe we can use this bug to escape from prison, jump out of the "ideal world", reach the world outside, and be cute. The code farmer God talked.

Is this a joke? The following is taken from a section of self-knowledge [10]:

If the world is virtual, what examples can be proved?

1. Why is it macroscopically rich, but the microscopic basic particles are exactly the same? This is just as colorful as the picture, but the pixels are exactly the same thing.

2. Why is there an upper limit to the speed of light? Because the machine is running at a limited speed

3. Why is there a Planck constant? Because the machine's data accuracy is limited

4. Why are microscopic particles a chance cloud? This is to increase the random disturbance caused by the system falling into the loop.

5. Why is there a Pauli incompatibility principle? It seems that the data organization used by the system is a multidimensional array.

6. Why do quantum computers run so fast and try all the possibilities in a flash? Because this is essentially the interface that calls the host.

7. Why is there quantum entanglement? This is actually two pointers that reference the same object.

8. Why is there an observer effect? This is obviously lazy updating

9. Why does time start? The system has a startup time

To be continued

Designing a cryptographic protocol is like walking a tightrope. If you want to achieve "zero knowledge" and "reliability" at the same time, it means that the content of the agreement is sufficiently random, and that "knowledge" can participate in the interaction of the agreement. If the agreement is not designed correctly, or if it is not implemented correctly, it will lead to system security collapse. For example, it may destroy zero-knowledge, causing "knowledge" to leak inadvertently; or perhaps destroying reliability, causing anyone to falsify proof. And this security is far more serious than the traditional code underlying mechanism vulnerabilities, and more difficult to find. Strict mathematical arguments seem to be indispensable.

Is our world really simulated by a "three-body civilization"? This possibility cannot be ruled out. Perhaps we need to seriously re-examine our various obsessions. But what about that? At least my own "thought" is real.

If you would be a real seeker after truth, it is necessary that at least once in your life you doubt, as far as possible, all things.

If you are a true truth seeker, at least once in your life, question everything as much as possible.

—— Descartes

Acknowledgements: Special thanks to Shengchao Ding, Jie Zhang, Yu Chen, and the consultants of Ambi Labs (p0n1, even, aphasiayc, Vawheter, yghu, mr) for their suggestions and corrections.

references

[1] zkPoD: Blockchain, zero-knowledge proof and formal verification, achieving fair trade without intermediation, zero trust. Ambi Lab. 2019.

[2] Hoffstein, Jeffrey, Jill Pipher, Joseph H. Silverman, and Joseph H. Silverman. An introduction to mathematical cryptography. Vol. 1. New York: springer, 2008.

[3] Schwartz–Zippel Lemma. Wikipedia. https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

[4] Damgård, Ivan. "On Σ-protocols." Lecture Notes, University of Aarhus, Department for Computer Science (2002).

[5] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.

[6] Brown, Daniel RL. "Generic groups, collision resistance, and ECDSA." Designs, Codes and Cryptography 35.1 (2005): 119-152.

[7] Descartes, Xu Tao. The first philosophical contemplative set. Kyushu Publishing House; 2008.

[8] Bostrom, Nick. "Are we living in a computer simulation?." The Philosophical Quarterly 53.211 (2003): 243-255.

[9] Nick Statt. "Comma.ai founder George Hotz wants to free humanity from the AI ​​simulation". Mar 9, 2019. https://www.theverge.com/2019/3/9/18258030/george-hotz- Ai-simulation-jailbreaking-reality-sxsw-2019

[10] doing@知乎. "If the world is virtual, what examples can be proved?". 2017. https://www.zhihu.com/question/34642204/answer/156671701

We will continue to update Blocking; if you have any questions or suggestions, please contact us!