Introduction to the basics of zero-knowledge proof and its application in the blockchain field

In the complex field of cryptography, zero-knowledge proofs offer a unique solution to a seemingly contradictory task: proving knowledge of a piece of information without revealing the information itself. This encryption method involves two parties: a prover and a verifier. The purpose of the prover is to prove that they possess a certain piece of information (let's call it x) without revealing any data about x itself. What the verifier learns from the exchange is the simple fact that the prover has this knowledge. Most importantly, the verifier has no additional information about x.

For example, when Xiaoling and Xiaoshi are playing escape room, Xiaoling tells Xiaoling that he has cracked the password of a certain "treasure box". But Xiao Ling is unwilling to share the ready-made "answer" directly, and he is unwilling to open the treasure chest in front of Xiao Ten. So how to prove to Xiao Shi that he really solved the puzzle and knows the password of the treasure chest?

So he asked Xiao Ten to write a string of strings that only he knew on a piece of paper, sign his name at the same time, and stuffed the paper through the gap in the treasure chest.

Then Xiao Ling opened the treasure box and took out the paper that Xiao Ten put in, and showed it to Xiao Ten. Xiao Ten checked the string and signature were correct. This proves that Xiao Ling does know the password of the treasure box, and this piece of paper is indeed taken out of the treasure box.

The decryption process was not known to Xiao Ten, and at the same time, Xiao Ling proved that he had cracked the password of the treasure box.

Zero-Knowledge Proof

In cryptography, Zero Knowledge Proof (Zero Knowledge Proof, also known as ZKP) or zero-knowledge protocol is a method that allows the prover to verify without revealing the information itself or any other information. The verifier believes or proves to the verifier the truth of a certain statement or assertion.

Zero-knowledge proof was first proposed by MIT professors Shafi Goldwasser, Silvio Micali and cryptography master Charles Rockoff in the paper "The Knowledge Complexity of Interactive Proofs". This algorithm concept laid a certain foundation for modern cryptography.

Zero-knowledge proofs have two additional properties: succinctness and zero-knowledge**. Conciseness allows a verifier to accept the correctness of a large computation without computing the statement or representation itself. And zero-knowledge guarantees that no data about the input is leaked.

Zero-knowledge proofs are critical to ensuring the privacy and security of many cryptographic protocols. They are a safeguard against potential information leaks, the invisible body armor of the Crypto world. The application of this knowledge can be extended to different fields, including blockchain technology and secure authentication systems, where the protection of sensitive data is of paramount importance.

Wide range of applications

**Blockchain and encryption technology:**Blockchain technology like Zcash uses zero-knowledge proofs to protect transaction privacy. A person can prove that they have enough Cypto currency to make a transaction without disclosing the exact amount of their funds. This ensures privacy while ensuring transaction integrity.

Authentication and **Authentication: **Zero-knowledge proof can also be used to confirm identity without disclosing unnecessary information. For example, a person could prove they are over 18 without providing their exact date of birth, or prove their identity without sharing sensitive data such as passwords. This minimizes the risk of identity theft or unauthorized access.

Secure Multi-Party Computation (SMPC): Zero-knowledge proofs can facilitate complex interactions between multiple parties, where each party can prove that they follow an agreed-upon protocol without revealing the specifics of their input. This is very effective in many aspects such as privacy-preserving data mining, secure voting systems, and so on. Network Security: Zero-knowledge proofs can provide improved security protocols such as secure password policies. It can verify that the password proposed by the user meets certain security standards without letting the server know or record the actual password. Because passwords are not stored anywhere, potential breaches are prevented. **Sharing data while protecting privacy:**Zero-knowledge proof can be used to prove that certain data meets specific requirements without revealing the data itself, which is especially important in fields such as medical care or finance. Data privacy regulations in these fields are strict, but sharing information in a safe and privacy-preserving way may bring huge benefits, such as promoting the development of medical careers and so on. Zero-knowledge proofs have unlocked new technical possibilities in the blockchain. This can be seen in various Layer 2s like ZKSync and Polygon's zkEVM. However, this is only a subset of blockchains created by zero-knowledge proofs.

How to express a proof

In this section, and the remainder of the article, we will focus on proofs built for PLONK-based proof systems.

PLONK is a zero-knowledge proof system, its full name is

"Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge", that is, "Global non-interactive knowledge proof arrangement based on Lagrange bases".

Essentially, **PLONK is a general-purpose, updatable cryptographic proof system, an innovation that allows efficient verification and scaling in blockchain systems and other distributed networks. ** The idea behind PLONK is to build a general and updatable proof system. In the context of zero-knowledge proof systems, "universal" means that it can be used for any type of computation; "updatable" means that the cryptographic reference string (a piece of data used to generate and verify proofs) update securely over time.

PLONK stands out for its efficiency and simplicity, making it a popular choice for projects and companies that require a secure, private transaction system. Compared with other systems, it uses fewer constraints per gate (the basic unit of computing, we collectively refer to as "gates"), which makes computing faster and more scalable. Vitalik Buterin has published a more comprehensive description of PLONK. [Copy the link to the browser to view the original text prove

Before proving a statement, we first represent the statement in terms of a circuit. A circuit encodes the value in the calculation along with two other types of data:

1. Operations: such as multiplication and addition calculations on input data
2. The order in which operations are performed

To encode this data, PLONKish circuits are represented as a set of vectors and constraints. Constraints are the relationships that the units in the vector must obey. The types of constraints are: gate constraints and copy constraints, which respectively represent the operations and the order of operations in the circuit.

There are many ways to express a circuit using different gate and circuit architectures.

Represent the statement as a circuit

Suppose we have two gates: a multiplication gate and an addition gate. The multiplication gate is represented as a vector |a|b|c| of length 3. If this gate is selected, then it will constrain c to be equal to a*b. Similarly, the addition gate is represented as a vector of length 3, and if the addition gate is chosen, c is equal to a+b. Using these gates, let's represent the dot product between two vectors (a,b) and (c,d). To do this, we need to perform the following calculations:

1. Use the multiplication gate to calculate a*b
2. Use the multiplication gate to calculate c*d
3. Calculate ab+cd with addition gate This can be represented by a vector.

Note that the output of the first and second multiply gates is the input value of the add gate. This data is encoded separately from the gate constraints in our circuit. This is called a copy constraint. So, why are circuit constraints important? If there were no constraints, then a malicious validator could put any value they liked into the circuit. For example, the verifier can replace ab+cd with aba*b. Similar to smart contracts, constraints must be verified through a proof system before they can be used. Certificate statement

Now that we can represent statements in terms of circuits, how does the prover convince the verifier that the proof is valid? For a PLONK system, the prover must convince the verifier that the gate constraints and copy constraints are fulfilled. For copy constraints, this is done by permutation checking.

Substitution checking was first proposed by Bayer-Groth and then further developed in the PLONK paper by Gabizon, Williamson and Ciobotaru. In order to prove the constraint of the gate, a certain quotient polynomial (polynomial of the quotient) needs to be calculated.

Intuitively, permutation checks show that if the entries of the copy constraints are permuted, the circuit remains the same. Replacement check

We say that a vector a is related to a vector b by a permutation σ if, for all i-th positions of b, there exists a σ(i) position equal to a. We denote this as σ(a)=b. Given two vectors a=(a,b,...,c), b=(a',b',...,c')$, and a permutation σ, we want to determine that σ(a)=b . This can be done as follows:

Represent vectors as a'=((a,1),(b,2),...,(c,n)) and b'=((a',σ(1),(b',σ( 2)),...,(c',σ(n)) ). This encodes a vector with respect to the permutation σ.

Rewrite the vector as a polynomial vector: a''=((a+1X),(b+2X),...,(c+nX)) and b''=((a'+σ(1)X ), (b'+σ(2)X),..., (c'+σ(n)X))

Checking whether a'' and b'' are equivalent as multisets can be done by randomly choosing gamma such that $(a+1X+γ)(b+2X+γ)....(c+nX+γ ) = (a'+σ(1)X)+γ)(b'+σ(2)X+γ)....(c'+σ(n)X+γ)$.

By choosing a β at random, we can check whether these polynomials are equivalent via the Schwartz-Zippel lemma. The sets a'' and b'' are equivalent as multisets if they are equivalent as polynomials. If they are not equivalent polynomials, then a'' and b'' are not equivalent multisets.