Read the simple logic behind the zero-knowledge proof

Text: Li Hua (Special Research Fellow, Coin Research Institute)

Source: BixinInstitute

The author would like to thank Guo Yu, Wu Weilong and Elder Ryan for their valuable opinions. Of course, they are responsible for their own responsibility.

This article is about 5,000 words, and it takes about 15 minutes to read the full text.

• Wuzhen Review | Cross-chain ecological stability coin "MOV" released
• Interpretation: Do you really understand decentralized collaboration?
• The bitcoin demand curve has been “significantly rising”: 2.2 times a year

The engineering realization of zero-knowledge proof is a very challenging job, but this does not mean that understanding zero-knowledge proof is equally difficult, and the logic behind it is simple.

Why do you need to understand it? Privacy issues need not be mentioned. Another important reason is that with the deep exploration of blockchain, we find that the implementation of trust through cryptography is an effective complement to the trust of consensus algorithms. These two trusts can be less frictional. The ground is combined and therefore easier to implement and apply. This trend can also be seen from the recent development of blockchain technology.

And only when we know the logic behind these cryptography methods, we won't lose it, we can understand why it is designed in this way, and what kind of application scenario it applies to.

So now, let's start the journey of zero knowledge proof. It consists of three journeys:

• Hide secret journeys;
• Prove a secret journey;
• Build a journey of universal zero-knowledge proof.

In the universe of Star Trek, P = NP.

◆ 1. Hide secret: one-way function ◆

In the universe of Star Trek, P = NP, which may be a good thing for the computational world, it means that all problems that can be verified in polynomial time can also be solved in polynomial time. But for the cryptography community, this could be a disaster.

Cryptography requires a "one-way function", which means that B can be calculated from A, but there is computational infeasibility in calculating A from B – the calculation is from A to B is one-way, we only It is possible to hide A. And if P = NP, the problem that can be verified in polynomial time is also solvable, then A can be calculated by B, and the secret cannot be hidden.

This is the simple logic behind cryptography: one-way functionality. The support behind the one-way function is P! = NP.

What is the relationship between this and zero-knowledge proof? We can decompose the zero-knowledge proof into two functions. The first function is to hide the secret, and the second function is to prove that there is a secret. And hiding the secret, as described above, is to find a calculation with a one-way function.

Zero knowledge proof:

Zero-knowledge proof means that the verifier is convinced that an assertion is true, and that the entire process does not reveal any knowledge other than "assertion is true." To make it easier to understand, this article simplifies it as hiding secrets and proving secrets.

The elliptic curve algorithm (ECC) is a one-way function commonly used in cryptography. It looks like this: k × P = Q. In the case of known P, we can calculate Q by k. , but it is difficult to calculate k by Q. It should be noted that the meaning of addition or multiplication in cryptography is not limited to the meaning of addition or multiplication on the real domain we are familiar with.

Let us see how it is unidirectional. In this function, P is a point on the elliptic curve. We put a small ball at the point and hit it in the tangential direction. The ball hits the elliptical curve and hits k times (this can be understood as such ), and finally will fall on a point Q. If we know the initial position P and the number of impacts k, we can calculate the falling point Q of the ball; but if we only see the ball falling on Q, it is impossible to calculate how many times it hits from point P to point Q, that is, k's.

The following figure is an example of k = 2. The ball starts from point P and hits twice on the point Q, so Q is equal to 2 × P. The elliptic curve algorithm is often used to generate the public and private keys. The public key is the last drop point Q of the ball, and the private key is the number k of impacts. The one-way function of k × P = Q makes it possible to hide the secret of the private key.

Elliptic curve

◆ 2. Prove the secret: the same state ◆

For zero-knowledge proofs, hiding secrets is only the first step, and we still need to prove that we really have the secret. Just as in the first journey, we only need to understand the one-way function. In this second journey, we only need to understand the "homomorphism". With the same state, we have the ability to prove the secret. So what is homomorphism?

We can think of the one-way function as a mapping relationship. For example, k × P = Q is the mapping of k to Q: in a space, we have an infinite number of k points, which are mapped to another space and become countless Qs. point. This is like the real world and the shadow world. Through the mapping of light, the objects in real space become the shadow of the shadow space.

At this time, it is assumed that there is a mechanical watch, and the movement is the hidden secret. We split the watch with the movement into 8 parts and map it into the shadow space. At this time, the shadow space will have 8 shadows; but pay attention to the real space, we show you a complete watch, the movement It is unexposed. This watch will also have a shadow in the shadow space. We call it the 9th shadow.

Now we combine the shadows of the eight components. If they can form a complete watch shadow, we can use this shadow to compare with the 9th shadow. If the two are the same, we can prove this piece of real space. The watch is made of an organic core because its shadow is the same as that of the parts containing the movement. This actually completes a simple zero-knowledge proof process.

The shadow of the complete component is the same as the shadow of the complete watch. We call this mapping the same state. Expressed by mathematical formula is f (watch) = f (part 1 + … + part 8) = f (part 1) + … + f (part 8). Among them, f (watch) is the shadow of the watch, f (part 1) + … + f (part 8) is the shadow of the watch combined with the shadow of the component.

To simplify this relationship is: f(a+b) = f(a) + f(b), which is the result of "calculated first and then encrypted" f(a+b) and "the result of the first encryption" f( a) + f(b) is the same. The homomorphism allows us to directly calculate the ciphertext, and then encrypt and encrypt the plaintext that hides the secret, and then verify whether the plaintext contains the secret by comparing whether the two are the same.

Homomorphic definition:

In abstract algebra, a homomorphism is a mapping that maintains a structure between two algebraic structures (such as groups, rings, or vector spaces).

If you only want to understand the basic logic of zero-knowledge proof, the journey can be ended here. There are only two knowledge points: 1. Hide the secret with one-way function; 2. Use the homomorphic map to prove the secret. Is it still easy?

Let's take a look at what this process looks like in real cryptography. Take the Elliptic Curve Digital Signature Algorithm (ECDSA) as an example. It is an algorithm with a zero-knot attribute. You can choose not to look at it, it will not affect your understanding of the same state.

Verification of the signature by the elliptic curve digital signature algorithm:

In this algorithm, the key process is to verify that f(Z + dA × R) = f(Z) + f(dA × R) = f(Z) + Qa × R, where Z is required to be signed with a private key. Message, dA is the private key, R is associated with the random number, and Qa is the public key. Because the homomorphic property, this equation is true, we can use the Qa (public key) on the right side of the equation to verify that Z is signed with the dA (private key) to the left of the equation.

Here, dA is the movement, Z+dA×R is the watch with the organic core, f(Z + dA × R) is the shadow of this watch, and f(Z) + f(dA × R) is the watch The shadow of the parts is combined into a watch shadow.

The homomorphic properties of the elliptic curve algorithm allow other algorithms, such as elliptic curve digital signature algorithms, to be used to hide and prove secrets, but the algorithm has limited capabilities because it only has additive homomorphism, which is f(a+b). = f(a) + f(b), but without multiplicative homomorphism, ie f(a × b) = f(a) × f(b).

This is equivalent to projecting objects in real space into shadow space. Shadow space can combine shadows with addition, but for some shadows that need to be combined by multiplication, it can't do anything about it.

How to do? A "pairing function" can be introduced. For example, the elliptic curve pairing function is a series of adjustments to the elliptic curve algorithm to generate a new mapping space. This new space satisfies both the additive homomorphism and the class multiplication homomorphism (note that it is just a class multiplication homomorphism). Come, in addition to addition, we can also use class multiplication to prove the secret.

Now, the second journey has arrived at the end. What we need to understand is that homomorphism is the key to prove the secret, but not all mappings have a "good" homomorphism, and different application scenarios have different requirements for homomorphism. In actual design. Different homomorphisms need to be implemented according to specific needs.

If the original space and the mapping space satisfy both the additive homomorphism and the multiplicative homomorphism, we call it a homomorphism. Full homomorphism means that you can perform arbitrary operations on ciphertext (you can combine shadows in any way), which is important for data privacy, but achieving full homomorphism is very difficult.

◆ 3. General Zero Knowledge Proof: NPC Problem ◆

You must have noticed that we say that the elliptic curve digital signature algorithm has a "zero-knowledge attribute", but it does not say that it is a zero-knowledge proof protocol, because its main business is to do digital signatures, hiding the private key is just that it must be implemented. a feature. And it can only hide the private key, if you want it to help you hide your own secret, it can't do it.

And zero-knowledge proof protocols, such as the familiar zk-SNARKs, whose main business is to hide and prove the secrets that need to be hidden. How is this done?

Let's go back to the one-way function k × P = Q at the beginning of this article. It can hide a secret k. If we complicate it, for example, it becomes t × h = (v0 + a1 × v1 + …… + Am × vm)(w0 + b1 × w1 + …… + bm × wm) Such a polynomial, is there a lot of "space" that can hide the secret, such as placing the secret in a1, a2, …, am .

In fact, the complex polynomial above is the polynomial used in zk-SNARKs to achieve zero-knowledge proof, which can prove various types of secrets because it can prove Boolean circuits.

Why can you prove the various types of secrets by proving Boolean circuits? Because Boolean circuit satisfiability is an NPC (NP-Complete) problem, and NPC problem has a "characteristic", that is, all NP problems (including NPC) can be reduced (converted) into a specific one in polynomial time. NPC problem.

For example, Boolean circuits, graph theory, and other minesweeping games that we are familiar with are all NPC problems. We can make the mine-sweeping game stipulated into the sufficiency of the Boolean circuit, that is, it can realize the zero-knowledge proof of the mine-sweeping game with the polynomial that proves the Boolean circuit; the graph theory can be simplified into the sufficiency of the Boolean circuit, that is, A zero-knowledge proof of tristimulation with a polynomial that proves a Boolean circuit…

So in theory, we can build a generic zero-knowledge proof protocol based on any NPC problem. But this is only theoretical, because the difficulty of using them for proof is quite different. The current mainstream method is to choose Boolean circuits or arithmetic circuits because they are relatively easy to implement and have small circuit scales. zk-SNARKs and Bulletproofs are the choices.

Minesweeper game

◆ 4. Zero Knowledge Certification Agreement ◆

After three trips, the zero-knowledge proof may no longer be mysterious for us. It has simple logic behind it: 1. One-way function is a method of hiding secrets; 2. Homomorphic mapping is the basis for proof of secrets. ; 3. A polynomial that proves the NPC problem (but this is not the only way) can implement a universal zero-knowledge proof.

The implementation of different zero-knowledge proof protocols in these three points is different. The most important difference may be reflected in the third point. Even if it proves that the same NPC problem, there can be a completely different method. Because of the different designs, the most frequently mentioned differences in zero-knowledge certification protocols include:

1. Different calculation space and calculation time. Smaller space and shorter time are the main driving force for our continuous improvement of the zero-knowledge proof protocol, and also the main indicator for comparing different zero-knowledge proof protocols.

For example, the following figure is the table used by ZCash CEO Zooko Wilcox when it comes to the zero-knowledge proof protocol. The main comparison is the proof time, verification time and proof size of different protocols.

Source: https://slideslive.com/38911617/privacy-for-everyone

2. Whether you need to initialize trusted settings. It's certainly better to not need trusted settings, which will reduce trust and security issues, but new proof methods can lead to new computing problems, such as Bulletproofs do not require trusted settings, but its cost of verification in high complexity situations It will be very high.

3. The security assumptions on which it depends. Security assumptions are closely related to security. For example, Bulletproofs relies on a standard security assumption: discrete logarithm problem, plus a random prediction model; and zk-SNARKs relies on an unverifiable security hypothesis problem: the exponential knowledge hypothesis.

These indicators and attributes are difficult to satisfy at the same time. Therefore, when designing a zero-knowledge proof protocol or selecting a zero-knowledge proof protocol/method as a functional component of a protocol, it is necessary to consider the requirements of a specific scenario. For example, if there is a high requirement for the proof time, it may be necessary to choose a method that takes up more space or has less versatility; if there is a requirement for a trusted setting, it may be necessary to select a method with a higher proof cost.

Therefore, on the one hand, zero-knowledge proof is constantly evolving, various protocols are being designed, and some new protocols will have advantages in some aspects; on the other hand, different protocols have different application scenarios, Designing or choosing according to your needs, there is no better agreement for all scenarios.

If you want, the journey will end here; if you want to continue, the next paragraph is a bit wild.

◆ 5. Another way ◆

This is about zk-STARKs. It is also a zero-knowledge proof protocol, but it is a zero-knowledge proof based on information coding, which is a completely different path and may disrupt your already clear thinking.

zk-STARKs does not use a one-way function in cryptography. If you understand it simply, it does this: suppose P has 9 numbers to prove, a1, a2, …, a9, then encode them into b1, B2, …, b9, each bi contains partial information of a1, a2, …, a9. At the time of verification, the verifier V performs a sampling check on b1, b2, …, b9, and can analyze whether there is an error in the code from a small amount of bi, so that a1, a2, …, a9 can be detected with a high probability. Is it true?

When V randomly samples P, P can actively confuse the sampled bi with random numbers, and at the same time enable V to complete the verification, thus achieving zero knowledge.

Therefore, the "one-way" of zk-STARKs is not based on the one-way calculation that is not feasible. It is because all the b1, b2, …, b9 are not exposed, which makes it impossible to calculate a1 by b1, b2, …, b9. , a2, …, a9. In the "homomorphism" part, it is not a homomorphic concept in abstract algebra (or cryptography), but is based on linear coding error correction theory for sampling verification.

zk-STARKs is also not validated based on the NPC puzzle described above, which is based on probabilistic checks. For this type of verification method, you can find clues from an ancient Probabilistically Checkable Proofs (PCP), but the method used in zk-STARKs is called IOP (Interactive Oracle Proofs). The difference with PCP is that it uses Is Oracle.

The reason why zk-STARKs is introduced is because it is also quite popular. On the other hand, it is to explain that zero-knowledge proof may be a thing that is difficult to explore the boundary. For example, zk-STARKs is very different, so this article only understands zero knowledge. An angle of proof, and because of its limited cognition, this angle may not apply to all zero-knowledge proof methods.

I hope this article will give you a better understanding of zero-knowledge proof, and hope that you can think that cryptography and mathematics are interesting because of its complexity and because of the simple logic behind the complexity.

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