ZK12: DART: Distributed argument of knowledge for Rough Terrains - Steve Thakur

Transcript

[Music] now we have Steve give him a [Applause] hand can I begin can I start all right uh so let me Begin by unpacking the acronym suggested by Chad GPT uh so distributed is a reference to uh the proof system being fully distributed which means you can massively parallelize with the cluster and with minimal communication complexity between the machines and rough terrains is a reference to the finite fields in question the ones where the circuits are going to live lacking uh high tuity or large smooth order

subgroups uh more generally so here are some of the motivating use cases so the first one the Edwards curve uh will be familiar to anybody who's tried building a bridge from Solana or from Cosmos and run into the issue of the non-native arithmetic uh the second is a curve used by ethereum for its consensus and although it's well suited for snarks it's not that well suited for one layer recursion which is why 377 was once proposed as a drop in replacement and lastly if you want to aggregate multiple evm compatible snark proofs together you need to deal with uh b254 scalar multiplications and pairings inside a circuit so what these seemingly disperate use cases have in common is the base fields in question they have low to adicity and more generally they don't have large smooth order subgroups

now this largely so there's actually some Nuance to be had here uh but it's largely precludes the the traditional snarks and stars which H upon uh Univar gr bases and uh Spar Vanishing polinomial uh there's always the option of using a multilinear PCS but that actually comes with trade-offs and I'll touch upon that a little bit uh on a broader note you can construct a paing friendly outer curve to this by which I mean a paing friendly curve that has a scalar field which coincides with the base field of the original curve all right so here's what I was looking for so I was looking for a backwards compatible proof system which first of all could C recommend the enormous overhead of non-native arithmetic uh for these use cases and secondly something which could be massively parallelized uh with a cluster uh with low communication complexity

between the machines and lastly for most of these use cases you probably wanted to leave the door open for uh recursion in a non-native circuit so you can compose the proofs with those of other NP statements uh so you want the verifier to be as cheap as possible uh this is roughly what the diagram looks like so you have the master node in between who's sending the fim challenges to the nodes at every turn and he receives the uh commitments to the PO to certain polinomial and evaluations of these polinomial at after each round uh and he can add them up because it's a homomorphic commitment scheme which I'll get into uh so here are some of the for runners to this uh plon needs needs no introduction uh pianist from the polyed team last year uh took plun and made it fully distributed uh the last one

actually I didn't give it a name but it's uh a monomial basis snark I worked on back at Panther protocol uh it's not fully distributed though all righty so uh here's the here here are some of the design choices so the polom commitment scheme that we use is a b variate kzg and a downstream effect of that is it gives you constant proof size verification time and communication complexity it requires a trusted setup which is not ideal but if you look around most of the hash based Solutions at the moment are wrapping their proof inside across 16 in circuit at the moment so I feel like we're already making that fast in bargain in some way uh because there is no efficient lar basis to work with we use the coefficients uh in other words the byari monomial basis to commit to vectors uh with each of the uh machines

holding a part of this polinomial uh so here's what a PCS opening looks like uh this actually is independent of the bivariate uh distributed setting but uh more generally so you have this bivariate polinomial and in order to uh verify that a certain opening is correct uh the verifier requires these the commitments to these two potion polinomial and the reason it works without any hiccups in the distributed setting is because the hom the scheme is homomorphic uh the PG scheme is homomorphic right uh so the master node all he's doing is he's adding up the elliptic curve points he receives from the uh various M uh various prer nodes all righty so just so there isn't a cloud hanging over the next few slides I'm quickly go going to go over how the

one nonl the super linear part of the proof generation is going to work uh so let's say you have two polinomial F1 and F2 or an fft unfriendly field and you want to multiply them right so what we're going to do is we're just going to treat them as polins or the integers or to be more precise or the non- negative integers and we're going to take the product over this monoid it's not a ring or a grip but that doesn't really matter here and the way we're going to do that is we're going to choose two nice primes P1 and P2 and we're going to choose them large enough so that the product exceeds the uh coefficient uh any of the coefficients of this resulting product now we're going to perform ffts uh to to obtain uh both this product modu of P1 and P2 and lastly we're going to use the

Chinese remainder theorem to recover the answer module of P1 P2 which is the same as recovering the answer recovering the answer uh over the integers and the last step is you reduce the the thing module of the original Prime to get what you were looking for in the first place all right so the arithmetization that we use is plish and uh that actually gives you custom Gates which is which comes in quite handy for the LI curve Point additions and doublings uh one of the common refrains about plun arithmetization is that the addition gates are no longer free and they're not cheap uh while we weren't really able to address that problem completely uh what we do have is we have a mechanism gets rid of the intermediate Gates arising from large editions uh I should say that it's not as nice as something like CQ

Lin for smaller circuits because sqin actually makes them free uh the flip slide is what we have here uh it doesn't require a quadratic setup and it doesn't require High two add all righty so uh the building blocks so because everything is committed using the coefficients the the perhaps the most important thing is you need an efficient uh protocol for the had product by which I mean you have two polinomial F1 F2 and you define a third by taking the product of the co efficient at each positions uh and the second thing you need because it's funish arithmetization you need a permutation argument for the copy constraints okay so let me quickly go over how the univariate het product is going to work before I jump to the bivariate distributed case so let's say you have two polinomial F1 and F2 uh what I'm going to do is I'm going to

take this Twisted product by which I mean I'm going to twist the first guy by uh this challenge gamma and I'm going to reverse the second guy uh you might notice that if you expand this polinomial uh the coefficient in the middle the one at x to the T coincides with the evaluation of this Hader product uh at the challenge gamma right so past this point the only thing you need is you need a low degree test for the thing on the left and the degree upper bound that seems to work the best for a use case is this guy all you need to do is you need to prove that the thing on the right the rational function is in fact a polinomial and this one lends itself quite well to the B very distributed setting without too much uh without any hicups and uh you can bat multiple haded

products by just taking a randomized sum okay so let's go over how it works in a distributed setting because that's what we're interested in so let's say you have this had product that you want to prove and uh the most important thing perhaps is you want to avoid any computations of products of polinomial held by different parties because that would just blow up the communication cost and that would kind of defeat the purpose of using a slow uh but homomorphic commitment scheme like kcg so uh one thing you might notice is that this one single hadim product equation is equivalent to these individual hadim product equations being valid for each uh for each of these univariate hadim product equations being valid so what we're going to do instead is we're going to very probably send a

commitment to this guy uh the one whose coefficient at y to the J is this Twisted product the same trick as before and it turns out that it suffices to show that the thing in the middle the Coe coefficient of x to the t is this polinomial C of gamma y uh ver C is the claimed hadim product and once again you need to prove a degree upper bound on the thing on the left uh to be more precise an X degree upper bound okay and in order to very probably send a commitment to this guy uh it turns out it just boils down to a hat product equation or fpy which is proven by the master node all righty so the other thing is the permutation argument by which I mean you have two committed polinomial F and H and you have a committed permutation

and you want to prove that the coefficients of these two polinomial are thus related uh it turns out the L log ofes argument turns to be a little bit cleaner in this distributed setting uh compared to uh like the more TR traditional uh brand product argument okay so I'm going to quickly go over how the snar constraints are going to work uh so let's define something analogous to plong selected polinomial so you can turn the different types of gates on and off uh so the first thing you need to prove is you need to prove the appropriate degree upper bounds for these wire polinomial uh the other the second thing you need to do is you need to prove that the uh addition and multiplic ation gates work the way they're supposed to uh which as I said before is largely

expressed through the Hader products uh and the third thing uh last but not the least is you need a permutation argument for the copy constraints okay so a brief overview of the snark uh so the proof size because we use kcg a downstream effect is that the proof size is constant as is the verification time and the communication complexity between the machines uh the worker node uh his proof generation time is dominated by the msms and to a much lesser degree the sum of polinomial products he computes using the multimodular ffts uh and the case of the master node is fairly analogous except uh the parameters are much smaller in this case so uh the msms are of length at most M uh M being the number of machines which in uh in practice is

quite small uh yes so one thing I wanted to touch touch upon is uh maybe switching to a multi-linear PCS uh so let me say the obvious ver so you would have a linear Time pro ASM totically which is great uh the downside of course is that the verification time gets worse uh and so the non-m recurs recursion would get worse uh and of course the the proof size is larger as is the communication complexity as a result uh here's the somewhat counterintuitive intuitive part right when it comes to the proof generation so first of all the benchmarks that we have so far they suggest that these multimodular ffts are not really the main bottleneck at least not compared to the msms uh even for a curve like b254 right at least when you're looking at circuits of reasonable

size uh the second thing is for the use case we're looking at the base field is actually at least twice as large as the uh scalar field uh so the base field field is where the msms are going to live as the ffts are going to live in the scalar field uh which means the threshold beyond beyond which the ffts start to dominate uh is even higher and the third thing is what this work is doing and that actually is kind of similar to what pist is doing with the lran basis is the length of the msms and the ffts performed by any one single machine uh gets chopped up by the number of machines right which means the threshold Beyond which the n login ffts start to dominate gets pushed back even further uh so some of the other things we have in addition to the snark uh I

mean because it's plish we have support for custom Gates and lookups uh one other thing that we have is we have a protocol for polom products in a pish circuit which kind of comes in handy for b254 pairings in a circuit if you want to aggregate multiple evm compatible proofs uh because you can actually multiply two fp12 uh elements in literally 12 Plage Gates uh here are some of the benchmarks so take these uh with a grain of salt because we haven't actually benched it with 32 machines we actually implemented it for 32 machines but we only used like a single machine so far uh but with an outer curve to 825 519 uh it's like 26 seconds for a million gig circuit uh for the same size circuit uh with a larger curve uh which is like a 12 Lim outer curve to BLS 12 381 it's like 56 and of

course if you use like 32 machines uh which we haven't done yet we expect it to get divided by 32 perhaps it might not be literally linear uh but should be close and that's because the communication complexity uh between the machines is like negligable yeah uh that's it [Music]