DeFi

Privacy Scaling Ethereum – Lecture 1

In this 1st lecture of the Elliptic Curve Cryptography hosted by Privacy Scaling Ethereum, we saw an introduction to the Naive Set Theory. We went over the algebraic view of functions, and specifically we dived into what sets are, including famous sets and operations on sets (union, intersection, complementary). We also saw how to move from one set to another using functions and the different types of functions.

Introduction to Naive Set Theory

Taking an example of a parabola in the plane:

y = x^2

We have 2 important visions:

  • In Analysis: we look for continuity arguments
  • In Algebra: we treat it as an algebraic object, constructed with addition and multiplication

Algebraic View

We take a geometric object (like the parabola) that can be expressed by algebraic means and we study it over different algebraic setups (i.e. the Primer Field, Fp)

The solution:

p = sol( f(x,y)) = { (x,y) | f(x,y) = 0 }

Makes sense over a prime field: 

Fp = { 0, ... , p-1}

where we get addition and multiplication.

We keep remembering the geometry we have over real numbers because this gives us intuition of what should be true.

Elliptic curves

Equation of the form of:

y^2 = x^3 +ax +b

where a, b are real numbers.

The solution set of this polynomial over real numbers:

E (R) = sol (y^2- x^3 -ax -b over R)

We can take 2 points P, Q, connect them in a line. We have a polynomial with degree 3, so the line will intersect in 3 points.

Then reflect on the x axis and add another point R. y^2 equals something means it’s simetrical in the x axis.

We defined a binary operation, from the set of all points, to the set of all points.

+: E(R) x E(R) --> E(R)

This operation is associative.

TLDR; we take 2 points from the elliptic curve and draw a line, so we’ll have a third point which we reflext on x axis. a set of solutions that are both for the line and for the E.

It admits the natural operation, abelian group operation on the set of solutions:

+: E(Fp) x E(Fp)

Adding points in the Elliptic Curve is an expensive operation. You could do it if you don’t do too many operations, but for a brute force attack is unfeasible.

Elliptic Curves admit special maps: pairings.

e: E(Fp) x E(Fp)        -->   Fp
e: G1 x G1                    -->   Gt

e(g^a, g^b) = e(g, g)^ab

This property allows us to build BLS signatures.

  • Standard cryptography books: they give an elementary account but it’s not rigorous (start with a pairing as a black box)
  • Rigorous cryptography (pure mathematics): proof everything

Sets

Sets could be seen as the machine code of mathematics. From a formal point of view, you can construct all mathematics from sets.

A set S is a collection of elements. You can say x belongs to S or it does not belong to S.

When you write it, you remove repetition of elements. Example:

S = { 1, 2, 3 } = { 1, 1, 2, 3 }

There are 2 ways to describe a set:

  • writing all elements separated by a comma
  • describe a rule that gives you all the elements of the set

Famous Sets

  • Natural numbers: N = { 1, 2, 3 …}
  • Integers: Z = { -2, -1, 0 , 1 , 2…}
  • Rational numbers
  • Irrational numbers
  • Real numbers
  • Complex numbers
  • Empty set

Relation of containment: A c B, for any element of a is element of B.

Operations on Sets

  • Union
  • Intersection
  • Complementary

Ordered Pairs

It is a construction that takes into account the order of the elements. If ‘a’ and ‘b’ are two elements, then the two different pairs are (a, b), (b, a). In an ordered pair (a, b), a is called the first element, and b is called the second element.

Two ordered pairs are said to be equal if and only if the corresponding first elements are equal and the corresponding second elements are equal.

Cartesian Product of Sets

The cartesian product of set A, B is the set of all ordered pairs (x, y) such that x belongs to A and y belongs to B. For example, if A = {1, 2} and B = {3, 4, 5}, then the Cartesian Product of A and B is:

A x B := {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5)}

If A and B are finite, the number of elements of A x B is the number of elements in A times the number of elements of B.

Functions in Sets

Let A, B be sets, a function f from A to B is a rule that assigns every element of a an element f(a) = B.

  • A = input set
  • B = otuput set
  • f = a machine that assigns every input object an output object

It can be seen as a collection of pairs, such that for every element in the input set, there is an element in the output, such that the pair belongs to f.

The graph of f: is the set of all pairs a, f(a).

Composition

From here, suppose f is a function which maps A to B. And there is another function g which maps B to C. Can we map A to C? The mapping of elements of A to C is the basic concept of Composition of functions.

The function f: A→ B & g: B→ C can be composed to form a function which maps x in A to g(f(x)) in C. All sets are non-empty sets. A composite function is denoted by (g o f) (x) = g (f(x)). The notation g o f is read as “g of f”.

In computer terms, we just concatenate: the output of f is the input of g.

The identity function is the neutral element of the binary composition. A function where A maps to itself (A).

Type of Functions

The functions can be classified by the manner in which arguments (input expressions from the domain) and images (output expressions from the codomain) are related or mapped to each other. We distinguish:

  • Injective: for any a and a’ in A, f(a) is different from f(a’). The routine f does not repeat outputs on different inputs
  • Surjective: for any element in the output set, there exist an element in the input set, such as f(a) = b
  • Bijective: if it’s injective and surjective

Bijective maps are invertible.

Inverse and identity function

Let A and B be any sets. Then if f : A –> B is bijective then it exists an inverse function, f^-1 : B –> A such that, f º f^-1 = identity of A (id A)

Bijective maps are invertible,

Leave a comment