PrivacyIN Week2 Lecture Review | Basic Principles of the Classic ZK Protocols by Dr. Yupeng Zhang
Introduction
PrivacyIN’s second ZK Camp started as scheduled at 9:30 on July 16. During Basic Principles of the Classic ZK Protocols (Groth16 Plonk Stark), Dr. Yupeng Zhang, an assistant professor at the Computer Science and Engineering Department, Texas A&M University, focused on the basic principles of classic ZK protocols. The two-hour intensive lecture on cryptography was attended by a small group of experts and scholars who focus on cryptography and related fields all around the world.
The full lecture is available on Youtube:
Main Content
Since Goldwasser, Micali, and Rackof first proposed the notion of zero-knowledge proofs (ZKPs) in 1985, as ZKP theories and technologies advanced, many classical ZKP systems have appeared, including Groth16, Pinocchio, Plonk, Marlin, Stark, Halo2, etc. These systems have allowed us to put ZKP theories into practice. Meanwhile, mastering the mechanisms and principles of these protocols is of great significance for designing ZKP application systems.
During the lecture, Dr. Zhang analyzed the basic principles of three typical non-universal protocols: SNARK, PLONK, and STARK, with a focus on polynomial commitments, prime number and modular arithmetic, the PLONK protocol, SNARK protocols, and the STARK protocol.
Lecture Review
Dr. Zhang started the lecture with a brief review of the ZKP system discussed in the first lecture to help students deepen their understanding of ZKP concepts and computation models.
Polynomial Commitments
Polynomial commitments are a common cryptographic tool for constructing ZKP systems, and the prover and the verifier are the main participants of its construction model. Constructed using the interactive proof method, polynomial commitments may also be validated by the non-interactive method using Fiat–Shamir-heuristic. We can think of polynomial commitments as a special kind of zero-knowledge proof that also features correctness, soundness, and zero-knowledge.
Here are the basic principles of polynomial commitments:
Many classic ZKP protocols, including Plonk, Dark, Stark, and Supersonic, are all built on polynomial commitments.
The KZG polynomial commitment is a classic, efficient polynomial commitment construction. In particular, it represents a very basic component in the Plonk protocol. Based on Bilinear-Pairing and generated groups (illustrated in greater detail in the below paragraphs), the construction normally features groups generated based on elliptic curves in a finite field (e.g. determining g after selecting the elliptic curve). The KGZ commitment mainly involves the following steps:
Prime Number and Modular Arithmetic
Zero-knowledge proofs demand a strong background in number theory. To address the many mathematical problems, and to help the students understand the mathematical principles behind the construction of the classic ZKP protocols, Dr. Zhang started with the definition of prime numbers and modular operations, which are the basics of number theory.
Prime number p is an integer no smaller than 2 and only divisible by p and 1;
Modular arithmetic means that any number or its arithmetic value (including the intermediate steps) requires a positive integer (e.g. p) specified on the modulo. This ensures that the numbers obtained from the modular operation fall between (0, p). For instance, the modulo 13 operation is as follows:
-1 mod 13 = -1 + 1x13 = 12；
-1 + 2 mod 13，i.e. (-1 mod 13) + (2 mod 13) = (12 + 2) mod 13 = 1
Group is defined on a set of numbers and satisfies an operator:
- Closure: elements in the group remain in the defined group after the operator is executed.
- Associativity: elements in G satisfy the commutative law for the operation of the defined operator. For example: (a+b) + c = a + (b+c).
- Identity element: There exists an element e in G such that, for every element a in G, the equation e + a = a + e = a holds.
Inverse element: For each a in G, there exists an element b in G, such that a + b = e.
Examples: for integer with +, integer mod n with + is performed.
Field is a group that satisfies the operation (+,x):
- Field is a group under +.
- Field (without the additive identity 0) is a group under x.
Rational numbers, real numbers, complex numbers, and integer mod primes p (finite field) are all fields. The finite field is commonly used in cryptography.
One characteristic of the finite field is that it can always find a generator, which is an element that generates all elements in the group by repeating the multiplication on itself, forming a cyclic group. Therefore, the exponential elements generated by the generator can be used to represent the finite field. In addition, existing fast algorithms can find generators of the finite field.
PLONK
To better explain how Plonk is constructed, Dr. Zhang provided a general ZKP construction model, in which the prover owns the secret data, and the computation problem is converted into a general circuit © computation. In this model, the prover proves to the verifier that he used the secret data as input and obtained the output by running the circuit. The verifier then verifies whether the proof is correct.
The construction of the Plonk protocol is mainly divided into two parts: circuit gate constraint processing and replication (linear) constraint processing.
Main steps for circuit gate constraint processing:
The prover uses the KZG commitment to generate a(x), b(x), c(x), t(x) as the proof and provides it for the verifier to examine its correctness.
Plonk的复制约束主要思路是，通过将相等的电路线进行置换（重排），置换后的元素和元素是相等同的，引入置换多项式，然后进一步转换为等价约束多项式： ，并最终转换为基于拉格朗日多项式的特殊多项式Z(X)，然后使用这个多项式和门约束多项式构成一个压缩的新多项式进行证明和验证。
Main steps for replication (linear) constraint processing:
Overall implementation of Plonk:
The overall implementation of Plonk is, in fact, the construction of a large polynomial constraint associated with gate constraints and replication constraints after the processing of gate constraints and replication constraints. It mainly relies on the KZG polynomial commitment and Lagrangian interpolation to build a complete protocol and finally uses Bilinear-Pairing for verification.
SNARK Protocols
The conventional SNARK protocol refers to the public parameters and public keys (proof key and verification key) required to generate zero-knowledge proofs through a non-universal trusted-setup. SNARK protocols are generally based on succinct, non-interactive ZKP protocols constructed by Bilinear-Pairing. Classic SNARK constructions include Pinocchio and Groth16, which mainly rely on R1CS to construct circuit constraints, which are then converted to QAP for constructing polynomial proofs. Moreover, they also use Bilinear-Pairing to verify polynomials.
A traditional SNARK computation normally involves the following workflow:
- Convert a computation problem into a circuit problem (represented as a circuit)
- Represent the circuit as an R1CS constraint (multiplication gate constraint)
3. Solve the R1CS constraint through polynomial interpolation to obtain QAP, and convert the QAP polynomial and the target polynomial t(x) into an encrypted group G as the proof.
4. Use Bilinear-Pairing to verify the QAP polynomial and target polynomial t(x):
STARK
STARK is a succinct, non-interactive ZKP protocol that does not require trusted-setup. The front-end of STARK mainly uses RAM (Random-Access-Memory) Program for co-construction. A typical RAM program consists of a CPU (including many registers), a memory, program execution instructions, etc.
STARK turns the proof problem into proving whether the RAM Program is executed correctly, which significantly differs from the execution of circuit verification in conventional zkSNARK protocols. STARK uses RAM Program for front-end program construction, which allows the program so designed to run instruction steps with much larger running time and cycles with few instruction codes. Moreover, such programs are not limited by the circuit size. The random access operation features advantages such as constant complexity.
STARK uses the RAM-to-circuit-Reduction technology to validate proofs. The protocol records all RAM interactions and changes in the CPU State during the whole computation process, then connects or aggregates them, and finally converts them into circuit-like constraints to prove and verify whether the RAW Program is executed correctly.
The arithmetic operation of STARK is represented by a series of polynomials. For example, the state of program execution Step 1 is P1(X,…,Y), and that of Step 2 is P2(X,…,Y). A polynomial is constructed by each step.
The back-end implementation of STARK can convert the polynomial involved in the execution step into a polynomial constraint similar to SNARK or Plonk, and then perform a random linear combination at a certain degree to construct a large verification polynomial, which can be used to prove and verify the correctness of program execution.
In fact, STARK uses the Merkle tree-based FRI protocol (low degree test) to implement the back-end construction. Furthermore, the protocol also requires additional Permutation tests and public constraints. As the FRI protocol involves more complicated theories, it was not extensively discussed during the lecture.
During free discussions, Dr. Zhang patiently answered the questions about the basic principles of ZKP protocols 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.
