Foundations

Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zkSNARKs) may sound intimidating at first, but they're built from just a handful of elegant mathematical and cryptographic tools. In this first module, we'll explore five key concepts that form the foundation of zkSNARKs.

By the end, we won't yet know how to build a zkSNARK, but we will understand the language and foundations on which they are constructed.

All Rust snippets in this module come from the companion repository github.com/bsaepfl/zksnarks-101-labs. Clone it locally if you want to run, tweak, or extend the code yourself — every cell on this page is pre-executed with the output shown directly below it.

1. Hash Functions

Before we build advanced cryptographic protocols, we need a way to deal with information securely. Imagine you want to prove that you know a secret — without actually revealing it. How can you share something about your secret, while keeping it safe? This is where hash functions come in.

A hash function is a mathematical function that takes any input and produces a fixed-size output, called a digest. Formally:

This means: it takes inputs of any length and returns a string of fixed length $n$.

Key Properties

To be useful in cryptography, a hash function must satisfy:

1. Deterministic — the same input always gives the same output.
2. One-way — given the output, it should be infeasible to recover the input.
3. Collision-resistant — it should be hard to find two different inputs that produce the same output.

Here is an example of hashing a message using SHA-256:

Internally, hash functions break input into blocks, mix bits with nonlinear operations (XOR, shifts, modular addition), and repeat rounds of transformations. The exact math depends on the algorithm (MD5, SHA-1, SHA-2, SHA-3), but the core idea is to scramble the input so thoroughly that reversing the process is practically impossible.

Since the digest is 256 bits long, there are $2^{256}$ different possible digests — approximately the number of atoms in the universe. The probability of a collision is negligible.

Everyday Uses

• Passwords: websites store the digest of your password, not the password itself.
• File integrity: a hash check after download verifies the file was not corrupted.
• Digital Signatures (covered later in this module).

2. Finite Fields & Modular Arithmetic

Cryptography relies on arithmetic where every operation behaves predictably. Two foundational tools are modular arithmetic and finite fields.

Modular Arithmetic: Numbers That Wrap Around

Modular arithmetic is a type of arithmetic where numbers wrap around after reaching a certain value called the modulus. Think of it like a clock: after 12 comes 1.

Example (modulus 7):

• $5 + 4 = 9 \equiv 2 \pmod{7}$
• $3 \times 5 = 15 \equiv 1 \pmod{7}$

All results are “folded back” into the range from 0 up to $n-1$. This gives rise to powerful properties:

• Commutativity: $a+b \equiv b+a$ and $a \cdot b \equiv b \cdot a \pmod{n}$
• Associativity: $(a+b)+c \equiv a+(b+c) \pmod{n}$
• Distributivity: $a \cdot (b+c) \equiv a \cdot b + a \cdot c \pmod{n}$
• Modular exponentiation: $(a \bmod n)^m \equiv a^m \bmod n$

Modular exponentiation is particularly important in cryptography because it lets us compute large powers efficiently, reducing numbers modulo $n$ at each step.

Finite Fields: A Safe Playground for Arithmetic

A field is a set of numbers where we can perform addition, subtraction, multiplication, and division (except by zero), and every operation behaves predictably. A finite field has a finite number of elements:

Here, $p$ is a prime number, and all arithmetic is done modulo $p$.

Key properties:

1. Additive inverses: For any $a \in \mathbb{F}_p$, there exists $-a$ such that $a + (-a) = 0$
2. Multiplicative inverses: For any nonzero $a \in \mathbb{F}_p$, there exists $a^{-1}$ such that $a \cdot a^{-1} = 1$

Example in $\mathbb{F}_7$:

• $3 + 6 = 2$
• $2 \cdot 4 = 1$
• Multiplicative inverse: $3^{-1} = 5$ because $3 \cdot 5 \equiv 1 \pmod{7}$

Computing Inverses: Extended Euclidean Algorithm

For small fields, we could try each number. But for large fields (hundreds of bits), we need the Extended Euclidean Algorithm (EEA), which finds coefficients $x$ and $y$ satisfying:

When $\gcd(a, p) = 1$ (always true in a prime field), the coefficient $x$ is exactly the modular inverse of $a$.

Generators & the Discrete Logarithm Problem

A generator $g \in \mathbb{F}_p^\times$ is a special element such that every nonzero element can be expressed as a power of $g$. Once we have a generator, we can define the Discrete Logarithm Problem (DLP):

Given $p$, $g$, and $y \in \mathbb{F}_p^\times$, find $x$ such that $g^x \equiv y \pmod{p}$.

Computing $y = g^x \bmod p$ is easy. Determining $x$ from $y$ is computationally hard. This asymmetry is the foundation of cryptographic primitives like key exchange and digital signatures.

3. Polynomials over Finite Fields

Polynomials over finite fields are a backbone of modern cryptography. They let us encode data robustly, split and reconstruct secrets, and reason about algebraic structures used in protocols.

A polynomial over a field $\mathbb{F}$ has the form:

We can perform operations on these polynomials (addition coefficient-wise, multiplication). The coefficients “wrap around” — they are reduced mod $p$.

Lagrange Interpolation

A polynomial of degree $n-1$ is uniquely identified by $n$ evaluation points. Lagrange Interpolation is the way to recover the polynomial from those points.

Given points $(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)$:

1. Build basis polynomials $L_i(x)$ that equal 1 at $x_i$ and 0 at all other points:
   $$L_i(x) = \frac{\prod_{m \neq i} (x - x_m)}{\prod_{m \neq i} (x_i - x_m)}$$
2. Scale each by its value and sum:
   $$P(x) = \sum_{i=1}^n y_i \cdot L_i(x)$$

The following demo uses arkworks's dense and sparse polynomial types to evaluate, differentiate, and cross-check the polynomial $f(x) = 4x^5 + 2x^2 + 3x + 1$ at $x = 3$:

Secret Sharing (Shamir)

Hide a secret $s$ as the constant term of a polynomial:

Give $n$ people their “share” $(i, P(i))$. At least $t$ of them must collaborate to recover the secret via Lagrange interpolation. Fewer than $t$ shares reveal nothing.

Error Correcting Codes (Reed-Solomon)

Encode a message of $k$ symbols as a polynomial, then send $n$ evaluation points. Even if some symbols are lost, Lagrange interpolation can recover the original. This is how CDs and DVDs protect against scratches.

The following demo Reed-Solomon-encodes the message $m = [2, 1, 4]$ (i.e. $m(x) = 2 + x + 4x^2$) over 5 points, then recovers the original polynomial from only the first 3 symbols using a generic Lagrange interpolation routine:

4. Pseudo-Random Number Generators

Cryptography thrives on randomness — from generating secret keys to creating nonces. But computers are deterministic machines. PRNGs stretch a small seed into a long sequence that looks random.

True vs Pseudo vs Cryptographically Secure

• TRNGs: Based on physical phenomena (thermal noise, radioactive decay). Truly unpredictable but slow.
• PRNGs: Algorithms that expand a seed. Same seed → same sequence.
• CSPRNGs: PRNGs where no efficient attacker can predict the next bit, recover the seed, or rewind the sequence.

Classic PRNGs

Linear Congruential Generator:

Simple, fast — but predictable. Good for games, not for crypto.

AES in Counter Mode (AES-CTR): Encrypt an incrementing counter with a secret key. Each output block is a pseudorandom number:

Hash-based (DRBGs): Same idea, using a hash function:

Exercise: LCG

Generate the first 10 values of an LCG with $m=16, a=5, c=3, X_0=7$:

5. Elliptic Curves

Elliptic curves are one of the most elegant tools in modern cryptography. For crypto, an elliptic curve is defined by:

where $p$ is a large prime, and $a$, $b$ are parameters. The solutions $(x, y)$plus a special “point at infinity” form a group.

Adding Points (The Group Law)

1. Draw the line through $P$ and $Q$.
2. Find the third intersection point $R$ with the curve.
3. Reflect $R$ across the x-axis: this is $P+Q$.

Scalar Multiplication & ECDLP

• Easy: Given $P$ and $k$, computing $Q = kP$ is efficient.
• Hard: Given $P$ and $Q$, finding $k$ is believed to be hard. This is the Elliptic Curve Discrete Logarithm Problem (ECDLP).

Diffie–Hellman on Curves

• Alice picks $a$, computes $A = aP$.
• Bob picks $b$, computes $B = bP$.
• Shared secret: $S = aB = abP = bA$.

Pairings: The Bridge to zkSNARKs

For zkSNARKs, we need a bilinear map (pairing):

with the property:

This allows us to multiply values in the exponent— performing multiplication on encrypted data. It allows us to encode polynomial relationships and verify them efficiently. That's why pairing-friendly elliptic curves (like BLS12-381) are used in zkSNARKs.

Exercise: Point Check

Verify if $(2, 4)$ lies on the curve $y^2 = x^3 + 2x + 2 \pmod{17}$:

Summary

We now have the mathematical bedrock for the sophisticated cryptographic structures we will assemble in the next modules.