ZK13: Vectorized implementations with AVX-512 for speeding-up zkEVM - Georgios Fotiadis

Transcript

[Music] So yeah, I'm Georgio. I'm from Neil Foundation and I'm going to talk about vectorization with AVX 512 uh for speeding up crypto operations in ZKVMs. So what is AVX 512? So it's a it's a family of vector extensions uh usually used to parallelize certain operations and there are different uh vector extensions supported by AVX 512.

The first one is um AVX F which uses a 32bit multiplier and the second one is the newest set of extensions if which supports 52-bit multiplier. So what happens is AVX 512 by default uses the uh 512F vector extensions. Uh if a CPU supports APX 512 then it uses this set of extensions. Otherwise the ifma are optional. It means that they are not currently they are not supported by all processors. The processors that support ifma instructions are Canon Lake, Ice Lake, Tiger Lake and Rocket

Lake. However, in the future, Intel plans to integrate if instructions to all processors. So, initially vectorization and vectorized implementations were used for accelerating um image processing and video processing. However, it became evident that they can be also used to accelerate cryptography, cryptographic operations, especially in cases where you're working over large fields like the case of elliptic curves. When it comes to crypto implementations, I think we were the first to use ifma instructions and basically what we did is we implemented um isogeny based protocols and a couple of years ago we

have seen some ifma implementations of latispace schemes especially kyber and the lithium. So these these are both families uh of algorithms in postquantum cryptography. But when it comes to classical cryptography, we have seen some some libraries for uh elliptic curves, elliptic curve crypto systems. What we would like to do is to see whether these if instructions can help us improve the performance of protocols that are used in ZKVM. For example, we have BLS signatures that we would like to investigate and the aggregation functionality. And we also have polomial commitment schemes like KG which use

elliptic curves and fry polinomial commitment scheme. We started with a with the first use case uh the BLS signatures and we have a software which we call AVX BLS and well the target is to vectorize the whole BLS signature scheme but we started with the first step which is the implementation of the optimal pairing on BLS 12 381 curve. So this was the first step that we vectorized and in the future we plan to vectorize the whole signature scheme. This is a joint work with uh howen Johan Gettle and Dan Page and we have a paper which is currently

under review and we expect to have some results next month. Okay. So just um a recap on how the optimal 8 pairing works and BLS 12 381 curve. BLS 12 381 is a pairing friendly elliptic curve with a bending degree 12. Um it has an equation of the form y^2= xq + 4 and it is defined over a base field of size 381 bits. It has a composite order order and in particular it has a prime factor of size 255 bits.

And one important property is that it admits the grease six twists. And this is an important property because this is um what can help us uh improve the performance of the optimal pairing. When it comes to the optimal pairing, how does it work? So basically the optimal pairing takes as input two points Q and P. The first point Q is defined over FP square while the second point P is defined over FP over the base field and the optimal pairing is executed in two steps. The first step is the Miller loop which computes this Miller function F and the second step is to raise this Miller function to the

exponent P 12 - 1 / R. This is called the final exponentiation. So I'm not going to describe how the optimal eight pairing actually works but what is important is to understand what kind of operations we're using in this optimal eight pairing and basically what we're using is arithmetic over a big field FP to the^ of 12 and what we want to implement is multiplication squaring cyclonomic squaring sparse multiplication these are all expensive operations because they are executed over a big field we also have arithmetic in sub fields of FP12 12. Um we have arithmetic in FP, FP square, FP4 and FP6. And of course we have arithmetic over elliptic

curves. We have point doubling, point addition and we need to do some line computation and line evaluation. Now before starting our vectorization, we wanted to identify which are currently the libraries that are uh that have the most efficient implementation of the optimal pairing. And there are actually two choices. The first one is the blast library. This is implemented by Zikas and in fact this library is an implementation of the whole BLS signature scheme and it's currently integrated and used in Ethereum. So this is the reason why we use this the blast library as a reference for our comparison but also

our whole implementation is basically a vectorzed version of the blast library. Now the second option is an implementation by Patrick Longa. This is based on the uh Relic library. Relic is a very well-known library that implements a variety of pairings. And Patrick's implementation is slightly faster than blast. It is faster by a factor of 1.07. And the reason is that uh Patrick is using a different implementation of the cyclomic squaring. Uh their method is called compressed cycllotomic squaring.

When it comes to the blast library, what we wanted to do is to identify which are the most expensive operations executed in the Miller loop and the final exponentiation. For the Miller loop, the most expensive operations are squaring over the big field over FP12, sparse multiplication again over FP12 with 32%. and um point doubling and computing the the the the double line. So these three are the most important operations and the most expensive operations in in the Miller loop. While in the final exponentiation around 74% of the total computation is spent on cyclomic squarings and around 18% on

multiplications over FP12. So if we want to optimize the optimal petting these are the the core uh operations that we need to target and we need to optimize. So how does our vectorization work? In the beginning I should say that if we want to represent an integer a over fp what we do is we split it in limbs. So basically an integer over FP where in our case P is 381 bits is split to eight limbs. Each limb has size 48 bits. And in the case of vectorization

we're working with what we call limp vector sets instead of integers. So we can represent um eight integers over FP using an array representation. What it means is we can have we can we can construct an array where each column of the array contains all limbs corresponding to an integer. For example, we can say here that the first column has all the limbs corresponding to integer A. Second limb has second column has all the limbs corresponding to integer B and so on. So this is this is an 8 * 1 limp vector set because it uses eight lanes, eight

columns um to represent the limbs of of of every integer. But you can also do a four* two-way uh limb vector set which means that you can use two columns to store all the limbs of one integer. For example, in this case, you have column one and two containing all the limbs that correspond to integer A. And in order to do a vectorzed multiplication over FP, what we did basically is we vectorized Katuba multiplication with Montgomery reduction.

And what we did is we we replaced the um single instructions with vector instructions. And we ended up with with an algorithm that performs eight multiplications over FP in parallel. Oops. Now moving one layer up we have um arithmetic over FP square over an extension field of degree 2 and if we want to do a multiplication over FP square there are two formulas that are usually used. The first one is Katuba and the other one is whole book.

Normally if we consider sequential implementation Katuba is the fastest option especially over large fields. Uh but when it comes to vectorization this is not always the case. What we did is we implemented um the SWbook method and in particular in four-way parallelization. It means that we're executing four multiplications over FP square in parallel. And for that we need two uh a * 1 limp vector sets where each limp vector set um contains um four FP square elements and each element in FP square has two FP

components. So basically each limb vector set represent eight integers in FP. And these are the speed ups that we got. Uh this is in green here. We can see that our vectorzed multiplication of FP square um gives us a speed up of uh three times compared to the blast library. While in the case of FP squareing we get a speed up of 2.54. Now again moving one layer up we have elliptic curve operations and here I will describe point doubling and computing the line uh in the doubling step. So in blast

uh points on the curve are representing projective coordinates and in this case we have a point t with three coordinates and all coordinates are defined over p square. If we want to compute the double of the point t, we need to implement this formula here. We need to do a bunch of squarings and multiplications over fp² um using the coordinates of the point t. And if we want to compute the line the tangent line that passes through t, then this will have three coefficients l, l1 and l2. And again in order to compute this these coefficients we need to do a bunch of squarings and multiplications

over fp square uh using the coordinates of the point t. So what we did is we vectorized this um the the algorithm that was already implemented in blast we vectorized it in four way it means that we're executing four fps operations in parallel. For example, in step two, you can see that we're executing four squarings in FP square in parallel. If you consider the the original blast implementation, all these instructions are executed sequentially. And the speed ups that we

got for the doubling process, we got a speed up of 1.93 compared to blast. While in the case of uh addition point addition and uh addition line we got a speed of 1.69. The difference is that in the case of addition we were only able to do a two-way parallelization not four-way. And here are some results regarding the FP12 operations. Um here I consider the FP12 cyclomic squaring, the FP12 multiplication, FP12 sparse multiplication and FP12 squaring

with blue uh blue is corresponds to the blast library, red corresponds to Patrick Long's implementation and green correspond to our AVX BLS software. And in all cases we got a speed up between uh 1.88 to 2.26. 26. We also did some additional vectorization of operations in FP4 and FP6. These operations are required mainly in the final exponentiation. Now what about the performance of the pairing? Here we can see that um we managed to reduce the execution time of

the Miller loop to half. So we only need um 500,000 cycles for the Miller loop. This is this gives us a a speed up of 2.09 sorry 2.01. For the final exponentiation we got a similar speed up uh by a factor of 1.94. And for the total pairing computation we got speed up of 1.97. So now we have our pairing is executed one pairing computation is executed in 1.2 million cycles. There are some additional tricks and modifications that we need to do to to our code and maybe we will be able to reach uh a speed up factor too maybe a bit more but this will be this will be

done near near future as well. Um our paper source code will be available probably late June. Now as I said in the beginning our goal is to vectorize the whole BLS signature scheme and in order to do this we are missing some operations and here you can see the different layers where we applied our vectorization. We started with uh arithmetic over FP. We moved to arithmetic over extension fields then elliptic curve arithmetic and everything that is in red we still need to vectorize in order to have um a vector implementation of the BLS signature scheme. And two operations that are important to be vectorized are the the

process of hashing to curve. This is starting from a random bit string and mapping it to a point on the curve and scalar multiplication. We also need to vectorize scalar multiplication and also we are interested in looking at ways to to use our vectorization strategies to accelerate the signature aggregation process. So these are things that we'll investigate will be investigated in the near future. One other use case that we would like to have a look at is the implementation of the KCG polinomial point machine. So KCG uh also uses pairings. It uses pairings on on a different it uses the optimal pairing on a different curve the BN24 curve. But there are many similarities

and we can reuse our code for this pairing as well because the extension fields that are used are the same and um other functions can be can be easily adopted in the case of PN254 groups. Another use case that we would like to have a look at is the Fry polinomial commitment scheme and how we can use R vectorzation to to improve the performance of Fry. So the trend in the in terms of uh fry the trend now is to use small fields like either 64 bits or 31 bits uh both in fry and circle fry but you still need to do operations in extension fields and you also need to do

uh polomial arithmetic scalar multiplications. Um so these are all things that we we we are planning to investigate how to how we can use our vectorization to improve the performance of fry and yeah that'll be all just for the uh for the AVX 512 u you mentioned uh when you're looking at the actual ability to put this on hardware um it was predominantly on Intel is there um so that you're not so reliant

on Intel for the actual hardware is there independent like ASIC or other ability to run this accelerated compute on on like on separate hardware so you're not reliant on Intel chips sorry could you repeat is there other hardware so like you mentioned to be able to to to be able to run our vectorization let's say in other types of hardware. Yeah. So you're using the EVX 512 library but it seems like a lot of it is predominantly on on on Intel silicon. So yes uh so it's great work that you're doing using this library but is it possible to use this on other hardware either dedicated independent other hardware that supports uh vectorzed instructions? Yes, because a vectorzation is generic. So you can you

can easily adapt it to to other other things like GPUs for example. Um you can still use vectorization and in particular our strategies for extension fields and stuff you can you can use it. Yes. Uh so you said that uh radic implementation by longa is faster than blast because of compressed c. So is it like carabina algorithm? So which compressed algorithm? So and the second question is so are you using this compressed algorithm in your avx implementation or are you using the blast uh one?

Sorry, can you repeat? I'm not hearing very well. So, uh at some slide you said that uh implementation by Patrick Longa is faster than blast because of the use of compressed uh so I assume it is carabina algorithm for the compressed SQL atomic square. So the question is in your implementation with AVX are you using the same algorithm as a or blast blast blast. Okay. So we use the cyclomi quering. Um so it's faster even because even if you're using the the old version. Okay. Yeah. Yes. But we also try.

So what happens is if you replace the cyclomic squaring implementation in blast with a compressed cyclomic squaring blast becomes faster than Patrick's implementation. Okay. Slightly faster but still faster. So we also did that. Okay. Thank you.