An article to understand the zero-knowledge proof behind ZCash

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 goal of a prover is to prove that they possess some 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 convince the verifier to believe or Proving to a verifier the truth of a statement or assertion.

Zero-knowledge proof was originally proposed by MIT professors; Shafi Goldwasser, Silvio Micali; and cryptography masters; Charles Rockoff; three authors 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: conciseness 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 Cryptography: Blockchain technologies like; Zcash; use zero-knowledge proofs to protect transaction privacy. A person can prove that they have enough ;Cypto; currency to conduct a transaction without revealing the exact amount of their funds. This ensures privacy while ensuring transaction integrity.

Identity verification and authentication: Zero-knowledge proofs can also be used to confirm identities without revealing unnecessary information. For example, a person could prove they are over the age of 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 proofs can be used to prove that certain data meets certain 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 2;ZKSync; and;Polygon;'s;zkEVM;etc. However, this is only a subset of blockchains created by zero-knowledge proofs.

How to represent a proof

In this section, and the rest of the paper, we will focus on proofs built on top of the ;PLONK; proof system.

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".

In essence, PLONK; is a general-purpose, updatable cryptographic proof system, an innovation that allows efficient verification and scaling in blockchain systems and other distributed networks.

PLONK; the idea behind 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 the proof) 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 calculation, we collectively refer to it as "gate"), which makes calculation 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 a 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 expressed as a length; 3; vector, if the addition gate is selected, then; c; is equal to; a+b. Using these gates, let's denote 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. Calculate with multiplication gate; c*d
3. Calculate with addition gate; ab+cd 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.

🎛; proof 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 replication constraints are fulfilled. For copy constraints, this is done by permutation checking.

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

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

We say that a vector ;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 σ (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 the vector with respect to the permutation σ.

Rewrite the vector as a polynomial vector: a''=((a+;1;X),(b+;2;X),...,(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;, thus showing $(a+;1;X+γ)(b+;2;X+γ).. ..(c+nX+γ) = (a'+σ(;1)X)+γ)(b'+σ(;2)X+γ)....(c'+σ(n)X +γ)$ .

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

write at the end

While zero-knowledge proofs are a complex topic, their adoption is on the rise. In this article we have given an intuitive explanation of how zero-knowledge proofs work. In the future, the CertiK; team will ;j; dive into the application of zero-knowledge proofs and how the team can optimize their circuits for new use cases.