PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.
PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang
PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang
PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

PrivacyIN Week1 Lecture Review | Basics of ZKP Cryptography & Research Overview by Dr. Yupeng Zhang

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.

This article is reproduced from https://medium.com/@LatticeX_SGP/privacyin-week1-lecture-review-basics-of-zkp-cryptography-research-overview-by-dr-yupeng-zhang-3f8f59556e4b

Like (0)
Previous September 10, 2022 12:08
Next September 11, 2022 11:58

相关推荐

Leave a Reply

Please Login to Comment