zkSummit: Inner Pairing Product Arguments and Applications - Psi Vesely (UC Berkeley)

Transcript

so the basic idea is that if people are familiar with the discrete log okay all right okay so is this happening I think so let's do it okay great so my name is Vasily used a them pronounced today I'm going to be talking about in our pairing product arguments and applications this is from a paper it's on ePrint I don't have a link in the slide I should have added that but it's I'll put one in the trap and it's drink work with Anna Koons Mary malar and Pratyush Mishra there's

been like a few iterations that have kind of come out where we've since introducing this where we've added more stuff to it and so the basic idea is that if people are familiar with the discrete log inner product argument from bullet proofs it's actually from an earlier paper but more people will be familiar with it from bullet proof this is basically like an application of that to the parent setting so this is an overview of our results what we're gonna look at today at least is a statistically sound inner pairing product where you can ver verify the outsource pairings way if you know like source Group one elements in source

Group two elements you can prove that they're interfering product is some public value and we should make a faster be less aggregate signature using that and then we're also gonna cover a trusted inner pairing product argument which allows for aggregation so you have two committed vectors of source group elements and then you show that they're interfering product to some public value and then we show how you can our gate across 16 proofs without cycles of curves using this so more things in the paper that we're not going to cover today are includes a compiler that takes we define the inner product commitment that

it's an argument of knowledge for that inner product so we basically like generalize this whole like in a product protocol and show how if you make a certain type of commitment scheme you can get a inner product argument that is computationally witness extended emulate able basically notched out out of it so yeah and then we have a transparent version of our trusted interfering product we have multi exponentiation and inner pairing product with both trusted and transparent variants and then we build polynomial commands out of these that have like an interesting position kind of in the polynomial commitment trade-off space where they are good if

you want to prove polynomials of super-high degrees and like you don't want a giant see arrest to get a square root CRS with some interesting other sort of asymptotic properties that other polynomial commitment schemes are don't have so presenting like new trade offs depending on your application and that might be interesting so anyway we'll start with sip which is the statistical interfering proof and has application to building faster I read dealer signatures so this top equation is basically what we want to prove we're just showing in like a small example for like the N equals 2 case of kind of how the whole

argument works you have this pairing product we call this like inner pairing product between a vector and the B vector which is supposedly equal to some value Z so the way that we can prove this is that we actually have the provers and these LZ and our values in the equation below it which we see is equal by like the BI linear properties to the single pairing on the left hand side of that equation so then after having the prover commit to these LZ and our values these cross terms we sample a random field element X and then compute this linear combination of

the claim Delvian our values and check it against the single pairing on the left-hand side and then we only have to compute one pairing and then these target group exponentiations to verify this so in the like n equals 2 case it's just faster to compute the parents directly but asymptotically this argument becomes faster to verify them to do the direct computation so the way that we build it larger is basically we repeat the same process many times so you have n being some power of two and then you have log

n rounds where in each each case the like instance like a and E the two vectors of source group elements are cut in half and then you delay the sort of final verification check until you get to N equals 1 and then a is just a single group element B is a single group element and Z is again the target element and you check this so kind of the security holds like recursively where if oh if the N equals 1 case holds then we know with you know overwhelming probability that n equals 2 case holds

MN N equals 4 and so on so here you have the left and right values instead of like you know just a are being just like a 2 here you haven't beat a whole right half of like the vector so this is like up this is from like element and prime up to n basically and similarly for BL and so you send these you have the verifier sample a challenge send it back you have both approver and verifier update the a prime and B prime values this is the like Hadamard product so you have like the first element of the left

half with the group operation added to the earlier Beck operation with the first element of the right-half raised to the X power and so a prime is half the length of a and B prime South length of B and you know you keep doing this recursively where you recurse on a equals a prime B equals B prime Z equals Z prime until you get to N equals 1 then you do this final check and so that's basically how the full argument works for Christmas lis so we observe that like this is actually an observation that first made in the blue cruz paper where the final a has

this form of like being a multi exponentiation in the original a values where these si exponents are linear combinations of the are equals log 2n challenges in the log log 2n rounds this protocol has and basically with pictures algorithm you can compute this and o n log n time whereas computing the parents directly there's not like a asymptotic win like this you can compute the Miller loops individually in a single final

exponentiation but is the constant speed up versus this asymptotic speed-up so because this multi exponentiation dominates the verifiers work the actual result is like when you benchmark this it looks like you're getting o n log n time I put some linear in quotes because it's technically not sub linear you're still doing a linear number of field additions and you have to read the full input and whatnot but it's almost like when you look at the benchmarks it looks like we're getting this o n log n speed up so basically this becomes faster at

to the 70 equals 128 pairings this is when the verification time and becomes less than the direct computation of the pairing product and the difference is growing log rhythmically as we expect the direct product versus verifier time so for about million pairings we see that it's about 11 times faster okay we're gonna show how to build a faster VLSI grit signature now with this BOS signature scheme is really simple we'll review it just really briefly you sample a secret key from the field your public key is

just some fix generator tree that secret key to sign a message em you take your secret key and all you do is hash em and then you this is the hash to field or sorry it's a hash two group and the group element that this gets hashed sure you raise to your secret key to make your signature Sigma to verify this you have a public key of someone a message and a signature and you basically check this equation which just relies on the bilinear properties where since this should be G to the SK if you think I'm just moving this exponent SK over here to hash of M that's what Sigma should be

so this check if it checks out then the signature is considered valid if you have a whole bunch of these basically we could do this directly but instead we get a benefit if we take advantage of batch verification where we reduce instead of having to check to in pairings we have to check n plus 1 so this is how you would do it if you just got all the signatures and public keys and messages individually you would compute this Sigma is equal to big Sigma equals a little Sigma 2 these are powers where R is just some random exponent

you've chosen so you're basically just taking a linear combination of and then you know seeing if all the equations check out at once and so we sort of prove this equation instead we have the approver commit to like a and r2 well to all the public key in hashes and then samplin are you know can do this non directively with premier and then have them then send Z and then you basically run sip on this and that's what you give you end up getting Sigma

the public keys and the messages to the verifier and then they run the SIP a verifier on the sip proof and this instance and yeah just note that when you do this sort of random linear combination of the messages you're protected against rogue key tax and you get bad verification on screen which is a different security property like past signatures have gotten screening like bgl so3 is the maybe the most well-known like aggregate signature based on vos

and we also just know that it's cheap to roll the are exponentiations into the severe fire basically you just have this the same si but you have plus R to the I here and so you can roll this into the final both you exponentiate in for the verifier okay so next we're going to talk about tip which is a trusted inner parent product argument allows you to compute again the inner parent product between committed vectors of group elements so if you think about it we're just trying to prove we know some source

group elements which satisfy like some equation generally batch verification equation that's how we like you know prove we need to make it into a single equation to check like a whole bunch of proofs or in this case to with 16 when we have 8 them to prove that we know a bunch of cross 16 proofs that satisfy this batch verification equation so this is what the relation for tip looks like basically this T is the commitment to the source group 1 elements which is just the pairing inner product of a and V for a there's a transparent commitment where you can just sample the uniformly

random sort of from the group and then this becomes part of the commitment key or the con referent string for our argument and similarly for BMW we commit to it with these W elements and this is this was proven secure and this AFGE h0 16 paper as a commitment scheme we wish that we could make a more efficient argument by having a commitment where we can commit to and be together but unfortunately anytime that you output source group elements in both group 1 and group 2 and a commitment you can't you can't combine them like this it'll never be binding so we have to keep them

separate and effectively with each of these commitments we we shrink them in the same way that we do a sip see if you can think of as being like the identity commitment so we'll show just for like tea you know you send these teo and TR values the verifier samples of X and sends it to the prover then the prover updates its witness a prime the verifier updates T Prime and the proven verify are both update the commitment key this is in the untrusted version at least and the transparent setup version like so and then basically you do this

recursively until you get and in you check the pairing of the final a a single group one element with the final V a single group two element is equal to the final T pranam you know which is is values are computed over log n rounds and basically you independently do this you have a ul you are here ZL z R and so on so we we wanted to get something that was better than like hip injures this like sub linear in quotes time so the way we did we went about doing this is

we realize that we could structure instead of having W and V you just uniformly random commitment keys we can structure them with a trusted set up such that the final W and V values that we ultimately use in the decision procedure we use here after recursions done in the N equals 1 case can be expressed as KC g10 polynomial commitments and specifically polynomial commitments to a long time a valuable halo polynomials like a form that was recognized in the halo paper and so what we do is have the prove or provide evaluation proofs for these committed

polynomials at random points to prove the final V and W were computed correctly so this is kind of what that looks like the setup takes a secret this is the trapdoor the alpha and beta values then it commits there then it computes W as these even powers of alpha and of G to even powers alpha and V as beta to be as H to even powers of beta and the reason we have to do these like even powers is that as part of the polynomial commitment verification

equation we need to give these H alpha ng the beta values and given these the prover could break the binding of the commitment scheme if if we gave all the powers instead of just even once so this is a way to get around this so just to refresh how the prove it computes the the final value you know it does this log n times yet ki final and basically what this looks like is now we have H values here we have this polynomial which is a long time

evaluatable these X values are the challenges so you have log and Ilocos log n challenges and this X is the indeterminate for V final it's in the beta and this is like basically exactly a kg g10 polynomial commitment so the way that the protocol works now is that P sends the final V the prover sends the final a V value to the verifier instead of having the bear fire computed itself with a multi exponentiation using temperatures and now to confirm that's right what the verifier does is that samples a challenge see it sends it to the prover and it evaluates it makes an

evaluation of this halo polynomial and long time then the prover sends an evaluation proof for the commitment V at point Z and the verifier checks the proof is valid with respect to Y and V if though then the verifier uses being the decision procedure to check this where it also computes of course the T final and long time like this and then you know you the same thing for the final W value and then of course the final tu and Z values can be computed all in long time the same way and the

approver sends the final aim B and if this all checks out then the verified so argument um so this is how we can use it to aggregate bruh sixteen proofs just to refresh we're not gonna obviously the jallat here we are not gonna go over but instances are this vector field almonds about field elements proofs are to group one elements and one group two element when you want to batch verify these you basically you get checked this equation which is some like efficient way to batch verify so what we do is we have the prover commit to the to the a and B

vectors and then this meeting will end in ten minutes sorry zoom notification okay and then send them to V and then what he does is it samples a challenge are insensate to verifier samples of challenge are and since it's the proofer and then the prover sends Z which is this left-hand so it sends the inter pairing product of a two like each of these a value scaled by the appropriate even power of of our

and so then we have these tu and Z and the proven verifier engage in the tip protocol with instance to Z with small changes basically the prover resets the value V so we make this observation that cook the commitment scheme has this property where if T is a commitment to a under the commitment key V then T is the commitment to aid a to the these powers of R or under the commitment key V to these negative these empowers of R so we just have the prove a reset V to be these negative powers perceives as normal and now the halo polynomial looks

like this it's like the exact except you have this like our inverse value next to the indeterminate and so after sending Z to the prover the verifier just reset Z as Z 2 R minus 1 and then checks the polynomial commitments with that reset vegan computes the that does the Hale polynomial evaluation with this reset Z and this all checks out so kind of just concluding we can compare inner product arguments to use of snarks so you think in inner product arguments are basically a specialized efficient form for for like in our case

of pairing languages the ones that we built so they're more efficient for this really specific thing but they can't prove everything some benefits are them of them are that we can do like proof aggregation without cycles or chains there is one other system that does that fractal but it's not as efficient as most starts and these inner product agreements have strictly linear provers with small constants whereas snarks are usually quasi linear and conversion to our one CS is like essentially a huge constant and yeah so snarks on the other hand have succinct proofs and verifiers

whereas the best we get is log proofs and log verifiers but they don't have to be just compared to compared against each other they can be combined and used together so if you want to prove like something with a snark that involves like a huge pairing computation then what you can do is first prove that with one of these like tip or something and then you can prove satisfaction of the kippah verifier circuit inside the snark and so now you have like a log size pairing computation basically to do in the snark versus the original

and that way in like proved or constrained environments or where you're just trying to prove really huge computations this effectively allows you to sort of prove more with the same compute resource and also may make it possible for some applications to where where you have to do incremental proving and you might do otherwise do like cycles like recursive compositions of snarks to use tip or whatever first and then you just need one snark because tip getting the log size verification reduction is enough to prove even really huge amounts of of data are like really

huge pairings make proofs about really large amounts of authenticated data without meaning full recursion and just having one layer being enough and there's a lot of benefits of using to chains which were introduced like as in the for applications at least and sexy so anyway thanks and I guess I'll open up for questions now just be a little careful cuz I think you only have five minutes they're left before it boots you out okay sure I'm digging into the details this is the best I can also like

shy share another I guess I have to like end this meeting maybe to make a new one and share another link to for like further discussion I mean I do have four and a half minutes still for questions but I can like make a new zoom chat if there's like more you know and the next should talk I guess can start or whatever if yeah I think actually just I was just talking to Dave and he's into it so I actually wanted to ask the audience here you still want to do it we could actually do our last talk and then the only person we won't have covered is Michael and I'm so sorry

about that if you're still there we can probably find a way to work you into another maybe a study Club or something like that because you're a session and first I got kind of cut off look it might be a way for me to add the video but anyway this is like a side note why don't we use this time for questions for this talk and then we'll do our next one are there any questions this like inner product or a pair as if argument require Piven jurors I'm mister or do they complete a boy Pippen juice the tip setup one mhm yeah it avoids it I'm

gonna go back to sharing my screen okay I think is actually quite difficult to do that I have to use or kazoom won't work with Weiland and this was I guess what's in my Linux config files I don't use these anymore okay

so yeah so basically normally you would use Pippen jurors to compute this final a in a tip it's actually the final fee that you would compute this way so what happens is that instead of having to compute the final commitment key with a multi exponentiation which we can speed up using Pippen jurors we instead don't have the verifier compute anything these instead the prover sends v-final directly to the verifier and we observe

that when we structure the commitment scheme so that the commitment key is these powers of like in of beta h to these even powers of beta that the final becomes this value here basically which is a kzg 10 polynomial commitment to this polynomial so which you know we called the halo polynomial and can be evaluated in long time and so because

the verifier can compute the evaluation of this polynomial for a random chosen point in a long time this will only hold you know with with it's only with negligible probability that the prover will be able to provide a correct opening for the point Z which where the evaluation is why you know if the final is not actually you know this h2 this polynomial evaluated at beta that makes sense

Thanks yeah so and then again these small X's are the login challenges that we have in the logarithmic number of rounds and then yeah the big X is indeterminate good question yeah thank you you