Pairing

Let’s look at the tools that we’ve covered so far to build a homomorphic hiding mapping. We have a finite field of order p, where p is a prime number, and a group of points (x,y), whose coordinates belong to the same finite field.

These points satisfy an elliptic curve, whose coefficients A and B belong to the same finite field. We’ll call the finite field “base field” or “F_p”, and “G1” the subgroup of points with generator g1. We’ll choose p and the curve such as r, the order of the group G1, i.e. the number of elements on this group, is a prime number too.

Ok, let’s add some other tools to this set. We know that p is the number of elements in the base field; we can calculate p-1, p²-1, p³-1, p⁴-1, ... and stop when we find the first (i.e. the smallest) k such that p^k-1 is a multiple of r, the number of elements of G1. We have chosen our curve so that k, the “embedding degree” of the curve, exists. The mathematicians tell us that this k has to be not too small, if we want to make sure that the mapping from Fp to G1 is hard to reverse, and that it can't be too big, if we want pairing calculation to be efficient. We’ll trust them on this.

Now, we need to introduce another field. This field will be a field extension of the base field F_p. To have an idea of what a field extension is, we can think of the field of the complex numbers, that it’s an extension of real numbers; that extension is defined by giving the name “i” to the root of the polynomial x²+1=0. This polynomial has no solution in the field of real numbers, and that’s why we can define a new field with it, made up of all possible linear combinations of the real numbers and the root (that we call “i”) of that polynomial: a + b*i. The element of this extended field can be represented as a bidimensional vector (a,b); when b=0, we get the elements of the original field that we extended, and that means that the original field is contained in the extended field.

As we know by now, in zk-Snarks we are not operating on real numbers, but on finite fields. We are then going to extend F_p, our base finite field. We’ll extend it with the linear combinations of the roots of a polynomial of degree k, where k is the embedding degree of the elliptic curve just introduced. This polynomial is chosen so that it has no root in F_p (so, no points in our base finite can make it evaluate to 0). The elements of this new field, will be themselves polynomials. This is important and not easy to get at first: the elements of our extended field are not just “numbers” as in our base field, but each element of the extended field is itself a polynomial. These field elements are polynomials that:

• have their coefficients modulo p
• are the remainder of the divisions of all the possible polynomials that are linear combinations of the base field and the roots of a given defining polynomial, by that very same defining polynomial. So they are themselves polynomials “modulo” the polynomial that defined them (i.e. the one we used to express its roots).

The following example can hopefully help here:

• 0
• 1
• 2
• z
• z+1
• z+2
• 2*z
• 2*z+1
• 2*z+2

As we’ve just seen, the elements of our extension field are polynomials. These polynomials include all the elements of the base field F_p, that are polynomials of degree 0 like the first three elements of our example above, and the p^k-p other elements of degrees up to p^k-1. It’s a field, with all the good properties: closure, existence of inverse, abelian over addition and multiplication (but the 0 element), etc. These polynomials can be informatically represented by their vectors of coefficients, same as we did for (a,b) in the complex number example. 

Wow, a lot of maths and complexity… and now,  what are we going to do with the new field F_p^k?

Well, we’ll use it to define a new group G2, made of all the coordinates (x,y) that satisfy the same elliptic curve used for G1, expect that this time the coordinates have to be elements of F_p^k. So, we evaluate the elliptic equation replacing x and y with elements of F_p^k (they will be polynomials, and not numbers this time!), and select the tuples that satisfy it.

If it’s not too clear how  polynomials can satisfy an elliptic curve, we can take a simple curve:

y²=x³

And the simple extension field that we calculated before.

Now we can see which combination of (x,y) solves the equation y² = x³ :

G2 = { (0,0), (1,1), (1,2), (2,z), (2,2*z), (2,2*z+1), (z,z+1), (z,2*z+2), (2*z,z+2) }

After all these calculations, we can step back for a second and take a look at what we’ve got now. We have two fields: F_p - whose elements are numbers - and F_p^k, whose elements are polynomials. We also have a group G1, whose elements are couple of F_p numbers, and a group G2, whose elements are a couple of polynomials. We can see that  F_p^k contains F_p (i.e. the “polynomials” 0, 1, 2, 3, … belong also to  F_p^k), and because of this, G2 also contains G1.

If we just stop for a while and stare at these 4 mathematical sets, you may feel a question coming up…  and that question may very likely be: why on earth did we build all this paraphernalia?

Well, it turns out that if we choose our elliptic curve“well”, we can build a function z=T(x,y) that maps two elements, one in G1 and one in G2, to an element in a new group Gt, such that, if g1 is the generator of G1, and g2 is the generator of G2, then:

• T(g1,g2)=gt (the generator of the group where the mapping lands)
• T(a*g1, b*g2) = a*b*gt

The coordinates of the points of this new group Gt are part of  F_p^k (they are polynomials).

So, and that’s the answer to the question, i.e. the reason why we did all the above, is that we have added a new operator to our homomorphic hiding: a “limited” homomorphic multiplication!

It’s easy to see that, given the hiding of a -> a*g1, and the hiding of b -> b*g2, we can compute the hiding of a * b ->  a*b*gt by knowing just a*g1 and b*g2, since a*b*gt=T(a*g1, b*g2). This homomorphism is not complete as it was in the addition case: the mapping is limited to two elements (we can’t multiply three elements “in the hidings”), and we can’t apply it more than once, but it’s enough for our needs: we’ll use it to check that the equations on multiplications hold, without revealing the hidden values.

We’ll use two different hiding functions, hh1(x) = x * g1, that maps to the group G1, and hh2(x) = x * g2, that maps to the group G2. As usual, we can use an example to see how we can check, for instance, that the right “B” polynomials were used. The prover needs to know the hiding hh1(u) and hh2(1)=g2, made available in the setup phase, and then calculates the hidings hh2[B(P)], and hh1[B(u*P)] from the hidings of B1(P), B2(P), ... B1(u*P), B2(u*P), that again were made available at set-up. By using the pairing function, a verifier can check that T{ hh1(u) , hh2[B(P)] } == T{  hh1[B(u*P)] , g2 }, i.e. it can verify, without revealing the secret point P nor the value u, that the hiding of B in the point u*P equals the hiding of u multiplied by the hiding of B calculated in the point P. And if we recall what we read in the “knowledge of coefficients” pages, since u and P are unknown, that means that B(P) was calculated by using a combination of the hidings of B1(P), B2(P), B3(P), …