Leveraging High-Performance Computing for Efficient STARK Provers

Bona nit a tothom, gràcies per ser-hi. Soc el Ricard Borré, com va dir, gràcies per la presentació. Jo treballo a Polygon. Bàsicament treballo en desenvolupar i optimitzar la tecnologia de GKE. Aquesta presentació es tracta de l'estabilització de la computació de alta performance per a proveïdors d'estalvis eficients.

La presentació es divideix en dues parts. Primer, parlarem del present en termes de producte, que és la ZKEVM. I explicaré una mica les lesions aportades en el desenvolupament de la ZKEVM. I després, lessons learned on the development of the ZK-EVM. And then I will talk about the future, which is what we are working now, which is the ZK-VM, so a general proposed proving system based on STARKs as well.

Okay, let's go for the ZK-EVM. The ZK-EVM was released two years ago, and its proof is based on a Stark method and we have a Stark and then we have aggregation to have a recursion process to aggregate proofs and then with a certain frequency we will send the proofs to L1. The only thing that we need to understand about a Stark for this talk is that it basically has two stages, or two phases. In the first phase, we will compute the trace, and then in the second phase, we'll take the Frey polynomial, which is kind of a summary of all the trace in a single polynomial, and we will prove the proximity to a low-degree polynomial. en una única polinomia i provem la proximitat a una polinomia de baix degrés.

La fase de comit es fa en diferents estages. Això vol dir que la trànsit es fira en diferents estages i això és perquè necessitem randomitat per a alguns dels estages. Necessitem uns números randoms per avaluar algunes de les polinomies de la trànsit i aquesta randomitat es rebut i aquest ràndom és obtenit des dels estats previus. Les raons de la polinomia avaluades en els estats previus són adjuntades al transcripte i després tenim ràndom per al següent estat que hem d'avaluar. En la aritmetització de la ZKEVM tenim 1.

300, més o menys, polinomials. I després, el ràndom de la polinomia és el que hem de fer. to evaluate. Okay, in our arithmetization of the ZK-EBM we have 1300 more or less polynomials and then the number of rows of the trace which is something that we can fix, it's a parameter of the prover let's say, it's 2 to the 25, so it's about 32 million. This is quite a lot and it ends up posing a requirement of 800 gigabytes of memory.

I will talk more about this. So, why we use such a big number of rows on our trace? Basically, because you have a monolithic approach on the remethization. This means that we have a static capacity, so the capacity of our trace is determined by the number of rows. And so we fix a big number because, basically, we want to be able to handle any transaction that comes to the network.

That's why for the most heavy-loaded transactions, the ones that will need more steps, we need to have enough space to handle them. This approach has advantages, but also some disadvantages. A clear one is that when we have to close a batch because we don't have more room for new transactions, because some of the state machines of the trace are filled, then there will be some spare cells on the trace perquè alguns dels machines de la trànsit són llocs, llavors hi haurà uns cels en la trànsit que hem de proveir però no estan llocs amb valors reals venent dels inputs. Així que tenim alguns efectes de padding, però també tenim uns avantatges, per exemple, que tenim un lloc constant que podem optimitzar molt bé, podem al·locar buffers on on advance etc so it also has some advantages related to performance now let's talk about timings a proof of this huge trace for the zkabm takes about six minutes and the cost with the i el cost amb la instància GCP que suporta l'AVX 512 és només 0,46 dòlars. Normalitzat pel nombre de transaccions, transaccions d'Ethereum que podem fitxar en un batx, és d'uns 0,2 mil·lidòlars.

Aquest serà l'abast per transacció. És un abast molt baix, que és negligible en termes de la gran esquema de coses, en termes de cost que adquireix la transacció. A més, OKEx ha fet un treball molt interessant, que ha portat el proveïdor a GPUs, i això ha reduït la latència a tres minuts. I fins i tot reduint el cost. És una situació perfecta on reduïm la latència al cost utilitzant GPUs.

Aquests són els números donats per ells i al final acabem tenint 0,1 mili dòlars per adreçat al cost de la transacció. Així que és molt bo. La velocitat obtenida des de la CPU a la GPU, si considerem la prova de l'endemà a l'endemà, és 2X. Aquí hi ha una de les limitacions de la prova. Com que tenim un trastament tan gran, a l'endemà, transferem molta data entre el host i el dispositiu durant l'execució dels kernels.

I serem limitats pel PCI Express. A més, si mirem els costats reals, el que és important, són molt menys. No és una cosa que és molt rellevant en el context actual. Si mirem una mica més enllà i mirem la distribució dels kernels quan fem una prova, és una situació perfecta o bona perquè tenim el 95% de la temps de la prova és només concentrat en quatre kernels, especialment en dos, que són l'entitat i la mercantilització, que prenen el 70% del temps. I després tenim expressions que són una combinació línia de polinomials, i després l'executor, que és la primera fase de la avaluació de la tracció.

Així que és la part de la avaluació de la tracció que depèn dels inputs. Aquesta és l'execució inicial dels inputs. Bàsicament, hem de focussar-nos en aquests quatre kernels, bàsicament en dos, i això és el que vam fer. Molt de feina en això, en el passat, abans de publicar el ZK-EBM. The first thing you have to consider when you want to optimize a code is to understand where are the boundaries for this code.

Basically, you have to do a roofline analysis. Basically, the roofline analysis shows you where is the limit depending on the arithmetic intensity of your kernel. If your kernel does a lot of operations per each field element that you upload to the cache of the CPU, it means that it will be bounded by the CPU, by the computing part of the process, and if you have a lower emitting intensity, you are becoming bounded by the memory transfers from the main memory to the cache of the CPU. In our case, we are basically bounded by the memory transfers from the from the main memory to the cache of the CPU. In our case, we are basically bounded by the memory transfers for all the kernels except the hash.

And this makes sense because the hash does a lot of arithmetic operations per each field element involved in the hashing. Okay, so we focused a lot on optimizing the optimizing the entity. We did a lot of basically the focus here was to minimize the L3 misses. Focos a l'optimització de l'entitat. Focs en la minimització de les emisses de l'L3.

Al final, el resultat és que la performance que obtenim és de fer l'entitat en 100 polinomials de 2.23, és a 1.9 segons. Aquesta és més o menys la referència. I després, la mercantilització, és més o menys la referència.

I després, la mercatització, és clar, és sobre, en la CPU, és una altra cosa, en la CPU és sobre vectorització, per tant, prenent avantatge dels registres vectorals per fer, en cada cop, 4 o 8 operacions al mateix temps. I anem a una performance amb Goldilocks 1, no Goldilocks 2, de 1 milió de hashes per segon. Així que aquest és el resum del que vam fer més o menys dos anys abans de llançar el ZKVM. A un punt vam arribar a la conclusió que mantenir i millorar el proveïdor no tindria cap impacte irrelevant en la performance que vam fer a l'aplicació. Aquesta és una bona situació, podem focusar-nos en altres coses, i això és el que fem ara.

El projecte en què estem involucrats és el CISC, el CISC-AVM, que és un CISC-AVM generalment proposat. which is a general proposed ZK-EBM. Basically, as others that are in the space, we want to prove any program that is written in a high-level language like Rust, CPP, or others. The motivation of doing this project, it's very meaningful for us because we have acquired a lot of experience, a lot of tooling, a lot of knowledge on running the ZK-EBM, és molt significatiu per a nosaltres perquè hem adquirit molta experiència, molta informació, molt de coneixement en fer el ZK-EBM, que ha estat en Mainnet dos anys i hem patit molt amb les performances. Així podem prendre avantatge de totes aquestes coses que hem après per posar-les en servei d'aquest nou projecte, que és més general i pot ser més impactant en general per a qualsevol usuari.

És obert, tu pots xerrar la GitHub, no és tot complet per fer una prova, però és gairebé allà, potser en un o dues setmanes serem capaços de provar qualsevol codi que es trobi escrit a REST. Ara, la major diferència amb aquest nou to prove any code that comes written in Rust. Okay, now, the main difference with this new proving system, so the proving system that we are doing for Zisk, it's different in many ways, but the main difference comes from the remitization, because now we don't have any more static capacity for the trace. We will have a dynamic capacity. This means that we will shape the trace depending on the inputs.

And it will be divided into different instances. All this will be explained in the next talk, so I cannot skip the responsibility of explaining this well, but of course I encourage you to stay to understand all the implications of this. On the proving time, basically you will have to prove all the instances that you have generated on the arithmetization. We call them sub-proof. So we have an array of sub-proofs to be proven.

And then, of course, we will have an aggregation phase on which we will aggregate all the proofs resulting from for all the instances that will result on a single proof. Okay? en què agregarem totes les proves que resulten en una sola prova. Pensem en les implicacions computacionals de tot això. De fet, en l'eficiència de la CPU, no es pot obtenir res d'aquest.

Es pot obtenir una hora pitjor. Per què? Bàsicament, el cost d one proof is proportional to the area, and this stays true even when you go to small instances. So you have proportional cost. You have divided the main trace into different sub-traces, but the sum of the areas is more or less the same.

Of course, we have eliminated the padding effects. This is helpful, and it will reduce a little bit the overall area, la suma d'àrees és més o menys la mateixa. És clar que hem eliminat els efectes de padding, que això és útil, i això reduirà una mica l'àrea overall, però no és una gran diferència. I tenim altres costos de degrada. A l'endemà, estem fent la prova una mica més costosa.

Aleshores, amb aquesta nova granularitat, hi ha un munt d'oportunitats. However, with this new granularity, there are a bunch of opportunities. And the most important one is that we can take advantage of accelerators without having this limitation of being to move data back and forth from the host to the GPU, with this PCI Express limitation. So this is one very important improvement here. We will be able to exploit GPUs much more efficiently.

We have other ideas, like vectorizing the execution of Starks. So we can kind of run eight Starks at the same time with trying to do every operation in a vector register containing elements of different Starks. These are some kind of ideas that we are considering. But the most appealing idea for us is going to distributed computing. Basically, the idea of distributed computing però la més apropiada idea per a nosaltres és la de distribució de computació.

Bàsicament, la idea de distribució de computació és que vols fer-ne la teva prova sense fer-ne una sola instància al cloud, sinó diverses instàncies, i amb això intentes escalar més fort la teva aplicació. Vols produir una latència, que és un dels focussos de aquest projecte. Parlem de la distribuïda proveïda. Primer de tot, som molt feliços, tenim una avantatge molt important en aquest projecte, és que tenim accés a un supercomputador, que es diu Selenius, és part de la organització de la CCEURO, una organització en els Neus. És part de l'EUROHPC, però és una divisió en els Neus, diguem-ne.

Ens van donar recursos per fer les nostres proves. Vam fer un projecte de recerca on volíem trobar els límits de la lluita per la Stark. Vam veure on ens podíem anar, com anar en la reducció de la latència. Aquest és el nostre objectiu. Aquí tenim tres línies.

Tenim centenars de milions de CPUs que podem llançar juntes en una prova. No anirem a aquest nivell, però la hardware és allà. I també tenim centenars de GPUs que podem llançar per fer una prova. A més a més, volem targetar la performance de màxima edat, però tot el que fem pot ser fer-ho a la cloud també. Volem reproduir a la escala menys, volem reproduir els resultats a la cloud.

I això és molt important perquè la producció no es farà en un supercomputador, serà fet en un sistema de la cloud, com els que utilitzem avui. Parlem de la primera part, de fer la traça. La computació de la winters és la part de fer la traça que ve des dels inputs. Com ho farem en un ambient distribut? La manera més naïfa de fer-ho seria...

Bé, tinc diversos processos. Parlo de processos i darrere. Un procés. Dos processos no comparteixen memòria, doncs són processos distribuïts a través de la xarxa i després els processos espanten darrere. Tu pots assignar un procés, el rol màster, i dir que computaràs el trac, i després distribuiràs the result into equal parts, and then send to the others, okay?

This is a functional approach, but it's not scalable at all. So we are not parallelizing anything. We have a lot of memory requirements in the master process, and we are also adding a high communication overhead. So it's not a serious approach. Now, let's try to get rid of the communication costs.

Let's do the computation of the witness, redundant in every process. Okay, that's fine. We have to get rid of the communication costs, but we are not accelerating because it's redundant, and we have high memory requirements in all the processes perquè és redundant, i tenim requeriments de memòria en tots els processos, perquè tots els requeriments han de guardar tots els trets. No encara hi són. La segona estratègia que hem desenvolupat és minimitzar els trets que generem.

Hem dividit la generació de trets en dues estades. En la primera estada, només generem el que anomenem el tre minimum, divided the trace generation in kind of two stages. In the first stage, we only generate what we call the minimum trace, which is the information that you require to then, in a second stage, restart the evaluation of the trace at any point. So in a second stage, we can, in parallel, recompute the trace and divide this computation. So we have this first stage of computing the minimum trace, which is very fast.

And then we can, from the information generated in this process, we can distribute the trace between processes. I mean, each process will have had run this same... This first step of generating the minimum trace has been run by all the processes. aquest primer pas de generació de la trama mínima ha estat fet amb tots els processos, tots els processos saben quin és el lloc actual que s'ha de distribuir, i tots els processos prenen una part i computeixen aquesta part, però només aquesta part. Això escala molt millor.

Ok, mirem els resultats. El test que estic utilitzant aquí i en els següents slides Let's look at the results. The test that I am using here and in the next slides, it's a program that executes 10,000 SHA-256 hash operations. The decision that we are generating is not complete, because as I said, this project is under development. At the actual moment, at that point, we're generating instances for the main and the binaries and some multiplicity tables.

Aquest projecte està en desenvolupament. En el moment actual, a aquest punt, estem generant instances per a la majoria i les binàries i algunes tables de multiplicitat, però és prou per entendre els resultats i el potencial d'això. Ara, si considerem com a referència l'estona d'emulació, que és executar el programa sense generar cap trac, encara que no sigui el tracció mínima, el temps és 0,6 segons per aquest programa. Això vol dir que estem fent 80 MHz, és la nostra velocitat. L'abans de generar les traces ranya amb un instant, amb un nodi de computació, és al 100%, doncs estem doblement aquest temps, a dalt del 37% nodi de computació, és d'uns 100%, doncs estem doblement aquest temps, a 37% en instances de computació.

Així que anem molt endavant. La escalaritat no és gaire bona perquè estem ja molt fàcils en l'execució d'aquestes... de la traça, perquè ho estem dividint en threads en un nodi de computació. Però, a la fi, because we are dividing it into threads on a single node. But at the end, really this overhead is very acceptable, okay?

Only 37%. Okay, I will go a little bit fast because I am running out of time. Then let's talk about the distributed, how we manage the distribution of the sub-proofs. So we have to solve the proof for all these instances that have been generated. Here we have a synchronization point because all these instances share the transcript.

This means that this object to get the randomness for the next stage is shared between all the instances. And this poses some synchronization between the execution of all these instances. What we do is a communication stage where we share the roots that we have to put to that transcript and then we get the same randomness in each of the proofs. Let's see the results. Scalability of this phase, generating the sub-proofs, it's 100% efficiency.

We go from 70 seconds down to 3.3 seconds. It's a little bit suspicious that we have even superlinality. So if you see the efficiency, which is the line, it goes over 100% at some points. So this is something that is not, let's say, which is the line, it goes over 100% at some points.

So this is something that is not, let's say, a little bit suspicious. The problem here is that the distributed prover even runs better in a single node. Because you can fix better the granularity of the threads that you are using for the subproves. Then if we compare the base point is the distributed proidor en un únic nodi computador, obtenim una cosa més significativa. Així obtenim una eficiència paral·lela de 80%.

Això és bo. Anem a la distribució. La recursió. Tindrem requeriments de comunicació quan generarem el 3, recursion, we'll have some communication requirements when we generate the tree, because the subproofs that we are aggregating can be hosted in different processes. We have to transfer to the process that will generate the aggregation.

And if we look at the parallel efficiency, really, it's not so appealing, right? It's 44%. Okay. But here, the problem that we have is that when we are going down to the tree, at some point we have less aggregations to do than processes. So there are some resources that are being not used at all.

So if we just release these processes to do other things, the real parallel efficiency related to the hardware that we are consuming is 88%. So it's, again, a very acceptable parallel performance. Now, if we look at the complete overall situation for all the proof, including the win-loss computation, the sub-proofs and aggregation, the parallel efficiency is 78%. We go from 125 seconds down to 12.2 secondsons.

La recursió es pren la major part del temps ara. És el 65% de la prova. Així hem de focusar per optimitzar la performance i menjar més la latència. I la conclusió més important és que, com que tenim una bona eficiència paral·lela, és el 70%, podem augmentar la latència per 10X. Hem augmentat la latència de la prova it's 70%, we can increase the latency by 10x, right?

We have increased the latency of the proof by 10x, while the costs have only increased 27%. So this is a very good situation to have because basically it means that you can really decrease the latency without additional costs. So that's why we... And this can be reproduced in the cloud because we are not we don't rely on a very high performance network because the transferring of data that we are doing is really minimal. We are transferring proofs or we are transferring routes which is minimal information.

So just I am closing with this. So we have, we can decrease, reduce the latency at a very low Estic acabant amb això. Podem reduir la latència a un increment de cost molt baix. I, com a millors millors, ens centrem en la recursió, en alguns algoritmes, com la estira i la multifrida. És clar que aquí no hi ha la GPU.

Amb la GPU podem extreure-la encara més, perquè la nostra performance, la nostra arquitectura, pot suport accelerate more, because our performance, our architecture can support GPUs very well, because the instances are smaller. We can even reduce more the performance with the GPUs. And also, run on the cloud infrastructure is our next step. OK, sorry for extending a little bit. And I can take any question.

Thank you, Ricard. Yeah, a round of applause. So we'll have a few questions. Reminder that great for everyone who submitted. The QR code is always in the presentation.

And you can also vote them. So we're going to start, if it's all right for you, with the first one. Could you give an intuition of how do you generate a minimum trace that can then be used to restart the trace at any point? What's the data structure like? Yeah, the minimum trace only has, it's kind of evaluating the columns that you require to then be able to extend the trace.

And this basically is two columns for the main machine, which is the ones that load data from the memory. It's kind of a A and B register. So it's only two columns. From that, the rest of columns that compose the main trace can be generated from this information at a given checkpoint. So that's basically it.

So it's all waiting just a subset of two columns. Great. So the next one voted, can we say SyscVM basically trades more aggregation costs with better concurrency architecture? So basically, yeah. Yeah, that is one way to see it.

Although the aggregation costs now are huge, and we have to pay for this aggregation, of course, to have this granularity that we are interested in, but we want to reduce as much as possible it by improving the algorithms. For instance, Flunky2 has a very fast aggregation. We can do something similar. We have the approach that reduces the number of queries that you have to verify on each aggregation step. So we have a package of things that we can do to improve this part.

Also, we have to really think which is the granularity that is more suited for our hardware. So maybe we can generate less instances if we can really exploit the hardware well. And then the recursion will have less levels Okay, so a lot of investigation. It's it's coming on this part because as you saw it's the one that It's more relevant at this point. Okay, great great great The next one is can Sisk run programs written in lower level circuit languages will they be faster than rust will the gap ever disappear?

the top one. Well, the purpose of this is not this. The purpose of this is basically generate the inputs with a high level language. Basically Rust, C++, or any other language. So this is mainly the design point of this.

Of course, you may be able to generate some arithmetization and then use the prover as a component that can be self-contained, and you may be able to use it. But the main purpose is just you generate your code in a high-level language. You don't care about anything. you will get the proof of the execution of this program from the inputs which would be the inputs of the program, the outputs of the program, and the ELF of the compilation of the program with RISC-V or any other architectures that we are also considering like Wasm or LLVM. Great, great, great.

And I think we got chance with one more quick. Just trying to be futuristic, can you give insights of what could probably be done in order to improve the CKE VM or VM prover in one or two orders of magnitude? For me, it's clear that we have to go, the distribution vector is a path, or a vector of improvement that we have to take, because if you rely on more specialized and complicated hardware on a single, but relying on a single instance, on a single node, you won't accelerate. But we're going to take advantage of the most sophisticated node available, the most sophisticated hardware available and compose it and take it two, three, four, whatever number can fit with a good parallel efficiency. Because we want to control all the time the costs of the proof.

If you have parallel efficiency, it means the cost doesn't grow. So that's the trade-off that we really have to take into account. Amazing. Please give a big welcome to AlphaPlus.