ZK13: Lifted FRI: A uniform multi-domain polynomial commitment scheme

Transcript

[Music] Hey everyone. So, uh I'm Andrew and this is Adrian. And today we're really excited and grateful to present to you all today about lifted fry which is a uniform mixed domain polinomial commitment scheme developed by Adrian Olic and myself. So, I'm going to talk about the uh foundation of our lifting technique and then Adrian will take over and talk about how we can apply it to different parts of the Stark protocol and uh some of the subtleties involved with that as well.

So today the teams that are building the most efficient proof systems use multi-dommain starks and that's because it allows you to commit to a bunch of differentiz traces on differentiz domains and that's what you see here a bunch of differentiz traces. So these traces must be a power of two in size and this is just an example. So in reality uh the these traces would be a lot larger. Our new technique is an improvement on multi-dommain starks. So at a high level we we don't have a mixed domain trace. Instead we lift traces uh to the largest domain by duplicating

rows repeatedly. What the verify sees is a protocol on a single domain. It's just a regular stark with a rectangular trace. But the prover gets all the benefits of a multi a mixed domain stark without the challenges that current implementations face. So the agenda for today is that I'll start um talking about uh some context on current mixed domain STS and then transition into our new lifting technique and how we can retain all the benefits without the challenges and then I'll uh hand it over to Adrian and he'll discuss how we can safely and

efficiently apply lifting to other parts of the Stark protocol. So let's start with some context on what mixed domain starks look like today. So one of the benefits of mixed domain starks is that if your proof system consists of committing to a bunch of different sized lookup tables, you don't need to commit all these lookup tables on your largest domain. You and uh this is a great efficiency gain for the prover. This is a mixed Merkel tree.

It's used to commit to the trace I showed you on the previous slide. And unlike a regular Merkel tree, it allows leaves at any layer of the tree, not just the bottom. And something I want to point out is that the shape of this Merkel tree can change. So imagine these traces are um traces for you know a ZKVM op codes. One proof might have more of orange one up code than of pink another up code. So the the ratio between these chain traces can change and it changes the shape of this milk tree. So that's mixed melt tree. Now let's look at mixed domain fry. So in mixed domain fry you combine you start

by combining and committing to evaluations on the largest domain. Then you fold and combine evaluations on smaller domains as you go. And notice that the smaller domains are actually just doublings of the largest domain. This is what allows us to combine smaller traces into the layers of fry as you go through the folding. This is really nice because it means that you can have one instance of fry for a whole bunch of different sized traces. So, um, speaking from experience at Starkware, we have proofs that could have hundreds of traces, um, with different sizes and being able to just

have one instance of Fry is a huge efficiency gain for the proof size. So, that's a little bit about mixed domain stocks and some of their benefits, but there also challenges that uh, face these stocks. So the mixed Merkel tree is an extremely uh complicated data structure and uh verifying Merkel decomm leads to a very complex control flow. Um in fact uh stquive verifier a large portion of the verifier step counts is actually associated with verifying these mixed merry decommitments.

It's also challenging to order just because of its complexity and um there's no uniformity. So it'd be really hard to unroll something like a plon circuit to verify a mixed mel tree digment. The complexity of the meltry also infects other parts of the protocol. So it affects the constraint quotients, the deep quotients. uh it also complicates fry and that's because you now need an implementation of fry that allows inserting polomials at intermediate layers of the fry folding cascade. Also you have to handle edge cases like not terminating fry before you've combined in all traces and that's

just frustrating. So um the other thing I want to mention is it's not trivially compatible with polomial command schemes like were and that's because all of the trace polinomial code words have exactly the same rate but the code words in the um different layers of were have uh different all have different rates. So the verify can't locally check consistency with the trace polinomials and the uh and the word and the word code words.

Um however with our new lifting technique we can actually overcome these challenges and um our lifting technique at a high level is taking traces and not interpreting them on small domains but instead uh duplicating them repeatedly until they're on the largest domain. And I'm going to go into that a bit now. So imagine we have uh on the left here a domain of size four and on the right we have a domain of size eight. Notice that we can project the larger domain to the smaller domain domain by applying the doubling map. So now let's look at polinomials evaluate on these domains. Um notice that uh we have our original polomial

evaluated on the domain of size 4 and then we have a different polomial on the right uh which is our original polinomial composed with that doubling map from the previous slide evaluated on the domain of size eight. What's interesting is that uh the evaluations on the domain of size 8 is actually just the evaluations on the domain of size four repeated twice. That's what lifting is. It's the idea of composing polomials originally defined on small domains with many to one maps so that they can be defined with the same set of values on much larger domains. With a perspecting perspective of lifting in mind, we can see how it

applies to different parts of the stark protocol. Um, we could use the mixed Merkel tree. Uh, but this perspective allows us to actually simplify it at no extra cost. um and it results in a much more efficient and uniform uh verifier implementation. So I'm going to go into that merit tree right now and then afterwards I'll hand off to Adrian to discuss applications to uh the other parts of the stark protocol and the subtleties that are involved there. So the trick with simplifying the Merkel tree is just to forget the mixed merke tree altogether. Instead, we just use a regular Merkel tree that commits to all lifted

traces. But naively, this incurs a larger cost for the prover because there's more values the prover needs to hash due to all of the duplications from lifting. And what we did is we developed a new efficient algorithm to generate these Merkel leaves. And I'm going to show you that right now. So we call the algorithm the memoized Merkel tree algorithm. And here is our unlifted trace. We start by creating a hasher and not a hash. So for those unfamiliar, a hasher is used to generate a hash and it has a very similar memory

footprint. So here we've inserted the trace on the smallest domain. Then what we do is we lift the trace to the next largest domain by duplicating the hashes state and we insert the trace at that size. So we repeat this process. We lift by duplicating and then insert the trace at the next size and we continue doing this. So finally what we do is we finalize these hashes and we've got the Merkel leaves that we wanted before. So that's our efficient memorized mercury tree algorithm. So great. So what we've seen

is we've seen our lifting technique and how we can apply it to get rid of the mixed merket tree and have a much more simple regular milk tree. Now I'd like to hand over to Adrian to discuss how we can apply lifting to other parts of the protocol. Um so Adrian over to you. All right. Thanks a lot, Andrew. Um, so in what follows I'm going to be like looking at how lifting affects the other parts of a protocol. So like how do you lift air constraints or perhaps adapt them uh how that like uh affects like the deep potions where there's some optimizations to be done and like overall like how do you combine that with lowderee tests with a focus on fry.

So again these are traces and from the perverse perspective like it looks like this but because they're lifted you know that certain parts are the same. Uh but for efficiency like the prover really only needs to consider this. So this is a memory footprint and it's going to be able to like duplicate these virtually. From the verifier's point of view though things are a bit different because it really only sees a single trace and this is useful because and as Andrew mentioned like you get a lot more uniformity and this leads to simpler implementations and um and and lower recursion overhead. But and this is really important uh the like the verifier doesn't actually know that these traces are lifted and so a malicious prover could actually inject

data at different uh levels and uh when like it and therefore it wouldn't actually be lifted. And so in most cases that's actually fine as we'll see. But you've got to be careful with some kinds of constraints uh because that might break soundness. And so we have to find techniques to either like prove the diff uh that the traces were actually lifted and we do that using what we call periodicity constraints. Um but we'll also see like what the conditions are on the air constraints to make sure that they can be safely lifted and we call those uh lift uh we call that liftable air. So just a recap like uh we took like a generic uh uh air constraint. So we have like uh it's a transition

constraint. So it's affects it enforces a condition on the current row and the next row and uh we use a selector which uh selects which uh rows it should actually be applied to. And so we're going to be lifting this constraint uh with a map of degree r. So this means that the trace is going to be repeated r times. Again r is a power of two. Um and on the right we have the lifted trace which I'm the lifted constraint which I'm going to be explaining. So when we yeah so like from the original constraint we just uh replace every occurrence with of x by x to the^ of r and so for the current row polinomial that just maps neatly so that's going to be the lifted polinomial and for the next row which is going to shift the current row by the generator of the

smaller trace well that corresponds to shifting the row of the lifted polinomial by the generator of the lifted trace and you can check that algebraically it's it's pretty neat uh for the selector Well, this is computed by the verifier. So, it just has to evaluate it in x to the r this time. Uh but this also has the effect of duplicating the sets of uh valid of enforceable uh points uh periologically over the larger trace. And finally, the vanishing polinomial or the zero which vanishes over the entire um smaller trace. Well, that just maps to the vanishing polinomial which vanishes over the entire trace.

And so as usual when you're trying to prove constraints within a stark well you demonstrate a quotient. So you take your constraint and divide it out by the vanishing polinomial. Um the really neat thing about this is it actually you can just evaluate your constraints over the smaller domain and then lift a quotient. So this is as efficient as if you were trying to do the quotient on the smaller trace. The other really neat thing is that because now all of your quotients have been lifted to the same trace. Well, you can just batch all of these uh quotients together which means that you the prover only has to commit to a single uh quotient polomial. Uh in contrast like current implementations they have to commit to one quotient per trace again using a mixed merkel tree.

So this is this should be a lot more efficient pure hashes. Um but yeah so like the problem is that these transition constraints, right? So usually you you're going to check that in every row it holds in the current and next row. So this is fine up until you get to the last row because here the next row actually refers to the first row of the trace. In practice, we don't really encounter these because it's not like it's mostly annoying and we're usually proving sequential computation and not necessarily cyclic computation. So most systems don't actually use this, but you still need to account for it because that could be a bad thing. It's because like as I mentioned before, the verifier doesn't actually know that each segment is

actually the same one. And so if the prover did commit to different traces, these would be different. And so if we look at the same transition constraint when applied to the last row of the first trace, well, this is actually going to refer to the next row of the next trace. And so this is a problem because we don't have any guarantees that the first rows of each trace are actually equal. And so if you depend on that well now your constraints are not sound anymore. So how do you do how do you prevent this? The first solution is to use what we call periodicity constraints. And this is going to enforce that every row which is uh separated by the size of the initial domain are equal. And so we describe it as a air

constraint which just says like if you take the current row and then shift it by the size of the original domain you get the same value. Um but this is a virtual constraint because it's linear so it doesn't actually contribute to the uh constraint polinomial. Um instead because we're now opening the polinomials at uh the shifted point the check is actually going to happen at the deep uh uh portion of the protocol. So we're going to test this constraint in a random point and uh check that it's equal. the so the steep quotient now instead of just quotienting by uh the the point at which is opened you also have to quotient it by this shifted point and so this doesn't increase the proof size because you're still proving

just one evaluation because it should be equal but it's a bit annoying because you you're going to have to open uh you're going to have to like handle the quotient uh differently for every trace size um it's going to have a little bit of performance impact but again for the verifier this makes it less uniform. So the verifier is going to have to be aware of all of the different trace um trace heights uh for every polinomial. It's safe but a bit annoying, right? The second approach which is to not do any periodicity constraints is to instead give conditions uh where you actually are safe uh in terms of your constraints and the main idea is just

like don't use transition constraints in the last row. Uh generally this is already satisfied by a lot of implementations because you're going to either use selectors or or different techniques to make sure that your constraints don't apply in the last row. Um and but there are some cases like for example there's this optimized uh sum check univaried sum check protocol which does use the fact that the uh the the the running sum wraps around. But in the paper we proved that um we showed that like these can be really easily uh fixed and it shouldn't have too much impact on the overall proving speed. Uh the other thing you can do is uh if you can get the algebraic graph of how you evaluate the constraints, you could just like

statically check that your constraints are either fine or at least detect the edge cases where you need to uh check that it's fine. Um, and yeah, because um because these constraints are like because most projects probably already satisfy these constraints, we think people are going to opt for this one because it's just going to be simpler and it has less ramifications on the rest of protocol. So you don't need to add any transition constraints or anything uh periodicity constraints. The one thing is though that this slightly changes the semantics of the proof because now what the proof actually means is that you've proved our different traces. Um but you really only but that also means that there's at least one trace which is valid and so that's what you care about and so it's

equivalent maybe slightly bit stronger uh but in most cases like those R traces are going to be the same. Um the advantage is that your deep quotients are now simpler. you're just quotient by the same point for every trace again better batching more uniform structure and um yeah so we expect most projects to go with this uh go and if you have any questions about if your constraints are safe like feel free to ask us um so yeah so now when we've done the deep quotient how do you test its low degree well there's actually nothing to do here because you ended up with a single lifted quotient and so you just have to run a regular low degree test with a batch of functions which are all

of the same degree. Um the the um this should as Andrew mentioned this makes it a lot easier to integrate other PCS's like stir or were or what have you. Um we haven't checked it out in detail but we expect it to work pretty uh to work fine. Um and if you compare to like current implementations of fry this multiffry protocol like this should drastically simplify the implementation because you're just handling a single polomial and you can apply optimizations like the uh like different folding factors or different size remainder polinomials. So I know this presentation was called lifted fry and I haven't actually talked about it. Um the that was the original plan right and we have uh we had written up a paper and we had

like these complicated protocols to handle folding at the fry level. Um but just last week Olri was trying to prove the security of the multiff protocol and he realized there's this extra property we had not we had overlooked and if you take that into account into the sound analysis of fry it turns out that you get lifting for free and so it just works with regular fry you don't have to take look at your constraints or proof that they're periodic and the argument should translate also to like other PCS's like stir were bas what have you.

But there's one caveat. Um, this relies on the assumption that the verifier can check that when it opens different rows of a committed Merkel tree that it checks that when you have the same row which is opened at different indices that it's actually the same one. So you lose a bit of the uniformity which Andrew mentioned. So I think I'm running a bit out of time. So like I'll quickly go over this but like the idea is like this is representation of your memorized Merkel tree. But so if you're opening for example rows two and three um the verify just has to check that like you're going to be opening the first two traces at the same row. And so the verifier has to explicitly check that these two rows are equal. Um however if you already have a mixed mergle tree

implementation like this works fine because it explicitly ensures that like these rows are going to be equal. So you should be fine like you don't even need to change any code. But yeah, so if there's one thing you need to retain is really like just a slide is like you take your regular multi multiple traces and then you extend them and you get a single trace and that's just really it makes things more simple. Um why should you fold? Well, it's really cheap actually and because it just involves like duplication which can be done virtually and it should most certainly like lead to better performance, simpler code and so whatever uh flavor you end up choosing and but the benefits go beyond that because like when you have uh like just simpler code well that leads to better maintenance and also

just reduces the attack surface. So like because less code is fewer bugs and like can probably cheapen your audits as well. Um, and with regards to uniform verify, because like everything is like much simpler, well, that's going to reduce the cycle count and therefore like your recursion overhead is probably going to be lower. Uh, which again leads to better performance. Um, but your cryptographers are also going to be happy because this should simplify their soundness analysis because now you only have to consider a single trace. And so in the future we expect that projects should be able to easily uh implement this and even in an incremental way because you can adapt different parts of a proof system. And overall I think this technique does generalize to other uh protocols like PCS's or even some check GKR other

codes. We haven't checked into it but like it should work just fine. And well when it comes to paper we were supposed to release last week. Uh we're going to have to rewrite a lot of it take a bunch of stuff out. If you want a draft like we please DM us or so we can go it but uh just know it's going to probably change a lot. Uh so yeah with that do you have any questions? Thank you very much.