'Scaling zkSNARKs to meet the demands of Filecoin' - Friedel Ziegelmayer

and i want to welcome friedel from protocol labs and we'll be talking about how they're scaling zika snarks to actually maintain the demands of fall coin so apologies again for uh for the technical side of this but um welcome to uh the summit and i'll let you take it from here thank you thank you for the introduction all right let me share my screen so we can get started all right um thank you everyone for having me yeah so on friday i go by dignified choir or dig for short on the internet um and i work on protocol labs and i've been working on um bringing zk snarks to popcorn for the last uh three years probably um and so uh if you don't know pro collapses we uh build things like ipfs and filecoin and uh if you don't know falcoin as uh falcoin is a decentralized storage network that happens to rely very heavily to actually work on uh using zk snarks and i'm going to talk a little bit about the challenges that we had making that actually work um all right so um as i said so i've been working mostly on on the proofs uh side of things for for filecoin and if i'm talking about proofs what i mean here is the part in falcoin that verifies that storage is actually maintained as as is claimed and it turns out that is a non-trivial problem to solve uh in fall coin i'm going to go quickly over this there's there's much more information on the lda proof's work and detail so you can find that out on your net or ask later but i'm just going to go very high level so we can cover some ground um so we have three big proofs that that we need to to take care of in fall coin and all of these use zk snarks um to um to actually make it on chain so if we look at the first one the first one is called corep called short for proof of replication this is a proof that gets generated every time some storage gets onboarded onto the filecloud network so uh storage gets onboarded in sectors uh which are just chunks of data usually they are currently either 32 gigabytes or 64 gigabytes and and if i'm giving numbers i'm usually referring to two gigabyte sectors because that's currently the most commonly used size the second proof is what is called winning post short for winning proof space time this is a proof that gets generated on every block so if a miner mines an actual block they have to generate this proof uh proving um that and some challenges actually are still valid on their current storage that they're providing and then there is window post which is short for window proof space time and this gets generated every 24 hours for all sectors or partitions and so basically it's a rolling challenge against the store that the miner provides storage miner provides in order to secure that that storage is still available now all of these proofs by themselves don't wouldn't actually need to use ck snarks you could just simply uh don't generate local proofs in most of these cases and just post them and be happy and live happily after ever after but unfortunately um the amount of proof merkel proofs that we would need to generate would make any blockchain explode in terms of size and so we use zk snarks really to compress the amount of information that needs to be posted on chain and to keep keep up with that demand now turns out when we've looked at the design of these proofs and what the amount of things that need to be proved here in zk snarks um there were some challenges uh looking at what we had when we started so so as a reference when we started building this the new hot stuff that was out was the library called bellman from the folks at zcash and they were preparing the sapling update switching over to this new library implementing graph 16 and rust as a very great baseline but unfortunately the thing that we were trying to do were a little bit more complex and so we really took us the last years and like getting to to a place where we can actually do the things that we run today on five minutes so the first the first challenge um that we ran into and this is like demand one that falcon gave us is hey we would like to have a billion constraints a billion constraints um is a lot of constraints in a graph 16. i want cs based and for reference um so i looked this up early on so the z cash sappling spend circuit which is like what was there back then was like this was you know really cool and a live deployment of of zk snarks um uses roughly 100 000 constraints so we are orders of magnitude beyond what was available and had known to actually be done now how do we get a building constraints put into zika snacks um we looked at a lot of things and what we ended up doing is so we had two steps really that we needed to to to deal with so the first one was we needed to look at just the setup um so for for graph 16 you know you need to run a trusted setup call and it's called powers of tal and this defines how many constraints can there actually be uh in any given circuit that you ever ever run based on this trusted setup so as you can see here um zcash ran back then a trusted setup um based on 2 to the power of 21 um maximum constraints which is roughly 2 million um now we ran a trusted setup um a couple years later to to solve our scaling issues um which allows us to construct circuits based on 2 to the power of 27 which is around roughly 134 million constraints now this is already a great increase but if you look at the math 134 million is still not a billion so how do we get to to a billion um well unfortunately we couldn't grow the trusted setup uh we could have but that would have introduced other issues so this this trusted setup generates a lot of output files and some of these have to shade later down the line um and so what we um and so if we had increased even more then we would run into issues there um that we could not distribute those files easily also the larger you go in this size the more complex the trusted set of computations become and so you reduce the amount of participants that really can deal with this which is really not something you want to do in a multi-party computation where you rely on having a lot of trusted parties uh participate so so we were stuck somewhat at this two three power 27 number um on how to to come up with something else so the next thing that that we did to solve this was well it it's not that exciting we split the snack um so in luckily for us the product circuit really is a repetition of the same thing over and over again proving that a certain challenge is still valid and so it is very repeatable and and so what we did we constructed this proof instead of just having a single dk snark we generate 10 zk snarks each with roughly 100 million constraints and so if we tend to take that times 10 we end up with 100 million constraints cool unfortunately this means now you're not putting 192 bytes on chain you're putting 1922 but by its own chain which is not great um but way better than if you would put all those those local proofs directly on chain so so this was how we got to a billion constraints now if you if you have folks um with a billion constraints um kind of obviously what follows is that the proving part of your snarks is is gonna go a little slower because you're suddenly generating very very very large circuits and trying to prove them and and the demand like that falcon gave us was really like look this has to be done in reasonable times and in some cases specifically winning post in very fast time so winning post has less constraints but it has because it needs to be generated per block and we have a block time of 30 seconds you need to generate this post in under 10 seconds so you need to go really fast and there's like this like is crucial for every miner like this there's no excuse or this is not going fast enough so um the first thing um and and really the the most critical thing to enable fast proving that we did is take um all the proving from the cpus and to the gpu so not all the proving but the most expensive parts so um when you generate a zk schnark using roth 16 the turns out the most expensive computations that you have to do are ffts and multi-exponentiations so um what we did is implement those um first in opencl and later in cuda to really optimize um the performance of those and if you look here at the graph we have the the amount of speed up that you get is quite considerable especially when you look at the hundred million constraint size which is the one that that really counts for us um for poor apps and the ten million ballpark for for winning coast um and so uh we we were see we're seeing a between four and six times speed up uh between between the optimized cpu version so as an explanation here bellman is the original roughly uh the original library that zcash gave us and to the world um and that we've built on and then bell person is the fork of that library that we we optimized over the past three years and so you have the cpu version which is it is slightly faster but it is by no means as fast as as the gpu-based versions here in opencl and the cuda version and the opencl version is the one that is currently deployed on mainnet the cuda version is has been in development for a little bit and we hope to ship it soon and it'll give give another nice boost to everyone uh running on filecoin for reference these these times are recorded uh using machine running a rtx 3090 but um you can also like you get similar results with with greater gpus there's some limitations around the amount of ram you have to have to load things in but generally you can use this well um so so that that that helped a lot let's take a look uh what else all right so the other demand is really uh fast verification right so um because we have a lot of snarks that that go on chain um block validation needs to handle snark validation and so you need to really make sure this goes as fast as possible because otherwise you will just simply stop the chain which would be very bad so um the first big thing here that we have is this blast and and this is a this was a collaboration with the folks at supernational we've built this really um based on on the requirements from from the ethereum community and and us originally blast is is focused on uh implementing a bls 381 based um the signatures bls signatures um but because we already when we designed this we really requested that the operations were available to also do everything we need to actually do graph 16 based on this because what you really need there is a fast implementation of bls 12 381 um this is a library implemented in where all the critical routines are implemented in assembly um and the higher level parts in c and and we've created bindings and rust to that and so we can use it as a drop in replacement for for the pure rust implementation of bls12381 um it's been audited by ncc and currently there is a formula of certification underway for the full library as you can see here this saves again very heavily factor of three i'm just just doing a simple pairing which is one of the biggest bottlenecks when you do verification times both g1 and g2 uh bls12 um multiplication is also considerably faster uh and um for most of other curve operations this is similar and so you end up with with considerably overall speed ups um not necessarily the 3x everywhere but but considerably faster um but this is not enough uh this was not enough and so another thing that we did was implement the graph 16 bash verification so so quartz 16 batch recreation uh the first time i've read about it is in the zika spec and as far as i know they did they hadn't actually implemented it back then uh but we found it and and luckily got it implemented and and this is really great because it allows you to um so there are three miller loops per uh per if you do a verification but this allows you to save two of those three and do them only per batch and not per per proof and so you can see here as soon as you start batching a lot of proofs together the growth and verification times really goes down which is great um but you [Music] and so we we currently don't fully employ this as much as we would like to uh currently so we we do this for for poor reps because as i mentioned we have 10 pour ups per per or uh 10 snarks per core sorry um and so we do a full batch verification there and gain the considerable speed ups um doing batch verification for for more proofs is a little bit more tricky because um you need to make sure on the execution path that you can actually do dispatching and the batching only gives you um everything is valid or invalid so if something is invalid you you need to go back and do more complex checks uh which is a little tricky to deploy but this is as you can see it gives us really good speed ups from like factors of six uh on just eight verifications which really counts if you look at the amount of verifications that we have to do on mainnet all right so we got that in so um seems like uh we've got already a lot of things in um but but there are no more demands uh ones to make more snarks really the the network and and really there's there's more demand and and the chain um is getting fuller and fuller um and so there's the request to to make the proof smaller so as i mentioned for core apps unfortunately we have we have not just 192 bytes from a single stack we have 10 snarks um and the amount of of of snarks uh and power ups that go unchained is considerably high i'll show the numbers later and so you really end up with uh an issue of having the currently if you look at the chain stats we still need we still need less less bandwidth to be used for for snarks and so uh one of the latest things that we've been working on is uh called snug pack this was just uh put up on on eprint and um as a collaboration with a couple of folks and based on some work from mary mallor and others that allows us allows taking a growth 16 based snarks and and to take them and aggregate them there are a couple of restrictions they have to be based on a parallel so the number of proofs you can aggregate are have to be a power of two but is really great because this is really what allows us to take size and verification times to to next level there's more detail there was just a more detailed work that the zk proof workshop earlier earlier this week from my colleagues on this if you want to know more about this um but just if we look at the numbers here um they're really good so we can see that um from from going uh so the blue the light blue line is what we have as the batch verification and up to 256 um we really go uh we're not faster yet if you look at the verification times it's the difference is not big but it's not worth it yet but as soon as you cross the 256 mark the verification time stays much much slower lower and and you have a difference at the end with 8 thousand when you agree it's a thousand snarks of a difference from from 30 to 33 milliseconds versus 435 milliseconds which is a roughly difference of 13x which is which is very considerable um if you look at the sides i don't have a graph here but if you look at the size differences um you have a similar cut over point at 200 aggregation of 256 and the the cut over there grows very quickly and if you aggregate at uh at the 8000 level you're looking at 40 000 bytes versus 1.5 million bytes and so the difference is about 37x so really considerable size improvements here if if you can use this this is unfortunately not yet deployed there is a fib open flip thirteen if you wanna look at that for more details on how this exactly is planned to land on falcon mainnet but it should enable a lot of improvements on onboarding storage uh which is where it's used for for the moment on improving poor apps um yeah um all right so so if we look at this a little bit um back uh did did we did we did we get what we needed um so we've launched mainnet back in october um and uh it's been running pretty stable so far so that's great um and people have been making some snarks so let's let's take a look at how many snarks and and what what are we looking at so uh currently we produce the main that roughly produces 30 000 winning posts per day which is the smallest one um we have um 36 000 window posts so window post has the same number of con similar number of constraints as a single snark and for rep so uh this is also this is roughly 130 million so just scratching at that the top level of how many constraints we can put in there and and this happened and this was specifically actually designed such that uh we're trying to get as much information into a single second snack there as we can get into onshane of course and then roughly 5.5 million per rep snarks per day so this is 550 000 pro reps per day um that we're currently averaging on on falcon main net um and so this is 5.5 million snarks there and and each of them again roughly 130 000 constraints um so that's a that's a lot of constraints so we have a fun number here that we calculated um where is my constraints per second sorry all right uh yes so for march 21 uh this this we average uh roughly uh fourth thousand seven hundred uh snarks per second and so this is a main that roughly produces uh one snug every 0.

2 milliseconds um if anybody was curious uh we think this is a big number of snarks we think this is a lot of constraints but one thing that i would love to ask folks is please do reach out to us um to me afterwards or in the comments i really want to know like who's deploying snorks and how many snarks are they deployed and i think it's really cool um to see what systems what what we can push these systems to today um so i would love to hear some numbers uh from folks um so far i have not heard anybody claim that they make this much many snarks but um please please prove me wrong um yeah this is the covered over roughly 2 000 miners and this proves currently 4.7 exabytes of storage and so um that's a lot of sectors right so most of these are 32 gigabyte sectors so um that is a lot of storage that we have there uh which is great um which is a great proof of that the this snark scaling actually worked and produced what we wanted um because it actually runs now um there was always uh as always with these systems if you think about them in theory and then actually deploy them there is still always the fear that might not quite work as you you plan to to work all right um so yeah if you um i'm actually well uh yeah that's all um if you have things please get in touch um uh help us create great things um and please uh send me all your success of all your systems i'm really really really curious what other systems are currently doing uh what other tricks are people using to scale their snarks and make them faster um yeah and if you we have time for questions i'm happy to answer questions absolutely so um thank you so much for that awesome talk i i learned a lot of new things personally and kind of looking at all the other chats we have going on where we're streaming this a lot of excitement about snark packs so um i think one question that's more of a follow from something you said would be great if you're able to uh share a link to the workshop on smartpak so others can catch up and learn more about it uh the only other formal question that we have is uh just generally speaking what is the the uh impact of stock verification during uh the sync on your end um i don't have exact numbers unfortunately i need to because the spares i need to reach out to the folks that make these styles i do know from a very active feedback from those folks uh it is it is usually always not as fast as they would like it to be so it is it is it is usually uh it has a high impact and especially it has high impact uh when there is an issue with it so certain if somebody is actually running into issues then you get really quickly problems with verification um it is in terms of related to block times not the biggest issue is more uh winning post for the miners because the actual generating that on time is is even more critical um and it's just more resource intensive and so that that is more critical in terms of block times currently on the network but verification always needs to be faster but quote unquote lucky for us there are also other parts of the system that need time so we're not the only ones slowing things up awesome well um i think we are slightly over time so i'm going to have to wrap this up but i am personally super excited to learn more about snark pack and i think to follow up on the ascii mate which is getting you in touch with all the snark apps i think we'll be happy to follow this up on on the hackathon side there's a lot of people working on this stuff and i also think uh you may be interested in the next talk which ends up covering how to speed up a lot of those things uh by using noir and vlookup or plug up so uh thanks again dignified choir and uh really appreciate you giving us the talk today [Music] thank you so much thank you for listening awesome