Maths Primer for Zero Knowledge Workshop
Terminology
Numbers
The set of Integers is denoted by ℤ$\mathbb{Z}$ e.g. {⋯,−4,−3,−2,−1,0,1,2,3,4,⋯}
The set of Rational Numbers is denoted by ℚ$\mathbb{Q}$ e.g. {...1,32,2,227...}$\{...1,\frac{3}{2},2,\frac{22}{7}...\}$
The set of Real Numbers is denoted by ℝ$\mathbb{R}$ e.g. {2,−4,613,π,2‾√,…}$\{2,4,613,\pi ,\sqrt{2},\dots \}$
Fields are denoted by 𝔽$\mathbb{F}$, if they are a finite field or 𝕂$\mathbb{K}$ for a field of real or complex numbers we also use ℤ∗𝑝${\mathbb{Z}}_{p}^{\ast}$ to represent a finite field of integers mod prime p with multiplicative inverses, these concepts will be explained further later.
We use finite fields for cryptography, because elements have “short”, exact representations.
Modular Arithmetic
When we write n mod k we mean simply the remainder when n is dividedby k. Thus
25 = 1 mod 3,
15 = 3 mod 4,
−13 =−3 mod 5 = 2 mod 5.
It is an important fact that modular arithmetic respects sums and products.
That is,
a+b mod n = a mod n+ b mod n
and
a·b mod n=(a mod n)·(b mod n)
Group Theory
Simply put a group is a set of elements {a,b,c,…} plus a binary operation, here we represent this as •
To be considered a group this combination needs to have certain properties
 Closure
For all a, b in G, the result of the operation, a • b, is also in G
 Associativity
For all a, b and c in G, (a • b) • c = a • (b • c)
 Identity element
There exists an element e in G such that, for every element a in G, the equation e • a = a • e = a holds. Such an element is unique and thus one speaks of the identity element.
 Inverse element
For each a in G, there exists an element b in G, commonly denoted 𝑎−1${a}^{1}$ (or −a, if the operation is denoted “+”), such that a • b = b • a = e, where e is the identity element.
Fields
Formally, a field is a set of say Integers together with two operations called addition and multiplication.
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 𝔽$\mathbb{F}$.
 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 𝔽$\mathbb{F}$ such that a + 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 that a + (−a) = 0.
 Multiplicative inverses: for every a ≠ 0 in F, there exists an element in F, denoted by 𝑎−1${a}^{1}$, called the multiplicative inverse of a, such that a ·𝑎−1${a}^{1}$ = 1.
 Distributivity of multiplication over addition: a · (b + c) = (a · b) + (a · c).
To try out operations on finite fields, see https://asecuritysite.com/encryption/finite
For a great introduction see http://coderserrand.com/zksnarksandtheiralgebraicstructure/
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 the power of a prime (an extension field)
In the simpler case, an element can be represented as an integer greater or equal than 0 and less than the field’s order: {0, 1, …, p1}.
When a finite field has a nonprime (ie ‘composite’) order its elements can be represented as polynomials, and the field is called an extension field.
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\to B$ between two groups A, B equipped with the same structure such that,
if ⋅$\cdot $ is an operation of the structure (here a binary operation), then
𝑓(𝑥⋅𝑦)=𝑓(𝑥)⋅𝑓(𝑦)$f(x\cdot y)=f(x)\cdot f(y)$
Polynomials
A polynomial is an expression that can be built from constants and variables by means of addition, multiplication and exponentiation to a nonnegative integer power.
e.g. 3𝑥2+4𝑥+3$3{x}^{2}+4x+3$
Lagrange Interpolation
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 2nddegree curve (e.g. 5𝑥2+2𝑥+1$5{x}^{2}+2x+1$) will go through them etc.
For n points, you can create a n1 degree polynomial that will go through all of the points.
Adding, multiplying and dividing polynomials
We can add, multiply and divide polynomials, we don’t need to go onto the details here, for examples see https://en.wikipedia.org/wiki/Polynomial_arithmetic
For a polynomial 𝑃$P$ of a single variable 𝑥$x$ in a field 𝐾$K$ and with coefficients in that field, the root 𝑟$r$ of 𝑃$P$ is an element of 𝐾$K$ such that 𝑃(𝑟)=0$P(r)=0$
𝐵$B$ is said to divide another polynomial 𝐴$A$ when the latter can be written as
𝐴=𝐵𝐶$A=BC$
with C also a polynomial,the fact that 𝐵$B$ divides 𝐴$A$ is denoted 𝐵𝐴$BA$
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
(𝑥−𝑟)(𝑄(𝑥))$(xr)(Q(x))$
where
𝑄(𝑥)$Q(x)$ is a polynomial of degree 𝑛−1$n1$.
𝑄(𝑥)$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.
SchwartzZippel Lemma stating that “different polynomials are different at most points”.
Elliptic Curves
The defining equation for an elliptic curve is for example 𝑦2=𝑥3+𝑎𝑥+𝑏${y}^{2}={x}^{3}+ax+b$
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 Curves
For example curve 22519 with equation 𝑦2=𝑥3+486662𝑥2+𝑥${y}^{2}={x}^{3}+486662{x}^{2}+x$
Generally this curve is considered over a finite field 𝕂$\mathbb{K}$ (with order different from 2)
BN254 / BN_128 is the curve used in Ethereum for ZKSNARKS
BLS12381 is the curve used by ZCash
Edwards Curves
The general equation is 𝑎𝑥2+𝑦2=1+𝑑𝑥2𝑦2$a{x}^{2}+{y}^{2}=1+d{x}^{2}{y}^{2}$ with a = 1
If a <> 1 they are called Twisted Edwards Curves
Every twisted Edwards curve is birationally equivalent to a Montgomery curve
Pairings
Bilinear pairings are functions that take two arguments and return one output, usually denoted by
e(G1, G2) > GT.
A bilinear pairing is a function e: G1 x G2 > GT with the following properties:

Order:All three groups must have order equal to a prime r.

Efficiency: the pairing function must be efficiently computable.

Bilinearity: For any elements P1, P2 of G1 and any elements Q1, Q2 of G2, the following holds true:
e(P1 + P2, Q1) = e(P1, Q1) e(P2, Q1)
e(P1, Q1 + Q2) = e(P1, Q1) e(P1, Q2)
This implies the following form, which is more often used (along with some other variants):
e(aP, bQ) = e(P,Q)ab = e(bP, aQ)

Nondegeneracy: the pairing of the generators of the first two groups is not the identity of the third group. If this were the case, every pairing would result in the same (the identity) element of GT:
e(E1, E2) != 1T
G2 is an elliptic curve, where points satisfy the same equation as G1, except where the coordinates are elements of 𝐹𝑝12${F}_{{p}^{12}}$ (this is an extension field, where the elements of the field are polynomials of degree 12)
Gt is the type of object that the result of the elliptic curve goes into. In the curves that we look at, Gt is also 𝐹𝑝12${F}_{{p}^{12}}$
Complexity Theory
Complexity theory looks at the time or space requirements to solve a problem, particularly in terms of the size of the input.
We can classify problems according to the time required to find a solution, for some problems there may exist an algorithm to find a solution in a reasonable time, whereas for other problems we may not know of such an algorithm, and may have to ‘brute force’ a solution, trying out all potential solutions until one is found.
For example the travelling salesman problem tries to find the shortest route for a salesman required to travel between a number of cities, visiting every city exactly once. For a small number of cities, say 3, we can quickly try all alternatives to find the shortest route, however as the number of cities grows, this quickly becomes unfeasible.
Based on the size of the input n , we classify problems according to how the time required to find a solution grows with n.
If the time taken in the worst case grows as a polynomial of n, that is roughly proportional to 𝑛𝑘${n}^{k}$ for some value k, we put these problems in class P. These problems are seen as tractable.
We are also interested in knowing how long it takes to verify a potential solution once it has been found.
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself.
https://en.wikipedia.org/wiki/Computational_complexity_theory
Decision Problem: A problem with a yes or no answer
Complexity Classes
P
P is a complexity class that represents the set of all decision problems that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.
NP
NP is a complexity class that represents the set of all decision problems for which the instances where the answer is “yes” have proofs that can be verified in polynomial time.
This means that if someone gives us an instance of the problem and a witness to the answer being yes, we can check that it is correct in polynomial time.
NPComplete
NPComplete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.
Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances
x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes
NPhard
Intuitively, these are the problems that are at least as hard as the NPcomplete problems. Note that NPhard problems do not have to be in NP, and they do not have to be decision problems.
The precise definition here is that a problem X is NPhard, if there is an NPcomplete problem Y, such that Y is reducible to X in polynomial time.
But since any NPcomplete problem can be reduced to any other NPcomplete problem in polynomial time, all NPcomplete problems can be reduced to any NPhard problem in polynomial time. Then, if there is a solution to one NPhard problem in polynomial time, there is a solution to all NP problems in polynomial time.
Homomorphic Encryption
Homomorphic encryption is a form of encryption with an additional evaluation capability for computing over encrypted data without access to the secret key. The result of such a computation remains encrypted. Homomorphic encryption can be viewed as an extension of either symmetrickey or publickey cryptography. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought as homomorphisms between plaintext and ciphertext spaces.
Bitcoin splitkey vanity mining
Bitcoin addresses are hashes of public keys from ECDSA key pairs. A vanity address is an address generated from parameters such that the resultant hash contains a humanreadable string (e.g., 1BoatSLRHtKNngkdXEeobR76b53LETtpyT). Given that ECDSA key pairs have homomorphic properties for addition and multiplication, one can outsource the generation of a vanity address without having the generator know the full private key for this address.
For example,
Alice generates a private key (a) and public key (A) pair, and publicly posts A.
Bob generates a key pair (b, B) such that hash(A + B) results in a desired vanity address. He sells b and B to Alice.
A, B, and b are publicly known, so one can verify that the address = hash(A + B) as desired.
Alice computes the combined private key (a + b) and uses it as the private key for the public key (A + B).
Similarly, multiplication could be used instead of addition.
Maths Primer for Zero Knowledge Workshop
Terminology
Numbers
The set of Integers is denoted byℤ $\mathbb{Z}$ e.g. {⋯,−4,−3,−2,−1,0,1,2,3,4,⋯}ℚ $\mathbb{Q}$ e.g. {...1,32,2,227...} $\{...1,\frac{3}{2},2,\frac{22}{7}...\}$ℝ $\mathbb{R}$ e.g. {2,−4,613,π,2‾√,…} $\{2,4,613,\pi ,\sqrt{2},\dots \}$
The set of Rational Numbers is denoted by
The set of Real Numbers is denoted by
Fields are denoted by𝔽 $\mathbb{F}$, if they are a finite field or 𝕂 $\mathbb{K}$ for a field of real or complex numbers we also use ℤ∗𝑝 ${\mathbb{Z}}_{p}^{\ast}$ to represent a finite field of integers mod prime p with multiplicative inverses, these concepts will be explained further later.
We use finite fields for cryptography, because elements have “short”, exact representations.
Modular Arithmetic
When we write n mod k we mean simply the remainder when n is dividedby k. Thus
25 = 1 mod 3,
15 = 3 mod 4,
−13 =−3 mod 5 = 2 mod 5.
It is an important fact that modular arithmetic respects sums and products.
That is,
a+b mod n = a mod n+ b mod n
and
a·b mod n=(a mod n)·(b mod n)
Group Theory
Simply put a group is a set of elements {a,b,c,…} plus a binary operation, here we represent this as •
To be considered a group this combination needs to have certain properties
For all a, b in G, the result of the operation, a • b, is also in G
For all a, b and c in G, (a • b) • c = a • (b • c)
There exists an element e in G such that, for every element a in G, the equation e • a = a • e = a holds. Such an element is unique and thus one speaks of the identity element.
For each a in G, there exists an element b in G, commonly denoted
Fields
Formally, a field is a set of say Integers together with two operations called addition and multiplication.𝔽 $\mathbb{F}$.
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
To try out operations on finite fields, see https://asecuritysite.com/encryption/finite
For a great introduction see http://coderserrand.com/zksnarksandtheiralgebraicstructure/
The order of the field is the number of elements in the field’s set.
For a finite field the order must be either
or
In the simpler case, an element can be represented as an integer greater or equal than 0 and less than the field’s order: {0, 1, …, p1}.
When a finite field has a nonprime (ie ‘composite’) order its elements can be represented as polynomials, and the field is called an extension field.
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\to B$ between two groups A, B equipped with the same structure such that,
if⋅ $\cdot $ is an operation of the structure (here a binary operation), then
𝑓(𝑥⋅𝑦)=𝑓(𝑥)⋅𝑓(𝑦) $f(x\cdot y)=f(x)\cdot f(y)$
Polynomials
A polynomial is an expression that can be built from constants and variables by means of addition, multiplication and exponentiation to a nonnegative integer power.
e.g.3𝑥2+4𝑥+3 $3{x}^{2}+4x+3$
Lagrange Interpolation
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 2nddegree curve (e.g.5𝑥2+2𝑥+1 $5{x}^{2}+2x+1$) will go through them etc.
For n points, you can create a n1 degree polynomial that will go through all of the points.
Adding, multiplying and dividing polynomials
We can add, multiply and divide polynomials, we don’t need to go onto the details here, for examples see https://en.wikipedia.org/wiki/Polynomial_arithmetic
For a polynomial𝑃 $P$ of a single variable 𝑥 $x$ in a field 𝐾 $K$ and with coefficients in that field, the root 𝑟 $r$ of 𝑃 $P$ is an element of 𝐾 $K$ such that 𝑃(𝑟)=0 $P(r)=0$
with C also a polynomial,the fact that𝐵 $B$ divides 𝐴 $A$ is denoted 𝐵𝐴 $BA$
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
(𝑥−𝑟)(𝑄(𝑥)) $(xr)(Q(x))$
𝑄(𝑥) $Q(x)$ is a polynomial of degree 𝑛−1 $n1$.
𝑄(𝑥) $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.
where
SchwartzZippel Lemma stating that “different polynomials are different at most points”.
Elliptic Curves
The defining equation for an elliptic curve is for example𝑦2=𝑥3+𝑎𝑥+𝑏 ${y}^{2}={x}^{3}+ax+b$
For certain equations they will satisfy the group axioms
We often use 2 families of curves :
Montgomery Curves
For example curve 22519 with equation𝑦2=𝑥3+486662𝑥2+𝑥 ${y}^{2}={x}^{3}+486662{x}^{2}+x$𝕂 $\mathbb{K}$ (with order different from 2)
Generally this curve is considered over a finite field
BN254 / BN_128 is the curve used in Ethereum for ZKSNARKS
BLS12381 is the curve used by ZCash
Edwards Curves
The general equation is𝑎𝑥2+𝑦2=1+𝑑𝑥2𝑦2 $a{x}^{2}+{y}^{2}=1+d{x}^{2}{y}^{2}$ with a = 1
If a <> 1 they are called Twisted Edwards Curves
Every twisted Edwards curve is birationally equivalent to a Montgomery curve
Pairings
Bilinear pairings are functions that take two arguments and return one output, usually denoted by
A bilinear pairing is a function e: G1 x G2 > GT with the following properties:
Order:All three groups must have order equal to a prime r.
Efficiency: the pairing function must be efficiently computable.
Bilinearity: For any elements P1, P2 of G1 and any elements Q1, Q2 of G2, the following holds true:
This implies the following form, which is more often used (along with some other variants):
Nondegeneracy: the pairing of the generators of the first two groups is not the identity of the third group. If this were the case, every pairing would result in the same (the identity) element of GT:
G2 is an elliptic curve, where points satisfy the same equation as G1, except where the coordinates are elements of𝐹𝑝12 ${F}_{{p}^{12}}$ (this is an extension field, where the elements of the field are polynomials of degree 12)𝐹𝑝12 ${F}_{{p}^{12}}$
Gt is the type of object that the result of the elliptic curve goes into. In the curves that we look at, Gt is also
Complexity Theory
Complexity theory looks at the time or space requirements to solve a problem, particularly in terms of the size of the input.
We can classify problems according to the time required to find a solution, for some problems there may exist an algorithm to find a solution in a reasonable time, whereas for other problems we may not know of such an algorithm, and may have to ‘brute force’ a solution, trying out all potential solutions until one is found.
For example the travelling salesman problem tries to find the shortest route for a salesman required to travel between a number of cities, visiting every city exactly once. For a small number of cities, say 3, we can quickly try all alternatives to find the shortest route, however as the number of cities grows, this quickly becomes unfeasible.
Based on the size of the input n , we classify problems according to how the time required to find a solution grows with n.𝑛𝑘 ${n}^{k}$ for some value k, we put these problems in class P. These problems are seen as tractable.
If the time taken in the worst case grows as a polynomial of n, that is roughly proportional to
We are also interested in knowing how long it takes to verify a potential solution once it has been found.
A computational problem can be viewed as an infinite collection of instances together with a solution for every instance. The input string for a computational problem is referred to as a problem instance, and should not be confused with the problem itself.
https://en.wikipedia.org/wiki/Computational_complexity_theory
Decision Problem: A problem with a yes or no answer
Complexity Classes
P
P is a complexity class that represents the set of all decision problems that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time.
NP
NP is a complexity class that represents the set of all decision problems for which the instances where the answer is “yes” have proofs that can be verified in polynomial time.
This means that if someone gives us an instance of the problem and a witness to the answer being yes, we can check that it is correct in polynomial time.
NPComplete
NPComplete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time.
Intuitively this means that we can solve Y quickly if we know how to solve X quickly. Precisely, Y is reducible to X, if there is a polynomial time algorithm f to transform instances y of Y to instances
x = f(y) of X in polynomial time, with the property that the answer to y is yes, if and only if the answer to f(y) is yes
NPhard
Intuitively, these are the problems that are at least as hard as the NPcomplete problems. Note that NPhard problems do not have to be in NP, and they do not have to be decision problems.
The precise definition here is that a problem X is NPhard, if there is an NPcomplete problem Y, such that Y is reducible to X in polynomial time.
But since any NPcomplete problem can be reduced to any other NPcomplete problem in polynomial time, all NPcomplete problems can be reduced to any NPhard problem in polynomial time. Then, if there is a solution to one NPhard problem in polynomial time, there is a solution to all NP problems in polynomial time.
Homomorphic Encryption
Homomorphic encryption is a form of encryption with an additional evaluation capability for computing over encrypted data without access to the secret key. The result of such a computation remains encrypted. Homomorphic encryption can be viewed as an extension of either symmetrickey or publickey cryptography. Homomorphic refers to homomorphism in algebra: the encryption and decryption functions can be thought as homomorphisms between plaintext and ciphertext spaces.
Bitcoin splitkey vanity mining
Bitcoin addresses are hashes of public keys from ECDSA key pairs. A vanity address is an address generated from parameters such that the resultant hash contains a humanreadable string (e.g., 1BoatSLRHtKNngkdXEeobR76b53LETtpyT). Given that ECDSA key pairs have homomorphic properties for addition and multiplication, one can outsource the generation of a vanity address without having the generator know the full private key for this address.
For example,
Alice generates a private key (a) and public key (A) pair, and publicly posts A.
Bob generates a key pair (b, B) such that hash(A + B) results in a desired vanity address. He sells b and B to Alice.
A, B, and b are publicly known, so one can verify that the address = hash(A + B) as desired.
Alice computes the combined private key (a + b) and uses it as the private key for the public key (A + B).
Similarly, multiplication could be used instead of addition.