zkSummit5: PLONK without FFTs - Justin Drake (EF)

Transcript

all right well welcome to the next session we're here with Justin Drake and he's gonna be talking about plunk without FFTs please let us know if you can hear us just in the side chat testing testing you can see us if you can hear us they seem to be here hey there we go very good okay so Justin do you want to take it away yeah sure thank you okay so I'm going to talk about a clock without FFTs so basically trying to do plunk you know starting from the lagravis and

ending in the language base is without having to do these these basis changes and you know I'm going to introduce some some new ideas some new techniques but some some of the ideas will mean that the the construction of clock needs to be changed a little bit so it's not strictly speaking plunk but it's more of a plunk inspired construction and the the goal is to to say one of the key themes in this talk is around basics trying to solve address scalability of

circuits and you know try and tackle a large circuit and use a six to help us so the the talk can kind of be summarized in this in this one slide where basically we have these FFTs these fast Fourier transforms and we want to try and trade them off for something else which I call flcs fast linear combinations so that's maybe not a term you've heard before but basically by linear combination I just mean Multi exponentiation but you know I'm kind of trying to use the additive notation which I think does those

probably at this point reference said it's it's better than the multiplicative notation at least it's clearer and the the fast here basically is in reference to the the algorithm that that we're using so instead of doing the naive linear combinations we would use your fancy Pittenger like algorithms that are quite a bit faster okay so I'm gonna try and take the f of T's and make them into F Dorsey's so my talk will have two parts one will be kind of trying to explain why we care so much about removing F of teens and the other part will be like an actual

construction you know more technical and I will present the key ideas in the second part so just to give a little bit of context where we are today in snarks I'd argue in a great presenter position in terms of the verifier the verifier is super succinctly protoss super short you know super cheap to verify on a CPU or in a medium even and we also have universality for for for plunk but the the big bottleneck to reaching kind of mainstream adoption with many more applications is basically a proof of speed and we want to try and accelerate the prover for for many reasons we want

to try and have tackle larger circuits we want to you know lower the proof latency so basically the time it takes to generate these proofs relative to the the negative computation and we also want cheaper proofs in terms of of a dollar cost and you know we this this desire to accelerate provers has kind of materialized more recently where there's a big focus on you know the actual constants involved in the prove is so breakthrough such as lookup and turbo plunk and

you know actual applications like like like loop ring and coda that have invested of significant engineering and speeding up this proof is ok and you know one of the things that's probably easy to make a prediction about is that we're gonna see exponential growth and in the in the circuits that are being tackled so you know we started with Z cash which is kind of a baby circuit and gradually with we're building up then the signs and so here we're we're roughly and in this column where you know on the order of two to the 25 gates

maybe a little bit more than that but in the grand scheme of things we're still tiny and I think there's lots of room to to grow to it to bigger circuit and you know maybe a tentative roadmap here is we could try and grow the circuit size by by 32x every four years which is I guess you know a bit more aggressive than than Moore's law okay so where are we today in terms of approval time distribution so we have a few three components in the prover we have the witness generation the FFTs and the linear combinations and where we stand today is that the the

witness generation is kind of a pretty essential step which is not super paralyze able but the good news is that it's quite a small part of the proof of time and then we have the FFTs which are significant but not the main bottleneck and then we have the the linear combinations which tend to dominate the time so one of the things that I'm suggesting that we can do is we can trade off the FFTs which is the yellow part for the for more linear combinations and here in this in this trade off it might seem kind of

disadvantageous at first because actually you have to do more linear combinations so and as a result the witness generation becomes only 1% versus 3% let's say you have to do 3 times more in terms of linear combinations but the good news is that you only have to worry about two things as opposed to three things and then if you introduce a linear combination ASIC here then and get you know on the order of a thousand x speed-up then we can get to a point where actually the linear combinations will only take about 10% of the of the total proof time and really

will be in a position where the witness generation dominates and and this is kind of where we're in a position we want to be and and once we're there I I expect we'll find all sorts of clever tricks to speed up the the witness generation which hasn't been a focus of today's optimizations so you know one natural question to ask is you know our FFT is so bad can't we just have to a six if you want to tackle very large circuits when one I think that does the linear combinations and one ASIC that does the FFTs and one kind of immediate argument of the bat is that if we go with you know 180 seconds both terrific

the ASIC cost and complexity just goes down by roughly a factor of two maybe more because you have you know more moving parts where you have to transfer the data between so a very significant simplification you know which is on the order of five million dollars also in terms of savings so because we're simplifying the the rnd we can we can deploy with with just a linear combination ASIC and and get results it immediately well we get get results and of sooner into the market and kind of have a more gradual timeline where we introduce fft

a6 maybe down the road so you know one opportunity maybe to introduce them would be lets say in 2030 when when we need them for for quantum security because as far as as I know all the quantum secure and snug schemes require FFT as mmm I mean if you watch any stalk you might give you some intuition as to why why this is at a point and the other thing is around cost and this may be one of the the bigger arguments for trying to remove FFT is is that basically as we'll see as we'll see in the next slide

for the types of circuits that we'd be looking at you know on the order of 1 billion gates and above and the type type of hardware that we have which is naming a six if we were to design both both FFT and and FLC a six would be the position in 90% of our of our system of the hardware is dedicated to FFTs so basically FFTs start becoming the bottleneck it's the opposite situation to what would have today and so we can have kind of the same performance at 10x less cost if it were a fifties so and this is the

kind of the relative cost very roughly speaking of FFTs versus flcs so if you focused on CPUs which is this this this first well you'll see that you know on CPUs roughly speaking the the FFTs and the flcs are on the same order of magnitude you know one is not ten times less than the other or vice versa otherwise if you move to to a six then suddenly you know if you look at the in the ASIC world with a billion gates then

the the FFTs is will will cost 10x the work relative to the flcs so let me try and and justify this this table a little bit so the first thing that may be worth noting is that as the size of the circuit grows basically FFTs have a natural tendency to start dominating over the linear combinations and the reason is that does this log squared divergence where there's a log factor that comes from the overhead in the FFTs and there's another log factor that comes from from Pittenger it is basically the speed-up of pitch Keppinger and the linear combinations

and so you see as I'm growing the the circuit size here the the relative proportion of the FFT is versus the FLC starts growing and the the other consideration is that CPUs today are are already pretty good in relative terms during the linear combination so the FFTs and the reason is that the the operations all over these fields as opposed to being group operations so the rhythmic the arithmetic that you have to do is is 256 bits and which which city is actually fairly well optimized to do

to do and it's like plain fairly simple you know and straightforward you know modular additions and multiplications but when you work with linear combinations you have you have to do these these operations which involves a you know for example if you work with a 303 381 you have to do these 381 bit arithmetic and you have to there's many more moving parts in a single operation so there's more opportunity for a 6 to speed things up and in in the linear combinations relative to the FFTs and also as we'll

see this there's a much more favorable parallelism story for linear combinations versus FFTs so roughly speaking we're looking at a 10x 10x more speed up for the linear combinations versus the FFT is if we were to go for for a 6 ok so just to quickly go over this parallelism point so you know the paradigm is kind of a spectrum there's things that you compare there's a toy at all like like the vdf which people would say are inherently sequential and then you have things like I extracted 56

proof-of-work which are embarassingly parallel and like the work for snarks kind of falls in between the spectrum so we have the the witnessed generation which is the least parallelizable but the good news is that it's not it's not the amount of computation is not too bad and we have the the F of T's which are kind of in between here where you have to to do these these memory shuffles and things can be paralyzed but there's the stuff moving around and then you have these linear combinations which are you know extremely paralyzed Abul not quite as paralyzed aboul Aish at 256 because you have to you know if you if you use

pip injured and then there's some constraints and paralyze that paralyze ability but it's much more straightforward to paralyze linear combinations and is to paralyze Fourier transforms and just to to to give a little bit of flavor of the parallels and FFTs probably the most appropriate project here is the sick distributed zero knowledge and they you know they try to you know paralyze the the computation of FFTs over very large circuits and one of the things they did is they try to minimize the number of of these memory shuffles so they used a number an algorithm called Z's algorithm now one of the

things that you know that that we found basically are looking at these graphs is that you have to pay you have to pay a constant factor which is not super favorable to have to benefit from this parallelism okay and this is kind of my final slide on the motivation and then I'll get into the nitty-gritty of the the construction so if you remove the FFT you can you can stop dealing with with larger circuits you have more scalability and you have this basic strategy where you can focus on the linear combinations and not so much on the FFTs and we have a final advantage that was

its highlight is that you can go beyond the tuadee city limits that that that the curves have so for example Venus 1281 I think has a to of the city of of 32 and so you know the generally you you want to choose your Twitter state to to be a lot larger than the size of your circuit so that you can do this the design 50 is efficiently the good news is that in in these constructions you don't need a travesty to be to be that high and if we go back kind of to the one key idea behind this this no FFTs idea is is actually the root idea is no

divisions idea so you want to try and do snarks without any divisions and in addition to having no activities you have to other kind of consequences if you do a little bit more work one is that you can you can have snarks which are our circuit friendly so if if you have a circuit wave with lots of zeros then you can significantly accelerate the proofer and you can also have binary circuits and friendly Krueger's so in type of applications here if we have lots of branching in the circuit something which is you know traditionally known as being very expensive then you can start

thinking of doing branching cheaply and you can also start of thinking of doing [Music] try and do zkv ends and basically trying to to do a VM inside the snark where you you might be calling one operation at a time and in the rest of the circuit is all zeros you could look at X accelerations there and also for the full binary circuits like lecture at c-56 you know one one way to accelerate things is is the lookup idea from aztec but here you have like a mode more

generic potentially like more generic approach to handling binary circuits that just works for for all binary circuits and that this will be for for a future talk okay I'll just check if there's any questions so far okay there's a bunch of questions from Vitalik can't you argue that OOP can't you argue that FFT Asics are going to be developed anyway because there will be people that want to use FRA yes yes I agree

Frye seems to seemed like a general-purpose enough ingredient that we can count on than existing soon enough yes I would agree and you know maybe stock where will be the one you know pushing forward these FFT a6 I think stock wise model right now is that they want to kind of make a business model out of proving and so proving will be done by them potentially and I think as a company they can you know they can afford to own you know to rent out you know data centers so one way to scale out is just to go in AWS and just get as

many computers as you can you know that is definitely one way to paralyze but if you want to be in the you know if you want to take a different approach you know around around provers where you you you won't end anyone in the world with a reasonable amount of hardware to participate then you know then the incentives of stock where while you need some sort of different different type of incentives so nick is asking what is the dependence on the security parameter for FFT versus FLC so not sure I completely understand the question but this you

don't have to play around with security parameters so there's as far as I can tell the the the construction that will present now basically that doesn't change the security parameters it just keeps everything the same in terms of security notice it just removes the FFTs completely and then it it adds it adds basically more than your communications as a trade off and then we have a question from Alan which says can the FFT be represented as linear combinations if so why can't f FC benefit from footages algorithm yeah I don't know how to represent FFTs as

linear combinations you know as far as I can tell the best algorithm to do FFT is is as and again and if you could you know use Pittenger to accelerate the 50s there will be there will be a great break fruit I don't know of any such things okay so let's go into the construction so the starting point is the plunk equations and you know it looks as intimidating because we're all these signals but let's try and and dissect what's going on here so we have the various polynomials each of degree at most n so that polynomials in in the leg Rajesh business and there's a few basic operations that you're doing on these polynomials so basically by the way these equations should be equal zero so

there's four equations and each one should be equal to 0 mod modulo the vanishing polynomial on the roots of unity so what are you doing here you you have some some multiplications so you're multiplying two polynomials and you have additions so these are two very important operations that you're doing on polynomials and then another kind of interesting thing to note is that you want to do shifts in the today ceccolini with wrap around all the coefficients you if you think of of the the roots of unity as being a circle and the

evaluations lying on that circle you kind of want to rotate the circle and the final thing that you you know you want to do as well is you want to be the prover wants to commit to the the wire polynomial so there's two types of polynomials there's the pre process once and the non-free process once the pre process one's already committed to you so this there's no trooper work there but the ones that need committing actually actually interview the commitments and so there's various FFTs hidden in these operations and i'm going to try and convince you that you can do all these operations without any FFTs so let's look at commitments first the key idea here is what I call the Lagrange

SRS so when you're given an SRS the structured reference string usually you're given the powers of tau but instead of using the powers of tau which is not like Raj friendly it's kind of in the monomial basis what if we were to pre-compute ahead of time I'm kind of trustless Li the the SRS and the Lagrange's and if we were to do this and we were given these these points as a prover and then it would be kind of trivial to compute the the commitment of the point over F as a linear combination basically just do like an immediate linear combination of size n which does

not require an FFT I mean one question that comes to mind is like I'm given the the powers of tau is an efficient way to compute the SRS in the background basis and it turns out there is and what you do is you consider this polynomial F which has basically as coefficients the powers of tau and then if you evaluate this anymore F on the roots of unity you know you get as an output on the evaluations the the like branch srs and so basically there is an FFT there but it's a it's a preprocessor 30 so you have to to pay n log n group operations

to to get this this SRS but it's a one-time thing and then you cache this as a program so that allows you to do commitments without any effort ease the next thing we want to do is additions so we have three polynomials a B and C and the prover has given commitments to these polynomials to the verifier and the the verifier basically wants to be convinced that a plus B is equal to C as polynomials so this would be addition point while addition of the of the coefficients in the lagravis and you know Katla has this kind of this super power which is called linear

homomorphisms and so you just need to check that the commitments of a classic mentum of B equals the commitment of C and you know this will convince you that a plus B is is equal to C okay okay we need to chef's now so if you have two polynomials a and B and the you know the prover has given commitments to the verifier of a and B the the verifier wants to be convinced that that a and B are kind of related in this shift way well there's a very standard technique which is just evaluate at a random point

so the the the the verify wasn't a random evaluation point to the prover and you can just check this identity on the random evaluation point and so that that asks the question then becomes how do you do evaluations without FFTs and how do you do openings without a fifties so evaluations is can be done with using the barycentric formula so you kind of have this this formula which tells you how to evaluate F at any point given the evaluations here and in the background spaces and it's it's a linear

sum here so you can you know this is this is a there's not even a linear combination in the group this is just a field linear combination and for the opening proof you kind of want to you want to compute the commitment of f of X minus f of Z divided by X minus Z and and this is what this part is here and again you use the same trick of the pre computed lagron srs so this is just a FLC a fast linear combination again without FFTs now there is a question of you know around divisions here you have to divide by

Omega to the power I minus Z it turns out that you can be bad operations I'm not gonna I don't have much time so I'll go fast but it turns out that you can the inversions are not very costly even even in the field okay so this is kind of so so far notice that there's been like zero changes to plunk the only thing that I've I've been telling you about is like implementation details like if you want to do evaluations use a the barycentric formula if you want to do this use that but here I'm it's kind of the the hot pot I remember removing FFTs and here I need to modify plonk a little bit so

let's let's like focus on the problem statement here so I have three polynomials a times B equals x a B and X each of degree n I don't want to show that on the roots of unity and they like the point-wise a times B is equal to X so H is there going to be the roots of unity and Z of H is going to be your vanishing polynomial okay so what we're gonna do here is we're going to use the fried any composition so what is what does fry give us it allows it to take a polynomial f of degree N and split it

into its even and all thoughts and one of the really cool properties is that the the even and on parts have half the degree of F and then kind of naturally defined on a domain which is itself half the domain of F so if f is defined on n roots of unity f of E and F o are commercially defined on on the sub group on a sub group of size of size half and that's because of the x squared here versus the X here so this is the decomposition that we're going to use and the key idea is that you know we as in Fri 1 and your logarithmic number of

rounds where every round we had a had a more check of size N and we wanna we want to convert that into your head my check of size and over to it and I know before I know and over eight until we get to a point where either we go all the way where we have a constant polynomial or we we kind of both halfway through or something like that and the FFT is so small that it it's negligible okay so this is kind of the the key the key theorem or the key lemma I guess so if you have a had a more check of the form a times B equals C plus D so if I've taken the X above

and I've just for convenience of presenting the theorem I have split into two parts the C and the D and I have kind of this dual check a times B bar where B bar is basically the the rotation of be a hundred and eighty degrees so if you this minus sign will basically flip the roots of unity which is equivalent to 180 degree rotation if I have this this this these two Adamo checks on each the roots of unity then this is equivalent to this the same kind of like statement where everything everything in the statement is basically

have the degree so the a prime B prime C Prime and D prime has each have half the degree of a B and C and the domain has half a half the size and like the reason why we have this cross product sorry there's this dual check is so that we handle cross products and and this is the definition of a prime B Prime and C prime so basically we do the you know typical thing with Fri where we we we decompose into two parts and then we reassemble them using verify randomness so the the all here is verified randomness and we we get something which is half the degree okay so I think I'm

almost out of time so I'm just going to focus on on giving a little bit of intuition behind this proof and then I'll just stop there so here's here's some of the the intuition behind the proof of this of this of this fact which allows us to basically remove the FFTs so we have these polynomials which I'll represent as as circles basically the the circle is the root community and you have the like ranch basis so you have evaluations on on the circles and you have the green the blue and the red polynomial turns out that circles in Google slides is difficult so I'm just going to use lines up in the flats and

the circles and then I used the Frye decomposition where I decomposed each polynomial into two pieces here instead of using the even and odd decomposition and I'll use the left and right decomposition so left right left right left right this this equation here can be written as two equations left times left equals left and right-handed write equals right and then I want to do the reassembly using verify randomness so here are actually denoted the randomness alpha so I'm you know I'm gonna try and and reduce these two equations into a single equation so I'm gonna have left plus alpha right here for the green left

plus alpha right for the blue and and here I'm gonna do the same thing here left plus alpha squared right so basically you see that this red left corresponds to the green left times the blue left and then this alpha squared right corresponds to alpha right for the green plus times alpha right for the blue but there's these missing cross product terms okay so like the what we're going to do is this is the reason why I want to consider pairs of how to not checks as opposed to single how to March X is we kind of want to consider the dual check where we take the exact same thing but we rotate be 180 degrees and when we rotate B we're kind of

flipping the left and the right left and right become flipped so here on the on the blue part the left and right become flipped everything become flat and now we kind of have the the red you know polynomial replaced by a green polynomial and so these these product terms can be fed back in to the original equation and you can do the same thing here so basically this is a showing in in kind of a diagram in diagrams how we can go from had more checks of degree n to have n objects of degree and over to by doing this Friday composition and then folding everything back in to a single volodymyr check

taking taking care of the of the cross product terms okay so this is you know I'm I am out of time so I will stop but you know we've this is kind of a summary where you know there's these operations that Catholic commitments need to do which is commitments openings and evaluations and there's some you know two key ideas here the Lagrange's RS and the barycentric formula so you can do cachi without that is no problem and then if you want to plunk without the fifties then you kind of need this this fry the composition idea and you need to avoid these these divisions and there's

a few optimizations which I'll skip oh cool thank you hey Justin one thing is you can actually stay in this room if you want to and so what I'm gonna do now is I'm gonna go on to the next session and I'm gonna pull everybody into that session with me but if anyone wants to remain you can actually go back up to the schedule and come back to this session Justin if you want to keep going I know there was a few questions so I'm gonna go to the next one we'll see you there and if people want to pop back and Justin you can stick around for a little bit cool sounds good alright see you soon thank you

so one of the questions which was asked is what goes wrong when you use the left/right decomposition rather than even odd and I actually think that you can make it work with the left/right decomposition one of the things which is which is possible that it is it's possibly basically less efficient and the reason is that if you if you go to the [Music] you go to the you know to the left right stuff here you basically sorry if you go

to if you look at the fried decomposition you need to to show that the basically introduce some sort of consistency check where you want to show that the even part and the odd part really do correspond to the polynomial that we started with and so to do that you you need to evaluate polynomials at the point Z and at the point minus Z and at the point Z squared so basically have Z minus Z and Z squared and it turns out is these nice you know batching things where you can batch the openings of many polynomials you know at the at this point but if you were to use the the

left-right decomposition I think that you would need to basically evaluate at more points than just these three you will need to evaluate at possibly Z squared Z to the power four was it oh no maybe would mean more like W times e and then W squared times e W to the power 4 times e so basically you need to do these these shifts when you construct the the left and right and these this shift will mean it evaluations at more points so slightly less you know optimal construction if you lose you use left

and right okay one cap is other in the efficiency proven time and proof size comparisons between the original plonk and this modified version okay great question yes so one of the trade-offs is that instead of having a constant size proof you have a logarithmic resize proof because you have these these logarithmic nouns of interaction in each interaction will

will cost less is one group element so you know you go from a proof size which is maybe you know half a kilobyte - you know several kilobytes let's say in the entry if you try and really optimize everything then you know maybe you know three four five kilobytes the good news is that the you own you only have to pay in terms of computational costs you only have to pay this the same amount of pairings so only two pairings in the modified scheme and the reason is that you can batch everything all the pairing operations can be matched the other thing to consider is the number of g1

linear combinations or multi explanations for the proofer here if the number of g1 explanations is going to to grow it's going to maybe you know triple but because the the explanations are quite a bit cheaper than the then the pairings my back of the envelope calculation is that actually the the cost for the verifier is only going to be something like 2 or 3 X then the normal plunk you know if you're if you're measuring for example in terms of gas usage on the on the EVM and this this F if this plunk without a fifties

will only be something like two or three times more expensive to to verify so even though the the increase in proof size sounds scary I actually don't think it's a problem in practice and the reason is that you know the cost that you pay per byte to go on the EVM is tiny and this is a reflection of real-world realities you know the fact that bandwidth is so cheap so often time if you proof sizes three kilobytes it's not you know bring it down - but it's not significantly worse than than half a kilobyte the real killer in these in these stocks is that it's the pairings which stays constant

and then the the next killer is gonna be your your Jiwon experienced Asians but these are still very much under control and it only increases the computational cost by by two or three okay Nick asked raised the question does this modification y'all know Nestle asymptotic improvement improving time okay great question and the reason it's a great question is because there's different people have different views on asymptotics so you have the complexity theorists like yourself Nick and then you have the

county engineers you know more like like exact and if you if you and so basically the the complexity of the whole scheme is basically going to be basically dictated by the complexity of taking these linear combinations with Keppinger and if you if you ask the complexity theorist he'll tell you that the complexity of Pittenger is actually you know like super linear if it's not it's not sublinear whereas an engineer will tell you that it's sub linear so the I

guess the the answer is is is yes it does it does yield an improvement so you're basically going from the FFT which is n log n down to the complexity of Pittenger Pippin Joe is going to be if I believe it's gonna be something like n lambda divided by law and lambda and I think that's slightly well it's it's it's super linear but it's a little less than then then then a 50s but if you take a climatic standpoint and you say okay we have this

this this lambda term which is fixed let's say it's 128 bits and you and then you consider Pittenger to actually be n divided by log n then actually the the bottleneck now from a computational standpoint is is is the the witness generation which which is linear so you know just just reading out the y-values just basic things like that this linear bottlenecks which are fundamental are the bottlenecks so yeah if if you want to take a more pragmatic standpoint then

this this this scheme is it's basically a linear time program okay one quick from keV is when would this protocol be more favorable compared to this to the original plunk so so there's gonna be two factors here to consider and a factor maybe three even factor number one is what kind of hardware do you use until you use if you use CPUs then this scheme is is not helpful to you

unless your circuit sizes are enormous which if there are enormous then CPUs will you know just won't work like you know you're proving time will be days or months and it's not practical so if you're using CPUs there's no advantage whatsoever if you use um a six then the advantage there are very clear as I hoped I explained in the talk and the reason is that a six are ridiculously good at doing linear combinations and so you know the next bottleneck will become FFT is and and unless you're ready to do

two things one is invest in the in an FFT ASIC and two is to have lots of these FFTs ASIC to compensate for the computational bottleneck well it's the linear combinations then then you probably want to go with this scheme one of the things that I don't know about this is somewhere in between like if you use if you accelerate your linear combinations with with GPUs then then you know it's on cleaner you know we need to look at the concrete numbers of you know what is the performance of of linear combinations versus FFT is on GPUs but as a my general rule of thumb is that as we move forward in the

maturation process of this industry we're gonna have circuits of sizes you know billions of gates and and you know at that point when you reach the billion gate level then this seems like it seems to be very clear win but of you know it will take it will take several years until we can access at this point one of the reasons being that we probably want some some form of hardware acceleration to get to a billion gates okay that's all the questions thanks everyone