'EVM384 - Doing Fast Crypto in EVM' - Paul Dworzanski

um we have a chat going there if you want to get involved um our next speaker i would like to introduce is paul dorzanski he is having some slight technical difficulties so we won't have camera on but paul will be giving a talk titled evm 348 doing fast crypto and evm so paul take it away when you're ready i hope you can hear me i'm in the process of sharing slides right now i hope you can see the slides can someone confirm that you can hear me and see the slides you are all good to go paul thank you so today um the topic is evm 384 for this talk it's a project and the in the title is also doing fast crypto in evm um i should explain uh the title um what i mean by crypto uh so that there are three sort of interesting things the word fast the word crypto and the words you know doing an evm what i mean by crypto is not all crypto just a certain class of crypto that's in demand right now uh don't worry this talk isn't crypto heavy um the by fast i mean uh pretty fast but not speed record fast but still pretty fast fast enough for for for our purposes and by saying in evm i mean user deployed user written in evm um so that's the topic uh this work is a lot of work went into this uh from alex casey i'm paul and jared and the rest of the ewozen team uh was very helpful as well so uh the goal is this is an engineering project so we should have some sort of goals in scope um so i have a goal slide uh the uh we want user deployed crypto like i said uh we want evm to to be generic enough to support any crypto uh for the for the for the purposes of this talk and this isn't very generic but there's a certain class of crypto that we're targeting for this talk in this project and that's any crypto with a bottleneck of modular 3d 100 384 bit or less arithmetic and for example bls 12 381 operations are very popular now for f2 especially and other projects as well but not only there are other things and we want our uh our project our evm384 product to support any crypto any crypto this is a strong statement uh with this bottleneck uh not some specific use case any any it's generic so i'm putting emphasis on the generosity and we want it to be fast uh what i mean by fast i said not speed record fast but very fast so approaching speed records uh there are optimizations that we you know we wanted users to deploy it we're in this evm world so we accept it we want some there's some tension between how generic we are and how fast we are so we are we we want it to be still be generic but we want it to be very fast more than fast enough for for use cases and the generic and then there's a whole interaction of the speed and why if we're generic then users can optimize for speed and as optimizations come along people can uh implement you know the new optimizations and the new crypto systems so there's some interplay with this as well so who's to say you know today it might be a little slower but as the optimizations come in it will improve with time um and the whole the whole idea is we want to have a renaissance of permissionless crypto innovation and we know with what we have with you know permissionless uh innovation with things like defy and earlier crypto kitties things like this and if we allow users to to deploy it themselves to design the whole crystal system themselves then we're hoping that there will be a whole renaissance and a whole you know blossoming of this whole ecosystem uh just based on adding uh this sort of evm384 project um so as engineers there are trends that we have to be aware of we want to design you know looking forward uh to the future we don't want to be obsolete so so the big trends in cryptography hardware and blockchain this is very loose this is a very high level you know i'm not being very specific about anything and maybe some of these things are controversial but one interesting thing i want to emphasize on this is that cryptography hardware and blockchain all interact with each other uh they drive each other they they and uh so i'll explain that as i go along uh the first bullet point fast crypto is designed with hardware in mind there are examples i'll give an example the blake hash function was based on some some cryptography some stream cipher that was designed with hardware in mind um the author of it said i designed this with hardware in mind and that's why it was fast because they knew that they if they knew how the hardware works they knew if they designed it like this uh it will be fast and if it's fast it's used you know slow crypto is unused fast crypto is good for everybody because people use it and the most popular crypto in the world the most used i mean crypto in the world uh is the fast crypto and and of course you know there's some mathematical beauty to cryptography we can do this this is possible but it's so slow that nobody uses it um maybe they will you know in the future when computers get faster another trend the second bullet point is there are breakthroughs in zero knowledge snarks and starks and others to point out a few but we are in some sort of renaissance as well in zero knowledge and cryptography in general uh and uh so there are interactions you know with with these these breakthroughs and with with hardware uh as well in the third bullet point that is making these breakthroughs possible uh because we can support hardware improvements allow more expensive crypto 30 years ago you know it would it would be too slow uh 10 years ago even it would be too slow but now it's it's it's usable because hardware is fast enough and looking forward as engineers we we wanted to we want uh we don't want to be obsolete um so we want it to be reasonably generic uh and um another one is there's a growing need for cryptography on chains your zk roll ups is one example but there are others so these are all trends and uh the the ethereum client complexity is growing so this might be controversial uh to say diversity is shrinking and some people have gone as far as to say stop freeze all proposals until we fix the diversity problem uh the reason that the ver they say that the reason diversity is shrinking is because client complexity is increasing and it's getting more and more difficult to implement the clients uh so there are interactions with with you know crypto and and the demands and there's a tension between the demand of new crypto and ethereum stability you know the diversity of is important for the for the stability and the robustness of the system if one client goes down it should be okay uh because there are other clients uh but but now there's a there's a major tension and we have to be forward-looking as well uh new crypto system systems it seems like they're coming out every year or two you know there are breakthroughs and we anticipate more in hardware there are co-processors fpgas quantum computers uh recently in the news was amd buying is in discussions to buy z-links which is an fpga producer as you know amd intel already owns altera which is another fpga producer uh and maybe they want to have co-processors uh and this this is already possible this is already you know in computing we see gpus as co-processors for uh high performance computing or for machine learning so there's a trend in this direction and that we're aware of and of course quantum computers we have to mention for cryptography they're very relevant but they're not here yet at least at any you know uh useful uh for any useful calculations and also wasm is plays a story as well uh it gives us nice guarantees and i will we'll speak we'll talk about wasm soon so at this point i want to give a history as well uh we want to be forward-looking with trends we also want to be backwards looking with history uh there are lessons learned along the way uh and we wrote a nice history in our first evm384 uh post in our first evm3 for update which is linked on the slide uh but i'll just i just want to mention the high points and there are more details there are more stories to be told that are very interesting but i just want to touch on a few things that are especially relevant uh some high points some historical high points and some lessons learned 2015 early pre-compiles uh for ec recovery shot 256 right on the id so this was the mechanism the pre-compile was a mechanism for doing crypto uh that users can call on chain with their contracts and you can talk about how they first came out uh in 2014 in a blog post by vitalik um and how evm came about as well we talked about that and uh something interesting happened in 2016. sha1 precompile was proposed and then someone said well do we need it is it possible to implement it in pure evm but in pure evm i mean user deployed you know just evm opcodes contract and uh in the contract code it it applies it uh it does this sha-1 calculation it implements the xiaowen function in other words and it turns out surprisingly yes we can do it in pure evm so this is a success story we don't need pre-compiles for everything we can do some things in pure evm it's not speed record but it's fast it's reasonably fast it's more than fast enough for for our purposes uh as the years went on we added more pre-compiles ec ad you seem all easy pairing moddy xp these each have stories behind them which you can read about mod exp has an interesting story that started with an proposal for rsa that got broken into five precompiles for primitives for rsa and then it ended up that only one was was especially needed which is mod exp the ec idc moisi peering uh is an interesting story about uh how this this pairing this bn 128 curve uh operations were needed and there was demand for it and in 2019 something interesting happened remember in 2017 uh ec mall was needed because it's too slow to do on evm but that was challenged in 2019 when with wire strudel uh it implemented fast ec mul in pure evm uh by fast i mean it competed it was you know get by by as fast i mean i'm we're loose well i'm not saying what fast is it's not you know by gas cost you know there's two questions there's gas you know is gas and speed uh but why shoot always you know what what do i mean by fast but wire shooter was optimized for gas use and it was just about equal to the ecmo pre-compiled this is shocking how can this be we needed the pre-compile because it's not possible to do an evm but no that's wrong we could do it in evm in pure evm uh and there's reasons for it if you understand the calculation that ecmol does but but it's sort of an interesting uh story and also in 2019 ev1 evm1 came out which is a fast ev-1 evm implementation pavo showed us that we can do evm fast and not not quite as fast as wasm but he closed the gap by a lot and the gap is small now smaller much smaller so these this is some historical high points and some lessons learned pre-compiles are controversial um there's a lot of pushback there's a lot of discussion there's a lot of uh discussions back and forth uh with with client developers and there are some other precompiles as well that that had more controversy uh and one fun question to ask you know if you're an engineer uh do we even need pre-compiles uh can we can we deprecate pre-compiles i know it's it's a sort of uh aggressive and maybe a dramatic question to ask but it's it's maybe it's fun to think about uh what would a world look like where we where we can uh deprecate them or where we can have user deployed perhaps that's what we might replace it with um so that brings us to and along the way uh the wasm uh was one of the options in the hopes and uh i'll talk about was in benchmarking now uh i don't have the url github.com benchmarking and i'll explain the chart as i'm explaining the text so the chart really quickly all the way on the right is bls12 pairing check uh so it's evaluating a pairing equation uh in in just an interpreter you can see how in the the uh dependent access is time in seconds i don't know if people can see if the resolution is too small but it looks like it's half half a second in the interpreter all the way on the right uh it's an inter it's you can see it's 469 milliseconds uh and all the way on the left is the rust native 5.1 milliseconds so you can see there's a huge like 100x slowdown for interpreters uh so interpreters are are too slow no surprise but then we discovered that the the all the way on the right but look for look just left of that the second i'm sorry the third and fourth uh so just left of the of this interpreter are compilers and those aren't those are fast but they're still you know six five six times 6x slowdowns from the native so we can't we find you know you can't be lazy you know compilers won't solve all the problems for you so we have to we have to uh you know dig deeper and uh understand what the problem is we profiled the bls 12 381 and this by the way i should say it's it was from wazim kurt wasn't curves that's the project that generates the the wasm the the code uh that we were benchmarking in wasm i should say wasm why are we talking about wasm right now uh it's it's relevant to evm because it sort of motivates evm because we have tools and we have implementations in wazim and we can usually as an approximation to evm and it's important to the whole story i think so we pref we profiled this vls 12 pairing check and we found that the bottleneck is in something called montgomery modular multiplication it turns out this is very popular to use uh this montgomery modular multiplication in many areas of crypto a lot of crypto uses it uh there are other ways to do modular multiplication in certain cases there are optimizations but uh this is a very popular one and maybe the most popular one and so we did an experiment and the second one we call uh uh interpreter with bigint native function so not all the way on the left not the rust native but then the interpreter with big nums we did it in 9.8 milliseconds versus about five so it's a 2x slowdown we can do better we think but already we see that you know all the way to the right it doesn't make sense compilers i don't know not quite but if we do some extra work we can get performance that might approach native and the whole there's a there's more to this story these numbers you know can be improved for the native as well as for the for the uh inter interpreter with big ends uh but this tells the story that you know about evm one natural question is can we do the same thing in evm uh so that's where evm384 came from uh wasm one more comment about wazimwasm is sort of perpetually almost on their features uh uh that we're waiting for and the mvp is you know already w3c put out the mvp but it's it's sort of very basic and there are very important features that are not finished yet and so wasm i don't think we should deploy it yet uh because uh we're waiting for for example interface types and reference types and some other proposals to be finalized that will affect the the design of ewoz and if it is if it is but anyway let's solve the problem maybe we can solve this problem based on our learnings from uh wasm with evm uh so let's do a similar experiment with evm with these three op codes uh we call them admob 384 submit 384 mult modem 384 and we believe that these will what we call cover all bottlenecks for bls 12 381 operations we hope this isn't confirmed yet but we're getting closer and closer we'll talk we'll talk about it in a moment and uh we want to be generic as well so it doesn't make sense for us to do you know domain specific cur you know curve specific modulus specific uh optimizations because then it's not usable by other people we want we are towards this sort of blossoming uh renaissance of of user deployed crypto we wanted to be generic for other you know bs 12 uh 3 81 but also 377 maybe starks which are heavy on a lot of cryptos heavy on you know polynomial evaluation to verify stark and the polynomial evaluation is just these these operations it's precisely these operations if we can maybe even we're also talking about other ones some sort of algebraic hashing things like this so uh we don't think that these are very limited op codes these are very generic op codes in fact and the evm384 is might also be a template for evm 378.

um the talk is almost done i'm going to go through some progress that we've made but we you know all the progress updates are listed in this magician so you can click through yourself to get more details i'm just going to be very high level um is it feasible we did some so uh there's a chart on the left is the same rust native uh and and then what this this uh middle one is the same lawson one that's like 2x slowdown and so our first iterations uh we have you know you can see it's another 2x slowdown from from wasm with big nums with big ins you know host functions and uh it's not fast enough yet we did a synthetic pairing algorithm we talked about it i don't have time to explain it but it's sort of an approximation it's an estimate of a pairing runtime because we do a similar amount of arithmetic but there is potential uh the problem is it's there's awkwardness with the stack with the evm there's just some things that are awkward so we we iterated and we kept iterating and you can see our iterations the independent access are the various uh versions the dependent axis is the the milliseconds and you can see the the version v1 through v7 uh at a certain point uh so we tried to these are all different interfaces what we call interfaces so that means how the stack has to look how the environment has to look when we call this evm opcode these evm opcodes and it turns out that we can make some you know do some things to make it uh faster and faster uh so we went from you know uh you know much slower than you know 2x of wasm or slower uh we tried these different interfaces along the way we tried different languages we started with fuel and then we went to huff huff you remember wire strudel from earlier the the ec mull breakthrough that was shocking they used huff which is a you're right uh in some in in evm you write sort of in this easy evm assembly but with macros so it's sort of it's not as as unforgiving but you're very close you're actually using the evm up you're writing evm app codes and that gave another speed up you can see from v1 to v2 that was like close to 2x then from v4 uh you know it's a v5 we had another improvement with huff we had another like 2x and all of a sudden all the way on the right is wasm and now we're faster than wasm this is shocking we were hoping that to match wasm with big ends but it turns out that we can beat it with a carefully chosen interface and we settled on interface v7 uh so next is we want to so this this is all based on the synthetic it's not the full pairing we're using this sort of synthetic with some something called an adjustment factor but we want to start implementing so that's what we did the the full pairing uh a big chunk of the pairing is the miller loop it's you can think maybe half of the whole pairing algorithm is runtime is in this thing called the middler loop um it gets a little bit more complicated but just at a high level uh it's a it's a huge chunk of the of the pairing we implemented uh the miller loop from this library that i i believe holds the speed record now called blst blast uh but but we simplified the malt their mall fp2 they do some handwritten uh assembly you know machine code optimizations uh which would be expensive using evm384 so we used a more generic simplified version of it of this small fp2 function and our numbers are agree so we are correct with blst the numbers agree our evm 384 miller loop and the bost miller loop they agree uh on the results after we change the small fp2 to be the same one so so we're very close uh correctness is still an open question but but we believe it seems to be it seems to be that we're on the right track and notice that our our uh v7 we're still using the v7 interface for evm384 uh but we have even better numbers than before so all the way on the right is our wasm with big ins uh just left of that is our old uh synthetic pairing and we went from 5.5 milliseconds now with our miller loop 4.7 so we're getting better and better and we're approaching native now there's a whole story to be told about native where you we're not we're doing naive things we're using a uh some azure vm that's mid-grade uh their algorithm there are optimizations that we're leaving out but it seems that we can get faster and faster and of course maybe these all these times can be halved once we do some tricks um uh and there are some other tricks that we can't do that you can do in native but but evm384 isn't generic enough isn't uh you know uh but we want evm 384 so there's a tension with remaining generic and i think we're okay you know if if we're desperate we can do these you know modulus specific or you know optimizations not even modulus specific but just based on what type of modulus it is uh we can do some optimizations but we're not doing them yet and i don't think we need them i think i think we're we're reasonably fast uh and and we're fast enough i think so where are we right now uh finishing bios 12 through 81 pairing uh to justify we want to say that we cover we want to make the statement we cover with evm384 we cover all bottlenecks or bs 12381 pairing and and we're we're pretty fast we want to make that statement that statement is close to being made but not made yet uh evm3d4eip is being written right now uh we are soliciting implementers you know the pairing is one algorithm but there are other algorithms uh to be implemented and uh we are soliciting implementers advice we are in discussions with teams and uh with the bst people for example and uh and with other people we are asking if they need this kind of thing but we're also having an open call we're soliciting feedback ideas uh and implementers especially um it would be great to see this this used um this eip has a lot of support already and that's where the talk will end i will open for questions i don't have the text window in front of me oh good paul um thank you so much excellent talk um i can give you some questions that have come up on the live chat so first one i have for you is um let's see how difficult is it to write the low-level crypto operations in evm using the evm 384 op code how difficult oh goodness um it depends on who you ask of course so they're asking me um it is it depends on your background in cryptography it depends on your background in evm there are growing pains of course but once you overcome the growing pains it gets easier so um and it depends on the tools you're using i think huff is a great tool uh but but writing the code in huff is is is tedious because the v7 i didn't go into details about this interface but we use something called packing off offset packing and if something changes with the offset we have to go in and manually change it so i have something i have a generator and written in python it's modeled after the javascript generator for the wasm code that the wasm curves uh code that we used earlier in the talk and this generator has been helpful because i just implement for example some small parts of the pairing and then i can reuse them uh so it's sort of uh i'm generating the code in python uh the huff code and then the huff code is compiled with the huff compiler so it's multiple steps very awkward and a lot of growing pains a lot of struggling to debug it's my least favorite thing it's the bane of my existence it's going up code by op code uh and and finding uh some something some bug or something uh so it's very painful at first but as you go along like with most things it gets easier that's it okay um all right i have another question if you have the time um paul what are the blockers uh to seeing this on main net and are there any security concerns uh what are the blockers uh the the finish the pairing it seems like we need to have a concrete evidence we need to have a concrete you know here it is you can't take this away you know it works it's fast you know you can't take that away from us so it seems like that's a blocker we want to say that it covers everything and then security yes there are security concerns obviously with a consensus system uh as big as ethereum of course there are huge security concerns but there is demand and i want to answer this question uh there are security concerns with uh the alternative so i think this is a path of least resistance in terms of security the the operations we want to implement are maybe 30 lines of code uh whereas if the alternatives if we want to do alternatives or perhaps pre-compiles it's much more than that it's it could be thousands of lines i think it is so i think that this is uh the the most secure thing we can do uh if we are to do something like this but yes of course there are there yes that's it nope