ZK11: Polynomial Acceleration for STARK VMs - Alan Szepieniec

Transcript

[Music] um so there there are many ways to introduce this topic and uh the way I chose for this presentation is to revisit briefly the Prov workflow of Stark VMS so the idea is we have the algebraic execution Trace which we low deegree extend turn that into a Merkel tree send the Merkel route to the verifier get an interaction get a challenge from the verifier use that challenge to extend the trace the uh extended Trace so this gives us new columns and uh allows us to populate

some of the variables of the air constraints and then we EV evaluate the air constraints uh giving us a bunch of quotients and in fact we can sum those quotients using weights also provided by the verifier at this point we get a single outof domain row corresponding to some Alpha which lives outside of the trace domain and then we can perform a deep update and run fry um that is the Stark workflow in a nutshell and if you didn't catch most of the details that's totally fine the relevant points that I want to draw attention to here is that there are

two stages the main and the auxiliary stage so the main stage the prover commits to upfront the auxiliary stage he can only commit to after receiving challenges from the verifier and so the way I want to introduce the topic of my presentation is by planting a question mark behind this fact that is usually taken for granted why are there two stages why aren't there less than two stages why aren't there more than two stages so let's start with the first question um in a zkv m we describe the state of a

processor as it evolves across time except the processor needs to fetch instructions from a program it needs to interact with memory it takes an input and it takes an output and all those interactions need to be authenticated as well even if you can produce execution traces for these individual units and airs air constraints for those execution traces you still need to authenticate that communication how do you do that well the way you do that is through the second stage you get random challenges from the verifiers and using the second stage you actually prove these cross

table arguments um and and so this is a first step towards answering the question why don't we just do one stage the answer is we want to link disperate logical units that depend on Randomness that comes from the verifier and in fact the concrete way in which we do this is we create extra columns auxiliary columns that depend on this Randomness and what these columns do is they evaluate step by step some polinomial that depends on the entire green part of the

trace and you can think of every Row in this extra column as the next step of some evaluation and the communication between these two tables is authentic if the column in their last row agree and so depending on the particular relation between the tables that you want to establish you get a different type of polinomial so if you want to just look up some elements in a table then you have a look up argument which gives one type of polinomial if you want to establish that two tables are permutations of each other then you want

a permutation polinomial and if you want to establish that at one table and another table that there's a subl list order matters but you can always skip over rows in your stepwise EV evaluation then you use an evaluation polinomial and so this brings us uh a step closer to a satisfying answer to the question I raised so we want to we want to use the equality of pols to authenticate uh the communication between these two tables but the problem is that the air constraints they don't

take polinomial they take scalers it's just a circuit and so what we do is we collapse these pols using evaluation in a random Point supplied by the verifier and that is sound because of the Schwartz simple LMA okay so the satisfying answer to the question why don't we use one stage is we use Elementary polinomial arithmetic to link tables together and since the air constraints do not take polinomial but scalers we

need to collapse those pols to scalers using evaluation in a random Point supplied by the verifier all right with that said what about more than two stages it certainly seems that going from one stage to two stages unlocks some power and so a natural question to ask is which power is unlocked by going to three stages and if you take nothing else at all from my talk take this the answer is arbitrary polinomial

arithmetic as opposed to scalar arithmetic which is what the air constraints usually authenticate and so what does that mean in in more concrete details traditionally we think of a virtual machine as containing a set of registers and those registers take values from a finite field F this is the green pi pict on the left but if we can authenticate arbitrary polinomial arithmetic then these registers can actually take values from the polinomial ring over that field and then in order to make the air

still apply we collapse those pols back to scalers using evaluation in a random Point supplied by by the air but the important point is that you can describe the evolution of your virtual machine as an evolution of a set of pols as opposed to the evolution of a set of scalers and so on the green side where you don't have any interaction with the verifier you can already authenticate basic arithmetic and that's nice if you use Randomness supplied by the verifier you can add multiply not just scalers but pols too and you can even commit to

pols inside of the context of the VM and you can already do this with the standard construction what polinomial acceleration gives you and I'll explain later uh how to do it is you get to do polinomial division and remainder checks you get to do polinomial evaluation queries and you get degree bound checks basically for free one instruction in every case one row in the algebraic execution Trace in every case and before I want to get before I get to the construction let's look at a few motivating examples firstly is Big integer

arithmetic the idea is we want to multiply or rather we want to authenticate the correct multiplication of two integers of 2,000 bits or so now you could split these up into digits and then use the schoolbook multiplication or even katuba multiplication and and run through that algorithm and that's rather costly the way you use polinomial registers to authenticate this correct multiplication is you construct polinomial that represent these integers a b and c where C is the product of A and B these polinomial have to have um binary

coefficients well I guess you can do some packing but as a first approximation it works if these pols have coefficients that are all zero or one corresponding to the binary expansions of the integers and then you calculate the product of those two polinomial A and B subtract what you claim is the correct product and you reduce that modulo X-2 reducing modulo X-2 is the same as is replacing every occurrence of X by two and so this corresponds to sending your polinomial consisting of bit coefficients to an integer with the same bits it works as long as there is no

overflow in your coefficients and then you just assert that this remainder is zero because it has to be if and only if you calculate C correctly and so the yeah it it only works if there's no overflow if your coefficients are never larger than P if they are larger than P then there's a problem and so in terms of cost you do need to spend a linear amount of time constructing a b and c but once you have constructed a b and c you can calculate this remainder in a constant number of steps and you can assert that it is equal to zero in one

step [Music] and this works independent of the circuit depth so you can do this again and again and again and you really only need to construct the inputs to your arithmetic circuit over the integers all right a second motivating application is the last round of fry before you sample the indices for opening the coefficients for for opening the the code word and checking the their colinearity checks um at some point the the prover needs to send a code word and the verifier needs to check that this code

word is of low degree and so traditionally what I think is the fastest way it is for the prover to send both the last code word and the polinomial that interpolates through it and then the verifier uses horer evaluation to evaluate the polinomial in a random Point uses bicentric extrapolation to interpolate and then re evaluate the code word in a random point and then he checks that those those two points are the same and the verifier needs to do the colinearity checks using polinomial registers polinomial acceleration we can improve

on this the prover only needs to send the polinomial which by the way does need to be represented as a list of coefficients because that's what the proof consists of um but actually I'm not sure about that last fact I I think the prover might even get away with not sending that I need to think about it um the point is in the complexity of the verifier drops so the verifier does need to construct this polinomial which takes around linear time and then he does need to evaluate at T times to get the points for the collinearity checks and he needs to verify the

collinearity checks but if you compare the second line the cost of the bicentric extrapolation disappears in favor of T evaluations and by the way evaluations of polinomial contained in polinomial registers can be done in one cycle all right last application is single instruction multiple data polinomial you can think of them as vectors and so it it should come as no surprise that when you add two polinomial you add two vectors of numbers very simple uh but the same works for multiplication if you want the Hort

product it depends on how you represent the vectors if you represent them as the evaluation on some domain then you need to modulo your pols by the zero fire of that domain but then you get the hadamar product of the evaluations on that domain you get Point checks into these vectors through evaluation queries and once again evaluation queries take one cycle and you might also want some kind of aggregate measure and and so as an example you want to compute the in product of two of two uh vectors what you end up doing is you compute their

hadamar product and then you want to compute the sum so how do you compute the sum of such a vector well you compute the sum that defines the polinomial um a minus s over the size of the domain and this is a new polinomial that has to satisfy this equation this polinomial that supposedly sums to zero has to be describable as the difference between the same polinomial evaluated in X and Omega * X and yes you do you do need to

construct C again that takes linear time but you only need to construct C once regard regardless of the uh number of sum checks that you do you can do 100 sum checks sum all the C pooms and construct it once so that's batchable but once again constructing these polinomial does take linear time and that is hinting at one of the open problems that I'm looking to solve all right here is a more concrete presentation of the construction um this is an example I'm sure there are many

different ways to achieve this and I'm afraid this slide is rather overloaded with formulas and notation it's mostly for the benefit of the recording so uh here we go we have polinomial registers pr1 through PRN and for every polinomial register we also need to track their degree somehow so we have degree tracker one through degree tracker n and then whenever we have a division operation we also need to store the results which are the quotient and remainder along with degree

trackers the purpose of this accumulator polinomial is special and I'll get to that later these polinomial are for uh bookkeeping you need the degree trackers and their inverses in some cases and these columns in fact don't don't interface with the state of the VM they are there for a different type of bookkeeping so for example we have a numerator of degree at most BN and this means that the degree tracker is X to the^ us BN and we have a denominator D of degree atmost BD which means that the degree

tracker is X to the minus BD we store the result and the quotient similarly excuse me we store the remainder and the quotient similarly the accumulator polinomial is the only register that represents a polinomial in two variables X and Y the degree trackers are the inverses of excuse me the the bookkeeping degree trackers are the inverses of other degree trackers and which other degree trackers depends on the concrete um instruction and which polinomial are actually being

combined and these extra bookkeeping columns represent the evaluation of the accumulator polom in beta where beta is a value supplied by the verifier at the right point in time and so the idea is we get beta from the verifier and we get Alpha from the verifier and with alpha x disappears with beta y disappears so whenever we have a y that becomes beta whenever we have an X that becomes Alpha and so after Alpha and Y Alpha and beta are known everything becomes

scalar and so in order to authenticate a divide a long polinomial long division resulting in both a quotient and a remainder we have to establish this relation where double slash denotes divide and forget about the remainder and and we have to establish their degree bounds and the degree bounds are tricky the equality that the numerator equals denominator time quotient plus remainder that's trivially encodable as an air constraint but how do we do the degree bounds well what we came up with is

using the degree trackers this is where the accumulator polinomial comes into play its purpose is to collect a whole bunch of Univar pooms in X each of them are assigned a unique power of y when you evaluate this in beta replacing y by Beta what you get is a random linear combination parameterized by Beta of all those Univar polinomial in X and so the Al the accumulator polinomial a underg goes a bunch of updates where you multiply it its old

value by Y and add in a new univariate polinomial the term that you add looks like this for a degree bound check on R right because the degree of R is supposed to be less than the than BR and so n is the maximal degree you sub subract BR from n and this gives you a little bit of space if you multiply the the uh polinomial R and the equation does not check out you will have a higher degree then is allowed and this will be caught um specifically if R exceeds the bound then

the degree of this term on the right hand side will be larger than n um and we do the same for Q on the right and so we've reduced the low degreen claim of pooms to low degreen claims of monomials these are the degree bound Checkers the point of this reduction of pols to monomials is that we can actually divide monomials cleanly it's easier to prove that monomials have a bound a degree than polinomial do and in fact we can uh this is where one place where we use the inverse degree trackers

you just multiply the right the right registers you get a new polinomial and you update your accumulator with those monomials all right these five updates to the accumulator polinomial can be authenticated through a rather complex air constraint but this is not enough because we still need to establish somehow that after we evaluate a in beta replacing y by Beta its degree is

low and that's what the extra bookkeeping columns in the red on the right are four because they go into fry and so this establishes that some polinomial that we hope is equal to the last row of a evaluated in beta has degree less than n but it still doesn't establish that it is corresponds to the last row of this register and so how do we establish that we use an outof domain sampling Point here um since this value is collapsed using both

Alpha and beta we just look at its value in the last row and then we have a when evaluated in Alpha and Beta And so that is an outof domain evaluation which we can use for a deep update and since we're integrating uh this last column that gives rise to an error constraint so using this Construction in the context of a stark modifies the Stark workflow in particular we have this extra stage in between the main and auxiliary stages this is where we

already received beta from the verifier but we did not receive Alpha yet at that point we can produce the extra bookkeeping columns um these extra bookkeeping columns they represent segments of a what is it a polinomial of degree K * n gives K segments each one of which are code words all right so this construction is uh nice but it's not it's not perfect and one limitation is that you cannot compose polinomial and that wouldn't be such a big problem

because you can still verify that two polinomial correspond to the composition of or two polinomial composed correspond to another you can still verify this but you cannot non-deterministically guess pooms um that's the second limitation uh the the efficiency gains come from deleg ating to the prover outside of the uh algebraic execution Trace work it shrinks the algebraic execution Trace but you're still always working on the prover side not on the verifier side so you cannot benefit from the succinctness

that verifiers get in traditional snarks um and so in particular you need to bind down your polinomial coefficient by coefficient somehow and that's why I keep reciting it takes linear time to construct these polinomial and so that gives rise to an open question and if you're if you're of that mind please solve this for me it could take the form of a hash function or of a commitment scheme but we want some way to verify that a divined polinomial or a non-deterministically guessed polinomial of degree n corresponds to a constant size cryptographic digest

and we want to do this in a number of cycles that is asymptotically less than the number of coefficients and corresponds uniquely you you you do get to use cryptographic hardness assumptions in fact I think you need cryptographic hardness assumptions but the point is you get to use single instruction multiple data instructions in the course of verifying this this polinomial so you can think of this as sublinear hashing sublinear in the input but assuming that you get single instruction multiple data

instructions um if we can do that that unlocks much more power than I've described so far then we can simulate arbitrary polinomial iops on the prover side thereby shrinking the algebraic execution trace a lot that's it thank you for your [Applause] attention uh we have time for for one question uh perhaps the while the next speaker sets up if he's here so uh in this instuction use three

phases uh you know two two two separate verifier challenges computered in sequence there um is there do you think there is a way to do this with with with st while stilling two phases or I think that's probably pretty fundamental to the construction not say no this is yeah anyway I I can't say that I've exhausted the search space but I did try to reduce the number of stages and I it's infeasible it it seems like you really do need one challenge before the other other challenge was sampled um you need to commit in between those two challenges you need to commit to something and that and that that third stage is added is mostly for degree

tracking essentially our degree uh guaranteeing low degreen of the results is that did I understand that correctly I didn't catch the question it the that third the the the third the red stage is about making sure that the results are low degree do I understand that correctly okay correct okay thank you very much [Applause]