ZK14 - Time-Space Trade-Offs for Sumcheck - Anubhav Baweja (University of Pennsylvania)

Transcript

Thank you. Hi, my name is Anubhav. I'm a PhD student at University of Pennsylvania and today I'll be talking about time space trade-offs for SumCheck. And just like I want to give people like a fair warning. This talk is going to have like some amount of like math and algebra. So I hope you all are ready to suffer. Okay, as all of you might already know, SNARKs are succinct non-interactive arguments of knowledge that help a prover convince a verifier of a statement with a short proof.

And a lot of recent work on SNARKs use SumCheck as a building block. As you saw in like the previous presentation by Antoine, their work also uses SumCheck and there's like a long line of work that includes like streaming SNARKs, ZKVMs, lookup arguments, all sorts of amazing stuff that uh uses SumCheck as like a building block. So uh of course, the space-time efficiency of these SNARKs therefore crucially relies on what the space-time efficiency of the underlying SumCheck prover is.

Uh and just to recall, I'm sure a lot of you are already familiar with what SumCheck is because you were in the like the last talk in particular. Given a multivariate polynomial F and a target sum sigma, the prover convinces the verifier that the sum over the Boolean hypercube of this particular function F equals sigma. And there are broadly I guess two existing SumCheck provers in the interactive proof model that go back to 2011 and 2012 by the work of Cormode, Taylor, and Yee which use a linear time and linear space and this is called the folding protocol. And then there's a log space protocol that is very very space efficient but uses n log n time and this

is by Cormode, Mitzenmacher, and Taylor in 2012. And if you're a theorist like I used to be, then you might say that like okay, there's this end time, this is n log n time, just like a log n factor, who gives a Let's just move on. But I mean this log n factor if your statements are like quite large, it can actually be practically speaking become something like 20, 30, and this is like a factor that you would ideally like to avoid if you can. So, naturally now you have like a time optimal and space intensive implementation, and you have a time intensive space optimal implementation of the sumcheck prover. So naturally, the question is can you get a prover algorithm with time and space that's somewhere in the

middle. That okay, you don't want to pay like linear space, you have like a some space budget that you can use, but you don't also want to pay like the entire log n overhead. You want your overhead to be like asymptotically small and ideally concretely small as well. Okay. Obviously a second question if you're a theorist, that you might say can we prove lower bounds for space time tradeoffs as well. And a third question you might also ask is can we get better tradeoffs if we depart from this IP model and allow the prover to send articles and polynomial articles and other things.

Great. So in today's talk, I will exclusively focusing on this first question, even though in our work we I guess answer all three of these questions affirmatively. And if you want to for example know more about the space time tradeoff lower bounds, then you're welcome to attend the same talk that I'll be giving at ZKProof in a few days, where I'll be more focusing on the lower bounds. Great. But today we're just going to talk about algorithms. And for the rest of this talk, just as a disclaimer, the model of time is going to be the number of field operations, and then the model of space is going to be the number of field elements that you store.

So broadly, our results are as follows. So for our upper bounds, if the prover has streaming access to your input polynomial, which we would consider So, so we're probably going to consider two cases, multilinear polynomials and product of multilinear polynomials. And these two cases cover practically all like relevant applications. This is somewhat of a lie, but anything that we will actually prove for the product of multilinear polynomials will also be true for the product of three multilinear polynomials, of four multilinear polynomials, and then the statement does become completely true.

Okay. Um so, for multilinear polynomials initially, we get a space of n to the 1 over k, where k is like any parameter that you can set, and you get a time of kn, and we get a corresponding lower bound that is tight, that if your space is at most n to the 1 over k, then you need time that is at least kn. So, this algorithm is optimal. And then for product of multilinear polynomials, we get for the same space, you have this additive log log n factor. And you might say that like okay, maybe you can get away with not having the log log n factor if you're doing a product of multilinear polynomials, but unfortunately that is not true we because we also prove a lower bound that shows that this log log n lower bound is

in some ways inherent. Um and if for example k equals 2, you would get something that's like space is square root n, and your time is n log log n. And just a minor note that this lower bound is conditional on like some natural conjectures about the multiplication of polynomials. In particular, the lower bound cannot be conditional or cannot be unconditional because you can get a faster algorithm if you had matrix multiplication that could be done in n squared time, but that's a story for a different time. And additionally, we also answer that third question on the previous slide that in the PIOP model where the prover can additionally send polynomial articles, you can for that same space n to the 1 over k, instead of the log log n factor, you get a log star n.

Practically doesn't make any difference for any value of n that you're ever going to see in your life, log log n is at most five, log star n is at most five. Yes. Great. So uh just to recap, this is like the these are these are asymptotic results for the upper bound for the product sum check, which is going to which is what we're going to be focusing on today. So, we have something that's like in the middle of the folding missile algorithm and the log space algorithm. And before we I guess move on to like what this algorithm actually looks like, uh, I know like this is also like a very engineering focused audience and you might want to know like, okay, am I hiding like a 1,000 like a factor in

this big O notation over here? And uh, fortunately, the answer is no. And uh, we do we did actually implement this algorithm as well. And uh, over a 128-bit field and your number of available variables being 28, you get numbers that look something like this. So, for the initial folding missile check, it's very very fast, uh, but it uses a lot of memory. And as expected, the log space algorithm is very slow, but it uses no memory at all. Uh, our algorithm is of course somewhere in the middle where where for k equals two, for square root space, you get time that is like kind of close to what the folding missile check would get you, but much less than what the log space algorithm would get you. And you have

memory that is much lower, in particular like 120 times lower, uh, but of course you're not like all the way there to the log space amount of memory. But if you really were in a memory constraint setting and you wanted like even lower memory but were willing to give up on time, of course you can change the parameterization of our algorithm, set k equal to four, and get something like a little bit extra time and no memory at all. Okay. Uh, and yeah, as Giacomo pointed out in his talk earlier in the morning all benchmarks are lies, but uh, we hope that like we we try to do as best of an apples-to-apples comparison for these numbers as possible.

Okay. So, for some background, what is a multilinear polynomial initially first of all? So, if you have a polynomial that is n-variate, then a multilinear polynomial is just one that it has degree at most one in each variable. Multilinear polynomials have like a very nice property that they have like this Lagrange basis representation that they can be uniquely represented by their evaluations over the Boolean hypercube. And in particular, if you want to describe this polynomial f of x, then you can describe it as this linear combination of the evaluations of the Boolean hypercube with the Lagrange basis coefficients.

And the Lagrange basis coefficients themselves are also very efficient to evaluate. And for the purposes of the talk, we're going to be assuming like a streaming access model where the prover has streaming access over the Boolean hypercube evaluations of the multilinear polynomial. So, initially you have a pointer that starts at like the first evaluation, and then you say give me the next evaluation, and then you move to the next evaluation, and then you move to the next evaluation, and so on. Right. So, very briefly I'm going to overview what sumcheck is. So, want to prove that the sum of f of b is equal to sigma, and the verifier only has oracle access to f, and the prover has explicit access to it or streaming access to f in our case.

In each round, the prover sends a round polynomial, which is defined as follows. So, for the first round, you set your first variable in your algorithm in your polynomial to be a variable, but you sum over the remaining variables. And then the verifier verifier performs some check, sends back a challenge, and then in the next round the prover fixes the first uh, value of your polynomial to be R1, the challenge of the verifier sent, and then your second variable is remains a variable and you sum over everything else. And then this pattern continues, and then in the last round you send this round polynomial.

So, what our goal in this talk is to understand how does this prover behave? Uh, we're not going to change the sumcheck protocol at all. The We want to keep the protocol exactly the same. We don't want the prover to be sending like extra stuff. And we really want this to be like as much of a black box change to the sumcheck prover and only the sumcheck prover as we can. And in that, in view of that, we have to consider two steps. Uh, in each round you have to compute this round polynomial, and you have to update some like internal storage that the prover is maintaining to compute these round polynomials for the future.

Okay. So, before we get to the product sumcheck algorithm, we'll first go over the multilinear sumcheck algorithm because this will serve as like a good basis for, uh, the, uh, stuff that we do later. Um, again to recap, if in the folding base sumcheck, you take linear time and linear space, and the high-level reason why you only need linear time and linear space, uh, why you only need linear time is that you really only make, uh, a pass over the input streams in round one. You never really have to make a pass over the input streams ever again because what the prover I really ends up doing is it uses its like linear space and stores like these folded polynomials.

And then afterwards it only really needs to access polynomials to be able to return, uh, compute the, uh, following round polynomials. Great. The log space algorithm uh, goes to the other extreme where it says like, "Hey, I'm going to read the input streams in all the end rounds. I'm never going to store basically anything except the random challenges that I have. And therefore I'm going to pay like a lot of time. I'm going to make a pass over the input streams. So, therefore I'm going to make log n many, uh, passes and therefore I'm going to pay n log in time, but of course I'm not really showing anything at all.

Um in our case uh for the multilinear case, we'll still get like a linear time for if you're restricting ourselves to the case of k equals 2. And we're only going to read the input streams in round 1 and n over 2. And that's it. And that is why uh the overall asymptotic complexity looks something like k * n. And so we're going to make two passes which and k is equal to 2. And here we're going to use square root n space. And the thing that we're roughly going to store are things called like the sums of sub cubes as we'll and we'll see what that means later. Uh like in the next slide.

So what do you do in the first n over 2 rounds? Uh the idea is to store all necessary information to compute round polynomials for any value of the random challenges for the first n over 2 rounds. So what do I mean by this? In round 1, what you would do is you would compute this generalized round polynomial. So recall that in the round polynomials that the sum check prover was actually sending, in each round you were only you only had like one variable, right? In the first round x1 was the variable, in round 2 x2 was the variable, and so on. But what we can do is we can define this generalized round polynomial where we set the first n over 2 variables to be variables and we only sum over the last n over 2 variables.

Great. And if you just I guess stare at it long enough, you'll realize that okay, if you can somehow compute this generalized round polynomial and not only just compute it but store it, then once you receive the values of the random challenges later on r1 through rn over 2, then you will be able to compute uh the round polynomials whenever you want very efficiently. So in particular, if you do make this pass in round 1 and compute and store this round polynomial, then you will not need to read the input streams in rounds 2 through n over 2.

And uh the next time you'll read the input stream will be around n over 2 + 1. So, you can expand this expression out into this expression via Lagrangian interpolation as we discussed in the preliminaries. And the only thing that you really need to do here is you need to rearrange the order of the summation and write it in this format to see that now you only really only the outer part of this expression here depends on these x1 through xn over 2 and this internal part does not depend on these variables at all.

Like it's completely independent of what the random challenges are going to be in the future. So, what you can do is you can just uh yeah, compute and store all of these different summations and this this is what I meant by those sums of sub cubes. Once you're able to do this, this you will be able to compute the round polynomial and you will be able to compute the generalized round polynomial and therefore the round polynomials for any of the first n over 2 rounds and you're done. And how much space are you really using to store this? You're using 2 to the little n over 2, which is squared n space. Fantastic.

Okay. What do you do for the last n over 2 rounds? You do something very similar. You define this generalized round polynomial where the last n over 2 variables are variables. And you already have the first n over 2 variables because you had the first n over 2 random challenges. And you again do a Lagrange interpolation of it. You write it in this format. And here every single one of these values you only require square square root of n time to compute and there are square root n many such values and therefore computing them takes a total of n time and again storing them only takes square root n space. And you're done. That's the entire algorithm.

Great. So, but how do we use these ideas to get a proof algorithm for the product subject because that is really like the case that is useful in designing SNARKs. For example, if you want to do a a PIOP for R1CS, for example. Um nothing about the folding base sum check and the log space sum checks changes uh between the multilinear setting and the non-multilinear setting. Like you're again in the folding base setting only making input uh stream passes in round one, and you're showing the folded polynomials. In the log space one, you're making input stream passes in uh all the n rounds, and you're only showing random challenges. Nothing changes for them.

But, in our case, we will have to kind of do something weird, which is we would have to read the input streams in rounds that are powers of two. So, 1 2 4 8 and so on. And that is where this log log n factor shows up, because the number of rounds is log n, and therefore you take the log of that, and you get log log n. Um and uh we will require square root n space, but instead of storing those sum of sub cubes, what we will be storing are these things called inner products. And we'll see what these inner products mean in just a second.

Okay. So, firstly, the question is, okay, why doesn't the same algorithm just straight up work for product sum check, right? Like why are we making like a big deal about this? Um so, in the multilinear sum check case, we were able to get away with passes just two passes in rounds one and n over two. And each pass requires n time. Um so, now if we just do this product sum check for k equals two, and we make passes only in rounds one and n over two, what happens? Let's Let's just see. Okay. So, firstly, if we make the input pass in round n over two, then we need to compute this round polynomial. So, now instead of just being like this one m, now we have a product of like two

different multilinear polynomials here. Right? Okay. Uh you can now expand this by the Lagrange interpolation again and just write it out in this manner. And uh, you'll see that okay, if for all X uh uh a such X you can just compute and store all of these different values. And uh, what these values are, these are indeed actually the folded polynomials from the folding based linear time sum check. So, all you're really doing is that you're emulating the folding based linear time sum check in the last N over two rounds.

And uh, you can get away with computing all of these values every single every single value in square root N time. And again, uh, you only need square root N space because you are storing like two to the N over two many things. And uh, because you have square root N many items and each item requires square root of N N time to compute, you only take linear time. Okay. So, what's what's the problem? This is just fine, right? Like uh, why uh, this just works. What doesn't work, so round N over two is completely okay. You can actually just do that. What doesn't work is if you try to do the same thing in round one.

So, what happens if you do the same thing in round one? Uh, now you are setting the first N over two variables to be variables and you're summing over the last N over two uh, variables. And the problem here is that what you're really trying to do, is you're trying to multiply these high like multilinear polynomials together and a bunch of multilinear polynomials together and then adding them up. That that is what you're doing here. But multiplying polynomials on its own is like a very hard problem and that we don't know a linear time algorithm for.

So, this is not something that you can just compute. Earlier, uh, in the multilinear case, we never actually had to multiply polynomials together. We just had to we were just working with one multilinear polynomial. Uh so, this would require more than linear time and would break our invariant that we have been relying on that oh, whenever you make a pass over the input stream, you would you're only taking linear time. But, uh fortunately, if you just make a few more passes, in particular, if you make the passes in these powers of two rounds, then you can actually end up with like only requiring linear time and we'll see how that why that is true in just a second.

And then this is log log n rounds. So, in around I, like you would expect, you would store all the information that is required to compute the round polynomials for the ith round I plus one round to the 2I minus 1 round. Great. Uh so, let's start with an example. So, at the start of round two, you would compute this round polynomial where you're just setting these two things to be variables and now you're multiplying these two polynomials together and summing them over all the values of B.

We have set the first variable to be R1 because this is at the start of round two, so we already have R1. Uh and these two variables are the things that are in question and if you're able to somehow compute and store this, then you are able to compute the round polynomials H2 and H3 and in particular, you would avoid reading the stream in round three. And the next time you read the stream will be in round four, like we want. The question is, okay, how is H2,3 computed and stored? Uh and again, we use the only tool at our disposal, which is Lagrange interpolation, which is that now we're going to open this this M1 and M2 up into their Lagrange interpolation.

And then what are we going to do? We're going to do the other thing, which is rearrange the ordering of the sums. And this is what you end up with. And we would make the pretty much like a very similar observation as the multilinear case, which is that again Oh. Uh uh Okay. Second. Yeah. We'll make a very similar observation as the multilinear case, where only this outer part uh is dependent on X2 and X3. This inner part does not depend on X2 and X3. Again.

Great. So, for all possible values of X and Y uh you would store these things. And what are these things? These are like inner products, right? You're taking You're saying like I'm going to fix R1 and I'm going to sum over these uh last N over three variables. And for these two middle variables, I'm just going to compute like all the possible uh uh like four many inner products that I have. Great. Uh so, I'm only showing four values. So, my space usage for this particular round is only order of one. I'm not even using my budget, uh which is like square root N. So, like I'm actually like not even space constrained in this particular round.

And each value here is taking linear time to compute. That's uh uh easy to see. And therefore, this round is perfectly fine. Okay. So, now we have to generalize to round two to the I, right? We just did this for round two, and it wasn't easy to see, I guess, like I I mean, I just say it said like, "Oh, you have only a constant number of things. Everything takes linear time. Of course, everything is fine." But if you wanted to generalize it to round two to the I, then we would have to kind of use like a very uh Yeah, I'm you also Yeah. So, so this this is a the polynomial that we had that we want to generalize to round two to the I.

Yeah. Okay. Uh and we'll have to use a very deep algebraic technique for this, which is called pattern matching. Um, and I was hoping to get a laugh for that, but oops. Uh, which is just that all we're going to do is that we're going to say that like, okay, uh, we have two variables here. Let's make them two to the I many variables. And, uh, ins- and we had like just one challenge received, and let's just say like, uh, now we're going to have like two to the I many variables here. Okay. So, we're now going to compute and store all of these many inner products, where now this again outer part, uh, is the only part that actually depends on

the, uh, random on the unspecified variables, and this inner part you can already store. Great. So, now one inner product here takes like this amount of time to compute because that is just like how many variables they are that there are that you're summing over. And, uh, now you only need, uh, this amount of space. So, you have two to the two, uh, to the I plus one. They're like powers of two, towers of two here. But, uh, the reason that it's two to the two to the I plus one is because, uh, there are two to the two to the I many values for, uh, each X and Y, and then you're just saying like, oh, because you're computing it for like every

possible value of X, every possible value of I, you get that plus one at the end. And this is at most square root of n space if two to the I is less than n over four. Okay, great. And, uh, this step also only took linear time because each of these inner products took that much time to compute, and that is how many inner products there are, and that two to the I plus one term in the exponent just like exactly cancels out. And this is why we kind of pick those specific rounds. Like we pick like these, uh, rounds that are powers of two, just so that like this cancellation can happen like perfectly. And uh, if you are more generous about when you do your rounds, if you want to

make fewer rounds than like what you're making right now, then what will happen is that like this product will not go through and you will end up with like super linear time over here and you're toast. Great. And finally, putting it together, what is the algorithm? You make input passes in rounds 1 to 4 and n over 2. And in round j equals to the i, you store the generalized round polynomial via inner products, which look like this. And in round n over 2, then you store the generalized round polynomial via the folded polynomial, so you switch to this like original folding folded polynomial algorithm and you store these values.

Amazing. And in every round, you would just compute the round polynomials from the previous generalized round polynomial, and that's it. This is the entire algorithm for the new space efficient sum check. Fantastic. So, in theory, like this kind of works that you Okay, you would just like pick like these rounds that are powers of 2. But in practice, when we I guess like discuss these like particular numbers, these are not exactly the round numbers that we choose. It turns out that like in order to get these particular numbers for k equals 2, we would actually choose rounds that look something like this, like which is I guess the Fibonacci sequence.

And is this a coincidence? Uh And yes, it is a coincidence. Uh because I mean, you might you could have just chosen rounds that look like some like slightly different if you were happy to pay for like a slower prover and you uh like if your memory budget was lower. So, but the main key key takeaway is that you can really parameterize this algorithm based on your specific memory budget. So, if you know that you are going to only have like 20 megabytes of memory, then you can choose whatever rounds that you need to make your passes in to figure out what is the best possible prover time you can get for your particular memory budget. And

in Yeah, in practical world you would not necessarily care about like oh, whether your space is n to the your space is square root n or n to the 1/4, you will really work with like a memory budget. You would know like oh, I have 20 megabytes of space and from there you can like figure out what the optimal round scheduling is. Okay, and that is all I have to say. Uh thank you. You can find paper here and the implementation here. >> [applause] >> All right. Thank Thank you, Anna. Well, we have a couple minutes for questions.

Um so, if you guys have any, please raise your hand. Yeah. I can get you the mic for a second. So, great talk. Great work. Um is there any function you have to get the optimized prover time depending on the rounds? Or is it a bit of like you just try? Uh wait, sorry. What was the >> Like if you go to the previous slide. Okay. No previous. Uh there. This one? Where you got the rounds that you actually chose. >> Okay. Okay. The rounds that I actually chose. Okay. Ah, yeah. Here. Yeah. Is there like a a function on like what will prover efficiency look like?

For the depending on the rounds you're you're choosing? Yes. So, the prover efficiency does matter in some ways. So, um in in general the more rounds that you actually pick, the more time you'll spend. That is like I guess clear. But even with like the specific scheduling you have, I think it turns out like the later rounds that you actually choose to actually compute these generalized round polynomials. Practically speaking, it does become like a slightly like harder because you have like more random challenges that you have received so far and therefore you have to compute like a higher arity folding by then. So, if you So, really maybe practically like the best I guess

workflow is to just like have like a specific memory budget that you're interested in and then just figure out like what the best scheduling for the rounds is. >> Okay, so this figure out is figuring it out. It's not the Oh, yeah. So, the Yeah, so yeah, that's there's no like exact algorithm for that. It is more based on numbers and just like like a grid method. Thank you. We have time for one more question. So, if you guys have any, don't hesitate. No? All right. Otherwise, we can wrap up. Thank you, Anish. And we're