Introducing zero-knowledge proof in a way that programmers can understand

I originally wanted to write "Explaining Zero-Knowledge Proof in Human Language", but I found that I couldn't do it, because I still can't explain the principle of blockchain in human language. Zero-knowledge proof is more abstract than the principle of blockchain. More than 90% of the information on the Internet is about the derivation of this algorithm, but for more than 90% of programmers, we don't care about the principle of hash algorithm, we only care about how to use hash algorithm. (As a 10+ year old programmer, I don't understand the principle of hash, but I am not ashamed, as long as I can use it)

First, here is a very basic function structure:

If this function is a hash algorithm, then, by inputting any file, you can get the corresponding hash value. Suppose there is such a situation, we all know a hash value, and want to know which file it is. This file is in your hand, and you excitedly say that the file has been found. Everyone says, "Okay, you take out the file, and we calculate the hash to see if it matches." At this time, you are worried, this is a confidential file, how can you provide it just like that? What should you do?

This is where zero-knowledge proof comes in. The algorithm structure is as follows:

The orange part is zk-proof, which is divided into two parts: proof and verification. The proof part is also called 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 public, and the output is hash value and proof. This proof proves:

There is an unknown input, which is calculated by the circuit to generate an output.

There is an unknown input, which is calculated by the circuit to generate an output.

There is an unknown input, which is calculated by the circuit to generate an output.

Important things should be said three times! And I will also draw it:

This proof is like a stamp of approval for this process. It is set in stone and there is no dispute. Don’t ask what the input is. We don’t know it, so it is called zero knowledge. What is known is 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 input is the confidential file that everyone is looking for, and you do not need to provide this file, you only need to provide a proof.

When verifying, we put the hash value and proof into the verify function and return true, which proves that:

You use a certain file and generate this hash value through the circuit hash algorithm.

Which other file could it be? It must be the correct file, otherwise how would this hash be generated!

Mixing coins

Zk-proof is obviously very useful in privacy scenarios. The principle of coin mixing is that users deposit coins into a safe, and the hash value of the safe password is posted on the safe. Whoever can provide this password can take all the coins in the safe. The principle is the same as the above file search. Users do not need to provide a password, but only need to provide proof. Once the contract verification is passed, you can withdraw the coins.

There is another problem. If you can open a safe, it means that you are the one who put the money in it. Who put how much money in which safe can be checked on the chain, so you cannot say which safe you opened. In the contract, a tree structure is used to store safes, 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 contract is finally verified, it is proved that the location of the safe and the password of the safe are all correct, but no one knows what the password is or which safe it is. The user may not know either, but the user just needs to keep the proof safe. Anyone with this proof can withdraw money.

Scaling

In addition to its application in privacy scenarios, zk-proof has also been found to be useful for blockchain expansion in the past two years. Each tx in a block has a user's signature to prove that the (transfer) operation is not forged. The size of a block is limited (fixed), so the more txs that can be stuffed into a block, the higher the TPS.

If the signature is removed to slim down the tx, more tx can be inserted. The problem is, if the signature is removed, how can we prove that the operation was signed by the user? Use zero-knowledge proof to write the verification logic of the user's signature into the circuit. The input is the block data (including the signature), and the output is the block data (excluding the signature), and a proof is attached. This proof can prove that all txs are signed by the user, achieving the purpose of slimming down.
Source: https://bress.xyz/zh/post/nKtuByYTvPri75xHQoA7f8vNyJ6NQPvCL_YH8KVp31Q