zkSummit6: arkworks: A Rust Ecosystem for zkSNARKs – Pratyush Mishra – UC Berkeley

Transcript

[Music] so welcome back to the last talk of the day of day one uh now we have pratush mishra who's going to be speaking about the rust ecosystem for zk snarks i know there's people who came just for this talk so they're very excited to hear what you have to say and so am i just take it away hi everyone uh thanks anna for having me uh and i'm excited to get this talk so in this talk i'll be talking about artworks which is our rust eq system for developing and programming with zika snacks this is the joint effort of a lot of my excellent colleagues at berkeley as well as a lot of external contributors the code is available at that link on the bottom

okay so let's say you want to make a zk snark application right so maybe you want to make an xz cache or the next dark forest or anything in between um to do this you actually have to develop knowledge of a lot of uh domains so not only do you have to figure out your own application but you have to figure out things relating to snacks such as finite field elliptic curve polynomial arithmetic you know information about your proof system such as security properties efficiency so on as well as you have to figure out how to express your problem in a language that the constraint system understands that the the snark understands right in a bit more detail uh you need to you need to have knowledge of many complex domains right so the lowest level you need to figure out how to optimize your arithmetic

above that you need to understand very non-trivial snack constructions as well as the security properties they offer above that you have to as i said express your problem in a language that the snack understands this is called constraint system programming right and within this language you have to implement securely your primitives such as hash functions prfs merkle trees and so on right and after you've done all this you still have to reason about the properties of your possibly complex cryptographic protocol right so this is a lot of stuff to try to figure out um when all you want to do is to develop a simple snark application or snack based application right and this is made worse by the fact that every few months there's a

you know some new techniques popping up right your snark that you're using now might become completely outdated in six months down the line all right so how can we sort of control this complexity how can we you know simplify the job of people working with snacks so that anybody can contribute so let's try this tool that everybody you know loves it's called abstraction uh and let's zoom out from you know these four domains and try to abstract away some common properties that you want you know for uh each of the roles within uh the ecosystem right so if you're an application developer right you all you care about is writing down your application and maybe you have some interfacing with the constraint system to express your problem in the language the snark

understands but you don't really care about the proof system or anything curves and so on right if you're a snark developer like you're developing new snacks or implementing them then you care about interfacing with the constraint system because your snark understands some particular constraint system and you care about interfacing with some elliptic curve or finite fields but primarily you're focused on implementing your snark and making it efficient right and at the bottom level you have your algebraic objects such as fields and curves and you have to optimize arithmetic there right so a little bit more detail uh the things you care about at each level include at the top level are good performance so you want your application to you know run quickly and not be slow it's the minimum

thing that you care about but you also want it to be easy to read and easy to write and part of this um in make requires that writing constraints is ergonomic right it shouldn't be look unpenetrable or impenetrable to auditors or contributors right and at this level as i said you don't care about details about the kinds of snacks that are using as long as you satisfy security properties and you don't care about the kinds of curves that the snark might be using underneath okay that's the top level at the next level when you're developing snarks here again you care about good performance because it affects the applications above you um but maybe slightly non-obvious property is that your imp you want your implementation to be high level

and in particular you might want it to look similar to the math description and what this allows is that you know an auditor or somebody else looking at the code can easily match it up with a description in the paper right and then they can gain some confidence that oh this implementation is you know actually you know possibly secure if the uh the math is proven secure right um and at this level again you don't care about what kinds of curves you have as long as you know to satisfy the properties that you need such as they're being pairing friendly or they're being a cycle you don't care if it's a bn curve or a bls 12 curve um you just care about the pairing friendly property for example and you don't care about how constraints are generated right they just take in

some constraints and the assigned witnesses and you produce and you want to produce a proof okay so that's the snark development level and what about for algebra here you're implementing new fields and you're implementing new curves right so you want this task to be easy you don't want it you don't want to have to repeat the same uh code 100 times for 100 new fields right but you want to also want to ensure that the performance of this sort of easy implementation matches that of a hand optimized implementation you shouldn't have to sacrifice performance to get readable and easy to reason about code right now across the entire stack you also care about other things such as

memory safety and ease of auditability ease of readability and so on right so these are common concerns okay so the question is how we how do we achieve the separation because at the moment um unfortunately many people working with snarks have to be experts in all three domains right so the question is how do we separate uh you know the concerns for each of these domains and our answer to this is to develop artworks which is a modular and coherent ecosystem for developing snarks and working with snarks that provides low cost abstraction so that you don't you can you know abstract away uh your lower level concerns without worrying about performance at all okay so in a bit more detail artworks consists of a few

libraries at the lowest level you have your libraries for your algebraic objects such as fields curves and polynomials and these provide a generic interface that can be reused by the next layer which consists of concrete instantiations of the fields as well as uh libraries for programming and specifying constrained systems okay so that's your middle layer and this layer provides a generic constraint system interface that can be used for developing gadgets so for common objects such as hash functions um prfs merkle trees as well as finite field arithmetic elliptic arithmetic you know lots of common operations inside snacks all of these are developed generically

over the underlying constraint system api and we also have lots of snarks which understand these uh this constraint system api and produce snark proofs for a particular constraint system so in particular we have graph 16 graph model 617 um marlin a lot of polynomial commitments which are useful independent of snarks as well as uh these recent inner product in a pairing product arguments right okay so together all of these comprise a sort of generic snark application framework so you can use these generic components to develop your snack in a very high level and inside our ecosystem we've implemented a couple of these applications such as uh we have a generic library for proof carrying data as well as

generic implementation of the xe system and all of these reuse uh crucially the components that we have um that live below them okay so let's take a deeper look at each of these components starting off with uh with the lowest level so let's see how that how we achieve the goal there okay um so a quick refresher so today all stocks require at least very efficient financial arithmetic think uh primes modulo some sorry uh integers modulus from prime right and they also require efficient polynomial arithmetic over these fields right uh so this yeah so all snarks require

this and additionally many popular snacks such as which which work over elliptic curves such as gross 16 marlin planck halo you know anything that you can name really also require implementations of extension fields and elliptic curves over these fields right so all of these things have to be implemented efficiently so as a reminder at this level what we care about is that it should be easy to implement these fields and these curves right you don't want to reimplement things again and again while the performance should match that of a hand optimized implementation all right so let's see how we achieve both of these goals so starting off with the ease of implementation right we show let's say we want to implement g1 of the bn254 bilinear uh

group uh and so we we let's see how we can do it in less than 60 lines of code so recall that to um specify an elliptic curve you basically need two constants this a and b in the curve equation y squared is equal to x cubed plus ax plus b right so this is all that you should need to you know specify along with maybe like the generator of the group right so on the right we have our uh the code for doing for implementing bn254 g1 inside arc works and this comprises the three tasks that we have and this does the three tasks that we uh want to do right so okay so i won't talk about implementing the underlying fields but rest assured that it's a you know looks similar to this it's not very complicated next we want to specify the constants a

and b right this is what goes in the curve equation and so there you can see that you know here a is zero and b is three um it's a little bit of arcane encoding but you can generate using a script and finally we specify the cofactor and the generators and this is all you need to do to specify g1 and now this is a fully working implementation of uh the bn 2.4 g1 in a and which you can use for you know your favorite snark without worry okay all right so this extensibility actually allows easy implementations of new curves and we take advantage of this by implementing inside the arc works ecosystem many different curves that are used across the ecosystem across uh sorry the blockchain space so

for example we have the you know soon what's going to become the industry standard pls-12381 right uh which is used by zcash algorand and many others we have bn254 which is still used by ethereum we have this tweedle pair of curves which is uh useful for doing uh recursive composition which is used by mina and potentially also by zcash we have the this family of curves that was introduced in sexy right which allows one step of recursive composition which is used by cello used by elio um at the moment and we also have this m t cycle of curves uh and we als i mean so which is useful for recursive composition along with all of these curves we also

have embedded adwords curves which might be useful for things like snare signatures or pedestal hashes so for example we have jab jab for bls 12381 the nice thing is that for all of these implementations uh the curse so for all of these curves the corresponding implementation looks basically just like um oops uh this previous slide here it's just the 60 lines of code that's all you need to do all right and so the reason why it's you know it's nice to have all of these curves implemented within the same library is that uh as interoperability between chains becomes increasingly more important you don't want to have to rely on multiple different cryptographic libraries in in your application in your interoperability application right

and so by using arc works you could just call one library and you would have uh implementations of all the relevant curves that you might care about okay so that's it on the sort of ease of implementation front what up what about performance right our goal was to match hand optimized implementations uh without doing the hand optimization every time and so what we actually are able to realize is that our generic implementations from the previous slide match or outperform specialized and hand-coded implementations for each of the curves all right so i'll be comparing on the bls-12381 curve um along you know a few of these

uh metrics and the baselines will be sort of uh bellman or more correctly the bls12381 crate within the bellman ecosystem right and so this is the rust standard for uh the dls12381 library uh for the for the store 381 curve uh and it's entirely safe there's no unsafe anywhere it's using entirely safe rust right and on the other extreme we have um this very optimized c library called mcl which uses fancy techniques such as dynamic code generation and by by using these techniques is able to achieve um very uh high speeds so yeah it's almost in some cases 2x faster than bls 123.1 right so let's see how arc works

libraries stack up against this um so arc works with sort of an entirely safe arithmetic back end for the finite field arithmetic achieves um speeds very comparable to the bls 12 381 library so in in bellman just a tad bit slower in some cases and then with an assembly backend for the finite field arithmetic we're able to get performance that's almost identical that's much faster than bellman and in some cases even beats uh the mcl library so for example for fq multiplication um yeah we're faster somehow right so yeah basically the point of the slide is to show that you can have your very nice implementation from before that fits in 60 lines of code without sacrificing performance

all right okay so that's it on the algebraic front well what about so let's move on to the next um uh yeah task in the stack which is snark r d right so here uh it is to recall what we care about is good performance um and also that the implementation looks similar to the description of uh the scheme inside the corresponding paper right so you want to as i said before this is important because it allows you to uh it allows auditors and other readers to you know be more confident that your implementation uh matches what is proven secure right okay so in this talk i won't talk about the performance uh but yeah rest

assured it matches you know state-of-the-art performance in in other ecosystems such as in lebsnack or in bellman and instead i'll focus a bit more on the implementation matches the math description uh point right okay so for this our example will be the graph 16 verifier right on the left hand side you have the mathematical description of this algorithm it consists of these three steps some multi-scale multiplication a middle loop and a final exponentiation and then on the right-hand side you have the corresponding implementation in the graph 16 library as it is today right so and it's very easy to see that you know which steps match up with uh which steps in the code match up with which steps in the math

description right so it's easy to see that the msm corresponds to the m two yeah to step one and the middle loop corresponds to step two and the final exponentiation corresponds to step three um right and so it's slightly less cleaner for other places like the snark prover and the setup but again it's usually easy to you know delineate which portions correspond to the width steps in the math okay so that's it for this portion of the stack let's sort of move up and see you know how we can write applications that um are able to to work with these snarks right okay so yeah to interface with snarks as i said before we have to do what's called constraint system program

we have to express our high-level problems in the low-level language that the snark understands and because this language is low-level direct directly programming in it is quite painful right so in particular many popular systems use uh this abstraction called r1cs right but as anybody who has experience with implementing you know r1cs related things directly programming in r1 cs is painful even something like a boolean xr it's non-trivial how to optimize that and how to write it cleanly right so to resolve this a number of folks have come up with high level approaches to programming constraints so that your your you know program is high level but it compiles down to r1cs uh via a compiler so for example with

leo as you heard in the previous talk but the issue is that balancing performance inside your r1cs and ergonomics of you know having a high level implementation is tricky and we'll see a little bit more about this in just a bit right okay so just to uh recall at this level what we care about is good performance but ergonomic constraint writing more importantly and what i mean by this ergonomic constraint writing is that your constraints should look very similar to native code right so it's easy to you know compare and be assured of the correctness of your constraints well and you also want it to be the case that you don't have to implement common

objects again and again like hash functions or signature verification or comparison so on right so you want to have a library of common components that you can just use off the shelf all right so let's see how we do this so for the for the second part which corresponds to many reusable components in arc works we implement a ton of r1cs gadgets so we you know support standard programming constructs such as booleans unset integers conditional selection equality comparison and so on right whatever you could really want but we also support other you know objects which are more common inside snarks such as you know finite field gadgets or curve gadgets or pairing gadgets so you

can do all of these inside uh we have a very high api so all of these high level apis for all of these and we use these high-level apis to construct our primitives such as pedestrian function uh pedestrian hash functions uh the optimized variant from uh the zcash folks uh commitment schemes uh snark verifiers merkle trees so on and so forth so you have all of these implemented and you can just you know in fact they're all generic so you can you know swap out one hash function for another hash function by changing only a couple of lines of code in your your implementation all right so it's nice to have these um you know reusable components um that you can just glue together

right but how ergonomic is it really to glue them together right it's that's useless if you know i have a hash function gadget but then to actually use it it's like take 60 lines of code right okay so let's uh assess this by looking at this example of current super multiplication this is an algorithm that's used in implementing some finite field related things you don't have to know anything about it beyond the fact that it involves some sequence of additions and multiplications right so on the top diagram we have our native code which uh is the native implementation of this algorithm and on the bottom we have um sort of the constraint version of this code but using an old version of our

constraint writing library right so this is via some uh yeah our old apis right so and it looks quite messy it's not clear it's unclear like you know which portion in the native code corresponds to what in the constraint code right and this is this is also like what similar to what you might experience if you were using something like feldman so because the api in our all the api is inspired very directly from bellman right okay so to improve upon this we completely refactor our constraint writing infrastructure and as a result now you can write constraints for this karatsuba multiplication algorithm which look almost exactly like the native code right so now on the bottom we have our new

constraint uh this algorithm using our new constraint writing infrastructure right as you can see it looks almost identical maybe there's a few extra ampersands somewhere but otherwise there's like no functional difference between the two and this as i said before like helps with auditability helps with readability and it's now very easy to see you know which parts of the native code corresponds correspond to which parts in the constraint writing code in the constraint code all right okay so so far uh so that wraps up the discussion of the constraint writing portion right so far we've done like a very well win tour of the various components in the artwork stack right but the claim i made earlier was that

arc works is like a coherent and modular ecosystem where you can swap out one module for another and have things just work right but i haven't yet demonstrated that claim or demonstrating evidence for that claim all right so let's see how we can uh how moderate the ecosystem is by looking at you know one use case which is let's say you've implemented a snack app stock based application right and now you want to imp upgrade some aspects of that application right so let's say you want to upgrade the elliptic curve that your snark uses or you want to upgrade your snark entirely so let's see how this can be done in our ecosystem okay so let's say you want to switch between curves right and you're using the grot16 snark to switch between the curves all you need to do is change exactly one type parameter of your

snark and now you will have cross 16 using for example the new bw6 curve and nothing else changes uh everything the rest of your infrastructure can continue to work generically and this is the only change you need to make in your code right okay so let's say i've done this right but then i hear of these newfangled snarks which have the universal trusted setup right so i don't like the circuit specific instead of across 16 and i want to upgrade to these new snarks so how would you do this right again it's a matter of changing just one or a few characters in your program so you can just switch out this proof system and now you have a now you have an application that uses the marlin snark instead of gross 16

right and again that's it so now you're you've successfully switched between proof systems right okay so now okay so i've heard of these universal trusted set of snacks but then i hear oh there's these new snacks which have transparent setup which is even better right so how would i move to that well in our poly commit library as i mentioned earlier we have lots of polynomial commitments including um ones which require any transparent setup and switching between these polymer commitments for the marlin snack is again a matter of changing just one type parameter and now you've upgraded from trusted setup to transparent setup almost for free right okay so we i hope this like slide illustrates the modularity of the ecosystem we also have other cases

like for example you can switch out hash functions easily um so let's say you you know develop your circuit initially in mind with the you know with the pedersen hash right but then we are saying okay poseidon is maybe good enough it has good enough collision resistance you can switch it out you can switch out your pedestal hash to position again we're just changing a couple of type parameters somewhere in your program and then now your circuit uses the much more efficient for site and hash function right so basically the entire ecosystem is built up in this very modular way that allows upgrading components in an easy manner all right that was all about artworks how do we compare against other libraries for snarks in rust right so i'll be talking separately about the front end

and the back end by front end i mean libraries are languages that are concerned primarily with constructing constraints right and these fall basically into two camps so you have a you know either you have sort of a library which does constraint programming or you have an entirely new language with an associated compiler right so the typical example of a project called architectural best example of libraries uh is belmont right sort of the original player in this space and um yeah it supports a lot of uh so it supports for example proficiency it supports non-determinism right but as you saw earlier when you're writing constraints using the bellman

api it's not particularly close to native code at all right it looks uh quite different right so people have come up with you know these languages which compile down to uh constraints such as zinc or socrates right um and they do look like native code but they give up on some efficiency requirements such as non-determinism right it's difficult to express non-determinism in these languages and i'm sure as a result there's like other optimizations that might be missed because you don't have this flexibility right but what we try to do is as i showed we try to implement a very high level api which supports uh which looks like nature code but also allows you to drop

down and leverage you know low-level knobs such as non-determinism to improve the efficiency of your code so we support this in our library um okay so that's it on the front end on the back end um yeah so on our front piece in our library we support a lot of curves as you saw earlier we have you know basically all the curves that are used in the ecosystem as well as a number of proof systems that you can use to implement uh that you can use inside your application right and this is you know much higher than what's in the ecosystem in the rest of the space right now right so the nice thing about the separation is that you can mix and match so you can use

the you know any one of our you can use our back ends uh along with one of the front ends and it's exactly what socrates is actually doing so socrates is for example using um they have a back end which uses an old version of our code background was still i guess called sexy and they use it to implement growth modeler 17 support inside the library and the nice thing is that when they want to add support for example for something like marlin they would just have to add maybe a couple of lines of code in their code base and they could take advantage of our modern implementation for free right [Music] okay so i guess to wrap up in this talk i presented artworks right which is a

sequence of libraries for working with all levels in stock development right so you have algebraic objects snacks themselves constraints for these knocks as well as applications built atop these knocks and all of this was done thanks to um you know a lot of hard work from artworks contributors at berkeley as well as contributors in the community and both of these have come has provided lots of improvements to the ecosystem and if you want to join there's always a lot of work to be done right so for example we're looking into integration with web assembly we want to implement new curves so for example today i think zcash announced a new cycle of curves

so you could participate in in implementing that in the ecosystem and for example the tweedle curves were just recently implemented by a first-time contributor to the library so it's very easy to get involved if you're focusing more on constraint writing then again we have um you know always a need for that and there's always need for documentation but there's a lot of stuff within the ecosystem to get involved we have a lot of um support so we have pr templates ci which can catch your mistakes we you know all of us are happy to mentor uh newcomers and say if you want to get involved yeah you can go to the artworks and this to this website and um that takes you to the list of

repos you can also ping me at berkeley at my email address and yeah i guess that's it thanks everyone and happy to be here uh very good i'll clap for everyone um so let's ask there's actually quite a few questions in the chat already so let's go back to the top or this this isn't a question but it's a comment there i mentioned that halo asking if halo comes under rip or ipp um so i guess halo does not we don't have

implementation of halo but yeah so rip does include implementations of inner product related things and there's actually the duplication so the inner product argument that we have implemented in polycommit does not use rip yet but we're trying to reduce the duplication um yeah and eventually we do plan to support or extend our pcd library uh to support accumulation-based recursion also hopefully in the near future your your mic is just brushing up against your uh a little bit i'll just hold it cool okay rob asked what factors went into the choice of traits versus macros on api um so i mean there's i don't think there's a you know need for separation so you can still combine traits and macros we just

haven't written our macros but what traits allow you to do is to write you know code against a generic interface so i can have for example a generic curve interface and just uh write my snark code in terms of that instead of you know having to hard code inside my stock implementation a particular curve so what macros allow to do is to sort of de-duplicate uh some common code and what traits like to do is to have a common interface so they sort of serve orthogonal tasks in this world uh but yeah there's certainly like we can combine the two to leverage the deduplication that macros provide and still have the common api that trace provide we just haven't

gotten there yet rob has a follow-up uh on execution which components can target a no std wasn't embedded environment what are the major barriers if that is not supported and i think there were there were some answers later later on in the chat but maybe you want to say something on that yeah that's a good question yeah so basically we develop all of our libraries to support i guess no standard with allocation so you can use it in wasm um as is already kev asked can you comment on audit availability or audit ability of the code yeah so we do try to have a good documentation and good uh comments everywhere and as i said we try to make our code sort of match the description in whatever paper

is available and i believe there's been some audits for parts of the prior versions of the libraries of some libraries um at various points in time um but i think overall it's fairly we have enough comments to make auditing relatively easy we also have good tests for some parts yeah hi do adera obvious asking do the curve apis inside the snark support both complete and incomplete formula formulaia oh that's plural um right so that's a good question uh we've actually been looking and so currently we okay so prior version had only incomplete formulae and since then that required some hacks

to work around for scalar multiplication we've moved to supporting only complete formulae but now for scalar for for stuff like addition and doubling we use only complete formulae but we want to upgrade scalar multiplication to use incomplete formally to take advantage of the speed uh that and the efficiency improvements that that provides um so there you have another oh no you want to finish there had another one i noticed there were no names for constraints in the new api is there any compromise on debuggability here right so what we do now is instead um so the sort of in the bellman approach and like the old arc works approach you had to specify for each constraint a particular name

and that does allow that does allow like uh you know allow you to give human-friendly names for each constraint when you're debugging or profiling so what we've done instead is try to use existing infrastructure called tracing which basically whenever there's a new constraint it like takes a snapshot of the function name line number and so on and so it gives you exactly where the constraint was generated and like what the path to the constraint was so you can know which constraint is failing and what the cost of the each of the overall constraint system how they're distributed well that it needs a little bit more work um it's definitely an early stage there but i think it's it it's the future isaac asked about uh wasn't support if

you could speak a bit more about that yeah so it wasn't support as i said like we already have no standard and bellman sorry no standard implemented uh so all of our library support compiling uh two two wasm it's just a question of sort of writing the integration with javascript and maybe writing out a nice tutorial that leverages uh this compiled library uh this uh our library is compiled to wasm uh which i am i'm like absolutely uh no experience with uh web related things so i wouldn't know how to do that um but yeah so i like from i guess the artwork side um compiling to austin we support that he also asked also with rayon

uh yeah so i think there's an issue somewhere which shows how to replace the rayon thread pool with something related to web workers i believe so i think that should work for uh multi-threading in in wasm i'm curious if there are any more questions the chat in here is interesting in general pratyush you should totally read back because there's like conversation happening people answering questions but yeah if you do have any more questions please put them in the chat now because otherwise we will sign off and eve oh it seems like i think maybe questions are answered either way you should stick around because i'm going to be doing a concluding talk and also pointing us

at the after party so don't leave the site yet but yeah if there are any other questions please do put them in the chat for pratush you're just getting a lot of clap uh is sexy gone then so yeah so sexy i guess was the old name for this ecosystem we started decided to move away from it because it was maybe too closely associated to the paper and since then there's been a lot of contributions from folks working on other projects and things completely unrelated to sexy and i feel like sort of the i guess the primary value of the ecosystem is not in in like the xe specific parts but rather

in everything else and everything below that so uh yeah zexi i guess is uh deprecated um as a name for the ecosystem but like a lot of the code just lives on this refactored and moved around and better documented that's actually good to know what was what's the parallel scalability so okay that's a very broad question but i guess so we paralyzed both ffts and msms using um basically whenever there's an option to parallelization we try to leverage it using rayon so ffts msms batch inversions wherever we can we try to paralyze if it makes sense cool all right well i think uh i think on

that note we can wrap up so thank you so much for the talk thank you so much everyone who listened and asked all these great questions this is fantastic yeah thank you so much anna for having me and thank you everyone for asking the wonderful questions