Episode 361 - Implementing Latticefold with Matthew and Albert from Nethermind

Transcript

[Music] Welcome to Zero Knowledge. I'm your host, Anna Rose. In this podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise to change the way we interact and transact online. [Music] This week, Nico and I chat with Matthew and Albert from Nethermind. We cover some of the research topics they are exploring at Nethermind before diving back into the topic of lattice-based CK systems. Matthew and Albert have been implementing lattis fold, a folding scheme that is built using lattises. And in this conversation, we tease out some

of the challenges and opportunities that such a system introduces. Quick note, I'll be taking the next two weeks off the show and we'll return with regularly scheduled episodes on June 4th. In the meantime, do check out our YouTube channel. There you can find the videos from ZKS Summit 13. So if you missed the event or just missed a few talks while you were at the event, you can see them there. And do remember to subscribe. There is also another event coming up. There is a ZK hack hackathon happening on June 20th to June 22nd in Berlin this summer. So if you're looking to jump into ZK and actually start building with this stuff, this would be a great place to check it out. Find out more at zkblin.com.

Now, here is our [Music] episode. Today, Nico and I are here with Matthew and Albert from Nethermind. Welcome to the show, Matthew and Albert. Great to be here. Thank you. It's a pleasure to be here. Amazing. Hey, Nico. Hey, Anna. Hey, Albert. Hey, Matthew. So, we recently did an episode on lattisbased CK systems with Vadim from IBM Research. And in that episode, we really did an intro to lattises and how bringing them into a snark context is a challenge, but also has some amazing payoffs. In today's episode, we're going to be diving a bit deeper into some of the cutting edge constructions. We're going to talk about lattis fold, a folding scheme that relies on lattises

in a major way, the challenges of implementing these types of lattice systems, and hopefully do a deeper look into where the space is moving. I think a way to think about this is the first episode was from the lattice perspective looking into ZK and this time I think we're coming more from ZK looking into lattises. I also know that at Nethermind you've been producing a ton of great research so hopefully we also get to talk a little bit about that later on in the show. So let's jump in. I think a good starting point would be some quick intros. Albert you've already been on the show. You were here actually talking about the security of Fry. We're going to be talking about something quite different this time. So it might make sense to just share with the audience what you've been working on kind of what

your focus is today. So when I was at the podcast the first time besides talking about the fam security of Fry and Starks, we also talked about proving uh statements over over rings for example. This is one of the problems we've been working on over over these three years and recently we published our conclusion to to this work which is called ring. M it's available online. We are quite excited with it. We have also been working on well latis based folding. We we implemented latis fold. We've been doing some internal research uh around it. We also looked at lookup arguments and how to fold them. We published a folding argument folding scheme for for lookup arguments called fly with Ignathio. We are also working

on ZKML. We have several ongoing projects. We are working on it from from different sites. we we are trying to do proof of inference via folding and because in ML there's lots of repeated computations. So the the circuit in in a large language model or a machine learning model is um it consists of a lot of layers, right? And each layer is it's the same as before but with different inputs. So it's it's very aminable to to folding. So we have an engineering team on that right now. That's really cool. If I remember correctly, there was a project called Zeter that did this back with like the very first version of Nova and R1CS. So there's a lot of new tooling since it would be super interesting to see what you guys get up to. Yeah, we are also

exploring other ways of doing things like inference of ML but without actually proving the entire ML model like trying to be a bit smarter rather than just proving the whole thing because for some applications proof of inference will never be fast enough and let's not talk like if if we go into proof of training then that's a complete mess. So we are trying to look at smarter ways to to go about it to to achieve a similar result without uh actually proving the entire thing and yeah we've continued looking at several sec uh security questions around fry and very important you recorded a ZK whiteboard session. Oh yes yeah that was that was the highlight of the of these

three years. Yeah for sure we can link to that as well. It came out in season two uh just recently. All right Matthew this is the first time we're meeting. Why don't you share a little bit about the work you've been doing, what your role is at Nethermind, and yeah, kind of maybe your interaction with Lattis space systems as well. Hi, my name is Matthew. I'm a cryptography engineer at Nevermind. I joined as an intern just after I graduated last year and uh they've been kind enough to keep me on. When I was an intern also towards the beginning of my full-time tenure, I worked on the lattis fold project. So, very much to do with latises and the folding techniques we'll hopefully be discussing later. I also did a bit of work researching the PU signatures, the postquantum signature work that we're

doing. And uh as of late, I've been working on the zinc project with Albert. It's a new proof system um that's currently online as of two months ago. Nice. So the first thing I wanted to ask you guys is sort of what does the landscape of lattisbased ZK look like today? Is it all folding or is there very different techniques? And in general, how does it compare to like pairing based or hashbased techniques? Okay. So, this is a a long question to like it's a question that has a long short question with a long answer. Yes.

Good. And there's two two questions in it, right? There's um what has been done so far and how does it compare to other existing schemes? You could write papers about how latisbased schemes compare to elliptic curve based schemes or hashbased schemes. So but uh let's try to answer. So there's one area of development where that's related to folding right there's all these new schemes that are based on on latises. They are folding schemes based on latises which I think they they have kind of become a hot topic lately in the space. I I hear a lot of people uh mentioning them and I I see there's a lot of interest in them. Outside of folding I'd mention Labrador and Greyhound as very exciting development.

So, Labrador is a snark that's uh that's relies on on latises. The the main feature of Labrador is that it produces very small proofs and the main drawback is that it has a a linear time verifier. So, it's not a succeed proof system. But if if you care about succeed, Labrador might be a great wrapper around something that's that is succinct. That's very reminiscent of like bulletproof style things in in the discrete lock setting, right? where you have tiny proofs but a linear time verifier. Yeah, Labrador in fact is some kind of bulletproof scheme but ported to latises which uses a a very interesting technique which is called um Johnson Linder Strauss lema uh for proving um

norm bounds. Uh, Greyhound is a polinomial commitment scheme that uses Labrador as a wrapper to reduce proof sizes and yeah, Greyhound I think is an extremely exciting well I find Greyhound a very exciting PCS. It's a a PCS based on latises. It has the the numbers published in the in the paper are are really good both in terms of proving time verifier time and and proof size. I think this is one Don refers to mostly in his episode uh end of last year on latises. Can I just do a quick word check and maybe I do know this but PCS what does that stand for? Yeah, it's a polomial commitment scheme. Oh, okay.

Got it. Yeah, the polinomial commitment scheme is kind of the key piece of a snark. It's the most complicated one to design. It's usually the most expensive to run uh etc. So if you have a nice PCS, you usually can build a a nice nice. I do know a polinomial commitment scheme I'm familiar with. I had I I wasn't fully getting the short form, but glad you shared. This is deep down in the lingual of ZK. Yes, I have a a pajama with PC, the PCS words on it. You're not wearing it right now, but that's No, no, good to know. The two that you just mentioned, Labrador and Greyhound, those are, as far as I

understand, aren't those quite like they're quite lattisy, but then you have things like lattice fold. Is Lattis fold also a continuation of that work? Is it an implementation of that work? Like how did how does that kind of compare? Labrador is a proof system. It's not a snark because it's not succeed. It's a proof system that produces very small proofs and greyhound is a polomial commitment scheme which can potentially be used inside a snark based on latises. Okay. Then latis fold and latis fold plus and neo and lava are folding schemes. Okay, so folding schemes are are not proof systems. A folding scheme is different from a proof system in the following sense. A proof system allows

you to prove that certain computation was performed correctly as listeners probably know or actually it allows you to prove that you know a witness to certain um certain MP relation for an instance of an MP relation. A folding scheme is different in that it allows you to take two instance witness pairs or two instances. So two two computations and produce a new computation a third one. So that is if this third computation is correct then the previous two were correct except with negligible probability. So latis fault is a is a latisbased scheme but for a for solving a different problem. Okay. What do you mean by a different problem? Well the

problem of designing a folding scheme or the problem of designing a a proof system for an MP relation. So, so Latisfault designs a folding scheme and um Labrador designs a a proof system for MP relations and Greyhound is a PCS. You can you can use it to compile a POP over a a latis to get a sax argument for latises. Right. Right. Right. So you could use Latisfault to combine a bunch of problems into one and then use something like Greyhound Labrador to prove that one problem. Exactly. Yeah. And you'd have a full Latis only stack.

Yes. Interesting. But could you also use things like lattice fold within existing systems? Like do you have to have a lattice-based system in order to use that folding scheme? No, you can potentially use latis fold to to fold um instances of your relation and then when you are done use a different proof system to prove the the folded relation. That's actually one area we are looking in. One problem we we have been studying is the problem if of how to do folding in the context of of starks. So say your whole pipeline are starks. Uh you want to use your stark proof system for proving uh your statements but you also want to do folding right maybe to to

reduce proof sizes. So we we've proposed some frameworks that rely on on latises. So you you use latises to do the folding and then you use your start proof system to prove the folded instance. Yeah, there there's another natural way of going about it which is using these hashbased folding schemes that appear recently namely arc and this new one which is called warp. I think I I think it it came out on on Monday. I'm not sure because there was the blackout so I was out of of air print. So, we've talked a lot about different lattice schemes and we have the proving schemes, the folding schemes. What does the tooling look like right now? Say I'm a developer and I want to work with

latises. Uh I've done a bit of I don't know worked with arc works maybe in the past or plunky 23 and I want to work with latises. What can I do? Well, so there are existing implementations of all of the basic cryptographic primitives that you'd want. So, let's say you want a signature scheme. We do have the NIST uh finalists will have to submit an implementation and those implementations do exist. There is some limited work going on which is like porting those schemes to new languages. That's very very much emerging work and the same could be said of all of these schemes that we're talking about. So Labrador has its implementation. Um we've done the implementation of Latisfold. These are very much emerging works and the implementations are very

much proof of concept implementations. If let's say you want to I don't know you want to use it on on like Android Blaze platform there's a heck of a lot of work that's going to need to be done before we get these implementations out of the academic space. So I would say that in general if we're talking about latterpased uh ZK or lat space cryptography the tooling is rather limited at the moment. The caveat I would add to that that the area of cryptography or latisbased cryptography that has attracted the interest of major tech companies is homorphic encryption um which you can talk about later and that has a much more developed infrastructure more developed tooling.

Okay. And so in the case of Latisville did you guys start from scratch or are you trying to normalize things? Um so we did use arc works libraries to a certain extent. Um but a lot of the work was done you know completely sort of hand implementations of stuff. So um artworks has a field library well known to anyone in the cryptographic engineering space. So we use their field stuff. We had to work over rings cuz there's lates and all the structured latises uh work over rings not over fields. So we had to handlement a lot of functionality that's a lot of that's open. So that's in our stark rings uh library. And then of course the Latisfold stuff it's fresh out of the academic press so that was

all hands implemented. So maybe before we dive a tiny bit more into the implementation can you guys give us a quick overview of latisfold like what are the main components and how to think about it from a high level the folding technique maybe where does it come from if it's taking from any other previous system as well. Um right so the folding technique I think was introduced by Valiant in 2008 and before it has been ported into the postquantum space so via latises um had some works via elliptic curve based schemes called nova and hypernova as well I think yeah we covered those on the show fantastic so that those works very much inspired latisfold but again because it's all elliptic curve based so not postquantum

secure so latisfold was the first latisbased folding scheme in the hope that is postquantum secure. My understanding was that it's a a variant of hypernova that's made sort of latis friendly, but I'm not sure what that means and sort of how to think about it. Yeah, I think that's a correct take. Uh let's unpack it a little bit. So let's start with hypernova. So in hypernova there's lots of shenanigans going on and then there's a very important thing that happens which is that you take linear combination of the commitments to the witnesses. So witnesses are always committed and when you are done folding you linearly combine the witnesses into a new witness. Yeah. So we do witness plus something random times the other witness. Yes. And the verifier gets a commitment to this new witness using the

fact that group based commitment schemes are homorphic. And this means that the sum of two commitments is the commitment of the sum. So if you commit to two vectors and you sum them, you get the commitment to the sum of the two vectors. I was going to jump in with the nitpick that they're additively homorphic, but anyone who understood understood that they're additive. Yeah. So, we say that the commitment is additively homorphic because the commitment to the sum of two vectors is the sum of the commitments to the vectors. And if we replace sum by multiplication, then we say that the commitment is multiplicatively homorphic. But those we don't use, right? We're just focused on additive here. Yeah. In in folding, we use additive um omorphic commitments. And if

they are both additive and multiplicatively homorphic then it's fully homorphic and we are very happy but it's hard to build those. So okay so if the if a verifier has commitments to do to two vectors and the commitment is additively homomorphic it can get a commitment to a random linear combination of the two vectors by randomly combining the the commitments. And this is super cheap to do because it's just I'm adding commitments together and life is good. I don't need to look at long vectors. Yes. So this is done in in hypernova. It is a crucial step but it is a step that's very small in hypernova because it's extremely simple because of this omorphism. Now in latises you have a natural commitment scheme which is

called itai commitment that works as follows. So the if you want to commit to a vector of field elements the commitment is the result of multiplying a matrix by the vector. That's the commitment. Matrix multiplication is a linear operation. So this suggests that the this commitment scheme is additively homorphic. There's a small issue which is that because of the properties of the of latises the commitment is only binding. So it's only secure if the vector you are using has small entries. Okay. So there's some like maximum limit on how big my numbers can be and if I go too big I lose security. Yes. Okay. So if you take a random linear combination of your of your two vectors then the resulting vector might have large

entries right because you are taking you are adding the first vector and then adding a random multiple of the second vector. So you have a a vector with arbitrarily large entries. So you can no longer use additive additive omorphism as easily as in hypernova when you use this commitment scheme because you might end up working with vectors that have entries that are so large that the security of the commitment scheme is lost. Right. And so most of the work in latis fold is to fix this problem. Exactly. Yeah. So latice fall you just do the whole hypernova over rings or latises a different structure plus extra steps to make sure that you are never committing to vectors whose entries are

too large. And in the paper that's called the decomposition step. Yeah, there's a decomposition step and there's also a norm check step because you need to make sure that it's not only about the composition, it's also um proving that the norm of of what you are committing is small. Mhm. And so how does all this extra work affect uh sort of performance of these schemes? Yeah. Is there an improvement because of this or does it actually hurt it? Well, so you have to do more work, right? Because you have to do the whole hypernova and then you have to do extra things to make sure that the you don't go beyond a certain magnitude in the entries of your vectors. So in this sense, this adds overhead. On the other hand, the ITI

commitment is particularly cheap. So there's several pros to using it commitments and latises that might outweigh the fact that you have to do extra work because of this nonomorphicity. And when you say cost, you're are you talking speed? Is it sort of like the itai part makes it very fast but then there's some slowdowns because of these other workarounds basically you need to make. The prover has to do more work. Okay. Exactly. Yes. Yeah. So in hypernob it turns out that the the bones of the II commitment are not are not enough to compensate for the extra work that the the prover does. But if we start talking about Latisfault plus and neo or a combination of both it seems

that uh we we get something that's possibly more performant than than curve based folding schemes. Oh cool. So I was going to ask actually about the implementation itself and sort of what are the lessons that come from it and it sounds like we're kind of skipping ahead to this which is great. I know you also gave a talk about this topic Albert recently. So yeah, let's go straight to the lessons of this implementation like how how does it compare to I guess folding schemes that we already have in the discrete log setting and then how does it compare to just the almost like more brute forces like I'll just do recursion of Starks you know the thing is it's kind of difficult to compare because there's lots of dimensions you you might look into right so first thing we can say is

is we can talk about plausively postquantum security right so the elliptic curve base folding schemes are not uh postquantum secure. Mhm. But the latisbased ones are plausibly and also the hashbased ones are. And you could argue that hashbased ones are more postquantum secure than latises just because these latisbased schemes rely on on uh cryptographic assumptions that are less understood or they are they are less um less battle tested. Exactly. Less battle tested. Yeah, exactly.

That's the word. Uh yeah, they rely on on this latisbased cryptographic assumptions on structure latises which yeah they they are not that battle tested. There's another angle which is the arithmetization part of things. The elliptic curve base folding schemes work over particular fields. So they are very rigid on on what what your computation work can work on. Elliptic curve based schemes force you to work over a large field of about 250 bits at least because you need a an elliptic curve and possibly a pairing on it. So a pair of elliptic curves and this um leads you to work with large fields because there's

no small fields and and pairs of elliptic curves. So working with large fields can force you to work with circuits that are larger than what you would like to because maybe you want to prove some computation. So a CPU computation which is not naturally written over a large field. So you have to rewrite this computation over a large field and then you end up working with large circuits. So even if maybe your folding scheme is very good, it's elliptic curve based and for a fixed witness size, it's very performant, but then it turns out that for what you want to prove, you end up with very big circuits and maybe it's not worth it.

The hashbased schemes allow you to work on smaller fields, but still they force you to to stay on a field which can be it can also lead to large circuits, but small fields are easier on the CPU. Yeah. and you don't have the sort of overhead effect that you were talking about when you actually run the algorithms. But this the circuit might might also be bigger depending on what you are computing. Everything I said is not specific of of folding schemes. It applies to any ZK system you can think of. I want the real numbers from the implementation. I don't know the meaty stuff. Okay, let me shut up then and give numbers. Okay, so yeah, the ITI commitment scheme is is very fast. So when you say fast you mean compared to Merkel trees or compared to

like these multiscaler multiplications that we would do with KCG or Person commitments? I mean compared to to both. Okay. So we can compare it with hashbased commitments. The main commitment scheme we compare it to is Merkel trees, right? Because if you are using hashes, you're using Merkel trees at least nowadays. And and there's two types of Merkel trees. There's Merkel trees where the hash is a classic hash like ketchup and there's Merkel trees where the hash is an algebraic hash like poson 2. If you are using folding the hash is likely posed on two because you want to recursively prove that the folding is done correctly. Turn it to be circuit friendly and therefore we have

one of these arithmetic hashes. I'm reading some of our benchmarks. So I see to commit to um a vector of size to 2019 with a blow up factor of two. So we do a read solommon encoding of of the vector which is also you all you need to do when you work with hashbased schemes with the merrip using procedon 2 it took us in our benchmarks 1.8 seconds. Now committing to 2019 field elements with itai commitment took us around 600 milliseconds. By the way, are these benchmarks? Can we also run them? Like, can we have a link to it and put it in the show notes? Um, I don't think we have the link right now, but we can provide it. That'd be amazing. Okay, so

the commitment is a lot faster. It's it's faster if if you use poson 2. If you use Ketch, so committing to 2019 field elements with a blow up factor of two with KAG is 387 milliseconds in our benchmarks. So, it's half the time of it, right? But it is potentially recursive friendly because it's very simple algebraically and ketch is not recursive friendly. And when I say that it is simple algebraically, I mean that this if you write a circuit where you compute that the commitment so the circuit is true if the it commitment was computed correctly. This circuit is much smaller than if you write a similar circuit for the kak hash function. So

it's not very practical to do recursion if you are using ketch hashes. Right. So, do you also have like end to- end comparisons of folding many things together, seeing how long that takes versus recursively proving stuff with hashbased schemes? No, we don't have comparisons. I guess that'll be the next steps for for those interested in contributing, right? Yes. Uh, by the way, we welcome contributors and maybe we can go over a list of projects we we have ongoing. We are really happy to if if people is interested in tagging along and we are completely open source so just reach out to us and we'll be really happy to to collaborate also on on the research side of things not not only on engineering side of things on the

lattice front are you doing research at nethermind or are you doing mostly this implementation we are doing some research oh so like we may eventually see a paper come out where you've like created one of these techniques or like a new system or something. Yes, we actually spent some time thinking of a latisbased scheme um that doesn't folding scheme that doesn't use samche. Okay, but we eventually dropped it because we thought it was it wasn't going to be that much faster than latis fold. Okay, so we we dropped it. Samche is hard to beat, huh? Yeah, we'll see where the new ones go. Where Latisfold Plus Neo be interested to see if they have implementations if and when. We'll see how how fast they can go. Who's the

group who wrote Lattis Fold actually? Who is it? It's a Damon and Bini Chen. Oh yeah, nice. Oh yeah, we had him on. You talked about that. I wonder do you know if they're doing more work in that direction because you also you mentioned Lattis Fold plus actually maybe we can just quickly talk about like what's the difference there? What was the plus and which one did you implement? Yeah, we we implemented Lattis Fold because at the time well Latisf Plus didn't exist. Mhm. I think implementing Latisf Plus and Neo shouldn't be a big um headache right now because of all the machinery we we develop for for Latis fold. What's the difference? Latisfault plus is is simpler conceptually than latis fold.

Oh, latis fold is quite messy. So the difference between latis fold plus and latis fold is how the race check is is done. So in latis fault as we mentioned there's this extra work that the prover has to do to to make sure that you are never working with vectors that have a large norm. So large norm means large entries. Okay if I say large norm that's what I mean. So in latis fault that's done you you write a gram product. So basically you write you you write a polomial uh of the form x -1 * x -2 * x - 3 and so on up to x minus the largest s the largest entry you want to allow in the witness and then you prove that when

you replace x by your witness this is always zero. Okay. So when you replace x by any any entry of the witness you get a zero. Yeah. This is our good old uh vanishing polomial and zero check kind of thing right. Yeah, it's a grand product relation, grand product constraint and then you use a a sum check of high degree to prove that this holds for all the entries of the witness that that's how it's done in Latisfault and that's a that turns out to have huge huge costs. So the the polomial has a big degree unless you have witnesses whose entries are very small right say that you want to allow witnesses to have entries up to two then the polomial has degree 3 right

x x -1 * x - 2 and then you run a sum check on a polomial of degree 3 but if you want to allow the entries to have say size 2 to the 16 then you are running a sum check on a polomial of gigantic degree and this something is extremely expensive. And why would we want bigger norms? Because at each step of the folding step, you have to decompose your weaknesses into chunks with small norm and prove that these chunks have small norm. So the bigger norm, the fewer chunks. Exactly. You want big norms because you have few chunks. But big norm gives you a polinomial of huge degree and are extremely expensive some check. So you have to reduce the the norm. But then

you have you have a lot of lots of chunks and you have to commit to each chunk in the implementation. Sorry, I'm just going to take a little tangent while we're there. How do you deal with this trade-off and how did you find optimal parameters for this? Um, I wish we could say we did it better than trial and error, but we essentially trial and error. So, we we did benchmarks over as many combinations as we can think of um to come up with good parameters. Nice. We we made a grid search. It's quite complicated to optimize the the thing by by hand or you can say numerical methods if you want to sound fancy about it.

Yeah. Okay. So in Latisfold we have this trade-off and now you were about to tell us how it disappears in Latisf Plus, right? Yeah. In Latisf Plus you can actually just stick to large norm and you end up making two de compositions on like de composing into two chunks only. How do they do that? It's a it's quite technical but what they do is they leverage the algebraic properties of of latises to create a smarter range check. Oh so instead of doing this naive approach I would say where you write a gram product and then run a sam check on this ground product they use tricks that are specific to latises. Mhm. This echoes very nicely with our previous episode on latises with Vadim Lubashvki

who was saying if you take existing techniques and put latises into them, it is going to work, but you won't have something super efficient. If you really want a good latisbased scheme, you have to design it from a latis thinking. And it sounds like this is what happened with Lattis Fold to Latisf Plus. Yeah, that sounds exactly like like that. Yeah, it's a it's a very nice very nice trick where you take your witness and you commit to a new vector where the witness appears on the top of a variable. So before you had a witness, a normal witness and now you put your witness on the top of a variable. So so each entry of the vector is x. So if your witness is v1, v2, v3 and so on.

You commit to a new vector where each entry is x to the v1, x to the v2, x to the v3 and so on. And then you use some tricks related to to these latises. Latises are basically rings of polomials. So you use some polomial magic to prove range checks. You had um this is a bit of a tangent here, but you had earlier mentioned about combining folding and lookups into a construction. And we actually asked Vadim this as well. I mean maybe there's two questions here. One is can you use lookups with lises? And the second is could you use folding plus lookups in lattises? So I think the first question the answer is definitely yes. Yeah, you

can use lookups within lises. Yes. Or with lises rather. Yes. I I haven't worked out the details or thought about it at all. But I'm I'm pretty convinced you can adapt lookup arguments to work on latises. Do you think it would help? Do you think it would actually be useful or like do you think there'd be speed up or do you think it's like lises are so different such a different beast that it doesn't make sense to kind of experiment with that technique? Well, if we have a piece a polinomial covenant scheme that's better than all others and it's based on latises. Yeah, let's say that that exists then you you want to go to latises probably because you just have the best PCS over there. Okay, another reason you you'd like to go to to

latises is if you are proving lookup statements pertaining objects that live in latises. For example, if you want to do lookups in the context of fat, then you want a latisbased lookup. Interesting. So you're saying there's some app like certain cases where you do want to use lookups and it would obviously help if you have a great lattice system to also use this new technique of lookups. Yes. In like in tandem with it. Okay. And since works over ring over um latises um and there's many there's lookup arguments that are based on sam for example lasso and we have polomial commment schemes for multilinear polomials uh over latises.

I'm guessing that you can just write lasso over latises and compile it with this with these pcs. What about that the second part of that question where it's like you do folding plus lookups plus lattises like the folding plus lookups work that you did could that be applied within a lattice context? Yeah, I think so. But I think that folding and lookups are difficult to combine even outside of latises. Okay. So one way to think about the difference between nova and hypernova is that in nova you fold before you do anything. M and in hypernoba you run a bit of a proof system and then you fold and then you fold. So it's later in the process. Yes.

H so for folding lookup arguments you either run almost an entire lookup argument and then you do folding at the end. Okay. Or you do it at the beginning which is the work we we did at Nethermind with withio. It's this fly scheme that's an in in a print and the folding step in this case is if you do it at the beginning the folding step is very cheap for the prover but because of the nature of of how lookups are expressed when you want to prove the faulted instance it becomes complicated you have in our paper there's a quadratic blowout we discussed some ways of mitigating this quadratic blowout when you are at the proving stage or the decider phase uh using another

terminology But still it yeah it's a it's a tricky subject. I'm I'm not sure folding lookup arguments is a fully solved problem. Maybe we need to figure that out first before we start applying it into a lattice context. Yeah, I think so. Unless do you think l I mean this is very hypothetical but would lattises you talked about some of this like lattice magic like the stuff the way that lattises are built actually open up new paradigms. Do you think there could be anything in there that could actually make such a combo easier? H that's a interesting question. Maybe. Yes, maybe that's a research question. I think you guys should hire Anna to give your research projects to to combine words and suggest ideas, folding lookups, lattises. Yeah.

Yeah. Maybe. Yeah. Maybe you have mentioned Neo just a couple times through the conversation. It sounds like it's a new step. Actually, I think at the at the start you did define what it was, but can you tell me again like what part of the stack is Neo? Is it a system? Is it a folding scheme? Yeah. What is it? So, NEO is this paper by Wilson Wilson and Serati. The usual suspects. Yeah. Usual suspects. Nova to Neo. Yeah. Yeah. So, they take Latis fault and change a bit the way that you commit to the to the witness. So if you want to use latis fault to fold witnesses whose entries are field elements, Neo proposes a better way to do it. In particular, it proposes a a

way where when you commit, you pay per bit. So if your witness is has small entries, which happens a lot in many applications, when you do the commitment, you just pay for the bits that are in these entries. In Latis fault, you you basically commit to random elements and because of that, they have very big entries. I'm not sure what's the speed up of Neo. We haven't sat down and tried to make estimate. We we have made some estimates on the benefits of Latisfall Plus. Uh we haven't done that for Neo yet. But I think it is a really exciting work. And something that's particularly exciting about it is that Latisfault plus and Neo are not enemies. They are actually completely orthogonal. They are attacking two different things.

Latisfault plus oh is improving the range check of Latisfault and Neo is improving the commitment. The way you commit to film damage. So you could combine them and get like a Wow. Lattis Neo Plus Fold. Yeah. Nice. Yeah. I'm sure there's subtleties, but it seems very doable. Mhm. Cool. Yeah. How far off is an implementation of something like that? Like given what you've already implemented it can you again use what you already have or would you have to sort of rebuild a lot? I definitely would be able to use a large part of our machinery which is all open source. So yeah, as Aba mentioned, we're talking about two different parts of the implementation. So you just be able to sort of fork cows and sort of change change where you need to inside. Nice.

Um, you mentioned other work at the beginning of the episode. What else have you been working on and do you want to talk about with us now? Albert, should we talk about as well the the signature stuff which is also kind of was more relevant to Latises as well? Right. Yeah, our engineering team is working on aggregation of of signatures. Mhm. for um Ethereum finality purposes. Right. So Latusbased signatures. Exactly. Right. Um so work that's going on is the we're working on postquantum signatures. So the concern is at the moment obviously we're quite a heavily Ethereum leveraged company. So we're highly concerned about the sort of the advent of quantum computers and current Ethereum

signatures the BLS scheme are not postquantum secure. So, we're looking at ways uh plausibly that Ethereum could go uh postquantum. Hey, cool. The reason I'm kind of excited about that is we just did an it like two episodes on quantum computing, quantum communications, and we did talk about a few of those ideas of how to transfer. We also actually talked about in the Vim episode like how to move, how to migrate, how to how to like make existing systems safe in the new world.

Yeah. A a lot of them as Nikico said before is just taking previous ideas and adapting them like um putting them in matrices and calling them letters based schemes. Falcon I would say is of that ilk and that's what we're working at the moment. Um we also think it's like a very good um candidate to be the new Ethereum signature scheme. So Falcon is what we're focusing on. Essentially a Falcon signature consists of a vector that satisfies certain constraints. And when we're looking at aggregating signatures, maybe to go back and aggregating signatures means um signing multiple things and verifying them at the same time in one shot. So um there's two approaches that we're looking at.

One is the Labrador scheme over falcon signatures. Essentially, if we have multiple of these vectors which um are valid signatures, we can prove knowledge of multiple vectors at the same time using a latisbased proof scheme. And um there's a paper which discusses how to use Labrador as a wrapper around Falcon signatures to to make an aggregation of Falcon signatures. And we're actually looking as well at folding Falcon signatures these Falcon vectors together so that you'd be able to create from multiple signatures one new signature. I was about to ask it sounds like there's synergy here between folding and aggregate signatures, right? Like you have many problems and you want to

oneshot verify them. H yeah yeah yeah at the performance probably not where where it needs to be in order to be like a real solution to the postquantum Ethereum signatures but yeah definitely step of progress. How come the interest in Falcon over um MLDDSA and I'm asking because we also talked about MLDDSA with Vadim in that episode we keep referring to was is MLDDS that's a signature scheme or was that's a that's a key yes no it's the signature scheme it's uh I think the dithium scheme oh sorry yeah so I know I know as dithium I think originally we were very interested in looking at this paper the Labrador uh wrapper around falcon so that that sort of was literature that already existed

And that's why we sort of decided to do some engineering on that paper. Um many of these papers come out without um inbuilt implementations. Um just if anyone's interested in getting involved in these you pick a paper and implement it. That would be your contribution to the latest uh cryptography world. Um so that's basically why we started focusing specifically on Falcon and from that uh spawned the Falcon folding idea. Yeah. Sorry. I used to call the ML MLDDSA dithium. Yeah. Yeah. It's I think Vadim was also making a conscious effort to call it MLDDSA now that it's been standardized so that people This is like the difference between SHA 3 and Ketchac right it's the same thing exactly right okay fine understood it's rather than using the name of the algorithm or the family of algorithms we use the name of

the standard so I I would like to mention two projects we are very excited about one is in the area of ML so as I mentioned at the beginning when you do proof of inference so well proof of inference is just proof showing that a certain ML model outputed certain output given certain input. Okay, you might want to do that for example if you want to authenticate that say you want to guarantee your users that they are they are talking to chat GPT right so you could create a proof of inference to convince your users that that's the case but it it is extremely expensive it is a really massive computation and right now we are not ready to to make such proofs

in a reasonable amount of time kind of a philosophy we are taking in our team is to try to come up with light ZKML solutions. So I call them light ZKML solutions in the sense that instead of proving entire computations which are massive, we try to come up with smaller computations such that proving them achieve a similar goal as the goal we had in mind initially. So let's continue with the example of authenticating a model. So now let's say that instead of of um doing full proof of inference, we fingerprint we watermark the model. So in this case a watermark an example watermark would be for example we have open AI or the model owner have two this

divide all words into two lists okay a green list and a red list and then we bias the model so that it outputs words on the green list more often than on the red list. You can do that and then run some tests and you will see that the the model you get you end up with is comparable to the original model. you don't lose much quality. Okay. But it's identifiable in the words it chooses. Yes. So now you want to keep the list hidden, right? Because anybody who has the list can then create a model and bias it towards the green list and pretend it's OpenAI's model. Mhm. So what what you can do you you have OpenAI or the model owner sign

the list. Okay. Then it creates the inference and it creates a zk proof that there's more green tokens than green words than red red words in the output. Mhm. And this way whenever you see such a proof you can be certain that whoever run the model knows the the green list and the red list which means that is um the claim owner and I guess you can even have like a public commitment to that green list red list and make sure the the proof verifies against this commitment every time. Right. Exactly.

Yeah. That's the idea. Super cool. That's super cool. And you end up doing a proof of membership basically a lookup argument. Right. You just do a lookup argument. Is this something that you've released already? No, we are implementing it right now. Wow, super interesting. More academic research direction we are really excited about and we've put a lot of effort in this direction is zinc. Zinc is a succinct argument or you may may also call it a framework for building succinct arguments for constraints that are expressed with integers. Instead of field elements, they are expressed with integers. Why is that desirable? because writing constraints with integers. So you can think arithmetic programs where the circuit values are integers instead of field elements. This is this is

desirable because it allows you to write constraints uh modulo any moduli very cheaply. So you can take any circuit that uses any modular arithmetic you can think of and write it as a circuit that uses integer arithmetic and the circuit is essentially the same size as the original one. Okay. Super interesting. So we don't have all this foreign field arithmetic issues that we usually have. Yes. And you can use different model. So you you can have circuits that use different moduli at different part of the circuit and lift it to the integers and the resulting circuit is almost the same size as the initial one. Okay, very interesting. Yeah, we we are very

excited about about this because we think that there's a lot of cost being paid right now because of this for field arithmetic. For example, say you want to prove a ZKVM instruction and you are not doing it with lookup arguments. VM in instructions usually deal with bitwise operations and mod 2 to the n operations and these operations are usually not easily read writable over a field. Mhm. Okay. But you can write them over the integers very cheaply, very easily. So if you want to prove VM instructions over a field, you end up proving statements of circuits that are maybe 16 times larger than the the actual circuit

you would write if you had integers. Okay. And is there also an implementation underway and sort of benchmarks? Yeah. So absolutely. Uh we're coming towards the end of our implementation effort. We do have some benchmarks. We're going to publish them relatively soon. Albert, but do we have a date when we want to publish them? I can actually just give um some of some numbers now. Sneak preview for this podcast. Although by the time this comes out they might be out but yeah let me um mention also that this scheme works with hash it relies on hashes. There's previous work for proof systems over the integers due to Campanellian Hal Anderson. it it is a framework and when they instantiated the

f framework they use hidden order groups but hidden order groups are quite slow and I don't want to spend too much time on on on that uh our that's a whole other bag of beans we've had latises curves and hashes let's not open a new section right now but but let's say that hidden order groups are a no no for for efficiency in this context they they are absolutely terrible that's everything I will say So we managed to to use hashbased techniques and it turns out that the actual scheme is very similar to other hashbased schemes that are I would say state-of-the-art or close to being state-of-the-art. So for example our

polomial commitment scheme for integer polomials uh is able to commit and evaluate a polomial with two to the 16 with 16 variables in a bit over 200 milliseconds. And for comparison breakdown um polomial commitment scheme for the same number of variables on a fixed field like the standard breakdown with a a bit different code takes 125 milliseconds in our benchmarks. So yeah our work is less than twice more expensive but on the other hand it has all these arithmetization benefits I talked about. Yes. So a two to the 16 circuit is going to do a lot more work than one in over fields right? Yeah, we

we believe that it like equates to a two to the four two to the five speed up. Wow. Okay. In comparison. So being double as uh as taking double as long is negligible in those terms. I think we are at the end of the episode. I want to say thanks so much Albert and Matthew for coming on the show revisiting lattises talking about the benefits that lattises can offer to folding schemes or vice versa. And and also a lot of this new work you've been doing. Actually, I think one of my favorite parts of this episode, just FYI, was like the lay of the land of Lattis and Snarks because like I don't think we've we actually really did that in our previous episode.

So, for me, this has been really helpful. And you can also see a bit of a trajectory like a research line, Labrador Greyhound Lattisfold Lattisfold Plus, Neo. And you wait, you also mentioned LOVA. Is that a continuation on the same thread or is it something else? LOVA is a um it's quite different from Latisfa Latif Plus and Neo. It is modeled as Nova. So it's a nova analog for latises but it it doesn't work on R1cs relations. It works on a different type of relation which I I forgot which one is which one it is but it's still MP. Okay. But I'm not sure it's it's usable in practice. I'm not sure. Uh cool. And it works on so-called unstructured latises which are

supposed to be more secure than structured latises. Oh, that's cool. But are less efficient. Okay. The tradeoffs. Well, yeah. Thank you so much for all of that. Uh it's been really helpful. Yeah. To dig back in with you and congrats on all of this work that's happening at Nethermine, too. It sounds very exciting there. Yeah. Thank you guys so much for coming on and sharing all of that with us. It was wonderful. Thanks a lot. It's absolute pleasure to be here. Thanks so much for having us. Yeah, thank you both. This was super enlightening. Yeah, I'm glad. All right. I want to say thank you to the podcast team, Rachel, Henrik, Tanya, and Kai. And to our listeners, thanks for listening.

[Music]