Preamble
Are you ready to explore a more complex side of zk-SNARK? In the previous section, we learned about some more advanced concepts like the Arithmetic Circuit and the Quadratic Arithmetic Program. In this section, we'll expand our knowledge by delving into another powerful concept: Elliptic Curve Pairings.
Note: Understanding a topic like Elliptic Curve Pairings in depth can sometimes be challenging for many. However, that's why we have this article – to help you get at least a basic perspective on this.
My goal is not only to thoroughly explain Elliptic Curve Pairings but also to make the topic more interesting and easier to understand. Hopefully, through this article, you will see the power of elliptic curve pairs in mathematics and cryptography in general, as well as in their specific applications in zk-SNARKs in particular.
Elliptic curves
Elliptic curves are part of the field of Elliptic Curve Cryptography. This is a complex subject that is not easy for everyone to understand. To understand them better, take a look at my article on ECC earlier.
Elliptic Curve Cryptography involves “points” in two-dimensional space, each “point” characterized by a pair of coordinates (x, y).
There are specific rules for performing mathematical operations such as addition and subtraction between points, allowing the coordinates of a new point to be calculated when other points are known.
Example: Calculate the coordinates R = P + Q
You can also multiply a point by an integer by repeatedly adding the point to itself as many times as that integer.
For example: P * n = P + P + … + P
This provides an efficient way to perform mathematical operations in Elliptic Curve Cryptography
On an elliptic curve, there is a special point called “point at infinity” (O), equivalent to zero in point calculus, it is always true that P + O = P.
A curve also has an “order”; there exists a number n such that P * n = O for all P ( P * (n+1) = P, P * (7*n + 5) = P * 5, and so on).
There is also a “generator point” (G), which is understood to represent the number 1 in some way. In theory, any point on the curve (except O) could be G.
Pairings
Pairings enable more complex equation testing on elliptic curve points.
For example:
you can check if p * q is equal to r just from P, Q and R.
Although information about p can leak from P, this leakage is carefully controlled.
Pairings allow testing of Quadratic constraints.
For example: Testing e(P, Q) * e(G, G * 5) = 1 is actually testing p * q + 5 = 0.
is a mathematical operation called pairing. Mathematicians also call it a bilinear mapping. “Bilinear” here will comply with the following rules:
Note that you can use the operators + and * in any way, as long as they comply with the following rules:
and
If P, Q, R and S are simple numbers, creating a simple pairing operation is easy with the expression:
The following results:
That's parallelism !
However, such simple pairing operations are not suitable for cryptography because they operate on simple integers and are too easy to analyze.
Once you know a number and its result when performing the pairing operation, you can easily calculate and find the remaining number.
We use mathematical operations like “black boxes,” where only basic operations can be performed without further analysis or understanding. This is why elliptic curves and the pairing operation on elliptic curves become important in cryptography.
Prime Fields and Extension Fields
It is possible to create a bilinear map (Bilinear Maps) on elliptic curve points — i.e. create a function
where P and Q are elliptic curve points, and the result is an element type called F_p¹²
First, let's understand prime fields and extension fields.
The Elliptic curve in the image above is so beautiful because the equation of the curve is defined using ordinary real numbers.
However, in cryptography, using ordinary real numbers can lead to using logarithms to “go backwards”, and screw things up as the amount of space needed to store and represent numbers can increase arbitrarily. Therefore, we use numbers in a prime fields.
A prime field consists of the set of numbers 0, 1, 2… p-1, where p is prime and the various operations are defined as follows:
All operations are performed modulo p
Division is a special case; normally, 3/2 is not an integer, and now I only want to deal with integers, so instead I try to find the number x such that
x * 2 = 3.
This can be done using the Extended Euclidean Algorithm. For example, if p = 7, then:
Next, we will talk about extension fields.
A common example you often encounter in math books is the complex number field, where the real number field is “extended” with the additional element sqrt(-1) = i.
Extension fields works by taking an existing field, then “adding” a new element and defining a relationship between that new element and the elements already in the original field (e.g. i² + 1 = 0).
The important thing is that this equation is not true for any number in the original field, and then consider all linear combinations of the elements in the original field and the new element just created.
We can also extend prime fields
For example, extending prime field mod 7 that we described above with i, we can do the following:
If you want to see all the math done in code, prime fields and field extensions are done here
Elliptic Curve Pairings
Elliptic Curve pairing is a mechanism that takes two points from two Elliptic curves and maps those points into a single number.
You can think of this mapping as equivalent to multiplying points on an Elliptic curve.
Mathematically, Elliptic Curve pairing is defined as mapping two points on an Elliptic curve to an element in another group as a finite field:
Here e is pairing, E1 and E2 are Elliptic Curves and 𝐹 is a finite field.
Note that Elliptic Curves E1 and E2 do not need to be different.
Once concatenation occurs, the result is that an element in another group cannot be reused for the next concatenation.
Elliptic Curve Pairings have certain properties called bilinear mappings:
Here P, Q and R are points on the Elliptic Curve and 𝑎∈𝑍, 𝑏∈𝑍
Using these “bilinear mappings” we can “move around” the coefficients 𝑎 and 𝑏 on those two curves while keeping the mapping:
Source: https://muens.io/elliptic-curve-pairing
We can imagine Elliptic curve pairing as a mapping from G2 x G1 -> Gt, where:
G1 is an elliptic curve, where the points satisfy a form equation
and both coordinates are elements of F_p (they are simple numbers, but the operations are performed modulo a particular prime number)
G2 is also an elliptic curve, where the points satisfy the same equation as G1, but their coordinates belong to the field F_p¹² (we define a new “magic number” w, defined by a polynomial of degree 12 like:
Gt is the type of object that the result of the elliptic curve goes into. In the curves we consider, Gt is F_p¹² (the same strong complex number as used in G2)
Here it must satisfy bilinearity:
Along with two other important criteria:
Efficient computability: Efficient computability means being able to calculate compound operations quickly and without too much complexity. For example, if we just take the discrete logarithm of the points and multiply them together to get create a concatenation, then this would become computationally too difficult, as would breaking the original elliptic curve cipher. Therefore, a compound operation is considered computationally efficient if it can be computed efficiently without imposing too much computational burden.
Non-degeneracy: Non-degeneracy ensures that the concatenation is not a useless concatenation, i.e. it does not just return a fixed value independent of the input points. For example: If we intend the compound meaning is e(P, Q) = 1 for all P and Q, which does not provide any useful information about the relationship between points on the elliptic curve. Therefore, a concatenation is considered Non-degenerative if it provides useful information about the relationship between input points.
So how to do that?
First, we need to understand the concept of divisor, another way to represent a function over points on an elliptic curve.
A divisor of a function essentially counts the zeros and infinity numbers of the function. To understand what this means, let's look at some examples. Let's fix some points P = (P_x, P_y), and consider the following function:
The divisor is [P] + [-P] – 2 * [O]
[P] + [Q] is not the same as [P + Q]. The reasons are as follows:
The function is zero at P because when x is P_x, so x – P_x = 0.
The function is 0 at -P because -P and P have the same x-coordinate.
The function goes to infinity as x goes to infinity, so we say the function is infinite at O.
The reason is in the equation of the Elliptic curve:
y grows to infinity about “1.5 times” faster than x to be able to keep up with x^3 . Therefore, if a linear function has only x, it will be represented as infinity with a multiplicity of 2, but if it has y, it will be represented as infinity with a multiplicity of 3.
Now, consider a “line function”:
Where a, b and c are carefully chosen so that the line passes through points P and Q on the Elliptic curve.
Because of the way addition on an elliptic curve works, this also means that it passes through point -P-Q. This function also goes to infinity depending on both x and y, thus dividing the possibilities
Each “rational function” (a function defined using only a finite number of operations +, -, *, / on point coordinates) uniquely corresponds to a divsor, subject to multiplication by a constant (i.e. if two functions F and G have the same divisor, then F = G * k where k is a constant).
The division of the product of two functions is equal to the sum of the divisions of each function, so
then
Article source: Team Tech/Research Alphatrue
Reference source:
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
