A comparison of different proof schemes in one article: Understanding the advantages and disadvantages of the ZK proof system

Compilation of the original text: Deep Tide TechFlow

Compilation of the original text: Deep Tide TechFlow

The concept of zero-knowledge proof is familiar to everyone, but many people may be confused when it comes to technical details.

Zero-knowledge and proof are actually 2 nouns, and the proof scheme is a basic part of the security assumption of the zero-knowledge protocol. In this article, Hill.bit will help more people understand the ZK proof system by explaining various proof schemes and their advantages and disadvantages.

In a zero-knowledge proof system, three entities participate: the setter, the prover, and the verifier. Different proof schemes affect their behavior in various ways, thereby affecting efficiency, security, and overall system performance.

The setter phase generates the necessary parameters and public keys required by the ZK system. The proof scheme affects the complexity of the setter phase, computation, communication, and whether it is trusted or trustless. The prover generates a proof that it possesses information about a secret input without revealing it. The proof scheme affects the prover's computation time, memory requirements, and proof size, which affects communication and storage requirements. The verifier checks the validity of the proof. The proof scheme affects verification time, memory requirements, and the number and complexity of requests to the proof. There are three different types of proof schemes here.

Linear PCPs + linear encoding only:

Using linear probabilistically testable proofs (PCPs) and linear operations;

Provide strong zero-knowledge attributes;

Generate the shortest proof;

Trusted settings are required;

Previous improvements mainly focus on reducing prover time.

Linear PCPs are a proof system in which a verifier checks the validity of a statement by querying a small number of proofs. The term "linear" means that the verifier's query is a linear function of the proof.

Linear-only encoding is an encryption technique used to hide information, allowing only linear operations on the hidden data. This ensures data privacy while enabling certain computations to be performed.

Polynomial IOPs + polynomial commitment scheme:

use algebraic structures;

Usually more efficient than linear PCP based systems;

Supports generic/untrusted settings;

Allows custom circuits;

Previous improvements have mainly focused on improving validator efficiency.

Polynomial Interactive Oracle Proofs (IOPs) are a proof system in which a prover and verifier exchange messages over multiple rounds. The prover generates an oracle (commitment to a polynomial) and provides it to the verifier.

The verifier queries the oracle at a particular point, and the prover evaluates the response in a corresponding polynomial. A polynomial scheme promises a polynomial without revealing information about the polynomial itself.

The efficiency gains compared to linear PCPs + linear-only encoding come from:

better use of algebraic structures;

More efficient proof generation/verification;

compressed polynomial representation;

Batch Validation Technology

However, the polynomial IOPs + polynomial commitment scheme has the following disadvantages:

more complex design and implementation;

Cryptographic assumptions for specific purposes;

Different performance tradeoffs, such as parallelizability.

Folding scheme:

allow recursive proof combinations;

Implement nested proofs for efficiency and scalability;

Provers that are fast and easily parallelizable;

Previous improvements focused on building recursive SNARKs.

Recursive proof composition can reduce the computational and memory requirements of the verifier, which is particularly useful in applications like blockchains. Proof aggregation can reduce the final proof size and verification time, but generating such a proof may be more computationally demanding on the prover. Compared to the polynomial IOPs + polynomial commitment scheme, the efficiency improvement of the folding scheme comes from:

Recursive proof combination;

proof aggregation;

Improved scalability;

Faster verification times.

Potential disadvantages of the folding scheme include:

more complex design and implementation;

Customized encryption assumptions;

Increase the computational time and memory overhead of the prover;

Applicability may vary by use case.

In conclusion, linear PCPs + only linear encodings provide strong zero-knowledge properties and shortest proof lengths, but they require a trusted setting and are limited in efficiency compared to other classes. Polynomial IOPs + polynomial commitment schemes offer significant improvements in efficiency over linear PCPs + linear encoding only through more efficient proof generation and verification processes, but may be more complex to design and implement.

The folding scheme excels in terms of efficiency and scalability, thanks to recursive proof composition, which is especially useful in blockchain applications. However, the computational time and memory overhead of the prover may increase, and its applicability may vary depending on the use case.