Introduce zero-knowledge proofs in a way that programmers can understand

I originally wanted to write “Explaining Zero-Knowledge Proofs in Human Words”, but I found that I couldn’t do it, because so far I haven’t been able to explain the principles of blockchain in human words. Zero-knowledge proofs are more abstract than the principles of blockchain. More than 90% of the information on the Internet is Regarding the derivation of this algorithm, but for more than 90% of programmers, we don’t care about the principle of the hash algorithm, we only care about how the hash algorithm is used. (As a 10+ year old code farmer, I don’t understand the principle of hashing, but I’m not ashamed, I can use it)

First, this is a very basic function structure:

Introduce zero-knowledge proofs in a way that programmers can understand

If this function is a hash algorithm, then, input any file, you can get the corresponding hash value. Suppose there is such a situation, we all know a certain hash value, and we want to know which file it is. This file is in your hands. You are very excited to say that the file has been found. Everyone said okay, take the file. Come out, let’s calculate the hash and see if we can match. At this time, you are worried. This is a confidential document. How can you provide it when you say it is provided, what should you do?

This invites zero-knowledge proof, the algorithm structure is as follows:

Introduce zero-knowledge proofs in a way that programmers can understand

The orange part is zk-proof, which is divided into two parts: proof and verification. The proof part is also called circuit circuit, which needs to be programmed in circuit description language (Rust\C++\Circom), and finally compiled into circuit logic (.wsam\.r1cs). In this example, we use circuit to write a hash algorithm to replace the original function. The characteristic of circuit is that the input does not need to be disclosed, and the output is the hash value and proof. This proof proves:

There is an unknown input, after the circuit operation, the output is generated

There is an unknown input, after the circuit operation, the output is generated

There is an unknown input, after the circuit operation, the output is generated

Important things said three times! And I also want to draw:

Introduce zero-knowledge proofs in a way that programmers can understand

This proof is equivalent to the certification and stamping of this process. It is so settled and there is no dispute. Don’t ask what the input is. If you ask, you just don’t know, so it is called zero knowledge. What is known, the circuit logic (this part should be open source), the output value, and the proof document.

In this example, the circuit logic is equivalent to a hash function. If the hash value you calculated is the same as the public hash value, it means that the file you entered is the confidential file that everyone is looking for, and you do not need to To provide this document, you only need to provide proof documents.

When verifying, everyone puts the hash value and proof into the verify function and returns true, which proves:

You use a certain file to generate this hash value through the hash algorithm of the circuit

Which file could that be, it must be the correct file, or how about generating this hash!

mixed currency

zk-proofs are obviously useful in privacy scenarios. The principle of currency mixing is that the user deposits the coins in the safe, and the hash value of the password of the safe is posted on the safe. Anyone who can provide the password can take all the coins in the safe. The principle of finding files is the same as above. The user does not need to provide a password, just provide proof, and the contract verification will allow you to withdraw coins.

There is another question. If you can open a certain safe, it means that you are the person who put the money in. Who put the money into which safe, which can be checked on the chain, so which safe you open, you cannot Say. In the contract, a tree structure is used to store the safe, and the number of layers is fixed, usually 16 layers. From the safe you want to open to the root of the tree, the 15 nodes in the middle are determined, which determines which safe you want to open, so these 15 nodes (paths) are also in the private input of the circuit.

When the final contract is verified, it is proved that the location of the safe and the safe password are all correct, but I do not know what the password is or which safe it is. Maybe the user does not know either, but the user can keep the proof well, and whoever takes this proof can Can go to withdraw.

Expansion

In addition to the application of privacy scenarios, zk-proof has also found that it can be used for blockchain expansion in the past two years. Each tx in the block has the user’s signature, which is used to prove that this (transfer) operation is not forged. The size of a block is limited (fixed), so if the tx that can be inserted into the block is The more, the higher the TPS.

If the signature is cut off and the tx is slimmed down, more tx can be stuffed in. The question is, if the signature is cut off, how can you prove that the operation was signed by the user? Using zero-knowledge proof, write the verification logic of the user’s signature into the circuit circuit, the input is the block data (including the signature), the output is the block data (without the signature), and attach the proof, a proof can be Prove that all tx are signed by the user to achieve the purpose of slimming.

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/introduce-zero-knowledge-proofs-in-a-way-that-programmers-can-understand/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2022-04-30 09:32
Next 2022-04-30 09:34

Related articles