What is a Zero-Knowledge Proof | A Practical Guide for Programmers

Blockchains are transparent by design. But what about cases in which we need data to be private? For example, what if I want to prove my age without revealing my birthday? Or prove I am who I say I am without revealing my identity. Or prove I have the collateral necessary for a loan. Enter zero-knowledge proofs.

Zero-knowledge proofs enable an entity to prove it knows a piece of information without revealing the information itself.

This article explores the concept of zero-knowledge proofs (ZKPs), explains how they work, and provides examples to illustrate what you need to know to understand them, all in the context of blockchain technology. It is tailored toward programmers who want to understand the high-level overview of mathematical ZKPs and how they work in practice.

For those not interested in the detailed breakdown and would prefer a high-level explanation, Jarrod Watts provides a high-level description of ZKPs using practical, non-mathematical examples in this excellent article.

‍

What are zero-knowledge proofs?

Zero-knowledge proofs (ZKPs) are cryptographic proofs that allow you to prove knowledge of something without revealing the thing itself. To do this, algorithmic ZK systems use algorithms that take some data as input and return whether the input satisfies certain requirements. For example, prove that I have the secret password to unlock a safe without revealing the password.

There are two roles involved in ZK proofs:

1. The Prover: The entity that wants to prove its knowledge of a secret without revealing the secret itself. They generate a proof based on this knowledge that the verifier can check. In our safe example, this would be the person (or entity) proving they know the password.
2. The Verifier is the entity responsible for validating the proof. The verifier confirms the validity of the proof without learning anything about the secret. Again, in our safe example, this would be the person (or entity) verifying that the provers’ password was the required password to unlock the safe.

‍

Interactive and non-interactive ZKPs

There are two overarching types of ZKP, interactive and non-interactive ZKPs:

Interactive zero-knowledge proofs:

• Require multiple rounds of communication between the prover and verifier to exchange information and verify the proof.
• The verifier actively participates in the process by sending challenges to the prover and receiving responses.
• Are not suitable for blockchain applications because the need for repeated interactions is impractical.

‍

Non-interactive zero-knowledge proofs:

• Involve a single message from the prover to the verifier containing all necessary proof information.
• Do not require further interaction between the verifier and the prover; the verifier can check the proof independently.
• They are ideal for blockchain applications because they reduce the need for communication, improve efficiency, and can be verified by any participant on the network. Thus, they enable trustless verification and easy integration into smart contracts and decentralized protocols.

‍

Requirements of a zero-knowledge proof

A ZK proof must satisfy the following criteria:

1. Completeness: If the input is valid, the proof must always convince the verifier.
2. Soundness: It must be practically impossible for a prover to trick the verifier with an invalid input (well, 99.999999% impossible).
3. Zero-knowledge: The verifier (or any observer) learns nothing about the secret, only that the input satisfies the proof.

A zero-knowledge proof contains three elements:

1. Witness: The secret information or data that the prover knows and uses to demonstrate that a statement is true. For example, in the equation $x + 2 = 3$, the witness would be $x = 1$. Typically, this is an array of inputs to the circuit.
2. Statement/Claim: The claim that the prover is making about the witness. For instance, "I know an $x$ that satisfies. $x + 2 = 3.$" Individual requirements are known as constraints. A collection of constraints forms a circuit that makes up the claim that the prover is making.
3. Proof: The actual cryptographic proof generated by the prover, which the verifier checks to confirm the claim without revealing the witness itself.

‍

Types of zero-knowledge proof systems

SNARK (Succinct Non-Interactive Argument of Knowledge) is a broad class of ZKP systems that are non-interactive (there is no back and forth between prover and verifier). They are efficient in both proof size and verification time, regardless of the size of the problem.

• SNARKs require a trusted setup (which will be defined shortly), where some initial parameters used to keep the witness and circuits concealed from the verifier are generated using a secret. If this secret is ever revealed, it compromises the security of all proofs generated with that setup.
• Many SNARKs use elliptic curve cryptography (ECC) to create proofs, which depend on the hardness of the discrete logarithm problem (DLP). Elliptic curves (ECs) are essentially just fancy curves often used in cryptography because the math is more efficient but don’t worry too much about this right now. This reliance on ECs makes them susceptible to future advancements in quantum computing since quantum computers are able to solve the DLP.
• Examples of ZK SNARK proving systems:
  • ‍Groth16: Named after its inventor, Jens Groth, Groth16 uses a circuit-specific trusted setup procedure. It is known for producing very small proof sizes and is widely used in various blockchain projects and cryptographic applications such as ZCash and Loopring.‍
  • PLONK (Permutation Argument over Lagrange bases for Oecumenical Noninteractive Arguments of Knowledge) is a versatile zero-knowledge proof system that uses a universal and updatable Structured Reference String (SRS). The trusted setup only needs to be calculated once and can be reused for multiple circuits, therefore offering greater flexibility relative to Groth16. It also enables easier addition of new programs or circuits without redoing the entire setup. Examples of PLONK protocols include Plonky2 and Halo2.

STARKs (Scalable Transparent Argument of Knowledge) uses a setup process that doesn't rely on secret parameters. Instead, it uses hash functions and publicly known randomness to construct proofs, making the setup "transparent" and trustless. Because ZK STARKs rely on hash functions rather than elliptic curves, they are quantum computing resistant.

‍

SNARKs vs. STARKs

The choice of SNARKs or STARKs for a specific implementation depends on the application. Comparing the two:

For the remainder of this article, we will be focussing on SNARKs since they are most commonly used, particularly in blockchain ecosystems.

‍

Key components of a zero-knowledge proof

Let’s go through some of the key terms associated with ZKPs so that you are familiar with what they mean when you see them out in the wild.

• Constraints are mathematical rules or conditions that describe the relationship between various inputs and outputs of a computation. All constraints must hold true for a proof to be valid. For example, a constraint could specify that a particular input, when squared, equals a given output (like $x^2 = y$). Careful attention must be paid to the specific constraint system required for the zero-knowledge proof system; therefore, circuits must be written in a specific format. For example, Circom targets Groth16, which requires R1CS-based circuits.
• Circuits are structured representations of the computational problem as a series of equations or arithmetic operations. In a zero-knowledge proof system, the prover uses the circuit to demonstrate they know a set of inputs that satisfy all constraints without revealing the inputs themselves.
• Constraint systems
  • Rank 1 constraint system (R1CS): a type of constraint system used in Groth16 that enables an algebraic circuit to be expressed as a set of vectors and matrices, which are then converted to a set of polynomials.
  • PLONKish: a constraint system for PLONK protocols that enables an algebraic circuit to be defined in terms of a rectangular matrix of values.
• Arithmetization is the process of converting a computational problem into a circuit in the form specified by the constraint system being used. For example, for R1CS systems, the problem needs to be converted into a system of polynomials with a maximum degree of two.

‍

The trusted setup

A trusted setup is an initial phase in creating a ZKP, where a set of parameters is generated. This setup requires trust because if the parameters are compromised or manipulated, the security of the entire system could be at risk.

• Toxic waste: Random values generated during the trusted setup phase that allow invalid proofs to be forged if compromised. They must be securely destroyed after use.
• Common reference string (CRS): These are the public parameters available to the prover and verifier and used to create and verify proofs.
• Structured reference string (SRS): This is a type of CRS that includes structured data  For example, elliptic curve points derived from powers of a secret value ($τ$) - more on this shortly.
• Multi-party computation (MPC): In the context of ZKPs and the trusted setup, an MPC refers to when multiple parties contribute to the setup ceremony by producing some randomness (an instance of toxic waste!). This increases security by reducing the likelihood that all participants are dishonest since the ceremony only requires one honest participant to ensure a secure setup. This is because if one participant destroys their random value, the combined secret cannot be reconstructed.
• Powers of Tau: These are used in SNARKs, such as Groth16 and PLONK, to provide an SRS through an MPC process.
  • The idea behind Powers of Tau is to generate a sequence of powers of a secret value $τ$ (tau) in a cryptographic group (like $g,g^τ,g^{τ2},…,g^{τd}$), where $g$ is a generator of the group, and $d$ is a parameter indicating the degree. These values are also types of SRSs and can be reused across different circuits!
• Polynomial Commitment: A polynomial is committed so that its coefficients are hidden. The commitment is a cryptographic object derived using the SRS from the Powers of Tau ceremony and evaluated at a specific point, chosen at random by the verifier - this is the so-called challenge.

‍

Examples of trusted setups:

Groth16 trusted setup:

Groth16 uses a two-phase setup process:

1. Powers of Tau phase: Creates a general SRS for circuits up to a given size. This phase is not circuit-specific. It generates a set of elliptic curve points based on random value τ. The output of this phase can be reused for multiple circuits up to a certain size limit, determined by the degree of the highest power of τ.
2. Circuit Specific: The parameters generated during the first phase are combined with the polynomials from the circuit’s R1CS representation and used to generate circuit-specific keys:
   • Proving key (PK): Used by the prover to generate proofs.
   • Verification key (VK): Used by the verifier to verify the proofs.
3. This setup involves creating certain group elements (points on an elliptic curve) that correspond to the circuit’s constraints. Each circuit requires a new trusted setup because the parameters generated encode the exact computation of that circuit.

PLONK trusted setup:

• PLONK uses a universal and updatable SRS generated by the Powers of Tau ceremony. This allows multiple circuits to share the same setup, providing the circuit is within the size constraint determined by the highest power of tau. Polynomial commitments in PLONK use the Powers of Tau to commit to and verify circuit constraints. The most common polynomial commitment scheme is the KZG commitment scheme. This works by combining the polynomials with the powers of tau, and the commitment is then evaluated at a specific point.

‍

How zero-knowledge proofs work in practice

Creating a zero-knowledge proof

Practical ZKP systems consist of a front end and a back end. The front end is the constraint system used to represent the problem mathematically. The back end is the proving system that generates and verifies the proofs based on the circuit.

To create a zero-knowledge proof, start with a computational problem. The zero-knowledge proof is then created and verified with the following steps:

• Arithmetization: Convert the computational problem into a mathematical form (e.g., a constraint system) that the proof system can work with. This arithmetized form of the problem is known as a circuit: a circuit is a group of mathematical expressions (e.g., $x > 5$) known as constraints that the witness must satisfy.
• Proof creation: Generate a proof using the circuit. The prover encodes their knowledge (the witness) into the proof without revealing it. This enables the prover to prove knowledge of the solution to the arithmetized problem without revealing the actual values.
• Verification: The verifier checks the proof to ensure validity and confirms that the prover must know the correct values.

Domain-specific languages (DSL) (e.g., Noir, Cairo, Circom):

• To simplify the circuit writing and verification process, developers write circuits in languages like Noir, Cairo, or Circom.

Intermediate representation (e.g., ACIR) and constraint systems (e.g., R1CS):

• For languages like Noir or Cairo, the high-level code is compiled into an intermediate representation such as ACIR (Arithmetic Circuit Intermediate Representation), which abstracts the circuit logic into a standardized format for further processing by various ZK-proving back ends.
• In the case of Circom, however, circuits are directly compiled into R1CS and represent the constraints that need to be satisfied.

Proving back end:

The proving back end processes the circuit representation, whether it's ACIR, R1CS, or another, and generates the cryptographic proof. The back end also verifies the proof (or creates a smart contract to verify the proof on-chain), demonstrating that the computations were performed correctly without revealing any underlying data.

1. Circuit processing:
   • The proving back end interprets the circuit according to the rules of the specific constraint system it implements.
2. Proof generation:
   • The back end generates a zero-knowledge proof based on the circuit and the inputs provided. This proof demonstrates that certain computations have been performed correctly without revealing the underlying data.
3. Proof verification:
   • The back end also includes mechanisms to verify that a given proof is valid.
   • Verification involves checking that the proof adheres to the rules of the circuit.

Deployment:

• The verifier (this is just a smart contract that can verify the proof) can be deployed on-chain, meaning that the proof can be verified on-chain.

‍

Summary

Zero-knowledge proofs (ZKPs) enable one party to prove knowledge of information without revealing the information itself, enhancing privacy and security in blockchain applications and providing a tool to build privacy applications. This article explores the mechanics of ZKPs, including the roles of the prover and verifier. It provides a concise overview to help developers understand the concepts of ZKPs and how they work in practical applications.