Introduction

PrivacyIN’s first ZK Camp kicked off at 9:30 on July 9. In Basics of ZK Cryptography & Research Overview, the very first lecture of the camp, Dr. Yupeng Zhang, an assistant professor at the Computer Science and Engineering Department, Texas A&M University, focused on ZK theories and their applications. The 90-minute intensive lecture on cryptography was attended by a small group of experts and scholars who focus on cryptography and related fields.

The full lecture is available on youtube：https://youtu.be/dx70mlBT39o

Main Content

The notion of zero-knowledge proof was first proposed by Goldwasser, Micali, and Rackoff in 1985. Zero-knowledge proofs are a type of cryptographic protocol that functions between the prover and the verifier. Specifically, the prover proves to the verifier that it can provide a solution (witness) to a computational problem (statement) without revealing any additional information about the solution (witness).

Zero-knowledge proofs ensure correctness without compromising users’ privacy, which makes them a powerful tool that has been adopted in a wide range of fields, covering electronic voting, anonymous proofs, group signatures, verifiable outsourced computing, etc. In particular, along with the advancement in Web 3 technologies, zero-knowledge proofs are now closely linked with cryptocurrency and blockchain technologies.

In this lecture, Dr. Zhang focused on zero-knowledge proofs and covered proof systems, the definition and history of zero-knowledge proofs, as well as their application in the field of cryptocurrency and blockchain.

Dr. Zhang first described the traditional proof problem using the Pythagorean theorem as the example: proving AC²=AB²+BC² given △ABC right angle at B. Here is how we prove the Pythagorean theorem: Draw a perpendicular starting from B and intersecting AC at D, the theorem can then be proven as triangles on both sides of the perpendicular are similar to the whole triangle and to each other.

Here, AC²=AB²+BC² functions as the statement of the proof, and the process of proving the theorem constitutes the proof. A statement may represent any computational problem, and the traditional statement is given by providing all the proof steps and then performing the verification. In this process, information (knowledge) is disclosed.

The prover/verifier interactive proof computation model is a typical proof system. Dr. Zhang gave an example of a color verification process where the prover claims that he “is aware that there is a piece of paper with different colors” (statement).

The randomness challenge was introduced into the above case: The verifier generates random numbers to determine whether to flip the paper for randomness challenges, and the prover receives the challenge by answering whether the paper is flipped. An honest prover will always answer correctly (100%) as to whether the verifier flipped the paper. If the prover tries to answer the randomness challenge by making a blind guess, the probability of giving the correct answer would only be 50%. After repeating the process multiple times (100 or more), if the prover correctly answers the verifier’s challenge every time, it is then very likely (almost 100%) that the prover knows the correct answer. In other words, this proves the statement that the prover claims: he knows that there is a piece of paper with different colors. On the other hand, if the prover does not know the answer, the probability of him guessing correctly every time would be extremely low. If the process is repeated 100 times, the probability would be 1/2¹⁰⁰, which is negligible. As such, this proves that the prover is dishonest or malicious.

A standard proof system mainly consists of the prover, the verifier, and the public computation C. In particular, the prover owns data and generates proof to indicate that he obtains the result using the public computation C. The prover then sends the computation proof to the verifier, who will examine the correctness of the proof.

A typical proof system mainly comes with the following features:

1. Correctness
   An honest prover can examine the correctness of the proof with an extremely high probability (almost 100%).
2. Soundness
   If the prover is dishonest or malicious, then the chances of him getting validated would be negligibly low.

An efficient proof system is primarily characterized by short verifier time and small proofs. In other words, the proof size should be succinct.

A zero-knowledge proof (ZKP) system, based on the regular proof system, is able to examine the correctness of computations without disclosing any original data from the prover in the proof, which represents a zero-knowledge proof.

During the lecture, Mr. Zhang reviewed the history of zero-knowledge proofs and introduced the earliest ZKP system, which was proposed by Goldwasser, Micali, and Rackoff. He also covered some of the early complexity theories relating to ZKP systems, including interactive proof, the probabilistically checkable proofs (PCP) theorem, zero-knowledge, etc.

Pinocchio marks a major milestone in the history of ZKP systems. The protocol is the first near-practical zkSNARK (Succinct Non-interactive Argument of Knowledge). Supporting general computing, Pinocchio converts the computation problem to the R1CS (Rank1 Constraint System) format and then to QAP (Quadratic Arithmetic Programs), which achieves succinct polynomial proof and verification. The appearance of Pinocchio marks the progress from theories to practice by zero-knowledge proofs, which is also the foundation of the Groth16 protocol.

Next, Dr. Zhang divided the cryptography technologies that power existing zero-knowledge proof systems into several categories, including Bilinear Pairing, Secure Computation, Discrete-log, Interactive Oracle Proof, Interactive Proof, Lattice, etc.

Right now, ZKP systems are nearly practical in terms of performance, and the best ZKP system has recorded terrific performance (e.g. generating proofs) for computations with 1 million gates. On the other hand, the proof size and verifier time are also related to how the specific cryptography technology is constructed.

Further, Dr. Zhang also touched on the characteristics of cryptocurrency, authentication, and blockchains. He analyzed the issue of compromised privacy concerning Bitcoin and said that Bitcoin features open data and is therefore pseudo-anonymous. Dr. Zhang then proposed that zero-knowledge proofs of data validity could be used to enhance privacy protection in the blockchain space.

Moreover, Dr. Zhang analyzed the scalability problem of existing blockchains, that is, their weak capacity to process transactions (e.g. Bitcoin: 5tx/s, Ethereum: ~30 tx/s), and introduced ZK-Rollup, a trending technology. He suggested that ZK-Rollup is primarily enabled by aggregating transactions to construct succinct proofs and perform efficient verification through the adoption of efficient zero-knowledge verification algorithms.

At the end of the lecture, Dr. Zhang explored some of the differences between the privacy-focused blockchain Zcash and ZK-Rollup, which helped students understand their features, concepts, and design goals.

During free discussions, Dr. Zhang patiently answered the questions about the basics of cryptography and zero-knowledge proofs from the students.

— About PrivacyIN —

PrivacyIN (Privacy Institution), founded by the LatticeX Foundation, strives to build an open community for preaching and studying cryptography and privacy-preserving technologies. The institution works with top scholars and developers who focus on privacy-preserving technology to promote the innovation and implementation of ZKP (Zero-Knowledge Proof), MPC (Multi-Party Computation), and FHE (Fully Homomorphic Cryptography) in the field of Web 3.

— About the LatticeX Foundation —

As a global community dedicated to open-source technologies, the LatticeX Foundation aims to set up a completely decentralized computation interoperability network and facilitate the transactions of data use rights under the premise of protecting data sovereignty and privacy, in order to achieve the vision of returning the data sovereignty to users, protecting data privacy, and realizing data value exchange by building up complex computing. To realize its vision, LatticeX supports various research programs.