zkStudyClub: Dory w/ Jonathan Lee (MS Research / Nanotronics Imaging)

Transcript

okay welcome everybody uh to today's zk study club today we're excited to welcome john lee um who's written a paper called dory and uh for efficient transparent arguments for generalized inner products and polynomial commitments so uh john take it away oh thanks for the kind of direction um so just to you know maybe maybe put this in a little bit of its sort of setting um most of this work was done at microsoft research uh where i was working with srinatseti quite closely so there we were working pretty intensely on some schemes like for example spartan um and some applications of that that were starting to uh move out to trying to accelerate ethereum and things like that so this this ended up being published as pepperine um and so as a corollary at

all that we got really quite intimately familiar with the pain points associated with running some of these uh you know interesting r1cs zk snarks on systems of maybe two to the 24 to 25 constraints um what sorts of pain points we were getting just this this was becoming a problem for us um and obviously we didn't particularly like the fact that these schemes at least the way we were doing them didn't have transparent setup so we were we were unhappy um we were very interested when we saw supersonic come out into the dark compiler work over in that space um and we started trying to think about you know how could we try and implement these could we optimize them um

and let's just say that went nowhere uh we didn't end up doing that instead uh i came up with some interesting ideas about how we can use bilinear patterns to get most of the same effects um so just to start with the real basics uh we're going to discuss mostly generalized inner product arguments and particularly how you can use this to build polynomial commandments so here we've got some field of scalars f uh although we're going to have some pairing those parents will be type 3 which means g1 and g2 there's no efficiently computable morphism between them um i'm going to be really loose in the rest of this talk about you know the distinction between these groups how often we're going to find that we have some argument where really all we need is the

fact that there is some f module structure here so you know i can take a g1 or a g2 or a gt and i can multiply it by some element of f um and in a lot of context that's the only thing so what's uh generalized in a product argument well we fixed some some vector spaces or more generally some modules uh we have some inner product between them um and the key idea is going to be that you have some commitments to some vectors in these two spaces and some products uh and you want to give some some argument of knowledge of the openings that will be consistent with this in a product um now phrase like this this captures the sort of simple inner product notion which would normally be uh two vectors in in the field um but it

will also capture things like maybe i want to take a product between some uh some scalars and some elements of g1 or even some elements of g1 and some elements of g2 now you can then take the stage further and say well suppose that these uh suppose we have some vector scalars and instead of it being an arbitrary vector of scalars it has some detailed multiplicative structure well in that context you can build yourself a polynomial command so here the notion is that you have some again in general multivariate polynomial with some degree sequence um it turns out you can always reduce this to the case of multi-linear polynomials uh so you know in sql we'll only really discuss that um and the key idea again is you have

some commitment to the polynomial expressed somehow um and you have some commitment to an evaluation and you want to show that this commitment to the polynomial and the commitment to the evaluation are consistent with evaluation at some point um so originally this was introduced as a notion by kate um here we're changing the definition very slightly because we're not going to give the evaluation in clear text we're going to commit it um that just makes it much easier to build case now it's later um so why would we build this well as i've mentioned a few times z case knocks and in particular we'd like them to be transparent so depending on how you want to package all those assumptions up that's either a stock or a

transparency case or whatever it happens to be um part of the reason that we can really look at this problem in isolation is there's been a bunch of work by other people uh and i will point at spartan here at our point of halo there are a couple of other schemes which have really made this distinction clean um that split building a zk snark for some np complete language into two fundamental stages first is some purely informative information theoretic stage uh this will normally use things like a subject um that managed to reduce whatever nd problem you have down to evaluating some hiding polynomial commitments

um now once you've done that you then need to somehow come along and cryptographically provide that heightened polynomial at the moment um but it's convenient because now we get to look at this simple problem we don't actually have to worry about details of what what scheme is being used uh we can sort of plug and play um and sort of you know we would like to avoid having a combinatorial explosion of papers where we take every possible polynomial commitment scheme and plug it to every possible uh information theoretic scheme to generate huge numbers of schemes um also again in the sql everything's going to require transparent setup um very crudely because if you don't need that it's just easier to use custody commitments paperman through which is the multivariate generalization or just go the whole hog and use growth 16. right so

everything's going to be fine so what do we care about well at least in the cases that we were interested in um one of the real pain points that we had uh is that we need the commitments to be small so this is a particular problem because for r1cs you're generally going to have some commitment that is associated with the witness um and that means that you have to send that to the verifier and in schemes based on hyrax for example that ends up being uh only a that ends up being a square root so you end up with quite large groups because of that we also care quite substantially about concrete constants um this particularly came

up in the context of trying to think about how you could use uh start or snacks as a way of accelerating certain aspects of ethereum um you know it becomes really quite critical that the prover is concretely efficient because you know sure gas is expensive by comparison to azure time but it's not infinitely expensive right there is still some requirement but we not be losing orders of magnitude on the prover um and we would also like to verify to be fast uh maybe o1 is is a little too much to ask for but if you get it down to at least log n or poly log n in the very worst case that would at least make sure that the dominant contributions to these overall proofs were coming from the information theory parts rather than from purely different

crypto at the end um and one other thing i'll sort of say as a nice to have is again we were finding that we were starting to have some pain associated with generating uh parameters for these schemes um yeah this sort of turns into a question like uh if you're doing a transparent setup how long are you going to have to run this for right um because the verifier at least naively has to go run that process at least once um or you know you could imagine other ways to finesse this you could perhaps have some uh some system which sort of generates parameters and proves those parameters were correctly generated but uh so like i'll defer that to other work um so at a very schematic level there are

right now i'm going to say there are essentially three other uh transparent polynomial commitment schemes um sometimes this take you know getting this getting the slide together is is a little bit awkward um because as you can probably see i'm listing three r1cs snarks here um so i'm sort of having to go into all three of them and section out what the polynomial commitment is and just really look at that in isolation so those three are very very useful we've got hyrax which is based ultimately on bulletproofs this uses matrix style commitment schemes uh it has square root size commitments uh square root size evaluations but it's quite nice because it only requires

working on a curve any curve you like so concretely we're going to use 25519 dalek and just that's that's where we're going to go um fractals based on resolvement iops now those again uh have some some properties that are really quite compelling uh the in particular the commitments are quite small um the uh the evaluation time is also sort of reasonable um i do want to put one asterisk on this which is that uh we were finding that at least again in the context we were looking at which is we're insisting on some fixed security level um and we really wanted to make sure we could achieve that one problem that we noticed

with the resolument-based iops is that their soundness especially their proven sadness is not that good so so concretely when i get when i take lib iop and i ask it to instantiate practical and give me 128 bits of security it ends up rerunning the internal proof system maybe 500 times so yeah that does become a non-trivial constant um and then finally we have supersonic which is based on you know dark and some some really interesting work over there those require groups of unknown water those are i won't say new uh those have been around in principle since the late 80s um but their sort of use in this context is is pretty new there's a lot of questions being raised uh there's an interesting

paper by galbraith al really going into what security parameters are necessary uh to make these kinds of schemes secure um and ready to enable transparent setup uh so there's essentially a problem here where there is a uh a merely sub-exponentially small um class of weak keys uh and so you have a natural problem which is that if you want 128 bits of security you really need to push up to sort of the kinds of scales or parameters which you'd normally expect to see for rsa um john real quick we have yeah in the chat uh by the way do you mind i do not see the chat of course i will take questions whenever um yeah i can i can read it out if you can't see it sure okay let's let me read this

i wonder why uh fri based polynomial commitment scheme isn't mentioned here is the same as fractals or yeah that's that's fractal um so a fractal under the hood is an rsiop um there are as i said there's been a sort of combinatorial explosion of papers where people will take one particular polynomial commitment scheme and attach it to various um sort of front ends so for example libiop which is the thing i'm going to be concretely benchmarking here it implements fractal uh it implements uh yeah like for example is the fast one but there is there's aurora there are a couple of different schemes that it implements and all of those are different front ends for taking an r1cs and turning it into a

polynomial commitment that you then evaluate with a read solomon code right so like again i i sort of kind of want to apologize for the fields in some sense because we really should be able to do this better um and and clearly distinguish these these two components but it's a little awkward as it is um so yeah um so i also want to point to some of the limitations of this uh before i go any further um so because i'm fixing the security level um in this context i don't care whether you're doing a field addition a multiplication or even a full exponentiation right i'm going to treat those all as an order one operation now you can criticize this there are papers

that do um there's again a really interesting paper paper by brutal kierster and lou uh that sort of essentially goes and points out that so these exponentiations you know necessarily picking up an extra factor of lambda um and you might you might feel some concern about that um i'm also sort of not going to get into the details of of how you get into type savings for the groups which can be a log which you know that's an order of magnitude for some of our systems so that's that's non-trivial um so so having said all that and with all those provisos here are some sort of concrete constants that you might expect to see so this is based on uh you know basically pulling the pulling up code on

you know my desktop and just running it right so essentially for higher x we're looking here at you know you're working on curve25519 dalek like how fast is that curve how long does it take you to do an exponentiation how large are your elements for fractal using say the blake 2s hash function because that's the the primary uh constraint is how fast is that how large are the elements associated with it and for supersonic again this is complicated because there isn't an actual implementation of dark anywhere that i know of um so this is based on the antique qfp library which is a fast um algebraic number theory library uh and feeding it a fifty hundred fifty five hundred bit uh discriminant which is what galbraith that i'll

claim is required for 120 bit security and just asking like again how fast can we do a 256 bit exponentiation how large are these elements um and i just want to re-mention that it's a minor issue with things like fractal or other retirement iop based games but so you might pick up a constant of 500 or so here so the time starts to become pretty competitive with things like hydrax and proof sizes become quite cool so yeah just pointing at some of the things which are awkward here um hyrax which is what's under which is what underlies uh spartan that's unfortunate because we have a polynomially large commitment um that is the evaluator that the verifier is polynomial um but it's concretely reasonably fast uh

fractal we have some pain points associated with that uh the evaluation like the sizes of the proofs uh because that log squared really does pick up a factor of 500. um and for something like supersonic uh again like the actual completely concrete numbers are in the paper but we have not run this um because we we saw how long we would need to yeah we saw how long we would need to to spend uh working for say 2 to 20. um and we were looking at sort of hundreds of thousands of seconds of cpu time so this was this was sort of uncompelling to us um so then you know as is traditional i've now presented a table with competition and now i'm going to present

what we do so uh so great so what's dory doing well dory is introducing parents so now we have uh gt's compare and parent computations um and essentially the illustrative constants are a little bit worse than they might be for something like hydrax right so because when we have to have occurred with the pairing we're now going to work on the bls 12 381 curve um that means that the sizes go up by 50 just from fields and you get other factors of two to four depending on whether you're sending g1s g2s or gts uh you also lose most of an order of magnitude in terms of concrete performance again this is comparing uh the fact that in higher axis of the

typical operation would be a g1 exponentiation with now the typical operation is a gt exponentiation so things are getting quite slow um on the other hand it's not too bad right so our commitment sizes are small uh our evaluation uh our proofs are small um and the time complexities are reasonably tolerable um so this is the sketch of where we're going now you know given that everyone's very busy i i figured i might as well make sure that sort of very early in the process i have a slide that sort of lays out everything we're going to do so the basic story here is this is going to be derived from the same sorts of ideas that give you bulletproofs uh or the

generalized dental product arguments of uh you know bronze mala uh gonna miss the autism yeah the bmm tb19 right um this is uh in a product pad in a product parents and their applications is the paper um so unlike something like cartage which would also use parent we're not going to be making any kind of koe type assumptions here so we're just going to use sxdh sxdh basically just means everything you might recently hope to be true given there's a pairing so you've got differential different helmets hard in g1 and g2 um and c code a different helmet is hard in g1 g2 so that's saying essentially that if i try and tell you the logarithm of an element by sending you two things in g1 and then i send you

something in g2 you can't raise that element in g2 to the power so that's the appropriate exponent so you sort of you can't make um you can't make uh diffie-hellman quadruples um but you can obviously attack them because of the pattern so at a very clear level what are we actually going to do so we're going to start with a system which looks a lot like hyrax so we're going to sample some uh polynomial number of generators for some commitments to vectors of length square root n the first thing we're going to do that is different is that we're then going to compute some logarithmic number of structural preserving commitments to those generators

right so this is like a slightly odd notion we're going to have sort of a set of generators and we're going to have a second smaller set of generators and we're going to generate commitments to the first set of generators with respect to the second why would you do that well the main reason to do it is that now when you're running your bulletproof and you get sort of to be you know later in the process normally you run into a problem where your verifier has to compute some linear size um multi-exponentiations based on the challenge they've got and based on the generators for the commitments they have here the notion is that we're going to offload that computer computation so we're going to go and say look i have some extra commitments that i computed once upon a time that relate to how these generators go

together and i'm going to use that to let the prover sort of do that computation for me so now the prover is going to be doing all the large exponentiations and the verifier is only going to be checking them um this is analogous for notion that came up in the context of spartan uh which is the notion of a computational commitment so here you have some oh so in the context of smarting you might have some sparse multilinear polynomials you don't really want to commit to those as dense polynomials because then they would become quadratic in size um so you sort of have to go and do some computation first and boil those down in some clever way to some dense polynomial commandments and do you need to verify to do that but they only need to do it once and thereafter they have this polynomial

commitment and they can use it to offload work to their approval now if if we just had those two ideas that wouldn't quite work on its own that would uh in fact give us a log squared proof so essentially that's because yeah as we go and do this and we'll see the details soon um each round of the bulletproof like folding that we do would generate one and order one additional claims about what inner products that we need to prove um and if you weren't careful about that that sort of turns into a a logarithmic number of rounds of protocols each of which is log in size so you end up with a log squared overall um so instead we're going to go and we're going to pay a little more attention to how inner products work we're going to find some nice two-to-one batching argument again conceptually

very close to work that was uh previously in halo and that's going to make sure that we can keep the number of claims to be constants in each round so you know this may be sort of teaching everyone psychics a little bit but i'm just going to go through uh some preliminaries and sort of how bulletproofs work with a particular eye to how we're going to put things together later so for starters all of our commitments here need to be linearly homomorphic so that means peterson commitments for scalars uh or uh afgho these are uh are they forced biograph harambee evan or kubo that's his structure preserving signatures and

commitments to group elements um for elements of g1 g2 you should really think of these as the same components um so in both cases using this sort of generalized notation for inner products that i sort of outlined a few slides ago the commitment you have to some vector with respect to some generators gamma and some source of randomness r is take the inner product of your vector with gamma and you add r times some other element right so in the context of a peterson commitment it's very easy to see how you do this gamma is some set of elements of g1 h is also in g for afgho the vector is in one of your source groups the gammas are in the other source group and h is in gt uh this is technically slightly different from how are they

i'll do it they they randomize slightly differently but it's a distinction that makes no difference um so the key point about these is their structure preserving which means that if you give me a commitment to affect two two vectors i can apply any f linear operation to those so i can take two things i can add them up uh i can multiply them by scalars now once you have this you might think then say well you know what else can we do with it one thing that's interesting to do is to take matrix commands so these are naturally bilinear objects and if you go even all the way back to hyrax and then you would actually see that there there's a polynomial commitment that's based on reframing the polynomial evaluations of matrix multiplication um but there the notion is that you take

each row of the matrix and you produce a peterson commitment to it and then your commitment to the overall polynomial is that vector of commitment now in our context we can do a little bit better than that because we have not just commitments for infected in f but commitments of x in g1 as well so this is actually an idea um this is this is slightly complicated this was in an earlier version of b of mtv when it was a fourth of paper back in 2019 but it's since become a five worth of paper and they've they've dropped this construction so i don't quite know how to credit it but it's true that uh you can build a two-tier commitment out of this um by you know again writing peterson commitment to each of the rows and then you've got a vector of g ones

so you take a abe al commitment to that so that's quite nice right that now gives us a order one sized commitment to a an object um and you might naturally hope that we've got sort of linearity above uh between the rows and within the row so maybe we can exploit that cleverly somehow and use these inner product arguments that we're discussing and somehow get some polynomial evaluation out of it it will turn out this is true um and just the convenience of notation later because we're going to be doing these operations a lot uh we're just going to assume that all of our vectors are of length 2 to the m for some m um so now that means there's a natural way to cut a vector in half into its left part of its right part the other thing which will really come

up and in some sense this this is the core idea that sort of leads you down the path to building the rest of dory um is to think about kronecker products um so maybe this is sort of natural to me i was i was once if you're not feminization um but there's a nice a nice notion here of being able to take uh in general two tenses but in our context we only need it for vectors uh being able to take a vector and take product of it with another vector so here the notion is that know if you have some vector v you can take a copy of v multiplied by some some scalar l and another copy of it multiplied by some scalar r and just stash those two vectors together so this is an operation that doubles the length of the vector but sort of retains

a certain important multiplicative structure to it um so you sort of as you might recently see if i take uh a whole bunch of short vectors and product them together with the chronicle products i end up with a vector that has lots of subproducts of of the original scales right this is very much like what you would expect to see if you were doing say a polynomial evaluation right that you would see products of x1 x2 x3 so the other thing is just so that i can fit the the here so i can fit everything on slides and so that i don't have to bore you with details of how sigma protocols work uh we're not going to do hiding in at least this presentation all the details are in the paper everything is hiding from the from the get-go but it just makes it easier to

fit on slides and also again just like technical details everything's going to be public coin and honest verifier sdk um again given the target of r1cs for snarks who cares you're going to compile it with fish in it anyway so this all goes away um just to you know make make things explicit though like the only reason that we need honest verification is because we're going to run some channel proofs um and so you could always use god rights to hide the height uh yes i got right so five and button um to get rid of that it would double the number of rounds but it would give you it would drop the odds verification requirement and also so much like bulletproofs much like

that entire strand of work all of our knowledge samples here is going to be constructed meaning witness extended emulation so again just to make sure that's really explicit and so again this is not this is not quite written down in many of the source papers frustrating um the notion here is that you have some tree of uh you have some tree each node is labeled by some message from the approver each edge is labeled by some message from the verifier um you need to make sure that the degree like the number of challenges that come out of a particular node is small by comparison to the space of the challenges that the verifier could emit um and you need to make sure that every path from the root to a leaf gives you an accepting transcript if you just catch all these messages together

now if you have all of that we're going to guarantee that you can extract awareness um the main reason for this for like taking this as an approach is that if we do it this way it's much easier for me to talk about just one ramp does this here is like sort of individual sub protocols and then stack them together um and how are we going to get this witness extended emulation again this is a little gnarly and apologies you know some apologies i guess for for like the math notation here um the key thing that we're going to be doing in order to get witness extraction is that we're going to be taking some sequence of elements of some group right so g1 g2 gt who cares some some f module

um and we're going to interpret that as giving us a polynomial well technically a wrong polynomial so this is some element of um of the ring the ring of polynomials coefficients in g and where you can use x and x inverse or we may need we will need it to be bivariates in some cases and the key thing about this is exactly as you would expect for a normal polynomial over a field if you tell me if you know there are degree bounds on these objects and you give me some fixed collection of evaluations then you can uniquely interpret later pointless and that's relevant here because it means that we are able to say that if for example the prover is able to

uh evaluate one of these polynomials at multiple places that the verified handsets as challenge then we can uniquely reconstruct everything must have had so we can go from seeing an evaluation to actually seeing the underlying polynomial and we can actually pull out the coefficients associated to that so if we end up with equalities we get to say that those are sort of true qualities um so now we get to talk about bulletproofs a little bit with all of that service background so i'm gonna again give a sort of slightly abstract presentation of what a bulletproof is um so this key initial point in my telling of this is that when you are given a inner product between two vectors of

even length there is this interesting equality you can just write down so you can take uh these these short vectors where you take alpha times the left half of the vector or alpha inverse times the left half of the vector plus the right half of the vectors and when you take that product and just expand that out you get this thing where you know you would expect to get to you know a l times b l times alpha times alpha inverse and also a r times b r and those happen to add up to give you the inner product of a and b and then you get these these other two short things so now we're in this interesting situation where this sort of seems to be giving me an equation for writing a inner product of two length m vectors as some combination of inner

products of shorter vectors like m over two now that's relevant in our context because it means that you know if for some reason you happen to be trying to prove that you knew some a and b with a particular inner product then maybe what i can do instead is i can send you these cross terms right this alpha is alpha dependent term is alpha inverse and then you can turn around and say well okay here's a challenge alpha now let's do the combined thing so now if i show you that i have those half length factors right if i show you that i have this a prime and b prime so very obviously what is a prime a prime is alpha a l plus a r what is uh what is b prime b prime is alpha inverse b l plus b r right like you know that i know that but

we actually have to show it so the key the idea for like how we will show this is we will go and look at this this right hand side and we'll really look at this and say that this is a long polynomial in alpha if if i the prover can can successfully pass this query where i actually show you these this out this a prime and this b prime i can actually show you that for a couple of different values of alpha then you will be able to take the values that i gave you you'll be able to show that they're linearly varying you'll be able to interpolate back and then you'll just be able to read off that okay well you know i i see that you have a constant term that is is this y what does that actually correspond to well that will correspond to the like a

linear alpha term of a times the constant in b in b so the constant alpha turning b plus the uh constant in a constant alpha term in a times the alpha inverse term of b and you you you work this back and you end up with exactly writing that equation um so then you know what what do you do with keeping well you know with a bulletproof you actually run it you know you start with some factors of like two to the m you run it um and so now sort of at the end of all that i have some some scale of y final um and what am i supposed to be verifying as the verifier about this well you know if i write down these two

sort of slightly messy looking vectors that are big chronicle products of things that have been generating with alphas then what i actually end up with is a final claim that x plus inner product of a multiplied by x minus inner product with b is whatever is my final is supposed to be now again like for the moment this is just some sort of toying around with mathematics right like i've not actually done any cryptography here um but now we're going to put some sort of cryptographic meter on these bonds so how do we build an enterprise argument out of this well so the idea here would be that we've got some fixed generators gamma one camera two um and again sort of in a in a typical bulletproof presentation we only think of that being one but we wanna make sure

that we have the flexibility to to separate these two vector spaces later so we're gonna have two sets of commandments and i'm going to claim as the proof that i have some vectors v1 and p2 such that their inner product is c commitment of v1 is d1 and for commitment of v2 with d2 so again like this is this is three inner products um and if i was to do a very traditional bulletproof way they were originally introduced with six group elements per rams what i would do is i would run this folding argument and i would end up with some claim that i know some i would say scalars like vectors of length one v one prime and v two prime such that there's this this nice set of uh so such there's this nice set of equations and then like why is this okay

well the notion is that you say look this this thing on the right like uh x minus comma gamma 2. if gamma 2 is properly sampled to be a set of generators then x minus is also some uniformly random element i can't fake the logarithms with respect to this element so you know you you do a little bit of work to argue that um if somebody's able to open up d1 prime or d2 prime then that must mean they're really like they're big they're bound to v1 prime and v2 prime and then if they're bound to v1 prime and v2 prime you get to go and run the wholeness extraction arguments and ultimately get p1 and v2 back so why is this a problem well you know the prover sends v1 prime vt primal run some some snore type product

argument proof to not actually have assembled but the real problem is that the verifier actually has to go compute x plus gamma one and x minus gamma two right and you know those are those are some linearly large uh inner products so you know in the context of something like hydrax it comes down to being on your square root but still like this is the fundamental issue we have is that the verifier can't be can't be asked to do this computation takes too long so how can we avoid that well we have this sort of abstract notion that we can do uh in a product arguments with something that looks like a bullet proof and that sort of again very abstractly takes you from some inner product between two objects to

some inner product right to two inner products of the same size but now with a vector of scalars in both cases that is generated from the commit from the challenges that the verifier has sent and which also has the property that it is multiplicative right so this is x plus x minus they have structure right you didn't have that before so now here's the the first cute trick so let's just think about how a verify might come to know you know x plus gamma one well they know something about x plus right they know that it has the structure it's just pulling out the first term it's alpha 1 1 across some other vector and that vector also has this this chronic entire structure though that won't matter so much for us

so what does that mean well that means that actually you know that whatever x plus gamma one is you can pull out that alpha one and push it over onto the right so now you've got something where you've got the x plus prime and this this vector you know alpha one gamma one l plus gamma one r so far so so right this is this is a half length uh generalized inner product but if i'm going to run into products then i won't have commitments to things right so how do we do that well one thing is actually we can do this right like the verifier could have found some other set of generators um and could have some commitment to gamma one l and gamma one r if they actually have those

commitments then they could absolutely combine those to form a commitment to alpha alpha one gamma one l plus gamma one r and x plus or well x plus prime isn't committed uh but it has this this interesting structure and it comes out of a chronic product so if you just sort of blindly plug that through a bulletproof again then at the end of that process what will you have to do you'll have x plus prime and you'll have some new set of of challenges that came from the from the second instance of running your bulletproof and you'll have another multiplicative vector that has been built of those challenges and you will need to take the inner product of that with x plus prime and here's the magic right when you give me two vectors that have

this chronic product structure i can take that in a product quickly and this is again the formerly this is the identity right that you you go through and you extract term by term you end up with some product um this is uh for what it's worth exactly the same as the uh underlying math behind being able to um evaluate monomials at arbitrary places at speed uh you know or to be able to evaluate lagrange bases um like this is this is the same thing um so you know so if you have this cute property then it looks like we might be in an interesting place here right so we'd run our bulletproof at the end of that the verifier has got in this case two uh large inner products

they have to do with some multiplicative vector of scales and what they're going to do is they're going to shrink both of those by a factor of two by using by using these commit contracts and then they're going to go back to the prover and say hey i have this commitment to a vector i have this this public vector of multiple of the public multiplicative vector of scalars i want you to help me figure out that inner product so we go with the bulletproof we keep going um well and can we keep going and turns out the answer is yes and again why well because not only do we have these structural preserving commandments but we sort of have a cycle between them right to commit to a bunch of elements in g1 i need some generators in g2 to commit to a bunch of elements of g2 i

need some elements some generators in g1 so now i just pick one curve and running along this sort of sketch at each stage i would have some some inner product with some g ones say and i would run my bulletproof and end up with some some more compact thing i would compress it now using some shorter commitments in g2 again all my commitments now are sitting in gt but the generator service cycling from g1 to g2 um and if you're naive about this you get some like oh log squared uh proof sites and verified computers the same that's still sort of somewhat unsatisfactory and so if you go back and look at this and you say well okay what's what's really going on

here well there's this sort of odd feature of this of this protocol right which is that you know even if i don't know what x plus is very early in the process verify knows what this commitment to alpha one gamma one l plus gamma one i is they can compute that after one round with a bullet reduction right they know that immediately they have no idea what x plus could possibly be but maybe they don't need to know it right in a normal bulletproof they wouldn't need to compute anything with that until the very end so you know possibly there's some way that we could say look we've done bullet reduction that's generated a half size and a product we need to compute and then maybe we use these tricks to generate a few more half-sized inner products and we could try and combine them somehow so

now again being a little abstract mathematical about it you know is the identity that you have to use to you know uh be able to combine um arguments of knowledge about inner problems at the same length so here the notion is it's it's actually it's the same thing we had before uh we just like changed the alpha betas and we've changed the weights a little bit and the key point here is that now uh whereas previously we would have somehow been really interested in uh ad plus cb like that was that was our larger inner product in the first case now we're interested in sort of a b and and c d has two second points so we're going to make sure that this is the constant temperature b squared term um again yeah if you want to claim that you have knowledge of this of this a b c and d

such that these two claims about inner products are true what you do is you send me cruster um i'm going to save back some some challenge and then we're going to uh you know just combine these in the obvious way you'll end up showing that you know you have some some pair of vectors uh with this in our product so again exactly analogously to how a regular bulletproof would win its extract you can win six trackers um and that's cool because now we have a two to one argument for inner products um there's actually a paper of last week um that might be of interest to the people here uh is nova which basically takes the same idea and goes and applies it directly to r1cs so you take two r1cs instances you can

find them in a clever way you get one i1cs instance um so again so like what's this trick look like now well it's just really braced out so after one round of doing a bulletproof you've got these two vectors uh alpha gamma one l plus gamma one r and alpha inverse gamma two l scanner two r which just for convenience we're gonna notate with u1 and u2 so the verifier at this point knows some commitments you know c1 to products d1 d2 to v1 and v2 with respect to these modified sets of generators you want you to and they also know because because they were able to compute some things they're able to know what uh their commitments to

you two you wanna you two are with respect to some you said generators gamma one prime gamma two prime so we have we have these five inner products product of half length um and we really like to look at this and say look one of these is a commitment to one one of these is commitment to u2 and this like c prime d prime and d one prime d two prime they need to somehow be combined into one in a product can we do that well yes um so like approver is always free to make some additional claims that might turn out to be false um so if the prover is actually going to tell you some commitments to v1 prime and v2 prime with respect to the new sets of generators and verifier because you know they can pre-compute a bunch of stuff about the

cameras those effects uh that they can pre-compute all across terms that would be associated and understanding what you want in a priority to it so really you should think of this as not just like you know v1 prime vt prime and enterprise with use but so basically anything that exists between the use the verify knows um because the prover is either going to send them or because they're verified um so you could just at this point say look we're done um we've got you've got four commitments we know how to combine those linearly uh we've got these three inner products we need to prove we know how to combine those with a two-to-one argument just do it it'll give you an o-log and precise and verified computation constants are horrible um complete trash this is a good way to get a constant like 30 or something you don't do it um

but like it does successfully get get the thing to work um so you know now uh unfortunately i'm actually going to show you what the story reduction is and all the same ideas uh it's just that we have to sort of reorder them a little bit so as to get the concrete constants to be better so this thing would click next right so you know just to lay out where we're going to start where we're going to end we're going to start with the proof of knowing some v1 v2 both length m vectors and g1 and g2 such that the inner product of v1 and v2 is c and the commitment to v1 with respect to gamma 2 is d1 and we have these commandments and at the

end we're going to have the same thing with half length vectors with respect to completely new generators right so what does that look like well first we're actually going to do the merging this is the main dentist we do the merging first and then we do the folding so uh the proof is actually going to start by sending commitments to the left and right halves of b1 and v2 with respect to the new generators so just send me four gt's right up front and then the verifier is going to come back and give you a challenge beta and what's the proof we're going to do with their witness they're going to you know just add some copies of gamma 1 um now what's that really doing basically what this is doing is um this

apologies sorry powerpoint throws up on me for a moment essentially that uh that first round of that first round of adding gamma ones uh to b1 and v2 is essentially combining cd1 and d2 into a single end product right this is now an inner product between some factors that we don't necessarily have concretely but that's okay um so then yeah yeah then what are we going to do in the second round well the second round we're now going to do a folding so we have this uh this inner product between v1 plus beta gamma 1 and v2 plus beta inverse gamma gamma 1 of gamma 2 even um and we're going to

uh do a regular block profile on that so you send me the terms that are linear in alpha linear and alpha inverse send you back the alpha again like what does the prover do they they squash their uh their vectors that wouldn't affect us down um and then you know it is true let's just put it that way it's true that if you work through what that has done to all the commitments these are the expressions that end up writing down on the verifier so what are we saying here well you know c prime has some uh alpha and alpha inverse contributions from fold and it also has a contributions beta and beta inverse associated with that first combination stage um and you know it also has this surprise constant cross term which is gamma one gamma two

um the commitment to d1 prime and d2 prime are just completely constructed from d1 uh d1l d1r d2l d2l um and again some mixtures so some some commitments to the left right halves of gamma 1 and gamma 2 with respect to gamma 2 prime and gamma 1 prime and so what are we going to do with this well i mean this is sort of this is everything right like the verifier is actually going to have pre-computed these inner products why can they do that well because you know you just have some logarithmic collection of sets of generators of of of diabetic size um and you just generate these commitments you do that as part of the uh the setup process um and

when you go and look at the concrete constant space instead of having something like 30 now we're sending six gts per round uh four four in the original status of these and c plus c minus um and if you use the usual tricks of deferring will verify computation to the end and turning into a single large exponentiation rather than doing doing it explicitly with additions like this then what you actually find is that the verifiers only have to do nine exponentiations per round um essentially those nine are the six things that they get sent um and yeah so if you're being like you'd get ten right because you get six things that are sent plus these plus these four cross terms but you can be a little bit clever and you can reuse your generators which lets you save more so thank you like fair to say that like so one of the

things that that was different from bulletproof is now we have the generalized inner product thing is that we have um with it in a pairing product like the nice thing was that our commitments to the same inner product as everything else so we can sort of mix them in together and that's what makes this work um yeah so that that will uh like i'll come back to that um at least at least here so because the setup here is that v1 and v2 are from uh g1 to the m and g2 to the m here everything's sort of uniform because i set it up that way to start with but when you actually build a polynomial commitment you're going to have to see some vectors of scalars in here somewhere and that that does bring some

non-uniformity um and there's there's there are some irritating things we have to do to work around that um the the the thing which is like yeah the thing which is working in its core sense is the fact that you can um combine commitments to the generators and treat those as being just another factor right you can treat the generators being just another vector right and like that's actually where the at least in my view that's that's where the interesting new power is coming from um if you were to try and do this with something where you could imagine some system where you had some sort of some chain of structural preserving commitments that just kept running off to the right um and in that kind of context i'm not

sure you get anything you can still get a log squared but i don't think you'll be able to get the while basically because you need to keep sweeping all those commitments along so they were all at the same place and could be combined and here we get to do that but we only sort of get to do it because in each rank we're swapping over where the generators are coming from and they're always coming out of g1 i'm not sure whether that's completely responsive to your question but like those are the thoughts i'm having in this space so yeah like as i just mentioned you know we're actually going to need to introduce some public scales into these um so you know this is a slight generalization of our language we've now got

some inner products in g1 and some inner product and g2 um you basically run exactly the same arguments uh so like now in that initial stage you know that you're going to be asking what happens when i send when i add some some copies of gamma 1 or gamma 2 to the vectors v1 and v2 so the prover better tell me what what what that's going to change how that's going to change e1 and e2 um that's you know one one g1 one g2 uh also when i uh do the folding there are two uh two extra cross terms in each case so two more g ones two more g twos um and the verifier is gonna have to sort of put all those together so you end up with some more log sized multi-exponentiations in g1 and g2

um there is however still a wrinkle here which is that you know at the end of all this process the verifier is going to have to compute something like you know s1 in a product with x plus or x minus in a product last two right there's no no real way around this um and i don't want to say i have a proof that you have to do this but it seems very obvious that you know you're going to have to read the entire vector of scalars right like if the verified doesn't look at some some element of that vector of scalars it seems not necessarily impossible to avoid having some polynomial sound this error but it seems likely you will have one um but in our case we don't actually care and the reason that we don't care is that we're going to be using this to

build a polynomial commitment and for polynomial commitments these two vectors s1 and s2 will themselves have this structure of being a product of of chronic products um and so again we can we can use the tricks described previously to just compute these things in a long time um and you know like there are some some nice things right we have a we have an inner product argument we have a two to one argument for combining these things it generalizes completely naturally so giving you a two to one argument for problems of this form so if you give me two instances of this nominal language right two two c d d one uh e two e two e one e twos and you kinda have witnesses both we engage in some some one protocol

um and then you know assuming you can open it up uh given my random challenges i can i can witness extract everything so it's the problem there's there's an interesting wrinkle here which again sort of came up when trying to really write everything down super special so we're going to use the same two-tiered matrix-based commitment scheme that you'd see in pyrex uh or bp or bmm tv um so what does that actually mean well that means we're going to take a polynomial evaluation which you can give that to me as a dense factor of coefficients um or in some ways this is more convenient you can give it to me as

a set of evaluations on some lagrange bases and you turn that into a matrix product so this is saying so if you want to evaluate f at x one to x t you're gonna have some left vector that's a function of x one two x d over two and some right vector that's a function of x d over t plus one up to x d um like for now i'm just gonna make the assumption that this is um you can turn anything into a multiple any polynomial by just you can have something be a polynomial in a multilinear in one x x square x for dot dot um so both these vectors l and r are then chronic products of vectors of length two um each row of m is committed with an element of g1 uh then this vector that's in g to the

square root n is committed as an element of gt and what does an evaluation look like for this and this is where the subtlety you would now even like to say you run one generalist in a product argument to compute a a commitment to l transpose n right why should you think you can do that well because you have commitments to all the rows of m this is a linear combination of the rows of m so you want to compute a commitment to it and that should be some sort of uh generalized inner product argument for the outer encoding right like we've got this commitment in gt for a vector of g1 elements i want to take that vector of g1 elements and multiply by some scalars that are fixed and then you'd like to run a second one technique there's just a regular inner

product arguments that would take this v and say well okay now i'm not going to think of that as an element if you want i'm going to think of that as a commitment to some vector in f and i would like to take the influence of that thing with the vector on the right and that that should if you if you have a an ipa give you a commitment to this y which is what should be l transpose m r and that should be your f value of x now this is cool because like in hydrax this means you only have to commit to square root n like vectors um if you have the generalist in a product argument then you don't even have to sort of send that right they can hire you actually consent you use the trivial commitment

which is sending them sending somebody the data um you know in in bmm tv you get to actually use a two-tape commit um but there is a problem here um and the problem is that at least on the definition that we want to use here of being able to do witness extraction you can't do it um the reason is that so if uh so if you just think about like what the what the witness extraction would normally tell you you would have an adversary there that gets to completely select the problem instance and in particular that means they get to pick x at the same time as they make their commitments to their polynomial f and that's a problem right because if we if we go back go back and look at this if if uh an adversary is selecting x at the same time as they come and tell me a

commitment to f then that means that they can completely control what the vector l is and that means they completely they can guarantee that whatever v ends up being it is independent of most of the entries uh of most of the entries in m right this is sort of so in some sense a really basic thing but it that means that the the approver could prove that they can open this polynomial commitment again and again and again and again again at some point and they would never actually show they knew a polynomial which could be which um which had the commitment they'd given you as a commitment because they could have just made up a bunch of random elements of g1 as they commit as the quote-unquote

commitments to a bunch of the rows and if they've carefully select the point of evaluation you never ask them about a linear combination that really touches those other rows so this this problem sort of technically exists even in high rats if you try and call out a polynomial commitment from it um however and this again goes back to that awkward discussion about how we factor the work here um it doesn't matter in the context of snarks because for all the snarks for r1cs that i've ever seen the point at which you do the evaluation is generated by the random verifier challenges in the course of doing that after protocol right and that means that the whole the whole notion of like needing a full polynomial commitment here is

actually a little stronger than you need you don't need that what you need is something which uh gives you witness extraction under the following protocol i give you a commitment to f you pick some point to evaluate i show you that i can evaluate at that point under the connect and if we run that for many random many random points then you can extract polynomial but this is this is actually not what this is not what you would write down as a polynomial commitment by default right um so yeah there are two solutions here one is say look we don't care we're going to ultimately integrate this thing into a in r1cs for the uh so we're going to integrate this into a snapchat r1cs so just use this this thing don't worry about it we know the point of evaluation is random this is fine it just means that now

every security proof you ever write down is going to have to reference the fact that there's this slightly different definition and the other approach is to say well we have a two to one battery argument it works on the inner products we can still pull it through here and so that means that the verify can always say hey just like give me a commitment right a hiding blinding commitment to uh a evaluation some other random point we'll do the two to one approach on that then we'll witness it and then we'll we'll run the protocol now if the prover can pass that then we can we can show it's it's slightly painful to do but it can be shown that if you can do that then the prover is

basically being forced to uh provide knowledge of essentially the logarithms of the evaluations at random places and if the prover knows not if the proven knows the logs at random places and you're using some kind of short proof that is extractable there then you actually get to get those logarithms so now you actually have the raw evaluation of random points and you interpolate f um what's that actually mean it means that we send we spent a few extra gt's just throwing around doing this two to one version um and there's sort of uh that turns into a square root work for the proverb because they actually have to update their witness factors um the verifier has to do some some extra work in gta now again like this is this is an interesting point like formally super technically

the this is not an order one operation anymore because the verifier has to oh log n extra work in the field why is that well it's because when we go back to these vectors of scalars actually this thing will actually go through slides and speed when we go back to that vector of scalars we have some so the way i've represented it is oh we're going to assume this has a chronic product structure and therefore you compute inner products in in block time um and that's no longer true right when you when you run the batch and you start taking linear combinations of these things but it is still the case that if i've got a batch of only l of these things say then whatever those whatever those vectors are they are some combination of

l vectors each of which has the appropriate chronological product structure so now if i want to take an inner product of that with some other vector that has the relevant structure what i'll actually do is i'll break it out term by term right so we're going to consistently keep these vectors as some some linear combination of this have multiplicative structure um right so yeah now that we have like

an approach there are various i will call them sundry optimizations they are actually important if you if you want to run the scheme at speed and get the kind of performance numbers that we're getting but they're sort of less fundamental so one thing which is quite nice is that actually the inner product argument that uh i was describing with public scalars gives you two generalized enterprises at the same time right it channels tenancy shows you that you've got a v1 and the v2 and the product of b1 with v2 is one thing and the product of v1 with some scale as s2 is the second thing and the product of uh v2 with some scalars s1 and some third thing so we actually get two inner products at the same time um so again what are we actually going to do here is uh we're going to take that second inner

product argument we're actually going to multiply it all by some element of g2 to turn it to a gipa between g2 and f um you have to throw one extra second pro for instance just show you you do know how you can show that approver doesn't know what they're doing here um but if that means that you just get to run this process once you get half the number of rounds basically has to prove sizes and how to verify time um the other thing which again um this is again this is all in the literature right like there's not new to us it uses this work in any way shape or form but at the same time i've not seen it in any library that does this we had to implement it by hand several times um you did so so this is this is one question we definitely have

because we've seen it in the literature too and we want to use it uh oh right well okay so so uh so so i i i have a four complexious that does this at this point i have a um i have a fork of relic i have a relic code that does this i have a fork of blasters that does this uh i would really like just like upstream that's blasters and go home um but uh yeah um [Music] i i don't know like the yeah so so so um i could go into pretty much arbitrary detail about this uh the the the basic the basic trick that's being used here um there are two

um essentially what you're using is the fact that uh okay so just to scope this whole conversation i'm going to assume that we're in the nice standard case where uh six divides your embedding degree where the final extension is by some x to the six minus eta um and yeah i'm just gonna make all those assumptions and those those are true on every reasonable curve that i know about um well that's not quite that like well it's true of all because that anyone's going to use in the next couple years so what you then do is you basically notice that um you know that this this this group gt is um absolute size like p to the four minus p squared plus one um oh sorry specializing to k is twelve

apologies i was specialized k is twelve um you you know that gt is of size p to the four minus p squared plus one um and when you think about what that means that tells you that uh you've got various normal relationships between uh what's going on in fp to 12 and fp36 and between fp to the 12 and fp to the four right i like and those norm conditions are what's actually cutting out gt within um within fb within the multiplicative group of fp to 12. so essentially what you're then doing is you're saying well i know what these norms are supposed to be and that gives me essentially like this projection coordinate chance for them um so the easiest one but the easiest

one to see here is to to just get that first harming um and the way you get that halving is you say well like like i'll pick my favorite sigma that's in um that's in fp to the 12 that isn't in uh fp26 um and then i just consider the map from fp to six up to fp to 12 that takes x and sends it to x plus sigma over x minus sigma and if you just compute what the norm of that guy is um everything drops out so like you know that that's actually sitting on the torus associated with uh with fp6 inside of fp to 12 which is which is nice um but now you've parameterized it with a single element of fp to sex use of half your size um and then you do it again uh it's now

more gnarly because you sort of have to be looking at this pre-image and you have to look at the um you have to look at the fact you've now got a uh some some of those you get you get some norm that looks like uh so messing around with the forgiveness a little bit you you messed around with the fruitiness a little bit you end up with these quadratic constraints um that are associated with being inside gt inside this this pre image um and then you just very explicitly write out all the formulae that are associated with that um and this basically you you get to write down uh you go from sort of uh an element of of gt to saying well

actually i could parameterize that with some element of uh fp six and then you go to say well i could actually parameterize that with with like three elements of fp2 subject for quadratic constraints um and i use the quadratic instrument to get rid of one of them um so i now have two elements about p2 um and you have to do a little bit you have to be a little bit careful to make sure you don't like accidentally do a double cover at this point there's there's irritating work um but it also turns out that in this particular case whereas x is six minus eta you can just write down the formula um it's a quadratic constraint so i'm actually yeah i'm sure we had something with cube root in it uh when you're trying to get the factor of three yeah yeah um yeah so so so um

yeah uh so so it turns out that um you need to use the fact you're on the pre-image right so you know that um like basically you know that uh whatever it is that that if you apply the you know the extra piece of six minus x to the one is going to vanish already right you know that sure right so so now you come along and say well okay now i want to understand like x to the p to four minus x p squared plus one um you know up in the exponent um and you [Music] you actually multiply it out like i really apologize i had to do this like four times just to convince myself that it was working um but there's there's yeah yeah there's a paper right

but basically basically when you multiply that the cubic terms cancel like that's the magic right is that when you expand these things out in terms of the um the fact you've got a an x plus sigma x minus sigma everything's cubic or linear in x cancels right so you only end up with things which are quadratic and right like you you get to say um but you do need to use the fact that you're already applying the other normal condition first um yeah um yeah like and so as a corollary you know when when three divides k again you you play the same game you get this quadratic constraints when you actually look at what that's telling you it tells you this interesting thing which is that you can uh double an element in gt using only three fp2

multiplications um which is quite nice um it's not it's not the hugest optimization in the world but again it's something which um isn't really exposed by many of the intermediate level libraries um this actually turned out to be like one of the pain points associated with implementing this is just like going from uh trying to write a high level high level library and you really want access to certain low-level features that are not in the mid-level libraries by default um because nobody else uses them right now um and then yeah usual tricks um with batch pairings for exponentiations uh at the end of this process verifiers got you know half a dozen channel proofs they need to check and things like this combine more with random scales in the usual way um the the one other thing which again

so on the implementation side was kind of interesting um is there's most of a factor of two available on the prover from being more careful about how you do paper um because the default way you do this would be that you would say but i've got some set of generators they do some pre-computation associated with that um and naively this list of generators is only squarely then long so how much precomputation what am i going to do right back to the end typically but in this context we actually know that we're going to hit that system generated again and again and again so each run of this process involves doing some sort of square root n set of multi exponentiations with respect to the same base points um and so it's it's really worth it for the prover to go and do quite a lot more

work um to pre-compute larger tables for perpendicular and therefore like save a factor too um so yeah like fundamentally we implement like i implemented it there's like 1600 lines of code and four clusters um i think they could i could probably convince them to upstream to work on tour i'm not sure i could convince them to upstream sort of an entire implementation of their interest algorithm um and there's like another 3400 lines of code that actually implements dory um uh and we're just going to compare with uh with spartan which is as i said based on on hydrax underhood um so so here like basically what we see like there's some constant factor slow

down on on the approver uh to do committing which you know when you when you check this is exactly the ratio of the speeds of g1 arithmetic between curve two five five one nine and the blaster's implementation of the ls12381 um when you look at the evaluations there's actually an interesting point here which is that you know you can sort of see what looks like quadratic behavior then becomes linear this linear behavior really is just evaluating the polynomial um so so once we start getting up to large systems you know 2 to 26 2 to 28 um then you actually start to find that the the a dominant cost is actually just doing the polynomial evaluation rather than as it were all the additional crypto work on the top um the thing which is

really interesting for once yes of course is that we change the sizes quite drastically so uh our commitments are to come to polynomial sort of constant size whereas in something like hyrax they grow um and so obviously in a in a stark situation where you expect to be sending one commitment to do a couple of evaluations um yeah you actually find that this this crossover point for sending an evaluation and and opening it up starts shift to the left you actually start to get savings maybe more like you know two to sixteen two to fifty um and then you know on a linear rather long scale obviously the verified performance starts to become quite competitive um so yeah like super super fundamentally if you're if you're using large systems

dorians are being a lot person the other thing which is is interesting actually just a capability that you have in dory that you would not have in something like hyrax um and i don't want to speak for all of the systems but i don't see how you would do it in other systems either is that because the commitments are very small and there is this ability to combine commitments to polynomials linearly you can do batching in an efficient way right so each yeah if i have a batch of l polynomial evaluations i want to do i need to do to to spend the costs that look like this once but then for each additional polynomial i want to find a batch and it doesn't have to be the same polynomial doesn't have the same point of evaluation arbitrary each additional one of those

only giving is only going to cost me an extra one and you just sort of see this right when so this is this is all normalized and n is 2 to the 20 just if we assume one doing about size of one it's one thing and then we just let the batch size roll up if i'm doing if i'm doing 10 polynomial evaluations then the verifier is spending you know thirty percent more time and the proof is spending seventy percent more time like this this actually gets quite cheap um this so uh there's there's some concurrent work that also went out on the archive uh which was uh so that was uh cfos or certain quarks which was the paper title in the end um which was essentially making this point that uh you know once you take something like spartan

you pull out the square root size commitments and you use something like dory instead things start getting quite fast um and there we were finding break even stuff again for like two to fourteen two to fifteen um and they as i said as i mentioned earlier the paper that this is uh just a paper tree nothing and his interns uh but the nova paper that came out last week um is sort of taking this a step further and it's really patching up the r1cs as well um and this this should give some uh some some really quite impressive performance numbers at least on some sort of ammo type spaces um so you know like i guess i i guess it shows up you know close with where i think this might go within the next sort of let's say a year year and a half

um so one thing i would say is like gta is not is not something that people have been messing around with before right when you look at the intermediate libraries they normally give you pairing right sometimes they're really nice they'll give you multi-pairing but even that noise just pairing um so here we actually need to do all our arithmetic in gta you want that to be fast i don't know what the right way to do that but i don't know that i have the most efficient way of doing that in the code we have right now um it is possible that there is some better representation all the arithmetic is still fundamentally done with uh representing gt by fp to 12 star right like it's entirely plausible there are more compact representations either in terms of memory or compute

that would make gt go better um i don't think it's really been studied that intensity yet um the again like the mid-level libraries anyone who's implementing piping will typically say just give me some sequence of generators i'll pre-compute some tables for you well like in this context i really want to be able to tell that library that hey by the way i'm going to be using these generators a lot do more work um because again it's a factor of two for approver um and the verified performance is driven by gt multi-exponentiation not pairing and that's that's also interesting because again just in terms of curve selection i know that all curves have been selected so the pairing is fast right but if we look at if we look at some number like this you know at 2 to the 20 verifies taking 25 milliseconds

of which three or four are in pairing investors gt multi-exponentiation um so if if somebody has some acute curve where the pairing is two or three times more expensive but gt is super fast you might really want to like think about how you could plug that into something like this um and then you know obviously concrete constants are always nice to optimize like bulletproofs initially were six elements of g per ram that came down to two yeah we're kind of doing some very naive things to get six and you know six is tolerable but it would be nicer if it was two um there seemed to be some difficulties there about really guaranteeing that you can extract the commitments um so so if i was to go hog wild and just machine agm and get going then i'm pretty sure i could get two g's uh two gts here but you know

they'll be able to take kgn as an assumption um and then you know again like if you wanna like take this sort of in the direction of doing something like halo and trying to do recursive proof composition you could probably do it right duty ultimately is just more fp arithmetic so if you have a cycle of curves you can do your fp arithmetic you can um you can probably do the pairing as well like at least on paper uh it didn't seem to be that competitive but that's not like really implementing these these uh slightly higher algebraic constructs in constraints is not something that i'm i wouldn't it's not something i would hold myself out to the next but as it is entirely possible to me that there's some clever trick or like the second trick that you could use to implement this

i wouldn't need to do the pairing inside the curve right you only need to do accumulation you probably could probably just do it with gt things right right right um yeah and you know you could probably do that uh and gt isn't actually so bad um because i mean again like if you're being if you're being very naive about it you'd say oh wait it's fp to 12. that drives going to be 144 elements but it's not because it's a polynomial ring so you just do it into the population could be 24 multiplications per the other thing is that when you're in a snark like square roots and cube roots become cheap oh yeah um the other thing of course is that you're

you're going to have to have some hash function inside there which is probably some variety of mimc some some mimc variant or something similar um you know you mentioned square roots keywords i i have a nasty suspicion that there is a much more efficient version of mimc floating around where you take some key routes rather than always keeping every time right yeah it's called rescue but yeah cool okay today i learned um yeah uh yeah there's just this this whole space of ways this could probably plug into an ecosystem of other tools and techniques um that that have not been not been completely exported anyway questions all right so john that was fantastic i

personally learned a lot not just about dory but bulletproofs honestly like you know walking through kind of the fundamentals and expanding the way you did through the through the presentation was great this so this presentation is packed uh with great info for my like kind of logistical question would be is this something that you'd be willing to share with uh with the community of folks and i don't know if you noticed as you were chatting but several folks joined about 10 minutes late and then had to have to pop out at like 10 or 10 15. i mean the presentation of course yeah yeah that would be great so i mean if you're up to you know you can send it to me on a pdf or something i just put it up on slideshare and attach it to the youtube link but um yeah i i thought it

was a great presentation thank you for all the work that you clearly put into it and uh and yeah this is this is very dense thank you thanks dents in a good way i guess are there any other questions sounds like no i i have a quick question um and this is maybe slightly different than i mean this isn't isn't as much of a technical question but you know john and by the way you know for everyone who doesn't know john uh you know this isn't he cryptography is no longer his full-time job so this is like you know he's he he's coming up with all these

great ideas to some in some sense on the side um uh but anyway i guess i'm curious um what you know in your new role and like what you focus on now at uh you know nanotronix is the company uh is that right uh you know do any do you ever do you find yourself you know personally interested in applying like any of these ideas or i guess like how do you how do you marry what you do now with your personal interest in cryptography i guess sure well i mean it's not that's something i've been dealing with for a while right like uh yeah even back when i was a phd student i was supposed to be doing a phd in combinatorics um and i instead ended up spending you know a year and a half proving that the number fields could be could be run uh in the time

that everyone thinks it can be running right this is this is not this is not like your canonical notion of what chocolate artist is supposed to be uh so i've always roamed a little widely um in terms of where this sort of applies over here um there's i guess we're amongst friends here so i can say this this this get away there's there's always a lot of uh less than fully coherent interest from so certain certain sections of industry about you know oh crypto crypto means blockchain blockchain means supply chain something something blockchain watching for this blockchain for that um and you know when i was at microsoft i would often have to experience people of the notion that that this was really something you would want to do

in a lot of contexts um there's a lot of interesting security work um there's a lot of you know really interesting you have to you have to have a reasonably complete model of how uh entire ecosystem is going to plug together in order to be able to save whether something you're proposing to do is going to help or not um that was certainly the experience that i found with with dory right like we like i didn't sort of get up in the morning and go out like maybe i should try and figure out how to structure preserving comments on this that and the others it was much more problematic right we had this problem um you know we were trying to run thousands like we were trying to run on the order of like two to the 35 gates split across a bunch of a bunch of

circuits that gets painful right how do we fix that problem and you know that that turns into a crypto problem in this case and when i'm over here like that turns into sometimes it's security issues sometimes it's figuring out how to make the ai like make some ai go faster it's yeah i find i find myself applying the techniques again and again if not the details of which papers i'm citing cool thanks uh any anybody else have questions i think we just got we got a couple other folks in the room so yeah anyone if you got any questions uh feel free to chime in i think i must be asked my questions yeah thanks alvin i agree

oh and i mean you know usual provisos but you know i i know the expectation is that ultimately this will get open sourced right like this this should end up as just a branch on on spartan at some point um and possibly worst case support blasters um but yeah that's the thing which is always going to happen next month so um okay cool well uh again john this was this was fantastic thank you very much for making the time for us this morning and for being willing to share not only your knowledge but you know but the you know the materials that you put together i really think the community that we represent is going to benefit a lot from

this and uh hope we hope that you know maybe in a future talk i think we're actually having uh straight off next month to talk about quarks okay i mean you're also a co-author of that paper i believe right right yeah as i sort of four-pointed right like quarks you could construe as okay take dory apply it to spartan and then solve all the problems that come when you suddenly find the crypto is no longer the bottleneck yeah so i can i can share that invite with you and if you want to join with turn off that'd be it'd be awesome to get to have both you talking about quarks too uh so that's next month i think april 15th is the day we have scheduled for that but anyway i can share the details with you but this was great thank you very much and really

appreciate your time today um yeah so thank you