# Ligerito: Modern Legos - Andrija Novakovic | Bain Capital Crypto

- Channel: [ETH Belgrade Community](https://streameth.org/eth-belgrade-community)
- Date: 2025-10-07
- Duration: 19:24
- Watch: https://streameth.org/watch/yt-lWS4JTzaUwM
- YouTube: https://www.youtube.com/watch?v=lWS4JTzaUwM

## Description

Ligerito: Modern Legos - Andrija Novakovic | Bain Capital Crypto

## Transcript

This is the the new work that I published with my colleague Gilerma uh a few weeks ago and happy to present it here. So uh on this talk I'll try to give like a quick overview of techniques and maybe keep it a little bit more high level so that we can discuss some implications of this but more than happy to dive into uh deeper stuff later if you want and we can we can spend some time on it. So uh as the name itself says uh it's based on uh previous work uh that's called Legerero Leero I I don't know like you can choose uh and thus you can choose how you call our paper based on how you pronounce Leher. So uh today we'll just go quickly through what Lehero gives us and just very briefly with some seemingly very stupid observations which will then build up to what we call leerita now. So um not sure how familiar you are with this stuff but uh in general uh Lehera is a really nice paper very useful and uh just on a very abstract way it allows prover to uh commit to some matrix by first encoding it and then it can prove that uh what he encoded is uniquely close uh is close to some unique matrix. matrix. Um, it makes a lot of sense when you work with coding theory, when you uh work with codes, when you want to test if something is close to code words etc. For us uh it will be interesting in a very uh seemingly nonrelated way. So uh you can actually represent the evaluations of the polomial you want to commit as these matrices then encode them and do a lot of tricks to get a polomial commitment scheme. So since you're on this stage I guess you know that once you have a good polomial commitment scheme you can get snarks zk snarks and that's kind of the backbone of every modern snark um okay so um I'm not going to go into details but um essentially especially for multilinear polomials they have uh very nice tensor structures so you can very nicely pack them into this matrices or hyper cubes and like partially evaluate them etc etc. Uh but let's keep it high level. So uh before we go into what we do let's just uh look into this very uh complex picture of how Lehera works. So we have some unique matrix Xtilda and we encode its columns with any code you want and then uh what prover does it commit to rows of this matrix via Merkel tree um or like any other vector commitment but practically it's always Merkel tree and then uh what happens next is that verifier sends some randomness as we always do in snarks and uh prover sends the matrix vector product of the matrix it has in its head uh or what he claims to have with this randomness. So uh after sending this uh vector we call y r that is in the red I don't have a pointer sorry for that um then uh the protocol is very simple uh it just uh checks uh some inner products between random rows of this matrix with the vector that verifier sent. So if you remember uh we said that uh the rows are committed via Merkel tree. So prover can open these rows and verif. So it's very simple but extremely powerful protocol. Um the main advantage is that it's super fast. So if you use efficient code, you encode this columns very efficiently. you commits to rows. It's just like a bunch of hashes which are very uh very fast and you just do some random linear combinations which is essentially also very fast on modern hardware and uh very important fact that we also use a lot in our work is that um the most expensive parts of this computation are fully parallelizable. Um so if you want to uh work with some uh binary field extension say 2 to the 32 um you can commit to very large polomials on like your normal laptops with just like around 1 second. So it's quite fast. Um the I would say a problem is that proofs tend to be large and when we say snark we want to have small proofs and efficient verifiers. So for example for above mentioned polinomial of 2 to the 24 uh the proof size gets to be like for optimal dimensions and packing you get around 825 kilobytes which can be large for what for the modern snarks we want to achieve. Okay, so you can actually see some very stupid observations and uh this paper somehow make sense and observations are seemingly very simple. So you can do a lot of uh smart stuff if you want to like optimize uh this proof size. So you remember we said we have this matrix. So like you can have a very few columns so very like uh shrink matrix and then these rows tend to be very small and you reduce proof size but then you have like another message called y r that then grows larger. So it's kind of you cannot optimize for both and the main observation of our paper is that you can actually merge the sum protocol which is a very very uh fundamental protocol in a lot of multilinear uh snark stuff uh with leer and um this is kind of the the the core fundamental thing that we do in our paper and you can be you have to be like smart how you combine randomness which rounds how you fold uh but that's maybe for like more detailed and more matty talk. So uh the kind of the core idea is if you have these tensor structures of your multilinear polomials when you pack them in these matrices and you do this matrix vector products they uh are equal to partial evaluations of your polomial. So what you can do is you in a few rounds you can actually partially evaluate your polomial until the very end where you get the full evaluation of your pol and having the polomial evaluation in random point gives you like PCS which you can use again to build very efficient snarks. Okay. So you need to compute like a lot of inner products as we saw on a very far side and the core idea is that you can actually delegate that to the untrusted prover via some track and combine everything and magically get a very nice. So um in like pureo what happens is that the prover just sends this y and then it just uses a few spots of this y vector. So the whole idea and again you can see this pattern happening in a lot of uh snarks how we build them is you essentially put all of that cost back to the prover to make uh efficient verifier and minimize all the work that he needs to do and the stuff that it has to see. So right now if you have a sum check and leerero you also get just inner products for free. Um so it's not just that you have a PCS but you also have an inner product for free and then if you have an inner product you can also build different kind of snarks. So it kind of all makes sense at a very high level. Okay. So then uh what people tend to do when they want to get like succin actual snarks and like very small proofs um that's like recursive wrapping. So you have like uh something you prove something you take that proof and then you also prove that you have seen the valid proof so to say. Um so the idea here is uh the idea here is very similar. What you can actually do you can verify hero within self and then recurse that many times until it gets something very succinct. Okay. So yeah this meme you can just do hero in hero by doing leer itself. Very weird. Okay. And then that's why we call it actually leherita. So you start doing the same thing. You have some unique matrix. You commit to the columns of this matrix by first encoding the columns and then sending it v again same tree. You get some randomness and you send Y R. Okay. So what's the difference? Now we don't want to send Y R because that's the whole uh problem of just using the normal a hero and that's where the proof size explodes. So what you can do instead of sending it you again just commit to that Y R and then just imagine that somehow magically recursion will solve this for you. So you can just proceed to the next round and prove something on that Y R and you use uh the soundtrack protocol to somehow glue all these intermediate steps. at the very end you can like have a very easy inductive proof that everything was correct and everything made sense. So leherito then becomes just like a lot of or I would say a few leer things which are together glued with like one big protocol that is also partially being run in parallel. the mechanics of it are a bit complex until you get like really deep into it. So it's like sounds stupid but actually it's very powerful. Okay. So after you solve some convex optimization problems you can compute this like optimal dimensions. I'm not going to go into there now, but for practically everything we need now, which is like around 2 to the 30 coefficients polomials for like larger ZKVMs, um you just do like three or four these recursive iterations which makes it very efficient practically. So um like I would say that around 90 but even more percent of the time that you spend on prover is in this first step that you would actually do the normal a hero. So you pay extremely little on the prover side on the prover side on the like computation part but you actually get a succinct argument which is again why we need snarks right. So um just to show you some numbers. So we'll just compare to Leher um we can compare to other PCs but that's like not going to go there now but in general the asytoics were like square n where we run in like log n square over log n doesn't matter but like just look into this numbers it's way better. So for example for 2 to the 28 you have a extremely small proofs which are like just 360 kilobyt. Okay that's not that that's not all. Uh the implementation I have is uh like written in only a few weeks and I was running it on this laptop. So like very like personal MacBook without GPUs, without uh some like crazy amount of cores etc. just eight cores and like the numbers are insane. For example, you can get two to the 30 polomials in just 80 seconds on a personal computer. So if you remember the beginning of the talk the every part every single part of this computation is fully parallelizable and it has very low like memory pressure on the prover. So essentially this linearly scales with amount of cores you have. So if you have 64 cores you can actually divide this numbers by eight. So I I would say with like more engineering and more hardware people who are not me uh you can probably do two to the 30 on a like in just a a few seconds on your personal machine which is insane. Um and right instead of having like a bunch of megabytes it's very practical. you get like for two to the 30 under uh under under half a megabyte of the proof size. Um if you're more familiar with like phones and stuff uh if you're smart and like if you manage memory correctly, you can get like a a very huge proof sizes and very huge uh polomials on your phones. Um which is again something that we were not sure was possible before this. So um the implementation is open sourced on our uh GitHub. You can also find the link to the paper on this cure code. So right like uh I think this might be like a very big news for snarks. uh we really I think unlock a lot of potential what people wanted to do for many years and you can have uh phones and computers being disprovers and since everything is like parallelizable and so independent you can have uh like a lot of other very light verifiars who can just sample a parts of this proof and it gives you like a very complex data available ability schemes which also means that we might even redesign how our like today's blockchains are working. Uh you can achieve a lot by just having the phones being like uh a good enough to do either like some proofs or just to verify a chunks of these proofs. So um it's like field agnostic but it's extremely like efficient on binary fields and we know that our computers are built for working over binary fields uh which I think it makes it even stronger. Um there are other uh like other theoretical uh aspects of this which I'm not going to go there but there is also some stuff called code switching which this paper gives us implicitly. Um so essentially at any round you want you can use a different code which is also like completely different uh theatics but you can do a very smart stuff to like have even even faster provers than what I showed because I was doing it like kind of read Solomon codes with a constant rate. Uh you can change rates over the rounds of faults. You can change codes. you can do a lot of smart stuff depending on what you need. Um and yeah having uh two to the 30 polomials being run on your computers should definitely be something very huge that we hope to get in the recent year in the next following years. Um my time is over right. Yeah, >> there is a question. >> Um, thanks for the presentation. Uh, I will definitely check out the paper. Um you like you also showed some like you know like some like optimization ideas regarding the size of matrices and rows and columns and also uh you at the final stage you said um it's pos yeah yeah it's possible to use different you know fields uh in different you know um time like steps. So I'm wondering would >> uh no different fields in like you have one field but you can use different codes in different rates. Yeah. >> I just thought like at least in the opening round would it help to you know use a smaller sub field. >> Yeah sure. Yeah. Yeah. Yeah. So what that's what we do you can have like uh your argumentization of a very tiny field and then anyway in the later rounds you have to use the big enough field extension. Right. Yeah. >> So yeah that's how we do it. And the first round is the biggest one where you have the smaller. Yeah. Yeah, that that that's right.