Zero-Knowledge Proofs: The Math

This is my second article about Zero-Knowledge Proofs (ZKPs). If you haven’t read it, check out Part 1 as a starting point.

My original undergraduate degree was in Applied Mathematics. While I find this material fascinating, your mileage my vary. I’m reminded of the quote, “Each equation, I was told, would halve the sales of the book. But that was okay. Equations are necessary if you are doing accountancy, but they are the boring part of mathematics. Most of the interesting ideas can be conveyed by words or pictures.” from A Brief History of Time by Stephen Hawking. I’m going to add many more formulas to this blog post because I can.

Zero-Knowledge Proofs (ZKPs) are one of the most elegant ideas in modern cryptography. They allow one party (the Prover) to convince another party (the Verifier) that a statement is true without revealing why it is true.

While the concept sounds almost magical, the underlying mathematics is rooted in number theory, abstract algebra, probability theory, and computational complexity.

Medium.com doesn’t have great support for mathematical symbols. You get some with code blocks, but I just added pictures of formulas (and the like) that I need to depict.

There are multiple approaches to implementing ZKPs. See Part 1. We’re going to focus on a simple implementation and its math in this post.

Quick Recap

Suppose I know the password to a system. A traditional proof would be “Here’s the password.” Maybe the password is one-way hashed prior to presenting it to the system.

A zero-knowledge proof is “I can mathematically prove that I know the password without revealing the password itself.”

The Verifier becomes convinced that the Prover possesses some secret knowledge while learning nothing about the secret.

The Three Properties of a ZKP

A proof system is considered zero-knowledge if it satisfies:

• Completeness: If the statement is true, an honest Prover can convince the Verifier.
• Soundness: If the statement is false, a dishonest Prover cannot reliably fool the Verifier.
• Zero-Knowledge: The Verifier learns nothing except “the statement is valid.” No additional secrets are revealed.

ZKP: Mathematical Foundations

At its heart, a ZKP proves knowledge of a secret value:

secret = x

without revealing x.

The proof usually involves demonstrating a relationship:

y = g^x

where:

• x is secret
• y is public
• g is

The Prover demonstrates knowledge of x such that the equation holds.

A Simple Example: Discrete Logarithms

Consider a large prime p. Choose a generator g.

Compute:

y = g^x mod p

where:

• x is secret
• y is public

The Prover wants to show that “I know x”, but without revealing ‘x’.

This forms the basis of many classical identification protocols.

The Schnorr Protocol

One of the simplest ZKPs is the Schnorr identification scheme.

The Group

From Wikipedia, “In mathematics, a group is a set with an operation that combines any two elements of the set to produce a third element within the same set and the following conditions must hold: the operation is associative, it has an identity element, and every element of the set has an inverse element. For example, the integers with the addition operation form a group.”

Schnorr’s algorithm uses a group where certain operations are easy to perform, but hard to reverse. A group G of prime order q with generator g in which the discrete log problem is assumed to be hard. Typically a Schnorr group is used.

The group contains exactly q elements, where q is a prime number. For example, if q=7, then the group contains 7 distinct elements.

The group operation is usually written as multiplication (although it could be elliptic-curve point addition in modern systems). A generator is a special element that can produce every element of the group. Starting with g, you repeatedly apply the group operation:

g⁰(=1),g¹, g², g³,g⁴,g⁵,g⁶

and eventually generate every element in the group exactly once before cycling back. If these are all distinct, then g is a generator. The simplest generator is y=g^x, which would produce the set G = { 1, 2, 4, 8, 16, 32, 64}.

The Algorithm

In this scheme, one has the following public information:

g (randomly chosen natural number, large) - the generatorp (randomly chosen natural number) - mod arithemeticy = g^x mod p

and a secret (again, large):

x

Step 1: Commitment

The Prover chooses a random number (a large one):

r

and computes:

t = g^r mod p

Then sends:

t

to the Verifier.

Step 2: Challenge

The Verifier chooses a random challenge:

c

and sends it back.

Step 3: Response

Prover computes:

s = r + cx

and sends s.

Step 4: Verification

Verifier checks:

g^s = t * y^c

This works because:

where:

• g = generator of the group
• x = secret known by the Prover
• y = g^x = public key
• r = random nonce chosen by the Prover
• t = g^r = commitment
• c = Verifier’s challenge
• s = r+cx = Prover’s response

The verification proceeds as follows:

Raise both sides to the power of g:

Apply exponent rules:

Recall:

Therefore:

Rewrite the second term. Using:

we obtain:

Substitute known values. Since:

and

we get:

Final verification equation

The Verifier computes both sides independently and checks that they are equal.

If the Prover truly knows x, the equation balances perfectly. If they don’t know x, producing a valid s that satisfies the equation for a random challenge c becomes computationally infeasible.

This simple algebraic relationship is the foundation for many modern ZKP systems and digital signature schemes.

Start with the Prover’s response

The Verifier gains confidence that the Prover knows x, but never learns x itself.

Why This Is a ZKP?

Imagine recording the conversation.

The transcript contains:

...t...c...s...

Surprisingly, a simulator can generate valid-looking transcripts without knowing x.

Since fake transcripts are statistically indistinguishable from real ones, then the Verifier has learned nothing about x.

This idea, constructing a simulator, is central to the mathematical definition of zero knowledge.

Interactive vs Non-Interactive Proofs

Early ZKPs required interaction:

Required Interaction

Modern systems often remove interaction. That lack of interaction leads to automation, which brings good and bad.

Using the Fiat-Shamir transform, randomness is generated from cryptographic hash functions.

Instead of having a manual step where the Verifier chooses c, we compute:

c = H(transcript)

This converts many interactive proofs into non-interactive proofs.

Arithmetic Circuits

Modern ZKP systems prove much more complicated statements using Arithmetic Circuits.

For example:

I know a valid Bitcoin transaction.

or

I correctly executed a machine-learning model.

The computation is converted into an arithmetic circuit. For example:

z = (a × b) + c

becomes gates:

a ----\       × ----\b ----/       +              \c ------------/

Large programs become enormous circuits with millions of gates. This feels a lot like my digital circuit design course in college.

The ZKP proves “I know inputs satisfying this circuit” without revealing those inputs.

Finite Fields

Modern ZKP systems perform computations over finite fields.

Finite groups and finite fields are closely related, but they are not the same thing. A group gives you one operation (such as addition or multiplication). A field gives you two operations (addition and multiplication) that interact in a well-behaved way. Every finite field contains groups, but not every finite group is a field. A finite group consists of:

• A finite set of elements
• One operation (e.g., multiplication)
• An identity element
• Inverses for every element

A finite field consists of:

• A finite set of elements
• Addition
• Multiplication
• Additive inverses
• Multiplicative inverses (except for zero)

As an example, the field:

contains:

{0,1,2,3,4,5,6}

with addition and multiplication modulo 7 performed.

Every finite field contains two important groups: the Additive Group and the Multiplicative Group. In the Additive Group, all field elements under addition:

Which exists entirely in the set:

{0,1,2,3,4,5,6}

In the Multiplicative Group, all non-zero field elements under multiplication:

Which, again, exists entirely in the set:

{1,2,3,4,5,6}

A finite field contains:

0,1,2,...,p−1

for a prime p. All arithmetic wraps around:

a + b mod pa × b mod p

Finite fields are crucial because they provide algebraic structure while remaining computationally tractable.

Many zk-SNARK systems use primes around 2²⁵⁴ or larger.

Arithmetic circuits are computations expressed using addition and multiplication gates, and those operations are performed over a finite field.

Polynomial Commitments

One of the major breakthroughs behind modern ZKPs is representing computations as polynomials.

Instead of proving millions of constraints individually, the Prover encodes them into polynomial equations.

For example, consider P(x). The Prover commits to P(x) and later proves properties about it without revealing the polynomial itself.

Popular commitment schemes include:

• KZG commitments
• FRI commitments
• Bulletproof commitments

Arithmetic circuits describe the computation, polynomials encode the circuit’s constraints, and polynomial commitments allow the Prover to cryptographically commit to those polynomials and prove they satisfy the required relationships without revealing all of their contents.

Computational Complexity Perspective

From a complexity theory viewpoint:

A ZKP proves membership in a language:

x ∈ L

without revealing the witness:

w

such that:

R(x,w)=1

where R is a polynomial-time verifier.

This abstraction allows ZKPs to prove virtually any efficiently computable statement.

Summary: The Math Is Considered Remarkable

Traditional proofs reveal information.

ZKPs separate knowledge from information disclosure

The mathematics demonstrates that it is possible to convince someone you know a secret, executed a computation, or possess valid credentials while revealing almost nothing else.

This result was so surprising that when the concept was introduced by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the 1980s, it fundamentally changed cryptography. It showed that proving truth and revealing information are not the same thing. This is a distinction that underpins much of modern privacy-preserving cryptography today.

Notes

• AI / GenAI / ChatGPT / etc were not used to generate the text of this article.
• ChatGPT was used to generate the images.
• I used em dashes in my writing before the current GenAI wave was a thing. Not planning on changing now.
• Names have been changed to protect the guilty.
• None of the hostnames or users used in examples actually exist.
• Feel free to post any comments or suggestions below.