In the complex field of cryptography, zero-knowledge proofs offer a unique solution for a seemingly contradictory task: proving the possession of a piece of information without revealing the information itself.

This cryptographic method involves two parties - a prover and a verifier. The prover aims to demonstrate their knowledge of a value (let's call it x) without disclosing any data about x itself. All that the verifier learns from the exchange is the simple fact that the prover possesses this knowledge. Importantly, the verifier gains no additional insights about the subject of the proof beyond the prover's knowledge of it.

Zero-knowledge proofs are crucial in ensuring the privacy and security of many cryptographic protocols. They are a safeguard against potential information leaks, a bulletproof vest for your digital secrets. Their application extends across diverse domains including blockchain technology and secure authentication systems, where the protection of sensitive data is paramount.

Some usecases of zero knowledge proof cryptography include:

• Blockchain and Crypto: Blockchain technologies like Zcash use ZKPs for transaction privacy. A person can prove that they have sufficient cryptocurrency to make a transaction without revealing the exact amount of their funds. This maintains privacy while ensuring transaction integrity.

• Identity Verification and Authentication: ZKPs can be used to confirm identity without revealing unnecessary information. For example, a person can prove they are over 18 years old without providing their exact date of birth, or prove their identity without sharing sensitive data like a password. This minimizes the risk of identity theft or unauthorized access.

• Secure Multi-Party Computation (SMPC): ZKPs can facilitate complex interactions between multiple parties, where each party can prove they are following the agreed protocol without revealing their private inputs. This is useful in various scenarios, such as privacy-preserving data mining, secure voting systems, and distributed games.

• Cybersecurity: ZKPs can provide improved security protocols, like secure password policies. For instance, ZKPs can verify that a user's proposed password meets certain security criteria without the server ever knowing the actual password. This can prevent potential breaches as the password would not be stored anywhere.

• Privacy-Preserving Data Sharing: ZKPs can be used to prove that certain data meets specific requirements without revealing the data itself. This could be particularly important in fields like healthcare or finance, where regulations around data privacy are stringent, but sharing information (in a secure, privacy-preserving manner) could lead to significant benefits.

Zero-knowledge proofs have unlocked new technological possibilities within blockchains. This can be seen with the launches of various Layer 2s such as ZKSync and Polygon’s zkEVM. However, this is only a subset of how ZKPs are innovating blockchains. As proof construction becomes cheaper and circuit writing becomes more accessible the number of applications will grow. In this article, we’ll aim to intuitively understand what a proof is and why it allows for trustless computations. Once we have a general understanding, we will explore how the PLONK proving system ensures anyone can verify that the proof of a computation is correct.

What is a Zero Knowledge Proof?

A proof allows one party to prove to another party that a particular statement is true without revealing the exact details or nature of that statement to the other party. Generally speaking, a prover computes and encodes the statement within a proof. The proof is then sent to the verifier. The verifier checks that the computation represented by the proof is valid. Within this interaction, the prover and the verifier are assumed to be adversarial.

Zero knowledge proofs uphold two additional properties: succinctness and zero knowledge. Succinctness allows the verifier to accept the correctness of a large computation without computing the statement themselves. While zero knowledge guarantees that no data is leaked about the input of the computation.

How Do We Represent a Statement?

In this section and the remainder of the article, we will focus on proofs that are constructed for PLONK-based proving systems.

(Hold Up, PLONK?)

PLONK is a type of zero-knowledge proving system. It stands for "Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge." Quite the mouthful. Essentially, PLONK is a universal and updatable cryptographic proving system, an innovation that allows for efficient verification and scalability in blockchain systems and other distributed networks.

The idea behind PLONK is to construct a proof system that is "universal" and "updatable". In the context of a zero-knowledge proof system, "universal" means that it can be used for any type of computation. "Updatable" means that the cryptographic reference string (a piece of data used in the generation and verification of proofs) can be securely updated over time.

PLONK is notable for its efficiency and simplicity, making it a popular choice for systems that require secure, private transactions. It uses fewer constraints per gate (a basic unit of computation) compared to other systems, which allows for faster and more scalable computations.

Vitalik Buterin has published a more comprehensive description of PLONK.

Let’s Proceed

Before a proof is constructed for a given statement, a statement is represented as a circuit. A circuit encodes the values within the computation along with two additional types of data:

1. Operations - such as multiplication and addition between inputs
2. The Order in which operations are performed

To encode this data, PLONKish circuits are represented as a set of vectors and constraints. Constraints are relationships that cells within vectors must respect. The two types of constraints, Gate Constraints and Copy Constraints, respectively represent the operations in the circuit and the order of these operations.

There are numerous ways to represent circuits in terms of gates used and choice of circuit framework.

Representing a Statement as a Circuit

Let’s suppose that we have two gates: a multiplication and an addition gate. The multiplication gate is represented as a vector of length three | a | b | c |.

If this gate is selected then it enforces that c is equal to a*b. Similarly, the addition gate is represented as a vector of length three where if the addition gate is selected c is equal to a + b. The enforcement of equality between certain cells are gate constraints. Using these gates, let us represent the dot product between two vectors (a,b) and (c,d). To do so we would need to complete the following computations:

1. Compute a*b using multiplication gate
2. Compute c*d using multiplication gate
3. Compute ab + cd using addition gate

This can be represented using vectors.

Notice that the output of the first and second multiplication gate are the input values for the addition gate. This data is encoded within our circuit separately from the gate constraints. This is referred to as copy constraints.

So why are circuit constraints important? If there were no constraints then a malicious prover could input any values they like into the circuit. For example, the prover could replace ab+cd with aba*b. Similar to smart contracts, constraints must be verified before use (by a proof system!)

Note: Copy constraints are also referred to as "wire constraints."

Proving a Statement

Now that we can represent statements as circuits, how does a prover convince a verifier that the proof is valid? For PLONK, the prover must convince the verifier that the gate constraints and copy constraints are respected. For copy constraints, this is done by performing a permutation check. The permutation check was first introduced by Bayer-Groth before being further developed by Gabizon, Williamson, and Ciobotaru in the PLONK paper. To prove the gate constraints, a certain quotient polynomial is computed. A good reference that explains why computing this polynomial shows that the gate constraints are respected can be found here.

Intuitively, the permutation check shows that a circuit remains the same if the copy constrained entries are permuted.

Intuition of the Permutation Check

Lets look at how intuitively the heart of Plonk works!

We say that a vector a is a related by a permutation σ to vector b if for all i-th position of b there exists the σ(i) position of a that is equal. For brevity we will represent this as σ(a)=b. Given two vectors a=(a,b,…,c), b=(a',b',…,c')$, and permutation σ, we would like to determine if σ(a)=b. This can be done as follows:

1. Represent our vectors as the following a'=((a,1),(b,2),…,(c,n)) and b'=((a',σ(1),(b',σ(2)),…,(c',σ(n))). This encodes the vectors with respect to the permutation σ.
2. Rewrite our vectors as a vector of polynomial: a''=((a+1X),(b+2X),…,(c+nX)) and b''=((a'+σ(1)X),(b'+σ(2)X),…,(c'+σ(n)X))
3. Check whether a'' and b'' are equivalent as multisets. This can be done by randomly choosing gamma such that and showing $(a+1X+γ)(b+2X+γ)….(c+nX+γ) = (a'+σ(1)X)+γ)(b'+σ(2)X+γ)….(c'+σ(n)X+γ)$.
4. By randomly selecting a β we can check if these polynomials are equivalent by Schwartz-Zippel lemma. If they are equivalent as polynomials then the sets a'' and b'' are equivalent as multisets. If they are not equivalent as polynomials then a'' and b'' are not equivalent as multisets.

Summary

While ZKPs are a complicated subject, their use cases are growing exponentially. Now that we’ve covered an intuitive explanation of how they work, we will explore applications of zero knowledge proofs and how teams are optimizing their circuits for new use cases.