# Leveraging High-Performance Computing for Efficient STARK Provers by Ricard Borrell | Devcon SEA

- Speakers: [Ricard Borrell](https://streameth.org/speakers/ricard-borrell)
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2025-10-09
- Duration: 27:30
- Topics: Science & Technology
- Watch: https://streameth.org/watch/yt--4Sz8etUrig
- YouTube: https://www.youtube.com/watch?v=-4Sz8etUrig

## Description

Zero-Knowledge Proof (ZKP) protocols' applicability hinges on the prover's ability to efficiently generate proofs. This talk explores the computational aspects affecting ZKP performance, specifically focusing on STARK provers. We will analyze performance across high-performance and standard computing architectures and interpret results by examining key workload characteristics. From this understanding, we can project ZKP capabilities in future scenarios.

Speaker(s): Ricard Borrell
Skill level: Intermediate
Track: Applied Cryptography
Keywords: ZK-EVMs, ZKP, STARK, optimization

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum, https://warpcast.com/devcon
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on Swarm, IPFS and more.

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon SEA was held in Bangkok, Thailand on Nov 12 - Nov 15, 2024.
Devcon is organized and presented by the Ethereum Foundation. To find out more, please visit https://ethereum.foundation/

## Transcript

[Music] hello everyone thank you for being here I am rard b as he said thank you for the presentation I work at polygon um basically I work on on developing and optimizing ZK uh technology and yeah this presentation is about leveraging high performance Computing for efficient star provs um the presentation is divided in two parts first I will talk about the present in terms of product which is the ZK evm and I will explain a little bit the the Lessons Learned on the development development of the ZK evbm and then I will talk about the future uh which is what we are working now which is the the a ZK BM so a general propose proving system uh based on STS as well okay let's go for the ZK evbm the ZK evm were released two years ago and each Prov is based on a a stark method and uh well we have an Stark and then we have aggregation to uh so we have a recursion process to aggregate proofs and then uh from uh with a certain frequency will uh send the proofs to L1 okay the only thing that we need to understand about an star for this talk is that it basically has two stages or two phases in the first phase we will compute the trays and then in the second phase we will take the fry polinomial which is kind of a summary of all the trays in a single polinomial and we will prove uh the proximity to a CL low degree polinomial right uh the comit phase is done in different stages uh this means that the trace is is is filled in different stages and this is because we need Randomness for some of the stages we need to we need some random numbers toate some of the polinomial of the of the trace and this Randomness is obtained from the previous stages so the roots of of the of the of the of the pooms evaluated in the previous stages are committed to the transcript or are added to the transcript and then we get Randomness for the uh next stage that we have to to evaluate okay uh in our arithmetization of the zkm we have 1,300 more or less polinomial and then the number of rows of the trace which is something that we can fix uh it's it's a parameter of the BL let's say it's uh two to the 25 so it's about 32 million this is quite a lot and it it ends up posing uh a requirements of uh 800 gab of memory okay I will talk more about this okay um so why we use such a big number of of of rows on our Trace basically because we have a you have a monolitic approach on imization this means that we have a static capacity so the our trace the capacity of of our Trace is determined by the number of rows and so we we fix a big number because basically um we want to be able to handle any transaction that comes to the network okay that's why for the most heavy uh loaded transactions that that the ones that will will need more steps we we have to uh we we need to have enough space to to handle them okay this approach has some disant has advantages but also some disadvantages clear a clear one is that okay uh when we have to close a batch because we don't have more room for new transactions uh because some of the state Machines of the of the trades are filled uh then there will be some spare um cells on the trades that we have to prove but they are not they are not being uh filled with with with real uh values coming from the inputs okay so we have some padding effects uh but also has some advantages for instance that we have a um like a constant workload that we can optimize very well we can allocate buffers on on Advance Etc so it also has some uh Advantage related to Performance now let's talk about timings uh aof of this huge Trace uh for the ZM takes about 6 minutes and the cost with the uh gcp instance that supports ABX 512 it's only 0.46 normalized by the number of transactions ethereum transactions that that we can fit within a batch uh it's about 0.2 milll uh this would be the overhead per per transaction okay so it's a very low overhead which is negligible in terms of the grand scheme of things in terms of the cost that adds to the transaction uh moreover uh okx has uh done a a very um interesting job that it has ported the pr to CPUs and this has decreasing the latency to about 3 minutes okay so uh and even decreasing the cost so this is a a perfect situation where we decrease the latency at the cost by using uh gpus those are numbers given by them and at the end we end up having 0.1 Mill dollar per added on on the cost of the transaction okay so it's really good uh the speed up obtained from the CPU to the GPU it's only uh if we if we consider end the end to end proof from the to the end it's 2x here is is one of the limitations of the appr as we have such a huge Trace at the end we will we will be transferring a lot of data between the host and the device during the execution of the kernels okay we and we will be limited by the PCI Express however still if we look at the real cost what it's the end what matters they are very low so it's not something that it's very relevant in the in in the Gurren context if we go a a little bit deeper and look into the kernels this distribution when we do appr pro it's a perfect situation or a good situation because we have that 95% of the time of the time of the proof it's just uh concentrated in four Kels especially in two which are the entity and the merization which take 70% of the time and then we have Expressions that are linear combination of polinomial and then the executor which is the first phase of the of the trace evaluation so it's the part of the tra evaluation that uh depends on the inputs okay this is the the initial exec tion of the inputs so basically we have to focus on on these four kernel basically on two and that's what we did a lot of work on on this during on the past before releasing the the ZK evm the first thing you have to consider when you want to optimize a code it's to understand which where are the boundaries for the for this code and basically you have to do a roof line analysis basically the roof line analysis uh shows you where where is the limit depending on thetic intensity of your kernel okay if your kernel does a lot of operations per each field element that you upload to uh the cach of the CPU it means that you it will be bounded by the CPU by the by by by the Computing part of the process and if you have a lower imatic intensity you are you are becoming bounded by the 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 uh field element involved in the hashing okay so we focused a lot on optimizing the optimizing The Entity uh we did um a lot of uh basically the focus here was to minimize the L3 misses we got uh well the at the end the result it's the performance that we get is to um perform the entity on 100 polinomial of size 2 to 23 it's 1.9 seconds this is more or less the reference and then the merization of course is about uh in the CPU in the GPU is another thing in the CPU it's about vectorization vectorization so taking advantage of the vector registers to do in each clock to try to do four eight uh operations at the same time and we go to a performance with goldogs one not goldogs 2 of 1 million hashes per second okay so this is the summary of what we did more or less two years ago before launching the zkm at some point we arrived to the conclusion that keeping improving the pr would not have any relevant impact on the on the performance of all the zkm because we were not the pro was not a ble neck at all okay so we were very happy with the with the performance that we were delivering to the to the application okay that's a good situation we can focus on other stuff uh and that's what we are doing now the project in in which we are involved is the the cisk dkbm which is a general propose uh zkm uh basically uh as others that are in the space we want to prove uh any program that uh it's written in a high level language like like thrust CPP or others okay uh the motivation of doing this project or the the it's very meaningful for us because we have acquired a lot of experience a lot of tooling a lot of er knowledge on running the zkm which has been in many two years and has been uh well we have uh struggled a lot with performance ET so we can take advantage of all these things that we have learned to put them for in the service of this new project uh which is more General and and can be more more impactful for for for in general for the for the any user okay uh it's open you can you can check the GitHub it's not fully fully it's not everything complete to do a proof but uh it's almost there so maybe in one two weeks we will be able to prove any code that comes written in in R okay now the main difference with this new um proving system so the proving system that we are doing for for zisk h it's differing in many ways but the main difference comes from deratization or because now we don't have anymore an a static capacity for the trace we will have a dynamic capacity this means that we will shape the trace depending on the input okay and it will be uh div dived in different into different eight instances all this will be explained in the next talk so I don't I can skip the responsibility of explaining this well but of course I I encourage you to stay to to understand all the all the implications of this okay uh on the proving time basically you will have to you will have to prove uh all the instances that you have generated onization we call them sub proof so we have an array of s proof to to be proven and then of course we'll have an aggregation phase on which on on which we will aggregate all the all the proofs resulting from for all the instances that will result on a single proof okay let's think about the computational implications of all of this uh in fact on the CPU efficiency out of the box you don't get anything of this you get worse time worse uh CPU time why but basically the GPU I the the the cost of one proof is proportional to the area and this this uh stays through even when you go to small small small instances okay so you have proportional cost you have divided the main Trace into different sub traces but the area is more or less the sum of the areas is more or less the same of course we have eliminated the padding effects that this this is helpful but uh and it will reduce a little bit the overall area but it's not a big it's not a big difference and of and we have added agregation cost so at the end we are kind of making more the proof a little bit more more costly however with this new granularity there are a bunch of opportunities and the most important one is that we can take advantage of accelerators um without having this limitation of being to move data back and forth from the host to the GPU okay with this PCI Express limitation so this is one very important Improvement here we will be able to exploit gpus more much more efficiently we have other ideas that Vector like uh vectorizing the execution of a Starks so we can kind of run eight Starks at the same time with trying to do every operation in a vector register containing uh elements of different Starks okay these some kind of ideas that we are considering but the most appealing idea for us uh it's going to distribute a Computing basically the idea of Distributing Computing is that you want to R to run uh your proof using uh not one single instance on on the cloud by various instances and with this try to Stronger scaling your your your application okay you you want to produce a latency which is one of the main focus of of this project of this project okay so let's talk about distributed prer ah first of all um one of the we are very happy or we have had an we have a very important advantage on this project is that we have access to a supercomputer which is called selenius it's part of the CC Euro organization with the in Netherlands okay it's part of the erpc but the Vision in Netherlands let's say and we were granted uh of resources there to do our proofs we kind of submitted the research project where we want to find the limits ofing a stark we want to see where can we go where where how how how far can we go on the reduction of the latency okay this is our goal uh there it's three line for us we have hundreds of thousands of CPU course that we can link together in a proof we won't go to at this level but Hardware is there and we can we have of gpus as well that we could link to to run a proof okay um nonetheless uh we want to we want to Target the high-end performance available but all that we are doing is can be running on the cloud as well so we want to reproduce at a lower scale we want to reproduce the results on the cloud and this is very important because the production won't be done on on a super computer will be done on a cloud system like the ones that we are using today okay let's talk about the first part filling the trace the wus computation is the part of filling the trace that comes from the inputs um how will we do this in a distributed um environment the most na way to do this would be okay I have um I have several processes I talk about processes and threats here one process two process don't share memory so are process distributed across the network and and then the process Spa threads okay so you can assign one process the master role and say okay you will compute the trace and then send distribute the result into equal parts and then send to the others okay this is a functional approach but is not scalable at all so we will have 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 approach uh serious approach now let's try to get get rid of the communication costs let's do the computation of the weakness uh redundant in every in every process okay that's fine we have get rid of the communication costs but we are not accelerating because it's redundant and we have um um we have high memory requirements in all the processes because all of them have to store all the trays so not not still there okay the next strategy that we have been developing is okay let's minimize the trades that we generate so we have divided the tra generation in like kind of two stages in the first stage we only generate the minim what we call the minimum Trace which is the information that you require to uh then in a second stage restart the evaluation of the tra at any point okay so in a second stage we can in parallel recompute the trace and divide this computation okay so we have this first stage of computing the minimum Trace which is very fast and then uh we can from the information generated in this process we can distribute the tra between processes I mean each process will have had run this same Pro this same M the same this first uh step of gener generating the minimum Trace has been run by by all the processes then all of them know which is the actual load that have to be distributed and then all of them um take one part and then compute this part but only this part okay this scal this will much better okay let's look at the results the test that I am using here and in the next slid it's a a program that uh executes 10,000 sh56 uh um uh hash operations that iMed that we are generating is not complete okay because well as I said this Pro this project is under development at the actual moment at that point we're generating instances for the main and the binaries and some some multiplicity table but it's enough to understand the the the results and the potential of this okay uh now if we consider as a reference the emulation time which is executing the program without generating generating any Trace anything even not the minimum Trace okay the time is 0.6 seconds for this program this means that we are going about 80 MH is our our speed okay the overhead of generating the traces ranges with one instance with one compute node it's about 100% so we are doubling this time down to 37% on on ban instances me Computing nodes so we are going really down the scalability is not very good but because we are already very fast on the execution of this of the trace after uh because we are dividing it into threads on a single note but at the end really this head is not so is not very acceptable okay only 37% okay I will go a little bit fast because I am running out of time uh then let's talk about the distributed how we manage the distribution of the of the sub proofs so we have to solve the proof for all these instances that have been generated uh here we have um we just need to so here we have a synchronization point because all these instances have common share the the transcript okay this means that this object to get the randomness for the next stage is is shared between all the instances and this poses some synchronization between the execution of all these instances okay uh what we do is a communication stage where we share the roots that have we have to put to the transcript and then we get the same Randomness in each of the in each of the proofs let's see the results scalability of this phase generating the sub proofs it's 100% efficiency okay we go from 70 seconds to down to to 3.3 seconds okay uh it's a little bit suspicious that we have even super lineality so if you see the the efficiency 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 uh the problem here is that the distribut appr even runs better in a single note because you can fix better the granularity of the threads that you are using for for the for the sub proofs then if we compare the base point is the distributed Pro itself on one single compute Noe as a reference then we get something that is more meaning meaningful okay we are getting a parallel efficiency of 80% that's good let's go for the distribution the distribution uh the recursion sorry the recursion we have some communication requirements when we generate the Tre because the sub proof that we are aggregating can be hosted in different uh processes and we have to transfer to the process that will generate the agregation and if we look at the par efficiency really it's not so appealing right it's 44% okay but here we the problem that we have is that um um when we are going down to the three there are at some point we have less aggregations to do than processes okay so there are some resources that are being not used at all okay so if we if we just release these processes to do other things 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 the all the proof including including the windus computation the sub proofs and agregation the parallel efficiency is 78% we go from 125 seconds down to 12.2 seconds the recursion is taking most of the time right now it's 65% of the proof so this where we have to focus to optimize the the performance to even decrease more the latency and the most important conclusion here is that as we have a good parallel efficiency right uh it's 70% by 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 to have because basically it means that you can really decrease the latency uh without additional cost so that's why we and this can be reproduced in the cloud because we are not uh we don't rely in a very high high um performance Network because the transferring of data that we are doing is is really uh minimal we are transferring uh proofs or we we transferring Roots uh which is minimal information so just I am to very I'm closing with this so we have we can decrease redu latency at a very low uh cost increase and as futter improvements we will focus on the recursion on some algorithms like a Ste and multif Fry of course here there is not the GPU in so with the GPU we can even accelerate more because uh our our performance now our our architecture can uh support gpus very well because the instances are smaller we can even reduce the more the performance with the gpus and also run on the cloud infrastructure is our next step okay sorry for extending a little bit and I can take uh any question thank you record yeah Round of Applause so we'll have a few questions reminder that great for everyone who submitted the QR code is always uh in the presentation and we and you can also vote them so we're going to start if if it's all right for you uh with the first one could you give an intuition how do you generate a minimum Trace that can then be used to restart the Trad at any point what's the data structure like yeah uh then the minimum Trace only um has is 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 the ones that uh load the load data from the memory it's kind of the A and B register so it's only two columns from that the rest of columns that compose the main Trace uh can be generated from this information uh at a given checkpoint okay so that's that's basically it so it's evaluating just as a subset of two columns great so the next one voted can we say cisk VM basically trades more aggregation cost with better concurrency architecture so basically um yeah um yeah that's is one way to see it uh although uh the aggregation costs uh now are huge and we have to pay for this aggregation of course to have this granularity that we are interested on H but we want to reduce of as much as possible the itat by improving the algorithms for instance pl2 has a very fast aggregation we can do something similar we have the a Ste approach that reduces the number of queries that you have to ver verify on each agregation uh step so we have a package of things that we can we can we can do to to improve this part also we have to really think which is the the the ground reality that it's more suet for for or Hardware so it's not maybe you 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 uh it's it's coming on this part because as you saw it's the one that um it's more relevant at this point okay great great great the next one is can cisk run programs written in lower level circuit languages will they be faster than rust will the Gap ever disappear the the top one well the purpose of this is is is not this the purpose of this is basically uh generate the the inputs with with a high level language okay basically rust C++ or any other language so this is mainly the Des design point of of of this of course you may be able to generate some arithmetization or some and then use the prer as a component that can be um uh uh it can be self-contained and you may able to use it but uh the main purpose is it's just you generate your code with a high level language you don't care about anything you will get uh the proof of correctness of of the execution of this of this of this program from the inputs which will the inputs of the proof would be the input of the program the output of the program and the elf uh of the compilation of the program with risk five or any other uh other architectures that we are also considering like wmon or llbm or great great great and I think we got chance with one more quick uh just trying to be futuristic can you give it insights on what could probably be done in order to improve the CK evm or VM prover in one or two orders of magnitude for me it's clear that we have to go the the distribution Vector is a path or a vector of improvement that we have to take uh because if you rely on more specializ it and and complicated Hardware on a single but relying on on a single on a single instance on a single note you you won't we won't accelerate but we can take advantage of the more sophisticated uh note 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 are we want to control all the time the com the cost of the of the proof If you have par efficiency means the cost don't grow so that's that's the trade-off that that we really have to take into account amazing please give a big Ro of applause