ZK10: Benchmarking SNARKs - Jens Ernstberger

Transcript

[Music] all right let's kick it off because this topic is too exciting to wait any longer uh so let's all give Yen a hand as he presents benchmarking [Applause] snarks cool um thank you very much um so today I'll talk about the performance characteristic of snarks um this is Joint work that we did in the past around like 3 four 5 months um uh yeah with a bunch of collaborators um okay so let me actually motivate a bit um why we care about evaluating the performance of snarks in a more systematic way um I kind of

looked through the talks of ZK Summit 78 and 9 and uh exactly the conversation that just came up um uh basically could have been a problem earlier um as there were like a bunch of like like 29 out of like 61 talks I found had like some relevance with regard to performance um but we're always like considered in an isolated isolated environment um so um it's quite difficult to track to performance improvements and also like practical implementations um even for experts which I guess like a lot of you are um I guess no one could really uh recollect what these 29 talks actually like um yeah how they compare to like other implementations right okay cool um so let me quickly

State what the talk is going to be about um so first we're going to talk about clarifying what we actually want to measure in snarks um we're going to introduce the the work that we actually did on a benchmarking framework for snarks and zero knowledge proofs in general um interpret some preliminary results and then outline how we can we like as a community actually improve performance benchmarking okay at the same time I also want to delineate what the talk is not so um we're kind of a team of academic researchers so this talk is not going to be biased um we're also not going to talk about a direct comparison of of starks and pairing based snarks um uh which has gathered a lot of attention recently I think um and also some of the results presented here are not Timeless

right so most of the benchmarks um uh always depend on like how the circuit is implemented and on different optimizations and these can change results significantly also in the future okay um and we're also not trying to decide what which proof system is the best okay so probably a lot of people already know this so I'm quickly going to skip over this the important part in this case um about snarks is what do we actually want to Benchmark from a theoretical perspective um most implementations always rely on pre-processing snarks so in a pre-processing snark you have a split uh split setup procedure uh where one part is randomized right like for example um uh the the a trusted setup or like a

trustless setup um uh where you can generate a common reference string um and then you also have a deterministic setup procedure where an algorithm that is commonly referred to as the indexer it takes the common reference string and circuit description and outputs the prover key and the verifier key which can then be used by the proof and the verifier algorithm um from a practical perspective um this is mostly how most of the implementations of snarks look like in either like circom gnark artworks or whatever um and uh this kind of uh shows what we want to what we want to Benchmark in practice right so you always have a front end the front end allows you to um encode the circuit and

provides kind of like an intermediate representation um which can either be for example R1 CS Air um or whatever um and then you also have the back end which is more interesting because this is like where it actually becomes fairly performance intensive where you have the the the setup algorithm which in this case is the the indexer that I mentioned before um that generates the pro key and verifier key you have the prover which is probably the most compute intensive intensive part and then the verifier which can be uh depending on the actual proof system uh either constant time or yeah and the important metrics I guess that we want to measure here are uh the execution time for the setup the approver and the verifier algorithm uh

as well as well as U uh the memory consumption for these algorithms as well as the proof size of the actual proof right which might differ between like different proof systems and implementations okay at the same time um is this actually enough um so if we want to measure the performance of a snark um does this suffice for everybody that is trying to develop an application with snarks right so usually when you want to develop uh an application with a snar you have some kind of idea you have some kind of system system design and then you have to figure out uh whether you need a custom proof system or not right and if you need a custom proof system for example that happens uh with zcash for Halo to with plony 2 F FL that uh

you kind of need custom optimizations for whatever you want to do you need to figure out with which arithmetic Library you actually want to uh use to implement that proof system and on the other side if you if you don't need that if you don't just want to build an application you want to kind of like figure out which domain specific language or library is like Optimal for exactly that so given all of these like kind of considerations that you have from both a theoretical practical as well as like an application side um what would be the requirements for for a framework that kind of uh allows the benchmarking of snares right so on the one hand it should be holistic so we want finite Fields um operations elliptic curve operations as well as uh endtoend uh

circuit executions um we want some kind of modularity so we it should be easy to both add like um a new library to the proof system but it should also be easy for an integrated library to just add a new circuits such that you can like like uh include um some kind of like custom develop circuits with new optimizations and easily just rerun whatever you had right and on the same time at the same time it should also be reproducible and also pragmatic right so you should um it should kind of like resemble a practical setting right on the quantitive side as I mentioned execution time memory consumption proof size um and statistical soundness are kind of like

of relevance okay so this is kind of what we came up with um uh in the recent month um so we have a benchmarking framework for snarks which is both an arithmetic back end as well as a circuit backend um that kind of holistically covers the whole snark stack so on the arithmetic side you have libraries like for example arcworks or gar crypto um which snark development tools don't rely on um where we measure the execution time of for example uh field addition in the scalar field uh addition uh and multiplication and in G1 and G2 as well as multiscalar multiplications and

pairings um on the circuit back end on the other side you can have like some kind of like configuration file um and some specification of inputs um that you then input into um different Integrations of different SN Frameworks and then we have some some standardized logs uh we try to use uh state-of-the-art performance measurement Frameworks like for example Criterion um to measure the execution time and we separate uh measurement of execution time uh and memory consumption by basically compiling uh independent binaries for example for proving verifying uh the individual setup procedure um and then we also have uh uh two front ends one is focused more on

the arithmetic side as well as U one that is focused more on display um dynamically displaying the the circuit benchmarks okay so um if you remember the requirements one of them was also like the ease of extension um uh so for example if you have like a library that you want to integrate let's say gar um takes around 80 lines of code um if you want to add a circuit to exactly that takes around like 30 lines of code and for domain spe specific languages like for example circom um it was around 250 lines of code uh to integrate the whole thing and then like it's pretty easy to just add a new circuit and run it again right uh so this is the current scope uh that we uh integrated and that

we kind of like rant some uh uh benchmarks on that are also Open Source by the way um we have a bunch of Curves the pasta curves um that are used in in zcash uh Nar crypto which has a variety of different curves arworks um Halo 2 curves which is fairly new and I believe is um being developed and like optimized at the moment but we also have like more traditional Integrations such as curve 25519 D which is I believe used by I think 880,000 repositories or something um just as like a baseline comparison and on the circuit side we integrated Bellman uh the Halo 2 from PSE with the kcg polinomial commitment

um gar Circ and starky um and we focused on the curves BN 254 and BLS 4381 um for at least like running the initial benchmarks um you could run it over like any arbitrary curve in Gnar for example um but we focused on these due to relevance in ethereum right um the current circuits that we integrated across those like five Frameworks are simple exponentiation circuit so just to simulate like a set of dummy constraints up to I think two to the^ of 24 um which is around like 16 million constraints um as well as uh shatu 256 um which is more of a realistic payload um and the reason for that is pretty simple um it was

already like implemented in most of the Frameworks actually not in all um and uh we could just use it without like having a non unoptimized um uh custom implementation that we do ourselves right um so we run all of this on on different machines in AWS um some of them are smaller so and others of them are more like server sized with 128 GB of RAM and 32 CPU cores with different um CPU architectur so we have x86 and arm um and we also have uh on the bottom two different machines where one is more optimized for for memory consumption and the other one is more more optimized for for CPU

computation right um so to show you some of the the initial results um uh here you can see the results for uh the arithmetic backend um for multiscalar multiplication in group G1 multiscalar multiplication in group G2 as well as pairings um for both curves B in 254 and BLS 12381 um there's a couple of things that you can see here for example gnark crypto so far has the fastest implementation due to several optimizations for example all the way in the back you can see um that for larger MSM instances both uh actually um blss this uh and uh gar crypto uh use batch aine Edition um and for smaller

MSM instances you can also see that FF JavaScript and BLS strs uh don't enable multi-threading which is why they have like a little bit lower performance for smaller msms um then when it comes to sh 2 to 56 um yeah uh this is quite optimization dependent um in general what you can see is that the memory consumption for uh Frameworks that are uh built in Rust uh is quite a lot lower um at least that's what we experienced um but as I'm speaking there has been like new optimizations for example in gark um with 40% less constraints um which would render it like a much less computationally

intensive right um right marks there uh same goes for the exponentiation circuits um here just as a reference for the proof size you can see that the starky proof size is quite a lot higher um uh around like I think it was like 600 times um at least for for 8.4 million constraints or row um and uh for a memory consumption we observed kind of like the same thing uh what we have to note here is that the starky circuit is not optimized um so you might see that like starky in this case is a lot slower which is like um probably a lot of you know like not that expected um as in

comparison to Gnar or rapid snark um and the reason for that is pretty simple um in this circuit we have uh three columns um and starky would be optimized more for wider traces so if we had like 10 columns and less rows um you would see like a significant increase or like decrease in execution time for this yeah okay when we uh we were also interested in looking basically in these two machines that are like where one is like more memory optimized and one is more computer optimized kind of to figure out um whether one or the other kind of like influen the performance of of of a specific like proof system and what you

can see here um is for example that I think you can't really read it but that like one row up there that is like fairly black um that is a rapid snark in BN 254 with gross 16 and here kind of the darker color means that the execution on a ram optimized machine um outperforms the CPU optimized machine and the number that is stated in there is a 1.4 so in that case it outperforms the CPU optimized Machine by 40% um only by running it on a different machine um and you can observe similar things for for Gnar where it's like a little bit like inverse right and that is like across both circuits so on the top you can see the

shadow 50 circuit and on the bottom the exponential circuit okay um so one thing that we asked ourselves now that we have like this holistic framework um of arithmetic benchmarks as well as circuit benchmarks um can we estimate the circuit runtime right so given like for example you have plon um this is like for example on the left the table that is uh plon with gar um over BN 254 and B L 12 381 um can we estimate from the number of multisala multiscalar multiplications ffts and so on can we estimate the actual runtime the answer is actually yes um this is not really optimized so we ended up with like around 6 to 30% um of being off it

gives you like a notion of in which kind of like range the execution time is um but it's not super specific so far and also it's like not a generic methodology because different implementations use different optimizations um for example in graph 16 you have in the verification step three pairings um in uh if you do it like in a simple fashion you would have to do um uh three three Miller loops and three final exponentiations whereas like in practice it's commonly um it's very common to use optimizations where you only do like three Mill loops and then one final one final exponentiation which you have to consider in the um uh which you have to consider in the estimation process all right and uh our

benchmarking data is open source so so um if anybody feels like uh improving on that or including something like that um in like compiler or an IDE um we would be happy to to guide you through or help with that okay um some of the recommendations um I think one of the things that we experienced is that it's it's fairly hard to compare performance if there's uh no kind of like standardized payloads that you can use so um uh it's it's fairly hard like if there's like custom implementations of shatu 56 um uh if you like realize there's no starky shatu 56 in these that was like a very conscious decision because we uh

looked at the implementation and it was fairly um yeah it was it was yeah that were no test tests for correctness let's say like that um so um really having standardized payloads by the projects that actually also develop these libraries um and kind of acknowledge like Optimal um uh yeah usage of a framework uh would make like um uh really like leveled comparison much more uh easy and also an agreement on Hardware specifications for evaluation would also um make a lot of sense right um yeah good uh so what would be further work that we can do in performance

benchmarking um so in general um uh I think there's still a lot of work to be done in our framework uh to to kind of like um make it more holistic in a sense of optimizations we currently don't really include any um comparison of lookups um or any comparison of recursion and uh we also don't really care for the optimality of arith arithmetization and uh yeah so these are some of the things that we really want to look into and also the whole um estimation of runtime that I've like gave a glimpse into um uh can be done independent independently from like whatever is done in the framework um our data is open

source and uh yeah if you want to look for more complex circuits that include lookups and estimate the runtime for that um I think there's a lot of room for optimization on this one exactly um and yeah we still like we only have like five different Frameworks integrate it I think there's a lot of uh different ones that we can still include okay if you want to take a look um at what we've done um we have the two front ends which is zal and ZK bch.org second one is not yet updated with the results that I've shown in here um that's why I had on the previous slide um we need someone who does like front end developments um and uh yeah if you want to look at the data um there's the

GitHub link um yeah and thank you so much and also there's going to be a preprint of a paper very soon um that discusses discusses the results in more detail um so yeah looking forward to that thank you amazing talk very important work any questions so if we want to add um a library or a framework uh for benchmarking we only need to um create an a PR on bench data um not on bench data it's called

like uh github.com CK Collective ZK minus harness um there's a bunch of like we have some documentation currently the branch is V 0.1.0 um we plan to merge that once we updated the front end um but yeah essentially the only thing that you have to do is like follow whatever like um uh description we have in the readme um and then create a PR to to basically integrate that and then we can run it uh with some of the funds that we have for benchmarking and how do you use uh Criterion which is R specific with uh JavaScript or go yeah we we use a different uh library for that there's we can use Criterion with with uh with go

or or JavaScript so if we use uh C C++ uh overall languages um you can just call from rust uh and use for this right uh no for that not um uh but we open a PR and we can discuss like we we haven't done any like C++ uh C integration yet so we don't have any like specific benchmarking framework that we use for that yet um but I'm sure there is something that we can use in that is CC C++ specific so it's not like Criterion was only an example for rest thanks uh we got a question in the back you mind getting that one thank you do you know if there's any like MSM

benchmarks where you limit the scaler weight so so in last one DRS they claimed that um um you know I mean Bas basically when you do msms um when you do random scalers it's always going to be you know more expensive and most benchmarks are doing on ROM scalers right while uh in a lot of systems you actually have a lot of you know non- random scalers that gener from the trace um do you know of benchmarks that's you know particular to that can you quickly repeat the question yeah so so in some um well basically when you limit MSM to scalers that have low weights for example uh when you have a 2 56 bit field but you actually have scaler that only have 32 bits um you know in in length yeah then it's faster right um do

you know of benchmarks that targets that particular use case uh no so far I don't know of any benchmarks we didn't integrate that like or or didn't consider small field so far um yeah can also hi zul here uh so like for the arithmetic part we don't do that but it's also a choice because you just want to write whatever you write in paper you have benchmarks for it would be a nice addition but also there is a restrict number of operation that we can do oh and I was going to say Z prize when we did the MSM acceleration last year was randomly weighted scalers but this year we're doing more uh the focus is more on endtoend uh like applications like ecdsa verification uh P like a Merkel tree uh or proof in Poseidon so potentially in

those cases you might have more structure and so hopefully the results that will come out of this year's Z prize you know might be indicative of what kind of performance improvements you could see at least on Specialized Hardware um for those types of problems possibly sorry we all helped in answering your question cool um is there a a plan to add uh GPU uh for uh your onest uh yeah we we could definitely do that but we we just didn't have the time to do it yet um so yeah it's kind of it's kind of difficult to set priorities like because there's like so much stuff so we're really hoping like that like some people will contribute and like make this more

holistic so we can have like a really like standardized performance comparison right also just commenting on that from the Z prize perspective I think optimizing GP like having it be optimized for gpus is is kind of different than you know just writing it generally for a CPU based AR Ure I think so if you look at Z prise if you go to the Z prise GitHub so Z prise 20 2022 you'll see some at least MSM uh uh GPU optimized MSM implementations and there's some really great videos actually at Stanford um their equivalent of RDI Center for blockchain research where people have kind of done some talks about specifically how to optimize for that um and and the speed up is pretty

dramatic so the the idea is uh so that people can just uh run the Arness maybe on their own uh machine or their own uh Amazon or uh whatever so that they can compare um because uh since uh Z prise 2022 uh things evolved we had this uh IID plus um uh ZK sync uh fused uh Solutions and we don't have the Benchmark data while if we had this we could rerun and make sure and then Hardware changes so we likely have soon new Nvidia gpus maybe people will develop on Apple metal so yeah I mean one one of the one of the

things that we also wanted to do is more like U like have like more of a cic CD architecture um where essentially like to make it easier for like library maintainers to like just like submit a poll request like with an optimized circuit and then like I don't know you accept a pull request and like it runs everything like in the background um but for that we Al we also need some more funding to to actually like do that stuff right yeah yeah it would be amazing to have a universal harness and I know for a fact I I talked to Nile from yid about this you know they for this year we're actually including like the fourth generation Nvidia gpus and I think the implementation potentially would look very different given like the different memory architecture in those gpus so here oh

here uh sorry uh for funding maybe uh so I don't know if you looked at the protocol Guild uh on eum it's a way to fund infrastructure work um and that could be one thing because many companies like Lio and others are contributing to it uh Millions now uh per and they just give 0.1% of their uh Revenue uh to this and this is enough I think to to get this and it's a worthwhile for everyone yeah definitely yeah we we we were actually um supported by Grant from the ethereum Foundation uh for this one for this work for this initial work um uh but yeah I agree definitely I'll look into it

y I'm so guys I think that's it I'm the only thing standing between you and lunch unless we have any final questions okay thank you everyone very much we'll REM meet back here at uh 2 o'clock so we have an hour lunch break thank you everyone for your attention let's give yens another hand thank [Applause] you