ZK13: Ligerito: A Small and Concretely Fast Polynomial Commitment Scheme - Kobi Gurkan

Transcript

[Music] So today I'm talking about Likarita. Let me first say that this is not my work. This is Andrea and GMA's work, but they're not here. So I'm presenting it. But I'm still really really excited about it because it explores a point in the trade-off space of proving time, proof size, verification time, which I think should be should be explored more. We'll see more about what this point exactly is soon and why I'm excited about it. But yeah, another thing that's really nice

about it is that it is very modular and flexible and there is a lot of opportunity for people to contribute to. So you know modern Legos you can play with it. So that's fun. Okay. First of all, as the name suggests, Licorito is inspired by Liro inspired users I guess. So let's first start with a quick introduction to Lihero. The high level idea of Lihero is that you have a matrix. You have a prover that commits to this matrix. You do some encoding in the middle. Let's

say using some code read Solomon code let's say. And eventually the verifier does some checks and checks that that matrix is close to some unique matrix that was committed during this protocol. Without getting too much into the details, you also get an evaluation of a polomial like of this unique matrix which is at some random point. Keep that kind of point in mind because we'll use this observation later on. This is not the usual way that people look at it. So just keep that in

mind. If you look at it uh more like pictorially you have this matrix, you encode it using some code G. You have this extended matrix which is encoded. you commit to the rows and you have like this let's say Merkel tree and Merkel root and in order to do the verification you you do some you do some sampling you take a few rows um out of this encoded matrix and you also take a random linear combination um of the original matrix you do some checks and the nice thing about it is that you don't have to do a lot of

checks. So maybe 100 200 and you get to good security which is nice. What are the properties that we get out of this kind of construction? One thing is that proving time is really really fast. First of all you do some encoding. You encode the columns of the matrix. So this is very parallelizable like embarrassingly parallelizable which is nice. Then you do commitments to the rows. This is also pretty fast. If you use Merkel trees, it's hashes also pretty good. And then you do a random linear combination. This is what we said about like y R is this random linear

combination. And that's also pretty fast. So good proving time like really really good. Concretely, if you look at a small field which you can use here, even a binary field one second on a laptop from a few years ago for 2 to the 24 coefficient, that's what you get. One downside is that the proof size is large. Specifically, you send a bunch of things from the prover. You send rows of this encoded matrix. you send a bunch of them and you also send this random linear combination, this Y R. If you

construct it nicely and in a smart way, these two things will be roughly similar in size, but they're still pretty big. One example of proof size that you can see in implementations is something like 14 megabytes for 2 to the 24 coefficients roughly corresponds to square root. Okay, but let's leave here. Let's see what we can do with it. Let's look at some stuff, some observations. When I said that we can make we can construct things in a way that these rows and this random linear combination

are roughly similar in size. That's a trade-off that you make in order to get to to that property. But you don't have to do that. You can also look at different different matrices or different shapes. One thing that you can do is you can instead of looking at something that is roughly square root in size of dimensions you can look at a matrix that is tall and skinny many rows less columns. The problem with that if you use that directly in the harrow is that it would increase the size of y r and that would create a like bigger proof size. Another observation

um which will not be obvious to see but I will say it anyway is that you can merge some checks with liarero. Specifically, if you look at the sailor sum check, it has an interesting structure where also during the protocol you have some randomness and eventually you you get to the point in the sum protocol where you evaluate a polomial at some random point. And that's similar to the observation we looked at in the beginning which is also what leero kind of gives you. So combining this because

of the structure works out pretty naturally and because of this property you also get some nice composition. So the observation that I want to make here is that some check and lio can be combined nicely. What that implies is that because of that we can get inner products with the entries of the matrix we committed to which is pretty nice. Another observation is that you know when we talked about tall and skinny matrices we said that y r is going to be big. Currently the verifier gets all of

it. But actually when we do the check that that we do eventually as the verifier we only check a few rows of this Y R or more correctly we check a few rows of like the encoded version of Y R. So do we really have to have access to the entire Y R as a verifier? Maybe not. So another way to look at it is that we do a few inner products with y r. Okay. But wait, didn't we just say that subject plus lero gives us inner products kind of for free? H maybe we can use lero to verify

itself in some way and some intuition around it. If instead of looking at liarero only on the initial matrix, what happens if we use liarero on a reshaped version of y r itself? Then we can use this combination of some tricks plus liarero to get us in products. That could be nice. So yeah, you can do recursively hero and you end up with pretty good things.

Let's talk about licorita specifically then and what we get there. High level we take a matrix we commit to it similar to what we did up until now. We receive some randomness. We previously would have sent y R. But that's not what we do anymore. Instead of sending it, we now commit to it some reshaped version of it. And we now use this observation of combining the hero with a sum check to help the

verifier and to do these inner products that are needed for security. One thing to note here is that this is not only something that you would do to let's say help the prover to to be nice or like for performance even as the verifier you just don't have access to y anymore you just have access to a commitment of it but that's all you need in order to run the sound check okay now we did this process and during this process we, you know, go through the Liharero sumic process

and instead of having to work now going one step further, instead of having to work with an original matrix and a random linear combination of it, we now take a random linear combination of what was already reduced in size. So this is a much smaller vector that you know called here ZR prime. And again some pictures. You start with a matrix. You encode it. You get this random linear combination. You use the plus sum check.

you have this reshaped Y R and you you help the verifier with the inner products and eventually you end up with a much much smaller matrix and that's essentially liaro that's like the high level insight of how it works like the details of it and the implementations are not as nice but it works out and yeah so not here like this that picture is just one iteration Yeah, you can continue doing the same process exactly many more times until the trade-off just doesn't work out. But practically, and you know, it

wouldn't be a GMO paper if we didn't have a convex optimization problem. So you can write this as a convex optimization problem and you end up with nice numbers that you actually need something like three or four iterations that like that's more than enough for two to the 30 coefficients. Let's say do note that after the first iteration where we already got to this ZR prime this is already pretty small like this is already small compared to the original matrix. So the first iteration pretty much dominates. So you want to improve that

iteration really well. So the time is similar to normally hero because this first iteration dominates but the proof sizes are much smaller because you don't have to send Y R you don't have to open big rows anymore. You can just keep reducing it um as much as much as you can. How much? These are some numbers. So let's look at the biggest one to the 28. If you just did naively the hero, you would get something like 3 megabytes. Licorito gets you something that is like an order of magnitude

smaller. Uh and also the timings are pretty good and you can see that for reasonable instances of the problem you get good proving times on a consumer laptop from a few years ago. It's like 1 second for 224. But also know that this is like Andrea working through nights and implementing this in Julia. So you know who knows if any of you wants to do it with rust and more time maybe this will be much faster as well. So if you look at it differently a

bit you add a little additional proving time you get much smaller proofs. Proofs are pretty like proofs are completely pretty small, smaller than 500 kilobytes and can be realistically done on a laptop or a phone for for reasonable problems that we care about today. And I will say that if in even if you talk about larger circuits like two to the 30 there are many ideas that can be explored and the team is already discussing it with a few people that there are different ways that you

can probably improve proving time significantly. One thing to think about [Music] is we said about we said that you use a code. So the implementation currently uses read solomon codes. Maybe if you use some kind of different parameters and linear time conable codes that could work better. Um the trade-offs still need to be explored exactly how to do that. But something something that can be done.

Uh I will say that one downside of this current construction is that the verifier time is not the best. It's it's not exactly linear but it is close to it. But also here there are ideas and I know that that already people in the audience have contributed some ideas to how that can be improved but maybe more of the verifier work can be offloaded to the prover in a very performant way.

So this is like where I would say that what kind of excites specifically me about this point in the trade-off space is that you know fast proving times are going to be really important in my opinion and if you have fast proving times reasonable proof size and especially if the verify time is already reasonable but maybe can improve further. That's that's a really interesting point to explore more. We don't always have to optimize for that very far time point in the space. So

something to think about and there is another spicy take that GMO posted a few days ago about how people have been constructing blockchains wrong. So also would recommend checking out that post. Uh yeah, if you want to check out the implementation in Julia, you can go here and also can have a read of the paper and give feedback. And yeah, that's pretty much it. All right. Surely we got a question or two, right? Yeah, that's one.

Hi, I had two related questions. At the very end, you said the verifier is linear time. Is that right or did I was confused? And then also, how does this compare to fry? Like is there some limiting case where it becomes fry or is it is it different? Yeah. No, great questions. Uh I will answer what I can. So um it is close to linear. It's not exactly linear. If you look at the paper, you will see it's something like n to one and like n to the 1 - 1 / l where l is like smaller than equal to 4. Basically it's the the dimensions of the it's

roughly the dimensions you have of the matrix after the first iteration. So that's kind of what you get in terms of verifier time and a lot of it is about the fact that you need to have access as the verifier to to rows of the the code matrix. And that's something that's not super trivial to compute and especially you need to do a couple of operations with it. But maybe that can be offloaded like that's something that there is good intuition that there is a lot that can be done there. And in terms of fry like an in-depth comparison would be good but one point of intuition to have

here is that when you use fry you you sometimes need to do let's say an encoding on the entire thing. Let's say you work on the problem 2 to the 30, you need to do an encoding on like two to the 30. Okay, screw that. Um, and here when you do the encoding, you actually do it on the columns of the matrix. So it could be something much smaller. So let's say that the matrix thinks about reducing the number of variables you work on by like six each time each iteration or like six and and that would allow you to just encode much smaller problems. So

and you can paralyze it so it's pretty nice. Yeah. Thanks. What else? Any more questions? We do have time. Yeah. Oh, sorry. One thing I forgot to mention. So, we do like I mentioned like that there's a lot of flexibility in Legos and one of the flexibility points that you have is that in each iteration you can actually use different codes. So maybe for the first iteration you would do a linear time encodable code for the second iteration you would go to read Solomon. So there's a lot to play with here and currently the current benchmarks and the current work is using just read Solomon but if anyone wants to

try different combinations that could be really interesting. Yeah. So where would you see this getting used in the world then you know where snarkbased systems exist and there's other options as well like what's what's the use case for this? So I I think like basically you can look at it in many different places but two prominent ones might be one is client side proving where you have to have really fast proofs and especially like you you can delay user experience too much and like that's an important place. So fast proving small proofs fits client side proving well as long as the verify time is not like

horrible. Um, and another one would be maybe if you're thinking about like blockchain compression kind of use cases because you can you can work with proofs that optimize for verifier time like you know you can do growth 16 but then you pay really high costs when when you do that and you need strong machines you can pay that but maybe you don't have to if the verified time and proof size are already reasonable. So that could also be a really nice target for it.

We do have time for another question if there is one. If there is one. Oh, in that case, thank you very much Kobe. [Applause]