From Bottlenecks to Breakthroughs: Optimizing zkEVM Provers by Leo Jeong | Devcon SEA

[Music] it's first time I'm wearing this microphone I feel like I'm a K-pop Star now anyway yeah so really nice to meet you um I'm a I'm Leo Jong i I'm a senior research engineer at Linea and today I'm going to talk about how to optimize ZK EV improvers so this is the outline of today's talk I will talk about the motivation and also the introduction of this talk I will share how to optimize zkv improvers based on our uh one more than one year of our optimization experience and we'll conclude the talk so first time um so this is the initial Challenge and problems we had so Linea launched our main net last year August and we were so happy so we are kind of dancing all the time but we realized that PR was really slow so we were like what's going on here uh and um we were spending a lot of money for provs so we thought it's a huge problem and we decided to optimize it so what we did is for uh more than one year we spent a lot of time and effort uh optimizing River in production so that picture that's actually me uh fixing and optimizing PR in re in production so your production your PR is running maget and you need to fix it uh that's what I did but luckily we were able to uh reduce the proval run time by almost 75% which is good so today uh that's the um main content that I'm going to share today first of all uh let's talk about why it's important to optimize improver uh the first thing is of course money this is the one of the biggest cost contributors in ZK rups and pro optimization directly means you can reduce the operating operating cost of your GK GK project so which is very important the second the performance impact so when you optimize um approver that means you have less leun time of your approver which also means you have faster verification and final finalization and that way you can improve your TPS right and you your users will be happy and lastly you have you can also improve your scalability by optimizing ZK improver because you can support more transactions which means you can handle more complex proofs as well so let me share some common bot legs here so most zkm provs and project they have really high complex ability so inheritant I mean ZK EVMS are very U complex because we want to kind of simulate EVMS right and we want to provide the full compatibility so every project has their own design um their architecture so it's really hard to optimize uh but all project project there something in common they have high resource consumptions right so CPU and memory they're using uh a lot of CPU and memory and also because to support large scale cryptographic calculations so we have uh these things in common so the common botle leg is you have CPU usage and parallelization issues probably and then you will have memory overhead a lot and we will have iole X because you are dealing with a huge amount of data so uh this talk I will uh I will talk about what we will cover and what will not be covered so first time we will not cover linear specific optimizations because you know if I share that kind of information you can't apply that to your project so as so I'm not going to talk about detailed cryptographic theory behind our project or ckvm and also I will not share about share uh Hardware accelerated optimizations and we'll focus on CPU optimizations so here I will cover some quick wins and strategies so you can just pick up and uh apply to your project uh in in a week or two weeks or sometimes maybe um on the flight going back your home uh you can actually apply that easily and then I will share mostly on CPU and memory optimizations without any significant changes on your architecture or on your code so that was the intro and we'll share about the problems right now and how to actually optimize it the first thing you have to do is you know you need to know um your your your code right so there's a really famous and famous quote in this programming World which is premature optimization is really bad let's just don't do that because you know uh sometimes you want to optimize your code because you know it it feels fun so you just optimize it and because you think it's going to be the botle leg but most cases it's not so before you actually start optimizing your code you need to find out the problems first and the most common way or easy easiest way to do that is using CPU and memory profiling so most languages they have kind of builtin profiling tools so that you can visualize your CPU or memory usage and you can understand your code there uh in our case we are using go we based in um so we used that kind of that tool that profiling tool to visualize our program so this uh is the CPU and memory profiling we actually had this is the whole whole life life cycle of our prover so I know what you're thinking right now you're like oh no I'm going to just sleep for 20 minutes wake me up in 20 minutes but don't worry yeah we spent a lot of time so and then we kind of categorized them for you and we'll share that uh quickly today so we here you can see many uh holes or sparse areas which is white white colored so here the green color means you are using CPU very extensively so you're good but white colors that means something is wrong so mostly it means CPU is underutilized so you find out which part is not being used fully and then you go into the code and you look at the code and you can fix it and on top of that we have memory usage patterns and the the main goal of memory usage or memory optimization is to reduce the memory pics so first time I will talk about CPU and then we'll move to memory so um you have many different CPU issues but mostly it's going to be two cases the first one is poor parallelization and then the second one is uh CPU under utilization the first first panel when you look at this um this graph here you have CPU number one to maybe CPU number 100 and we are using only five CPUs actively and the others are just doing nothing so we realized many cases we have these issues so we had to to add more parallelization to improve that uh the second second one is you are actually using 100 CPUs but between uh between some run times you are waiting for something so that means you are underutilizing your CPU the first thing so how to improve parallelization uh this is common methodology that you can apply to your program so first thing is you just draw your modules like like a graph of on the left and then you show you grab you also draw your dependencies like that and then on the right side you can have those Lego blocks and then you can um find out some better execution scenarios for example in our case so this was the issue right now right and the this module actually was about reading the setup for the prover and the especially proven key we were reading this from the disk and and originally on the left side at V5 had issues of paralyzation so we changed this uh this blocks on the left to the right so we moved that V5 uh to the early stage of of our approval life cycle so that the total runtime of T2 became smaller than T1 uh the other issue common issue is CPU underutilization so this has has actually many uh many pro U many causes so many root issues so the first one could be poor penalization second one synchronization issues and lock up issues and most sometimes you have some uh blocking iio operations operations when you're using disk or network so in our case uh we had this issue in fft and we we had synchronization issue in our data structure so we have to slightly change our data structure so the CPUs are not not waiting for other data so after uh optimizing CP CPU so we changed our CPU usage pattern from left side to the right side so we got one okay cat is happy so got one uh okay cat for CPU optimization but we need one more for memory optimization so let's move to memory optimization actually more than CPU uh memory optimization is more important because in general in most Cloud systems or cloud service cloud services memory is more expensive than CPU for example uh you can see that we our Peak memory usage was 700 Gaby and then so we have to use sub machine with 970 Gaby right which is very expensive but when we can move from this one to the other one with 380 gab we can save a lot of money but we will also we can can get more ches so our plan was let's to reduce our CPU pick memory to maybe somewhere between 308 uh so around 380 gab so the goal is flatten memory usage and memory pick that's the most important one when you are working on memory optimization so the first thing we we did is using memory pulling so it means sometimes you have many data stru structures in approver and some data structures are being used tens hundreds of times or thousands of times and when you just allocate that data structure every time when you need that um you will allocate that memory and also sometimes the garbage collector uh will spend some some time to return that memory to the system so instead of you instead of doing that you just set up this large memory pool for your data structure and you just allocate that and use it and when you don't use it when you don't you're not you're not using it anymore you just return it to the pool and you keep doing this so you only allocate once and you just use it and you just return it only once so by using this one we reduced our memory pick to 450 GB but still not enough so we use this mem limit most languages they support this feature so it's a soft limit of memory pick so so the language for you they trigger garbage collection when the memory usage hits uh this memory limit so in our case when you see here uh in the inside right Circle we have many many memory pcks but that's exactly around 307 gigabyte so your your language or run time will just run garbage collection so it will not go up above like 37 uh gigabyte here so finally we were able to move to the smaller machine and then but with more course and cheaper machine but we found out we are spending too much time in these specific areas uh because of garbage collection so we thought maybe we need to do something more um so garbage collection is something that many in many garbage collected languages they just do it for you right so it's very convenient but it's really hard to predict when this will be when this will and this will happen so what if it happens during a very critical tasks or areas of your code this this will be a huge problem for example in our code here so we are doing some fft inverse function over there and it's very CPU intensive and memory intensive so we realize that every time when this part is running the the runtime language runtime try to to actually run garbage collection randomly and because this is really critical in terms of CPU usage and memory usage it slowed down the pro whole program a lot so so uh we realized let's manually garbage collect before entering that critical areas so we decide to run manual garbage collection before these critical tasks so that we have less context switching overhead inside or during these critical areas and which actually reduce the runtime a lot so uh if you have these kind of issues you you can just manually run garbage collection before those areas and will you will get a lot of improvement lastly um so we felt everything's okay looks good but sometimes when you have really large uh input data um you you will see sometimes out of memory issue right uh and because we have a very specific size of physical memory it's not easy to to solve that so sometimes you need to move to larger machine very expensive machine with larger memory and then you have to learn run that but we we we find out this solution it's called zerm it's a inmemory swap feature most Linux systems have this feure and you can just turn it on and turn it off we all know the swap space in uh storage or dis right but it's slow so in production it's almost hard um it's impossible to use it but this feature here it's inmemory swap so this one if you don't have enough memory this will compress your data inside your memory and will just sort that within your memory so for example over there you have like we have like 74 7 140 gab of memory physical memory but I set up like 100 1.5 terabyte of swap space so you can actually have a lot more memory and that kind of fast swoft space in your system so we are actively using this for massive integration test with terabytes of memory usage so finally we got two happy okay cats uh and let's um I will'll share quickly one more optimization things so one thing is data compression so we realized the trans data has really high compression ratio so if you IO or network is the bottle deck you can just compress it and for example our case 40 gab of Tres could be um 2 gigabyte of trace and zero isation is a kind of time you you spend on initializing your data so because you we are dealing with very large data set and very large data structure sometimes time time taken for uh initializing your data is a lot so you you might need to auto zeroize iation supported by your language or use optimized library or lowle libraries for zation so let's conclude the talk um so result we were so happy happy happy yeah and then we reduced like okay we improve a r Time by 75% which is good and we saved a lot of operating cost cost not only saving the operating Cod we reinvented that reinvented that to uh into our PR system so we increased the final F finality speed and also higher TPS and ironically we were able to und understand what we did and what we built and what we are doing which is I think most important one and some lessons we learned please uh do not pre- optimize your code unless you fully understand your code so I strongly recommend that make optimizations only based on on your measurement and instead of doing this with a kind of a local view uh you you need you need someone to have a global view so that you some uh you can set priorities for optimizations our future work includes distributed gkv improver so different modules running on different machines that means we can run some we can use some smaller machines to save cost and then we are thinking about also how do we accelerate provs we think optimization is never a one-time task so please measure analyze optimize and repeat thank you nice seeing great great great presentation Leo all right so remember you can always uh ask more questions and vote for the questions that you want it to be answered so let's start with the first one How could a f CH okay this this is a spicy How could a thir challenge Benchmark over same machines and input be organized among um CK l2s to get like yeah to Benchmark up against different systems um I think it's really hard yeah I think because I I explained that um in the maybe introduction because every team or every project has different architecture different models different based on different cryptography so I think this is just a good research area I me has been solved yet so yeah it's hard at least um maybe CPU based CPU based or some specific cryptography based it could be yeah benchmarked but in general it's really hard yeah yeah yeah agreed would you recommend on Prem PR or Cloud PR um right now I think uh you can you can I think you better start from the cloudbased yeah because cloud based especially on the early stage or especially when you are a small project M makes sense if the memory compresses well then couldn't you instead use more efficient data structures in linear sorry um is the top one if the memory compress as well then couldn't you instead use more efficient data structures in Linea yeah actually yeah that's true um we are trying to use optimize our data structure as well uh right now we are we don't actually imp uh compress the data structure in production because uh to avoid some side effects but uh after optimizing a lot and and we have too too many transactions or too much trans transactions I think yeah we need to come up with better Tera structure yeah as you say it never ends right always optimizing I've read that the finality of line is around 8 to3 to hours will these improvements allow these to be reduced and if so how low can it go um actually um the finality time has includes many different factors actually not not only the prover itself but number of transaction or uh service lay uh service layer agreement or something like that so it's not only it doesn't depend on solely on the Prov optimization actually it's more than that so yeah agree have you had examples in where an attempt said optimization actually backfire in an unpredictable way yeah that's true um so I I think that um M limit stuff is actually one of them without M limit the soft memory limit stuff because that automatically triggering garbage collection for you we didn't have any issues in global constraints part but after applying that we actually got a lot of garbage collector collection calls within glev constraints and maybe the runtime increased a lot by that and uh that was actually a huge issue and we finally found out and I fixed it great great has Linea ckvm thought about switching to ckvm to further improve performance um I I have no idea on this to in this question so yeah maybe I'll skip it yeah yeah let's skip it uh remember you can always find the speaker after these these questions we can discuss about discuss it and yeah what are some tra ofs that lenia made in contrast with other CK EVMS well let's say I I saw many Project based on CPU or F fpga and how to accelerate and uh we thought uh starting with the simplest design and architecture is the best one and especially for uh so that any small project or researchers they can just simply run our product and then share ideas uh to be more decentralized so for for a while I we think uh we're going to keep this um design choice and we'll uh continuously work on optimization of yeah CPU based Cs and stuff great and I think we have one more time for one more besides those techniques did line explored uh Hardware acceleration oh yeah a disc question um we are still thinking about it actually but uh in maybe in next maybe at least for a while whenever before everything's until everything's stabilized enough researched enough uh we will keep working on CPU based