fflonk: a Fast-Fourier inspired verifier efficient version of PlonK [Ariel Gabizon, Aztec]

Transcript

hello everyone welcome to this week's edition of zk study club this week we're really excited to welcome back uh arielle gabazon who's going to be presenting his work on uh ff f flank i'm not actually sure how what's the canonical way to say it but i'll maybe let arielle say it in a minute but anyway he's here to present new work on opening many polynomials using the fast fourier equation uh work that he co-authored with zach williamson so again really happy to have you here and uh ariel over to you thanks uh yeah i guess just flank is is is fine uh i probably should have asked about that but yeah no no it's long f okay i guess i guess a slightly longer flank

uh yeah uh it doesn't matter too much uh yeah so thanks for coming uh these slides are pretty fresh from the oven so if there are no very embarrassing type god exists uh yeah so um to get started wait i got uh oh and by the way please if you have questions please just uh just ask like with your voice because it's always hard on zoom to find the chat and then you find it it's not a question it's just a discussion so yeah so please if you have a question please

just ask uh right let me just move these zoom controls out of the way uh all right so yeah the motivation for this uh our work on this uh was um basically save gas on ethereum so uh the recent snarks we have which are what people call the polynomial iop based i mean several papers kind of made almost equivalent terms we called it polynomial protocol in planck but it polynomial iop is what people have been using uh so basically the verification cost is usually two pairings and some number

t of uh scalar multiplications now how expensive say on ethereum is a g1 scalar multiplication well it's 6 000 gas that's roughly 5 right now so say you're you know you have some layer 2 and you're doing some proof on the main chain every half hour so that's gonna be like seven seventy seven thousand dollars uh per year per scalar multiplication so this is what uh what gives motivation to to minimize here's someone exactly zach just joined

yeah sorry no problem good to have you here uh so right so that's going to be a roughly 77 000 per scaler multiplication per year uh if you want to do a proof every half hour uh so this gives a lot of motivation to really uh bring this number this number down and the sort of the bottom line of our work for planck is that this number of scalar multiplication goes down from 16 to five uh yeah with with the cost of tripling uh proving approval time so uh this is really good for the sort of

if you're doing some recursive proof with many layers this is really good for that final layer of what goes on chain all right so uh yeah please ask questions because i'm i'm going to assume uh some level of familiarity here but so please interrupt me with questions but uh as as we as we know snark verification in these polynomial appease this to opening a polynomial commitment scheme uh so that's what we're going to concentrate on and uh yeah let me just give a reminder on the the kzg

polynomial commitment scheme that we all know and love um commitment scheme probably for the 50th time for most of you so uh it's uh the prover sends some short commitment to a polynomial uh later the verifier chooses some value s in the field and uh and then the prover sends sends the value f of s uh or you know sometimes we can think of that value being known in advance uh or being sent before uh doesn't matter too much but then the important thing is that the

prover sends a proof that really yes z is f s for the f i had in mind uh during commitment time i'm not changing my polynomial after you you chose s and of course the the really the really cool thing about kzg is that it gives us polynomial commitment schemes where these commitments and openings are only 32 bytes or if you're more number field see paranoid maybe 48 bytes uh so let's really quickly remind ourselves what what the kzg scheme looks

like and uh yeah let's just use this notation that x in in brackets is uh just x times g for some you know public randomly chosen generator g uh of the of an elliptic curve group right or like the first right the g1 the first source group of some elliptic curve with uh with a pairing right so with this notation let's quickly remind ourselves of kzg so we we have some setup where for a secret x we uh we have the encodings of the powers of x and now what what is the commitment to a

polynomial f it is just the encoding of f at this secret x uh and of course right the point is that since uh that this is this is just gonna be a linear combination of srs elements so we can we can compute this without knowing x just from the what we got from the setup and uh right in the opening this is the the main part so how do i i want to prove uh that uh what is the correct value f of s so right in the important point this divisibility thing that we're using all

over the place that um well suppose if i look at the polynomial f of x minus f of s so obviously this polynomial is going to be 0 at s and therefore it's going to be divisible by x minus s so therefore this this rational expression f of x minus f of s divided by x minus s it's not just a rational function it's an actual uh polynomial and uh and so we can we can compute the prover can compute it and uh

and and this this will be this will be the opening proof right the the encoding of this polynomial h and now well so so how how does the the the verification work say i want to check that z is really f s so uh basically i i'm just using the pairing to check that really h is is of this form which which will correspond to to you know is the commitment minus z uh encoded is it the same as the pairing of of of pi and the encoding of x minus s

right this is this pairing thing right it's just checking that really if i multiply you know the denominator in this equation i defined x that really f of x minus f of s is equal to h of x times x minus s uh right so this is the kcg scheme and uh you know using this algebraic group model that makes our life very easy uh we can we can actually prove this is sound and uh the prover can't cheat if uh if if some if z is not f of s uh so yeah so everything good so far [Music] yeah this is great so ariel just one

quick note there's a couple spots where you're cutting out a little bit it's only happened a couple times but i just wanted to give you a heads up on that i'll let you know if it gets too much worse but i think we're fine to continue but yeah yeah let me know so i'm in this room where it's quieter but maybe the internet yeah so let me it's yeah it's if if it becomes problematic i will let you know but i think it's probably fine for now but that's right i i can i can move to a room where the internet is better but there's like a no actually let me let me move there's like a five percent chance it'll be noisier but uh let me just move okay cool yeah yeah i see the i see i

see the bars going up so that's probably a good sign the future viewers of uh of this youtube video will thank you so when you're explaining like the key thing of the vlog scheme they're gonna be like oh i i missed i missed it so no it's yeah thanks yeah yeah and like in the the crucial point is that yeah exactly all right that sounds that's it sounds a lot better so all right yeah i see now i see all the bars now okay uh right so uh [Music] all right so okay so that was the basic kzg scheme and now right uh

why right what what what makes us have a certain a lot of scalar multiplications in these snarks it usually has to do with the fact that we're not just opening one polynomial uh we're open we're opening many polynomials so let's let's now look a little at this problem of opening many polynomials uh say for simplicity at just all at the same point s uh for this talk uh so right so we're thinking of a scenario where we have now these polynomials f 0 to f d minus 1 and we have the alleged evaluations z 0 to z d minus 1.

and now the verifier has uh commitments to these polynomials and uh and wants to check that all these z's are correct so right so what is the naive solution well let's just use this kzg scheme for each fi and what will be the the cost of that uh well we're going to have a proof of length d because every uh polynomial will have some opening proof and we're going to have uh d d pairings to to check these proofs or i guess

the 100 that you think it'll be 2d pairings because each kzg check is is two pairings uh right so that's the super naive thing and the less the less naive thing that has been used very a lot uh in these last few years is this following scheme for batch opening so here the verifier will send some random gamma uh and now the the prover will compute this random combination of the polynomials

so so f is now the combination the polynomial that is some gamma to the i f i and now the point is the the verifier can independently uh compute a commitment to f right because k c g is is additive uh as similarly as some gamma to the i c m i and and now the uh the proven verifier can uh run kzg kzg just once to check if uh [Music] f of s is equal to z for z that is the

the analogous uh random combination some gamma to the izi and you can easily prove in the algebraic group model that if if any of of uh of these values zi was not the correct uh value then uh the approver will uh the verifier will reject with with very high probability and now again in our context the question the main question is well what is the verifier cost here and the verifier cost here is the d minus one scalar multiplications why because

in this commitment in this phase of computing the commitment to f uh the the verifier needs to take this this random combination of the the commitments of the fis [Music] any any is that clear so far [Music] any questions i'll be watching the chat and i'll vocalize anything that comes through but yeah i think everyone's good so far okay great yeah yeah like i said i i personally prefer just uh audio questions uh

because i uh unless that interferes with their recording too much okay yeah so i yeah please feel free to just ask uh anyway the punch line of this work is that we can get rid of this of this d uh not uh we can get or more more precisely we can get rid of this this dependence on d when the opening point s is a d power uh and and uh so one important tool for

uh for our work uh is this uh this little this theorem from uh this work uh with uh drake and and and fish that uh uh uh he is evolved into this paper called a halo infinite uh that says basically if uh say we want to open a polynomial f at uh uh it's some d points so one polynomial at many points uh the result also works for many polynomials but for simplicity let's say one polynomial so the important so we can do it with two verifier scalar multiplications

so when we open one polynomial at many points we can do it in a way that the number of verifiers scalar multiplications does not grow with the number of points [Music] so naturally this suggests the following route uh so if we can reduce opening many polynomials at some point s which is what our goal is to um opening one polynomial at many points then we can use this this bdfg theorem to

to get our desired result which again is being able to open many polynomials uh without the verifier group operations cost depending on the number of polynomials so uh if we'll have time i'll go back to bdfg and so show you how how that this component we're using works uh but let's you know without much to do

let me show you the main uh idea of this uh this work flunk uh which is to reduce opening many polynomials to opening one using the the well-known fft identity so let's for simplicity let's think of just having two polynomials f0 and f1 and say that their values at s are a and b and uh and we want to convince so we want to convince the the verifier of this sort of by opening only one polynomial so let's let's make a first uh first

attempt uh let's say we try to only open the sum so we define uh capital f to be the polynomial f zero plus f one uh and you know no note that if if the verifier had commitments to f0 and f1 you can compute the commitment to f uh by just a elliptic curve addition which is of course much cheaper than the scale scale multiplication so suppose we did that and now we used kzg to prove that uh f of s

is equal to a plus b so is this good um well obviously it's not this is not good enough because it doesn't constrain a and b individually right for any a prime i could take a prime and then c minus a prime is my b prime and if this is this is my verification procedure uh also a prime b prime will will pass the procedure uh so i need sort of a way of generating two independent linear constraints

on a on these values a and b without resorting to using two polynomials so the solution is to to use the fft equation in reverse direction so we'll define now this capital f to be the polynomial

f zero of x squared plus x times f one of x squared uh right so reverse direction because usually we we start from f and uh decompose it down to this fc or an f1 and here we're doing the the other thing and to uh to commit to f0 and f1 we will just send the kcg commitment to this capital f and now let's assume our

opening point s is a is a square so to open f zero s or to sort of verify f zero of s and f one of s we will open f at the the points t and the minus t now uh so why does this work uh well again the the point is uh uh [Music] just that um so so let's let's see let's see what what what we get say uh so f f zero uh oh sorry there's

um [Music] sorry let me make a slight a slight correction here um you might be actually making this correction but there's a question in the chat uh why is it not s t equals s squared or s squared equals t so i think why is it not squared i think they're asking why is it not s squared equals t uh so s is the point where

uh where i want to open where i want to open uh f0 and f1 [Music] i'm assuming it's a square and and it's root and so it has a root t got it um okay i'm assuming that answer your question if not just chime into the chat uh yeah sorry one more second okay yeah i just fixed

some confusing typos uh right so so so why does this work well right f of t uh right is f zero of t squared which is f zero of s plus t times f1 of t squared which is again uh just s right so this is if we call of zero of s and f1 of s a and b so this is a plus t b and now f of minus t it's again because of the squares f zero of s minus t times f one of s of one of minus t squared which is f one of s

which is a minus tb so [Music] the point is that when if we verify uh that b0 and b1 are correct it imposes two linear constraints on a and b and and so it it proves that a and b are correct or to be more precise like what will the verifier do the verifier will the prover claims these are the right values a and b of f f0 at s and f1 it has so using these

a and b the verifier will compute a unique b0 and b1 that um from these equations and now uh the verifier will check use it using the openings of capital f that b0 the the unique b0 and b1 they derived from the alleged a and b if values and b are are correct so so let me maybe uh pause here for a half a minute to see if there's questions because this is really the the central the central thing

[Music] maybe i will look at the chat maybe we could see this actually so guillermo just wrote i guess the tldr is that b o and b one are the injective functions of a b yeah yeah exactly camera you also could have said that actually but you know i'm gonna break my anon uh voice or whatever true yeah okay thanks yeah yeah you can you can use the chat if you

prefer uh also uh right so yeah that's the basic idea [Music] um arielle do you know if there's any questions that you would kind of expect people to ask around this were there things that you [Music] yeah that you were thinking of when you did it um well there are there are some uh questions that come to mind uh when you see this uh that i'll that i'll get to soon like one i mean what one question is why

instead of opening many polynomials maybe change your your snark to use less polynomials and the the answer there briefly is that that does almost work as well uh but uh it creates an even higher uh prover cost to by a significant factor to to achieve the the same result um but anyway um sorry so uh

that that you can see in in the paper it's sort of the the natural the natural uh generalization um [Music] and an important point is right we want to use this for snarks and um and the point is that polynomial iot based snarks they usually work uh work fine with a polynomial commitment scheme that can only open uh these powers for for some for some small d hey sorry

arielle i don't know if um i think you're just the beginning of your sentence when you just said this at least for me i didn't i didn't capture it uh i think your your audio dropped off for a moment there sorry to do that but do you mind actually just sharing again what you just said about this slide yeah so so two again two points uh one is that a sort of a straightforward generalization of this allows you to open uh d polynomials uh at any point that is a a is a deep power so here we're opening we open two polynomials using one polynomial if you want to open d polynomials at some point

s using also just one polynomial you you can do it using a point that is a d power and the second thing is that well we want to use this for snarks and now we have a polynomial commitment scheme where we can only open points that are deep powers and [Music] uh mo like usually at least plonk we saw that it can it can easily be sort of massaged so that your opening points are are always uh deep powers cool

cool um okay so uh so now um i want to so that that that was really again that was the main sort of that that was the central sort of this is that was the central thing in the paper uh so again please ask if something that was not 100 clear uh but now i i want to explain a little about this this component we use which is okay so how do you cheaply open one polynomial at d points right because we reduce to this so

we need to do this cheaply so right so here we're in a situation where uh we have a commitment to one polynomial f and we have these d points s zero to s d minus one and we have the alleged values of f at all these d points call them z zero to z d minus one so how do we how do we open how do we verify all these values cheaply so let's define a polynomial r of degrees smaller than d that agrees with f

on all these points so r of s i is going to be z ir and now let's define the polynomial z which is uh the zero polynomial of this set of evaluation points and the the important point is that uh z divides f minus r right because

uh it at all of these points s i you you'll have f of s i minus r of s i which is zero uh so f minus r will divide x minus s i and so it will divide z which is the product of of these terms so [Music] okay so so that this this suggests the the following thing that in fact was in the original kzg paper that okay so let's

similarly to standard kzg let's now compute this quotient f of x minus r of x divided by z of x and let and call this h this quotient h and let the prover send uh the encoding of h and uh [Music] sorry i think a line here uh got got cut from the uh important line got cut from the uh well that's this is what study club's

all about it's proofing yeah yeah uh should it should appear now uh looks the same i think do you have to refresh it it's yeah just the compilation takes ah there we go right so so the prover sense sends the encoding of h and uh and now the verifier can can check that

sort of check that really you know z times h is really f minus r which right in the in the pairing it corresponds to uh the commitment the original commitment to f minus this commitment to r uh the parent of that with one is going to be the same as the pairing of pi with the um the encoding in the second group of z but of course this is uh this is pretty expensive for the verifier because uh they need to compute this commitment uh to r

which is going to be d uh g1 scalar multiplications and also uh this encoding z of x in the in the second group second source loop where we know of course operations are are more expensive so this this is going to be pretty expensive for the verifier and sort of what happens in bdfg is we that we trade uh we trade these these scalar multiplications for an extra group element in the proof so how do we do this well well the the verifier chooses a random alpha

in sense the prover uh and and now we look at the polynomial so sort of these these polynomials that uh before the verifier had to encode them in g1 and g2 we we sort of just randomly fixed them and so we look at this polynomial l of x which is equal to to f of x minus our alpha minus z alpha times h of x and so right so we this this uh so we know right before these these uh

x's change change to alpha we knew that this was just a polynomial identity this was just supposed to be identically zero so when we fix r and z to alpha and and and so so we know that l l of x should be zero at alpha right because if we set we also put an alpha in f and h uh that it's just this this is zero this identity evaluated at alpha so it's always zero so um so so anyway l of x should be zero at alpha and uh and and also the the the important point is that

computing the commitment to to l the verifier can do with only two uh scalar multiplications right the commitment of l is just the original commitment to f uh minus uh r of alpha encoded in the first group minus uh z of the the pi uh multiplied by z of alpha right so you have you have your two scalar multiplications so so the verifier can compute c c m of l um with only two scalar multiplications and and now uh sort of our original claim about uh all these evaluations of

f uh right just to remind you sort of our original claim was that uh at the all the values 0 to zd minus 1 are really the values uh of f at the points s 0 to s s d minus 1. so our original claim for this random reduction it it now reduces to just checking that l is uh zero at alpha uh so now basically the the prover and verifier just just are just doing a kzg check that l of alpha is zero on one polynomial at one point [Music]

so so yes so we've only in total needed needed two uh two scalar multiplications all right so any any more questions about this or about the thing before uh looks like still no questions so yep cool uh all right so uh yeah i i want to i want to end by uh addressing a question that uh yeah like

like i sort of mentioned before it it uh it comes to mind uh when seeing this work uh which is um can you write everything we did we wanted to reduce everything to one polynomial so we'll have less scalar multiplications can you just reduce the number of sort of to less polynomials without this thing by just in advance having the snark use use less less polynomials and uh in fact uh there's these these very nice

there's these very nice slides of to exemplify these there's very nice slides of dumb down bonnet and in his version of plonk he really he really does uh something like this so uh for for example um right if and if people are familiar with plunk you'll you'll know that we have usually we have these three polynomials uh f l f r f o where uh where f l is like the um the left uh the left wires the right wires the output wires and we have them in three separate polynomials so you could say

well why so if you want less polynomials why not just uh you know encode all your all these uh all these values in in one polynomial of degree three n instead of three polynomials of of degree n and yeah and really here these are very nice slides uh he he does something like this uh the sort of the the cat this this works almost as well when you when you compile it into into plonk in terms of verifier complexity except the small caveat which i'll show in a second uh but basically the but you pay uh you pay much more in the in the prover because the degrees of

your equations blow up much more and uh to exemplify this let me let me briefly show you show you show you this sort of directly on the on the flank paper and at the same time give you a little uh show you how how we we really use this scheme to get our final snark uh verifier efficient snark and uh if you're familiar with with plonk it'll it'll it looks almost the same but i'll sort of highlight the uh the differences uh so so right so so and at the same time i will i will sort of explain again

exemplify the uh the disadvantage of just directly using less polynomials so so right so here here we go actually ariel i'm yeah there's there are actually a couple questions excellent uh excellent in this context where they were asked um so i think if you go back it's yeah so okay so i might have to have you rewind a little bit here so back to your original slides on the last slide i think simon in the in the in the yeah check out simon's do you have a chat up or i can go and read it yeah so that we have it for the video actually yeah that's right yeah the people can't okay so i see from simon uh

commitments corresponds to evaluation at x using the trusted setup and pi is an evaluation at another point so maybe simon can say what pie he was uh referring to exactly i'm not totally sure i think yeah i think it was the last slot the last of your slides but simon you can chime in on the chat if that's right uh yeah i'm just trying to get back to the my slides i believe it's in the it's a commitment

to h of x uh wait is this from simon uh maybe you're referring something else simon if you are there do you do you mind maybe just weighing in you're muted right now yeah sorry i was referring to this equation the commitment of l is equal to the commitment of f yeah and pi is the proof so it corresponds to the opening of h and to me it was kind of an evaluation at another point

but maybe i'm wrong uh so h yeah i mean h is the evaluation of this quotient at the secret srs x [Music] okay i think i'm mixing everything but yeah at the end you this polynomial h you evaluate it at the same x okay uh yeah i mean at the end we sort of uh

so yeah like we we know that this l when when if there were x's here that this should be just identically zero uh and it means that this l if we evaluate it at alpha it should yeah it should also be zero is it clearer or is it yeah it's clear i think it was just mixing the s that is needed to do this evaluation of the polynomial from the yeah on the excel numbers okay thanks cool um cool

yeah so yeah so there's there's still a couple other i think k i don't know if you ever had your question answered so k asks does that require an srs of size three and i actually don't know where that was back it's okay if you want to clarify where where that was referring to um that would be great and then also just oh and dan's slides uh i think going back to dance slides also um i am happy to read the chat but it might be easier if people just like pipe in if they you know if they if they want to ask the question directly because i'm trying to infer context um from that i may not have so i'm happy to read the slides but um or read the questions but if you guys want to chime in don't be

shy so yeah back in back in dan slides um doesn't that require an srs of size three n so uh if you the plunk the the dan bonnet plonk slides i think he's referring to yeah the way by the way to get to these slides if i mean maybe someone can write the actual link but if you go to his 20 20 21 fall course uh syllabus and then it's it's it's there in one of the lectures um yeah and by the way about about uh k's which i i'm a question uh so

i think if i understand correctly the the question yeah basically every time i like uh these the degree blow ups they yeah you suffer from them both in in you'll suffer through both improver computation and in um in srs size um yeah so so so basically here right if we look at the the the font version of plonk how does the the high level protocol uh go so that the one sort of difference main difference from um uh yeah uh

yeah but about this work by the way with uh with the vectors i have i have to say i didn't understand it fully uh but it seems the bottom line is that still they're verified the number of scale multiplications there they they get it to 12 with and and here we get it down to five so um yeah which work are you referring to is it the one oh yeah this is someone put in the chat it's um it's i think it's called vc proof v o proof yeah yeah yeah v o v i think v o proof i think it's gonna be maybe they changed it at least the link here says that but we can add this link

also in the video if vector oracles we can add this link to watching can actually follow along yeah actually maybe that's a good talk for a study club because i i never understood it fully and uh would be nice maybe to have a talk uh it'll save me some time because i feel maybe there's a trick or two there that i i didn't fully understand yet um yeah so so the main difference uh [Music] between sort of the high level protocol here in plank is that uh in plunk we have sort of the round at the end we sent this quotient which is sort of a random combination of of different quotients of the different

equations um but sort of when we're really trying to shoot for best verifier efficiency this extra round like basically we're gonna pay for rounds like like because every round of the protocol we're just going to send this one commitment to all the polynomials of that round like that you know this capital f had committed to f0 and f1 like we saw so we really want to minimize the num and we're going to have a scalar multiplication per per one of these polynomials of it uh so so we really want to minimize the number of rams so so this is why uh here as you see in in this font protocol we send actually a few a few quotients

like we sent here one quotient that sort of proves the uh arithmetic equation and then in the uh in the subsequent rounds we will send two other quotients that um sort of verify the permutation as opposed to original clock rules we just send sort of a randomized one randomized t uh because again that cost us another round because before we send the one randomized quotient the verifier needs to send us some alpha to allow to combine them and and sort of right now here i want to exemplify the so you could say okay you want less polynomials so sort of like in in why not instead of fl o have one f that

includes all the three and values and you could say the same thing of the selectors right why instead of having these five selectors uh why not just have one q of degree five and that and so you could do that but then what you'll pay improver complexity will be very high because then right so now so really in plank you have um you have sort of eight selectors because you have the permutation selectors and these sort of these q's so so you'll have suddenly an equation where yeah where this q will be of degree eight n and now this f will be of degree three n so this this this equation degree you know you've you've got it up to 11 n

um and uh sort of that that that'll sort of mean you're when you these quotients you'll you'll need to compute the similarly their degree will uh will blow will blow up um yeah so so that that was that was mostly what i wanted to say um awesome um anybody else have uh any questions yeah and these uh to the question yeah

these are these are exactly the the slides in the chat are are the ones i was referring to okay awesome well um thanks very much for uh for sharing this work um arielle and uh if no one else has any questions we can uh we can call it and uh and yeah thanks again for coming on zk study club