Introduction
Welcome to our tutorial on the fundamental mathematics needed for zero-knowledge proofs (zk proofs)! In the world of cryptography and secure computation, zk proofs play a vital role in ensuring privacy, integrity, and trust. Whether you’re a beginner curious about the inner workings of zk proofs or an experienced professional seeking a refresher, this tutorial is designed to provide you with a solid foundation in the mathematical concepts behind zk proofs.
In this tutorial, we will explore the essential mathematical concepts that underpin zk proofs. We will cover topics such as modular arithmetic, number theory, group theory, fields, polynomials and more. By understanding these mathematical foundations, you will gain the necessary tools to comprehend the inner workings of zk proofs and their underlying security guarantees.
Throughout the tutorial, I will strive to provide clear explanations, intuitive examples, and step-by-step demonstrations of mathematical concepts. Please note that a basic understanding of algebra and discrete mathematics will be beneficial for this tutorial. However, I try to provide brief refreshers on key concepts whenever necessary, ensuring that learners of various backgrounds can follow along.
By the end of this tutorial, you will have a solid understanding of the mathematical principles that form the foundation of zk proofs. You will be equipped with the knowledge and confidence to explore advanced topics within the realm of zero-knowledge proofs and contribute to the exciting field of secure computation.
Let’s embark on this mathematical journey together and unlock the fascinating world of zero-knowledge proofs!
Number Theory
First, it’s important to understand the types of numbers and fields
Let’s dive in
1. Integers
Integers are whole numbers, including both positive and negative numbers, as well as zero. They’re denoted as {..., -3, -2, -1, 0, 1, 2, 3, ...}.
Example: The number 5 is an integer.
2. Rational Numbers
Rational numbers are any numbers that can be expressed as a fraction where the numerator and denominator are integers, and the denominator is not zero.
Example: 1/2, 2/3, and 7/1 are all rational numbers.
3. Real Numbers
Real numbers encompass both rational and irrational numbers. Irrational numbers are those that cannot be expressed as a simple fraction, and have non-repeating, non-terminating decimal parts.
Example: 2, -1, 3.14159 (pi), and the square root of 2 are all real numbers.
Modular Arithmetic
Modular arithmetic, also known as clock arithmetic, is a system of arithmetic for integers where numbers “wrap around” after reaching a certain value—the modulus. The primary usage of modular arithmetic is in the implementation of cyclic or circular phenomena.
When we write n mod k, we mean the remainder when n is divided by k. This operation is called the modulus operation. The result of n mod k is the remainder of the Euclidean division (also known as division with remainder) of n by k.
Example:
25 mod 3 means we divide 25 by 3, and then the remainder is our answer. When 25 is divided by 3, the remainder is 1. So, 25 mod 3 = 1.
Similarly, 15 mod 4 means we divide 15 by 4, and the remainder is 3. So, 15 mod 4 = 3.
Note: In this context, the remainder is always non-negative.
Modular Arithmetic in zk-SNARKs
Modular arithmetic plays a crucial role in cryptography, including the concept of zk-SNARKs. In cryptographic algorithms, modular arithmetic is used to ensure that computed values remain within manageable bounds. Also, the properties of modular arithmetic help provide the desired characteristics of cryptographic algorithms, such as the apparent randomness and complexity of the cryptographic keys.
Application in zk-SNARKs
In zk-SNARKs, we use modular arithmetic to create an arithmetic circuit over a finite field. This is a way of expressing a computation such that it can be efficiently verified.
Example:
Consider the computation x * y = z. Let’s say we’re working within a finite field defined by a prime p = 13. In this field, the computation x * y = z would be performed as (x * y) mod p = z. If x = 7, y = 8, the computation would be (7 * 8) mod 13 = 9, so z = 9.
The use of modular arithmetic here allows us to perform computations within a manageable range of values, as defined by the prime p. It also adds an extra layer of complexity to the computation, which is useful from a cryptographic standpoint.
In a zk-SNARK, the prover would provide a proof that they correctly performed this computation without revealing the specific values of x, y, and z. The verifier can then check this proof without having to perform the computation themselves, and without learning anything more about x, y, and z.
Practice questions
If you would like to challenge yourself, here are some practice questions for you.
- Compute the following:
18 mod 730 mod 521 mod 6
- Given a finite field defined by a prime
p = 17, perform the following computations within this field:
(8 * 9) mod 17(15 + 7) mod 17(11 - 4) mod 17
- Consider the computation
x * y = zin the finite field defined by primep = 19. Ifz = 5, can you determine possible values forxandywithout revealing their actual values? - In a zk-SNARK, if a prover wants to prove that they know values
xandysuch that(x * y) mod 23 = 1, how can they provide this proof without revealingxandy?
Group Theory
In mathematics, a group is a set of elements combined with an operation that combines any two of its elements to form a third element satisfying four conditions called the group axioms:
- Closure - If ‘a’ and ‘b’ are members of the group, then the result of the operation, often denoted ‘a*b’ or ‘ab’, is also a member of the group.
- Associativity - If
'a', 'b', and 'c' are members of the group, then(ab)c = a(bc)`. - Identity element - There exists an element ‘e’ in the group such that, for every element ‘a’ in the group, the operations ea and ae both return ‘a’.
- Inverse element - For each element ‘a’ in the group, there exists an element ‘b’ in the group such that ab and ba both equal the identity element ‘e’.
Let’s consider the set of integers under addition. This set forms a group because it satisfies all four group axioms:
- Closure: If you add two integers together, you get another integer.
- Associativity:
(1 + 2) + 3 = 1 + (2 + 3). - Identity element: The number 0 serves as the identity because adding 0 to any integer does not change its value.
- Inverse element: The inverse of any integer ‘n’ is its negation ‘-n’ because
n + (-n) = 0, which is the identity element.
Subgroups
A subgroup is essentially a “group within a group.” Formally, a subgroup H of a group G is a subset of G that is itself a group under the operation of G. To check if a subset H of G is indeed a subgroup, we need to verify that it satisfies the group axioms:
- Closure - If ‘a’ and ‘b’ are in H, then the result of the operation, often denoted ‘a*b’ or ‘ab’, must also be in H.
- Associativity - This axiom is inherited from the larger group G.
- Identity element - The identity element of G must also be in H.
- Inverse element - For each element ‘a’ in H, there must exist an element ‘b’ in H such that ab and ba both equal the identity element.
Let’s consider the set of integers under addition, which we’ve established is a group. Within this group, the set of even integers also forms a group, making it a subgroup. It satisfies the group axioms:
- Closure - Adding two even numbers together always results in another even number.
- Associativity - This property is inherited from the integers.
- Identity element - 0 is the additive identity and is an even number.
- Inverse element - The additive inverse of any even number is also an even number.
Homomorphisms
A homomorphism is a function between two groups that preserves the group operation. If we have a homomorphism ‘f’ from a group G to a group H, and ‘a’ and ‘b’ are elements of G, then f(a * b) = f(a) * f(b)in the group H.
Let’s consider a concrete example. Let G be the group of integers under addition, and let H be the group of even integers under addition. Define a function f: G → H by f(x) = 2x for all x in G. This function is a homomorphism because it preserves the group operation: f(x+y) = 2(x+y) = 2x + 2y = f(x) + f(y).
Isomorphisms
An isomorphism is a homomorphism that also has an inverse function that is a homomorphism. When a group G is isomorphic to a group H, we can think of G and H as being essentially “the same group,” just described in different ways.
For example, consider the group of integers under addition and the group of even integers under addition. The function f(x) = 2x is a homomorphism from the integers to the even integers. Its inverse function g(y) = y/2 is a homomorphism from the even integers to the integers. Therefore, f is an isomorphism, and the group of integers and the group of even integers are isomorphic.
Here is a resource where you can read more about group theory: Group Theory. It provides a comprehensive introduction to the topic, making it an excellent starting point for those new to the theory of groups.
Fields
A field in mathematics is a set of elements that is equipped with two operations: addition and multiplication. These operations must satisfy several properties, including closure, associativity, commutativity, and the presence of additive and multiplicative identities. Additionally, every element (except for zero) should have a multiplicative inverse.
One example of a field is the Real Numbers under addition and multiplication, another is a
set of Integers mod a prime number with addition and multiplication.
The field operations are required to satisfy the following field axioms. In these axioms, a, b
and c are arbitrary elements of the field .
- Associativity of addition and multiplication:
a + (b + c) = (a + b) + c and a · (b · c) = (a · b)· c. - Commutativity of addition and multiplication:
a + b = b + a and a · b = b · a. - Additive and multiplicative identity: there exist two different elements 0 and 1 in
such thata + 0 = a and a · 1 = a. - Additive inverses: for every a in F, there exists an element in F, denoted −a, called
the additive inverse of a, such thata + (−a) = 0. - Multiplicative inverses: for every a ≠ 0 in F, there exists an element in F, denoted by
, called the multiplicative inverse of a, such that a · = 1. - Distributivity of multiplication over addition:
a · (b + c) = (a · b) + (a · c).
Finite Fields and Generators
A finite field is a field with a finite set of elements, such as the set of integers mod p where
p is a prime.
To try out operations on finite fields, see Here
The order of the field is the number of elements in the fieldʼs set.
For a finite field the order must be either
- prime ( a prime field)
or - the power of a prime (an extension field)
An element can be represented as an integer greater or equal than 0 and less than the
fieldʼs order: {0, 1, ..., p-1} in a simple field.
Every finite field has a generator. A generator is capable of generating all of the elements in the set by exponentiating the generator .
So for generator g we can take g^0, g^1, g^2 and eventually this will give us all elements in the
group
For example. taking the set of integers and prime p = 5, we get the group Z5= {0,1,2,3,4}.
In the group Z5 , operations are carried out modulo 5; hence, we donʼt have 3 × 4 = 12 but
instead have 3 × 4 = 2, because 12 mod 5 = 2.
- In a finite field of order
p, the polynomialx^p - xhas all elements of the finite field as roots
Example: Z_5
- Exponent 2
1^2 - 1 = 22^2 - 2 = 43^2 - 3 = 34^2 - 4 = 1
- Exponent 3
1^3 - 1 = 32^3 - 2 = 43^3 - 3 = 24^3 - 4 = 1
Group Homomorphism
A homomorphism is a map between two algebraic structures of the same type, that
preserves the operations of the structures.
This means a map f : -> B between two groups A, B equipped with the same structure
such that, if * is an operation of the structure (here a binary operation), then
To try out operations on finite fields, see Finite fields
For a great introduction see ZK-Snarks and Their Algebraic Structure - Part 1 • Coder's Errandstructure/
Polynomials
A polynomial is a type of mathematical expression involving a sum of powers in one or more variables multiplied by coefficients. The simplest polynomials have one variable. Here are some examples:
2x^2 + 3x + 1is a polynomial. It’s also called a quadratic polynomial because the highest power is 2.5x^3 - x^2 + 7is another polynomial. This one is a cubic polynomial because the highest power is 3.
Polynomials are a single mathematical object that can contain an unbounded amount of information.
Furthermore, a single equation between polynomials can represent an unbounded
number of equations between numbers.
For example, consider the equation A(x)+B(x)=C(x). If this equation is true, then it’s also
true that:
A(0)+B(0)=C(0)A(1)+B(1)=C(1)A(2)+B(2)=C(2)A(3)+B(3)=C(3)
Adding, multiplying and dividing polynomials
We can add, multiply and divide polynomials, for examples
see here
Roots
For a polynomial P(x) of a single variable in a field and with coefficients in that field, the root r of P is an element of such that P(r) = 0.
P is said to divide another polynomial B when the latter can be written as B = A*C with C also a polynomial. The fact that A divides B is denoted A|B.
If one root r of a polynomial P(x) of degree n is known, then polynomial long division can be used to factor P(x) into the form (x - r)(Q(x)) where Q(x) is a polynomial of degree n - 1. Q(x) is simply the quotient obtained from the division process; since r is known to be a root of P(x), it is known that the remainder must be zero.
Schwartz-Zippel Lemma
The Schwartz-Zippel Lemma is a fundamental principle in computer science and mathematics that provides a method for testing whether a polynomial is identically zero. Specifically, it states that if you have a non-zero polynomial in one or more variables, and you substitute each variable with a randomly chosen number from a sufficiently large set, then the probability that the polynomial evaluates to zero is at most the degree of the polynomial divided by the size of the set from which numbers are chosen. This lemma is particularly useful in algorithms for symbolic computation and error detection, as it offers an efficient probabilistic method for testing polynomial identities.
different polynomials are different at most points.
Polynomials have an advantageous property, which is, if we have two non-equal
polynomials of degree at most d, they can intersect at no more than d points.
Lagrange Interpolation
Lagrange Interpolation is a method of constructing a polynomial that passes through a given set of points. The goal is to find a single polynomial that accurately represents the given data points. The Lagrange polynomial is the polynomial of the least degree that passes through each data point in the set. The formula for the Lagrange polynomial is a linear combination of Lagrange basis polynomials, where each basis polynomial is constructed such that it equals 1 at the corresponding data point and 0 at all other data points. The Lagrange Interpolation method is widely used in numerical analysis and computer science for approximating functions and solving differential equations.
If you have a set of points, then doing a Lagrange interpolation on those points gives you a polynomial that passes through all of those points.
If you have two points on a plane, you can define a single straight line that passes through both. For 3 points, a single 2nd-degree curve (e.g. y = ax^2 + bx + c) will go through them, etc.
For n points, you can create an n-1 degree polynomial that will go through all of the points.
(This concept can be used in all sorts of interesting schemes as well as Zero-Knowledge Proofs (zkps))
Cryptography Background
Hash Function Diagram
- A hash function takes an input (or ‘message’) and returns a fixed-size string of bytes, typically a hash value.
- The output is unique to the specific input; a small change in input will produce such a drastic change in output that the new hash value appears random.
- Despite the randomness, the hash function is deterministic—meaning that the same input will always provide the same hash output.
- It is computationally infeasible to reverse-engineer the original input value from its hash, making hash functions useful in various applications like data integrity checks and passwords storing.
Encryption
Symmetric Encryption
Symmetric encryption is a method of encryption where the same key is used for both the encryption and decryption of the data. The sender uses the key to encrypt the plaintext and sends the ciphertext to the receiver. The receiver then uses the same key to decrypt the ciphertext and retrieve the original plaintext.
Asymmetric Encryption
Sending a secret message
Asymmetric encryption, also known as public-key cryptography, is a method of encryption that uses a pair of keys: a public key, which is shared openly, and a private key, which is kept secret. When a sender wants to encrypt a message, they use the recipient’s public key. Upon receipt, the message can only be decrypted using the corresponding private key. This system allows secure communication even over insecure channels, as the decryption key is never shared.
Elliptic Curves
Elliptic curves are a type of mathematical structure defined by a specific type of equation, typically written in the form 
where a and b are constants. These curves have unique properties that make them useful in a variety of mathematical disciplines, but they are particularly important in the field of cryptography. In the context of cryptography, the discrete logarithm problem on elliptic curves is significantly harder to solve than its equivalent in the realm of integers. This means that cryptographic systems based on elliptic curves can provide the same security as traditional systems with a much smaller key size, making them more efficient. Moreover, elliptic curves over finite fields are used, providing a group structure for protocols that require one, such as elliptic curve digital signature algorithm (ECDSA) and elliptic curve Diffie-Hellman key exchange.
The defining equation for an elliptic curve is for example:
For certain equations they will satisfy the group axioms:
- Every two points can be added to give a third point (closure);
- It does not matter in what order the two points are added (commutatitivity);
- If you have more than two points to add, it does not matter which ones you add first
either (associativity); - There is an identity element
We often use 2 families of curves : Montgomery and Edwards Curves in zero knowledge.
Montgomery Curves
Montgomery curves are a form of elliptic curves used in cryptography, particularly in the implementation of elliptic curve cryptography (ECC) algorithms. Named after Peter L. Montgomery, they are defined by the equation:
over a field, where
A and B are constants with B not equal to 0. Montgomery curves have the property that the computation of the elliptic curve point multiplication, a fundamental operation in ECC, can be implemented more efficiently by using Montgomery ladder, a method that has resistance against side-channel attacks. This makes them advantageous in cryptographic applications where both security and computational efficiency are critical.
For example curve 25519 with equation 
Curve 25519 gives 128 bits of security and is used in the Diffie–Hellman (ECDH) key
agreement scheme
BN254 / BN_128 is the curve used in Ethereum for ZKSNARKS
BLS12-381 is the curve used by ZCash.
Edward Curves
image from From Serious Cryptography Jean-Philippe Aumasson
Edwards Curves are a type of elliptic curve which are used in the field of public key cryptography. They are named after Harold Edwards, who introduced them in 2007. The defining equation for an Edwards curve is 
for some non-zero element d of the field that is not equal to 1. These curves have complete addition laws, which means that there are no exceptional cases to deal with when performing point addition. This makes them easier and safer to implement in cryptographic software, and also allows for more efficient arithmetic operations. In addition, they are naturally resistant to several types of side-channel attacks, making them a good choice for secure applications.
The general equation is 
with a = 1
for some scalar d which can be 0 or 1.
If a <> 1 they are called Twisted Edwards Curves
Every twisted Edwards curve is birationally equivalent to a Montgomery curve.
Verifiable Random Functions
A VRF is a function that, given an input, produces a random output. However, unlike a typical random function, a VRF also produces a proof that the output was generated correctly from the given input. This makes VRFs useful in situations where it’s important to be able to verify that a particular output was not just randomly chosen, but was actually generated by the function in a specific, reproducible way. This property of VRFs is often used in consensus protocols, such as those used in some blockchain systems, where the randomness needs to be unpredictable but also verifiable.
Main steps
- Key Generation: The user generates a pair of RSA keys, (e, n) as public key and (d, n) as private key. The public key e is the exponent, and n is the modulus. The private key d is the secret exponent.
- Computation: Given an input x, the user computes the VRF output y and the proof π as follows:
- Compute the hash h = H(x), where H is a cryptographic hash function.
- Compute the output y = h^d mod n. This is the RSA signature of the hash.
- Compute the proof π = (h, y). This is simply the pair of the hash and the signature.
- Verification: Given the public key (e, n), the input x, the output y, and the proof π = (h, y), anyone can verify the correctness of the VRF output as follows:
- Check that the hash h equals H(x). This ensures that the correct input was used.
- Check that y^e = h mod n. This is the RSA verification equation. It ensures that y is the correct RSA signature of the hash.
The security of this VRF scheme relies on the RSA assumption, which says that it’s hard to compute y = h^d mod n without knowing the secret exponent d, and on the security of the hash function H, which should behave like a random function.
Read More About VRFs Here
Conclusion
Congratulations! You have successfully completed our tutorial on the basic mathematics needed for zk proofs. I hope this journey through the mathematical foundations of zero-knowledge proofs has been enlightening and empowering for you.
Don’t forget to practice your newfound mathematical skills regularly. Solving additional problems and exploring real-world examples will help solidify your understanding and prepare you for more complex challenges.
We encourage you to continue your exploration of topics on zk proofs. If you’re interested in diving deeper, you can follow up on the pathway here Zero-Knowledge Proofs on the Celo Blockchain: A Comprehensive Tutorial Series - Pathways - Celo Academy
About the author
I’m Jonathan Iheme, A full stack block-chain Developer from Nigeria. With a great passion for Zero Knowledge Technology.
