From Zero to Hero in Zero Knowledge Proofs [Part 3]

This is the third part of the series that takes you from absolute ground zero in ZKPs to a fairly advanced level. We will start from the absolute basics and then move onward and upward. Subscribe to get regular updates!

Building up on our previous maths refresher lesson, we will now double down on the maths part and get done with it before moving on to more interesting ZKP concepts.

Fields

A field is any set of elements that satisfies the field axioms for both addition and multiplication and is a commutative division algebra.

In simple terms, think of a field as a set of elements together with two operations called addition and multiplication that satisfy the following properties (also called field axioms).

The field operations are required to satisfy the following field axioms. In these axioms, a, b, and c are arbitrary elements of the field F.

1. Associativity of Addition and Multiplication: a + (b + c)= (a + b) + c and a · (b · c) = (a ·b) · c
2. Commutativity of addition and multiplication: a +b = b + a and a · b = b · a
3. Additive and multiplicative identity: There exist two different elements 0 and 1 in F such that a + 0 = a and a · 1 = a
4. Additive Inverses: For every a in F, there exists an element in F, denoted −a, called the additive inverse of a such that a + (−a) = 0
5. Multiplicative Inverses: For every a≠ 0 in F, there exists an element in F, denoted by a-1, called the multiplicative inverse of a such that a · a-1 = 1
6. Distributivity of multiplication over addition: a· (b + c) = (a · b) + (a · c)

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.

Finite fields

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.

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 than or equal to 0 and less than the field’s order: Zp={0, 1, …, p-1} in a simple field.

An extension of Zp is the multiplicative group of Zp , written Zp*, and contains the elements coprime to p.

So, where Zp = {0, 1, … p-1}

Zp* = {1, …, p-1}

Generators of finite fields

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 g0, g1, and g2, 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} and Z5*= {1, 2, 3, 4}.

In the group Z5*, where the binary operator is multiplication(*) and operations are carried out modulo 5; we don’t have 3 × 4 = 12 but instead, we have 3 × 4 = 2, because 12 mod 5 = 2.

Z5* is cyclic and has two generators, 2 and 3, because:

2^0 = 1,

2^1 = 2,

2^2= 4,

2^3 = 3,

2^4 = 1 -> cycle starts again

and

3^0 = 1,

3^1= 3,

3^2 = 4,

3^3 = 2,

3^4 = 1 -> cycle starts again

Group homomorphisms

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: A-> 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:

f(x⋅y)=f(x)⋅f(y)

The complexity of algorithms: Big-O notation

Big O notation describes the complexity of your code using algebraic terms. It describes the time or space required to solve a problem in the worst case in terms of the size of the input.

An algorithm’s Big-O notation is determined by how it responds to different sizes of a given dataset. For instance how it performs when we pass to it 1 element vs 10,000 elements.

For example, if we say for input size n, the time complexity is O(n2), we are saying that as n increases, the time taken to solve the problem goes up proportional to the square of n.

Similarly, if we say for input size n, the space complexity is O(n), we are saying that as n increases, the space taken to solve the problem goes up proportional to n.

Visual representation of various algorithmic complexities

This notation is important to compare the performance of various algorithms.

Polynomials

A polynomial is an expression that can be built from constants and variables by means of addition, multiplication, and exponentiation to a non-negative integer power.

For example, 5x2+2x+8 is a polynomial.

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)

and so on.

Degree of a polynomial

A polynomial’s degree is the highest or the greatest power of a variable in a polynomial equation. For example: 6x4 + 2x3+ 3 is a polynomial. The degree of this polynomial is 4.

How do we use polynomials in zero-knowledge proofs?

In zero-knowledge proofs, there is always a prover who wants to prove something to the verifier.

If a prover claims to know some polynomial (no matter how large its degree is) that the verifier also knows, they can follow a simple protocol to verify the statement:

• The verifier chooses a random value for x and evaluates his polynomial locally
• The verifier gives x to the prover and asks to evaluate the polynomial in question
• The prover evaluates her polynomial at x and gives the result to the verifier
• The verifier checks if the local result is equal to the proverʼs result, and if so then the statement is proven with a high confidence

The above is a simplified example of how polynomials are used in zero-knowledge proofs.

With this, we end our mathematics refresher for understanding zero-knowledge proofs.

If you want to test out your knowledge of this lesson, try out this quiz!

In the next section, we will discuss some mental models to understand what ZKPs are using ELI5 (Explain like I’m 5) examples. Stay tuned!

Hey there, thanks for reading this far. If you liked this article, don’t forget to follow and leave a clap.

I am building Plurality Network, the user context layer on web3. Join our discord to get alpha!

Follow me here, on LinkedIn, on X, or on Farcaster to get the latest blockchain technical content in simple, bite-sized reads.