---
theme: cyanosis
---

Zero-knowledge proofs, as a cryptographic tool/concept, play a significant role in encryption, blockchain, privacy protection, trusted computing, federated learning, and many other crucial areas. However, the idea and the specific protocols are relatively intricate, posing a significant challenge for ordinary developers and enthusiasts. Existing introductions to zero-knowledge proofs are either too simplistic, with some examples even flawed and not satisfying zero-knowledge properties, or too professional, demanding a high level of background knowledge from the reader.

**Therefore, this series aims to start with basic mathematical tools and, through rigorous reasoning, help readers understand the mechanism of zero-knowledge proofs. It also guides them to deduce, prove, and construct zero-knowledge proofs on their own. This series strives to use the simplest possible mathematical tools. Most of the reasoning is based on high school mathematics, with some parts touching on college algebra and discrete mathematics. These sections will be highlighted and explained. If readers still find it challenging, they can accept the conclusions and revisit the proof details later.**

This series references works by experts and scholars such as Shafi Goldwasser, Silvio Micali, Charles Rackoff's "The Knowledge Complexity of Interactive Proof Systems," and Maksym Petkus's "Why and How zk-SNARK Works: Definitive Explanation." After reading this series, it's recommended that readers delve into the original texts of these classic papers for deeper insights.

The birth of zero-knowledge proofs is marked by the paper "The Knowledge Complexity of Interactive Proof Systems" published in the SIAM Journal on Computing in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff. This paper innovatively used computational complexity theory to analyze how much knowledge a proof needs to provide. For instance, to prove that the equation \(x^2-3x+2=0\) has a solution, one only needs to show one solution, e.g., \(x=1\). However, this reveals more knowledge than just proving the existence of a solution. Thus, if a proof conveys no knowledge other than the correctness of the proposition being discussed, it can be considered "zero-knowledge." Due to their pioneering work, the three authors of this paper received the highest honor in computational theory, the **"Gödel Prize."** The first two authors also jointly received the **2012 Turing Award** for their outstanding contributions to cryptography.

However, the acceptance of zero-knowledge proofs by the academic community and the public was not smooth sailing. Even the groundbreaking paper "The Knowledge Complexity of Interactive Proof Systems," which opened up a new field and even an industry, was rejected six or seven times during its initial submission. Understanding zero-knowledge proofs, especially intuitively grasping a simple understanding, is challenging. Interested readers can refer to a segment of Goldwasser's Turing Award interview ([http://youtube.com/watch?v=DfJ8W49R0rI](http://youtube.com/watch?v=DfJ8W49R0rI)). This might be why many readers who are new to zero-knowledge proofs feel uncomfortable. **So instead of trying to establish a macro intuition before understanding the details, it's better to follow the guidance of mathematics and logic step by step. Because zero-knowledge proofs might not be simple knowledge in themselves.**

Moreover, for many readers learning about zero-knowledge proofs and various cryptographic tools, the most significant obstacle might not be how to implement them but the mathematical foundations of these algorithms. Therefore, this series starts with mathematical basics to address these challenges step by step.

The idea of zero-knowledge proofs can be traced back to the RSA asymmetric encryption algorithm proposed in 1977 by Ron Rivest (2002 Turing Award), Adi Shamir (2002 Turing Award), and Leonard Adleman (2002 Turing Award), and even to the Diffie–Hellman key exchange protocol proposed in 1976 by Ralph C. Merkle (2010 IEEE Richard W. Hamming Medal, inventor of the Merkle tree), Bailey Whitfield Diffie (2015 Turing Award), and Martin Edward Hellman (2015 Turing Award). The mathematical foundations of these essential cryptographic algorithms have much in common, so learning this knowledge will lay a good foundation for further understanding cryptography. Not only these mathematical foundations, but the mathematical structure of zero-knowledge proofs themselves is also very enlightening. Hungarian mathematician László Lovász and Israeli computer scientist Avi Wigderson recently received the prestigious Abel Prize in 2021 for their related work. Additionally, related research includes the "Millionaire Problem" proposed by Yao Qizhi (2000 Turing Award) in 1982, but this problem is often used as an example of oblivious transfer.

## Zero-Knowledge Proof = Zero Knowledge + Proof

A zero-knowledge proof is a proof that can attempt to prove any proposition, such as:
- User A's credit score is above 10;
- Company C's revenue in 2021 exceeded 1 million;
- User R has permission to log into the ticketing system.

Of course, propositions can also be more mathematical, such as:
- Prover P knows a third-order polynomial, and 1 and 2 are its two roots.

Don't worry about how to prove meaningful propositions with mathematical propositions. We can easily design a set of mapping rules to map actual propositions to mathematical ones, such as the ASCII code table, which can use numbers to represent English letters and symbols to form "meaningful" sentences. In any case, from a mathematical perspective, there is no insurmountable gap between these propositions (of course, only the ones we are concerned about).

**A proof is for a specific proposition. It's a process of logical deduction based on axioms.** One of the most famous axiom-proof systems is the geometry constructed by Euclid in "Elements." We should all have encountered Euclid's plane geometry's five axioms in high school:
1. A straight line can be drawn from one point to another;
2. Any line segment can be extended indefinitely in a straight line;
3. Given any line segment, a circle can be drawn with one endpoint as the center and the segment as the radius;
4. All right angles are equal;
5. If two lines intersect a third line and the sum of the interior angles on the same side is less than two right angles, then the two lines will intersect on that side.

Based on these axioms, various geometric theorems can be proven/contradicted through logical reasoning. For example:
- Two lines parallel to the same plane are parallel.

Zero-knowledge proofs are a special kind of proof. Their uniqueness lies in their "zero-knowledge" nature, meaning the proof only indicates the truth or falsehood of the proposition and does not reveal any other information. For example:
- User A's credit score is above 10, but there's no need to reveal the user's credit score or other personal data;
- Prover P knows a third-order polynomial, and 1 and 2 are its two roots, but Prover P doesn't need to reveal what the polynomial is or provide any other information about the polynomial.


Therefore, a zero-knowledge proof system must contain at least two roles: **Prover** and **Verifier**. The prover needs to provide proof that convinces the verifier of the truth or falsehood of a specific proposition. Moreover, the proof process should not leak any other knowledge.

Based on this, we can identify three attributes of zero-knowledge proofs:
1. **Completeness**: If the proposition is true, the prover can convince the verifier that it is true;
2. **Soundness**: If the proposition is false, the prover cannot convince the verifier that it is true;
3. **Zero-Knowledge**: The entire proof process, besides revealing the truth or falsehood of the proposition itself, should not reveal any other knowledge.

From this, we can see that properties 1 and 2 are inherent attributes of the proof itself, while property 3 is the key to zero-knowledge proofs. That is, all subsequent work is based on the proof and uses mathematical methods to avoid revealing any other knowledge, ensuring zero-knowledge.

【1】Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems[J]. SIAM Journal on computing, 1989, 18(1): 186-208.

【2】Petkus M. Why and How Zk-SNARK Works[J]. ArXiv, 2019.

【3】[Euclidean Geometry](https://en.wikipedia.org/wiki/Euclidean_geometry)