Zero-Knowledge Proof (ZKP), was proposed by S. Goldwasser, S. Micali, and C. Rackoff in the early 1980s. It refers to the ability of a prover to convince a verifier that an assertion is correct without providing any useful information to the verifier.

Zero-knowledge proofs are now widely used in reality, especially in authentication protocols and digital signatures. This article will be divided into two parts to analyze the application of zero-knowledge proof technology in the blockchain.

Introduction to ZKP

Zero-knowledge proof (ZKP) is an important part of modern cryptography, which refers to the ability of a prover to convince a verifier that an assertion is correct without providing any useful information to the verifier. A zero-knowledge proof must satisfy three properties.

Completeness (Completeness): When both the prover and the verifier show honesty and follow a protocol to perform the verification steps, it must be acceptable to the verifier if the prover’s statement is true.

Soundness: If the prover’s statement is false, then it is unlikely that any cheating prover would convince an honest verifier of his statement.

Zero-knowledge: After the proof is executed, the verifier only knows whether the prover’s statement is true or not, and has no other information about the proof process. Zero-knowledge proof techniques rely on strong theoretical foundations, such as computational complexity theory and information theory. These include Turing machines, probabilistically checkable proofs, and the P/NP problem.

Theoretical research on zero-knowledge proof techniques has been developed for more than three decades, and the development can be divided into three phases, which were proposed by S. Goldwasser, S. Micali, and C. Rackoff in the early 1980s.

In the early period, cryptographers proposed several concepts such as the Fiat-Shamir transform, CRS, PCP, Sigma, and other protocol concepts, which laid the foundation for the subsequent development of zero-knowledge proofs.

During the theoretical development period, after 2000, cryptographers proposed the non-interactive zero-knowledge proof technique of bilinear mapping; the technical idea of generating zero-knowledge proofs based on secure multi-party computation; the GKR protocol, etc., and zero-knowledge proofs gradually began to mature.

In the application development period, after 2010, zero-knowledge proof techniques gradually came to the ground, such as Groth16, PLONK, etc. were applied to various fields.

ZKP algorithm

In recent years, zero-knowledge proof technology has developed many algorithms in the blockchain field, and the following is a compilation of the current mainstream blockchain algorithms

The following is a brief introduction to the three algorithms that are currently being used more widely.

Bulletproofs

Bulletproofs was proposed by Stanford University’s Applied Cryptography Group (ACG). It does not require trustworthy settings, has a wide range of applications, has a small proof size, is fast to verify, and is currently used in many projects.

Groth16

Groth16 is an algorithm proposed by Jens Groth in 2016. The advantages of this algorithm are the small number of proof elements provided (only 3 are needed), the simplicity of the verification equation, and the guarantee of completeness and reliability under polynomial computational power. It is currently widely used for Layer 1, Layer 2, and Dapp.

Plonk[JN7]

Plonk was proposed by Ariel Gabizon et al. It supports a generic, scalable reference string and some scenarios and functions can actually share an SRS as long as the size of the circuit design does not exceed the SRS upper limit threshold.