The post BN254 For The Rest Of Us constitutes the base point for this article, so I highly recommend reading it to get a solid background of the BN254 curve. This post will reuse some parts with an emphasy on the computational aspect of the optimal Ate pairing over the BN254 curve.
For those with a poor background on Pairing-Based Cryptography (PBC) but with a decent background on Elliptic-Curve Cryptoraphy (ECC) I recommend reading the following resources in order:
Only after (and not before) you feel sufficiently comfortable with both PBC and ECC come back to this post and start to make sense out of it.
The implementation in zkASM can be found here.
The BN254 is the elliptic curve of the form:
defined over a finite field , where the prime is the following -bit number:
The number of points happens to also be a prime of bits:
where t = 147946756881789318990833708069417712967
is known as the trace of Frobenius.
The point is a point of order , i.e. a generator of the group of points of the curve. In fact, all points in are generators, as Lagrange's Theorem shows.
The embedding degree of this curve is .
For more information, refer to BN254 For The Rest Of Us or the EIPs 196 and 197.
To represent we use the following tower of extension fields:
fields:
where is not a quadratic residue in and is neither a quadratic residue or a cubic residue in .
In the particular case of the BN254, we have and and therefore:
from which we can extract the identities , , and consequently the idenity .
Using the latter identity, we can also write:
These two representations of will allow us to apply some optimizations:
BN curves admits a sextic twist defined over of the form:
or more specifically:
This means that pairing computations can be restricted to points and and avoid computations over entirely.
The number of points of is:
which concrete to:
The mapping
defines a group homomorphism from to and we are going to use it to send points from the twisted curve to the curve (but not the other way around).
The optimal Ate pairing over the BN254 curve is defined by:
where:
is the only subgroup of the -torsion of over .
is the only subgroup of the -torsion of over .
is the set of -th roots of unity over .
x = 4965661367192848881
and therefore 6x+2 = 29793968203157093288
, which is a number of bits that can be expressed in the base as follows:
which has a Hamming weight of 26.
We prefer base over base because 6x+2
expressed in the latter is:
which has a Hamming weigth of 37.
I moved from base to base by using the identity[2] that holds for any such that . In words, it is unpacking groups of 's of any size to a single and in the binary decomposition.
, for any and , is a rational function on that is computed using Miller's "double-and-add"-style algorithm:
starting with .
denotes the equation of a line passing through and while denotes the equation of a vertical line passing through . However, due to the final exponentiation, the value of remains unchanged if we omit the division by the vertical lines, so we will not care about such computation.
is known as the Frobenius operator.
Therefore, what we want to compute is the following:
In what follows we explain how to compute each of the components of the previous pseudocode snippet.
To summary BN254 For The Rest Of Us, we have:
if and only if . That is, if we write then we simply need to ensure that the equation holds over .
Costs:
A point belongs to if and only if , where is defined as:
where .
This was proven in Proposition 3 of 2022/352 and it is clearly much faster than the naive check , since the constants can be precomputed.
TODO:
A more efficient approach appears in 2022/348, which ensures that belongs to if and only if:
Costs:
Given two points and in the twisted curve such that and and a point in the curve , the evaluation at of the line passing through and is given by:
Costs:
Given a point in the twisted curve and a point in the curve , the evaluation at of the line passing through is given by:
Costs:
Now we explain some tricks for the computation of the lines:
For the first line notice that if , then:
where are precomputed.
The conjugate of an element in in is .
Moreover, due to being an homomorphism we have that for all . Consequently, we compute as in the previous section, with (it's a good exercise to check that belongs to ).
Costs:
I don't include the cost of computing , since it is obtained in the Miller loop.
For the second line we similarly have:
Again, due to the homomorphic property of , we compute as in the previous section, with (again, check that belongs to ).
Costs:
Hence, in both cases, the Frobenius operator comes for free.
In the final exponentiation, we raise an element to the power .
First, divide the exponent as follows:
Let's start with the easy part of the easy part, when we first attempt to compute . But since, , we have , just one conjugate, one inversion and one multiplication in .
The conjugate of an element in in is . Hence, if we write we have:
To finish the easy part, we first compute which is the Frobenius operator applied to and then multiply the result by to finally obtain .
Importantly, after the computation of the easy part, the resulting field element becomes a member of the cyclotomic subgroup , which means that inversion from now on can be computed by simply conjugation. Moreover, when an element belongs to , one can compute using fewer multiplications and therefore the overall costs of performing exponentiations (see this section).
Costs:
Following Section 5 of this 2008/490, we can write:
where:
So we just need to compute:
and then multiply them all.
In what follows, remember that x = 4965661367192848881
, which is a number of bits that can be expressed in the base as follows:
which has a Hamming weight of 24.
We prefer base over base because x
expressed in the latter is:
which has a Hamming weigth of 28.
We proceed as follows:
We start by computing .
Then, compute (use the Frobenius operator).
Next, we group the previous elements as follows:
(recall that at this point computing the conjugate is the same as computing the inverse)
Finally, compute the product:
To compute this product as efficient as possible, we use the vectorial addition chain technique as explained in the last part of Section 5 of 2008/490:
which requires only multiplications and squarings.
Costs:
As we have shown, in the final exponentation we must compute the first, second and third Frobenius operator over an element in . Recalling that , a naive implementation would take -operations, but we will do it much better.
Recall that we can write any element as:
where and with and .
We will now show that raising an -element over any power of is almost cost free and therefore so is .
Using all the previous observations, we have:
which can be computed using a few multiplications and a few conjugations, assuming each is pre-computed for .
Similarly, notice and therefore , where .
Lastly, we can use the identity to show that
and therefore , where .
Then, we have:
with , and . Hence, assuming the precomputation of for , we can compute or almost for free.
Costs:
I follow 2010/542 closely for this section.
Recall that:
and also:
For this optimitzation, we will further need the following representation:
so that for , we can equivalently write .
This optimization is due to "compression" and "decompression" technique, which exploits the algebraic relationships arising from elements belonging to the cyclotomic subgroup .
If then the compression function is:
and the decompression function is:
where:
Now, on input we will be able to compute its square on compressed form. That is, , where :
Given and , the idea is to compute using the squaring formula in compressed form.
Represent in binary as with and define . Then:
Therefore, we can use the square-and-multiply algorithm to compute such product. Since we are going to be squaring in compressed form, we start at rather than the standard in such algorithm.
Recall that:
We use two additional representations of .
The first one is used to efficiently compute the Frobenius operator and is as follows:
The second one is used to speed up the squares and exponentations in the hard part of the final exponentiation:
We start with and , where we notice that if we take , we can use the identity to rewrite it as:
This relationship induces the following field isomorphism and its inverse :
Exercise: Check that is a field isomorphism between and and that for all and it is true that and .
We continue with and , for which we notice that can be equivalently written as .
This relationship induces the following field isomorphism and its inverse :
Exercise: Check that is a field isomorphism between and and that for all and it is true that and .
Addition
Subtraction
Multiplication
Scalar Multiplication
Square
Inverse
Square
Addition
Subtraction
Multiplication
Scalar Multiplication
The following three algorithms help to compute the line equations. See the sparse multiplications algorithms of next section for a full understanding.
Sparse Multiplication A
Sparse Multiplication B
Sparse Multiplication C
Square
Inverse
Addition
Subtraction
Multiplication
The following two algorithms are used to compute the line equations avoiding all multiplications by zero that arise from the sparisity of such equations.
Sparse Multiplication A
Sparse Multiplication B
Square
Inverse
First Frobenius Operator
Second Frobenius Operator
Third Frobenius Operator
The following two algorithms are used for computing squarings and exponentiations over the cyclotomic subgroup . Luckily for us, this is the case after performing the easy part of the final exponentiation.
Fast Squaring
Fast Exponentatiation
if you don't know why, make sure to review Galois theory. Start by noticing that Galois group is a cyclic group of order generated by the Frobenius endomorphism . ↩︎
I recently discoverd that this is just a particular case of the more generic non-adjacent form (NAF) of a number. ↩︎