Episode 385 - Lattices, Folding, & Symphony with Binyi Chen

Transcript

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. This week, Nico and I speak with Biny Chen, a post-doal researcher at Stanford University. We discuss his work, Lattisfold, Lattisfold Plus, and his new work, Symphony. In this episode, we get to ask him some of the questions we still had about lises and folding and try to tease out why they combined so well. We discuss how the folding work

began back in 2023 and the opportunity that the introduction of lises created once it became clear they were a feasible replacement for Peterson hashes. We cover some of the key ideas in lattisbased folding work including the benefits and limitations of this combination. We then move on to his new project Symphony and explore the new techniques described in this work. This episode is researchheavy and serves as a great complement to the recently released ZK whiteboard sessions module all about Lattisfold which was also hosted by Beign. I definitely recommend watching this as an additional resource.

I've added the link in the show notes. Before we kick off, I just want to point you towards the ZK jobs board. There you can find job postings from top teams working in ZK. And if you're a team looking to hire, you can also post your job there today. We've heard great things from teams who found their perfect hire through this platform and we hope it can help you as well. Find out more over at jobsboard.zeronowledge.fm. You can find this on our website and I've added it to the show notes. Now Tanya will share a little bit about this week's sponsor. Aztec invented the math, wrote the language, and proved the concept that privacy is in fact the missing link to mass adoption. And now Aztec is on the road to mainet. Aztec is a privacy first layer 2 on Ethereum supporting smart

contracts with both private and public state and private and public execution. It is one of the most exciting ZK projects out there and we are excited to see it go live. There are a ton of ways to get involved. You can join the test net, explore the noir ecosystem, become part of the community or look out for ways to participate in the last steps before the upcoming mainet launch. Details about Aztec's technology, research, and community programs are available at aztec.network. And now, here's our episode. Today, Nico and I are here with Bini Chen, a posttock researcher at Stanford University. He's been advised by Dan Bonet, someone who listeners of this

show will be very familiar with. Welcome to the show, Beigny. >> Thank you, Anna, and thanks, Nico. And nice be for being here again. Yeah, >> since last time in the prostar episode. >> Exactly. Hey, Nico. >> Hey, Anna. Hey, Beny. >> Yeah. And Beigny, you have been on the show before. Last time you were here, it was with Benedict Buns and you were talking about Protoar, which was like a very like very focused on IVC and folding. Today, I think we're going to be spending more time talking about Lattis Fold. So, kind of the continuation of that work, and hopefully get to hear about some new work. Yeah, >> but before we do that, I just want to highlight a few kind of connection points that we've had over the years. I actually was looking, you know, just to

to put together this episode, but you've hosted a ZK study club. You've spoken at the ZK summit. We just released your ZK whiteboard session all about Lattisfold and Latisfold Plus. It's just kind of cool to have you on the show today. >> Yeah, me too. It's a great pleasure and it's always like very pleased the experience when I host anything here and give a talk here. Yeah. >> Cool. I think it would be cool to bring us a little bit up to date on the research and the focus of your work. As we mentioned last time you were on it was Protoar. It was folding. What what kind of happened since then that pushed you more towards the lattice work? Yeah, since the last time a lot of thing has

happened and I've been exploring many directions of snarks improve system such as coding based snarks like base fold and blaze but still my main focus is still in folding and especially recently on post quantum folding like lice base folding schemes. >> I want to mention the one thing that I talked about in the last protostar episodes. I think Ben and then I mentioned this open problem on whether we can have post quantum folding schemes and we think that lattice is actually one of the promising direction by that point we mentioned this is pretty hard because non-b blow up but I'm pretty happy that after maybe two years I guess we have so many new works in the last

setting that >> cool do folding using lises. What was it about those earlier folding works though that made them not postquantum or or impossible to make postquantum? >> Yeah, very good question. So I would call them as the first generation of folding schemes like starting from Nova and the BCLms 21 and probably Halo is also one of them and we have also have some follow-ups like protostar, product galaxy, hypernova and moa etc. All of them are following some kind of similar framework for using Pison hashes to uh commit the witness and these pedison commitments they are unfortunately

vulnerable to quantum attacks because they are based on this so-called discrete log assumptions and this discrete log assumptions are exactly broken by this very famous SH algorithm. So that means if you have a very powerful quantum computer, you can easily break this assumption and that makes these kind of schemes no longer secure in the quantum world. >> I see. >> That's why we need some new schemes. >> Was it using this sort of the characteristics of the Peterson hashes though? Like why not just switch it out with some of the other hashing functions anyway? Like why did you have to wait for lises to come along?

>> Yes. So previously when we do the folding we need homorphic oper property meaning that you can combine commitments which becomes commitments to the combination of the underlying opening or witness and the most natural way to do that is using pis and hashes. >> So that's why people starting using them. But in order to make it plausibly postcon secure you have to switch it into another commitment. And the most natural way to switch it is to using attack compments which is a lice space commitments. And recently I want to mention there are also some really cool work by Benedict and his coerces that achieve folding without homorphic commitments. They basically just use hash or mercle commitment to achieve it

which is also very elegant. Ah >> by the way I'll also add at the time we were looking at these like linearly homoromorphic commitments and we suddenly realized well if we want something quantum secure we cannot have this homorphism because as soon as you have homorphism you have a group structure and as soon as you have a group you have discrete logs >> so there was this sort of feeling of like is this possible or not and that's why it was a cool open question that bin and me and the others tackled over the past few years. >> Exactly. Yeah. So I think I want to be more precise and Nikico is right like this commitments is not fully homorphic nichomorphic in the sense that they have to make sure that the opening is always no norm. So yeah they are only like somewhat nearly homorphic

>> compared to pen hashes which is basically nearlyomorphic over the entire field. >> Is the type of hashes you're describing it? Is that the word you're using? Yes. Itai. >> And this is spelled a j t ai. >> Mhm. >> Exactly. Okay. So, this is actually one of my questions that we were going to get to later, but what is that work? What is itai? >> Itai is an very famous cryptographer. >> Okay. Yeah. It's a person. >> Yes. Yes. He's like one of one of the pioneers in the lattice cryptography and he invented this shortest integer solution assumption which is a cryptographic assumptions that can be reduced to some uh worst case lis problem which is amazing work

>> and from that he gave us a this really elegant constructions for collision resistant hash function using SIS or shortest integer solution assumption. Hm. There's a bunch of these terms that come up in your work, but also in the work of other kind of lattice folks. >> We had two modules within the ZK whiteboard sessions this season on lattises. We had one with Vadim Lubashevski and one with you and I I mean because they they've just recently come out. Yeah, I'm I'm excited to kind of dig in. I for this episode, we don't want to go through it again like we're going to point to those videos like people and and those are whiteboard sessions so those are like really detailed. I think a great way to learn about this stuff.

>> But yeah, I wanted to ask you sort of questions that came up as I was watching it and also to get some context around like you know maybe where the research is coming from. So this like it tai explanation is helpful. I one question another question I've had about that though is when was that work from? Is this older? >> It's very old. Okay. >> It's uh I think it's the year as when I was born like 1992. >> Yeah. Yeah. >> Okay. It's like 30 something years ago. >> Yeah, I think it's 1992 if I didn't remember incorrectly, but definitely at that period. Yeah.

>> Which, you know, for people is not very old, but for a paper in cryptography, surprisingly old. >> Yeah. Cool. >> Before we actually dive into Latisfold, I sort of want to bring it back to something you mentioned is you also worked on like hashbased schemes. >> Yes. >> Um like base fold. You also mentioned that there are hashbased schemes that do folding. And so I was wondering as someone who's worked sort of on both fronts of the current like postquantum ideas, how do you compare schemes that are based on hash functions and those based on latises? Do you find that some are like easier to work with as a researcher or more promising to implement? Like what do you think?

>> Yeah, that's a good question. I think both direction are very interesting and promising. What I can do is just give some kind of comparison on their pros and cons. I think for hashbased schemes in particular hashbased nark they're pretty mature right now there are many industrial implementation for it compared to the latis word and the assumption underlying it is also pretty solid they only rely on this symmetric hash functions which uh we believe is definitely postcon secure as long as we increase the key size or the output size large enough but sometimes we don't even need So in terms of security, I think they are more robust in terms of the quantum

attacks and they're also pretty efficient in terms of prover because what they do is basically just do some error correcting coding and doing miracle commitments. >> Mhm. >> But why I care about lises, right? Like if we already have a really good hashbased solutions, I think in terms of lises, they have uh two really nice features compared to hashbased schemes. The first one is they are more algebraic. They have a lot of algebraic structure and a property which is similar to those ellip curve based schemes like some homorphism something.

This makes them more powerful to achieve more powerful primitives. And second is that the verification when we do the folding the verifier is really small like is much more efficient compared to hashbased folding schemes. In hashbased folding schemes, the verify have to check a lot of miracle pass openings and that means when you check when you want to prove this like when you represent it as a circuit is really large in terms of lice space for schemes the folding verifile is only slightly larger than those ellip curve based schemes but much smaller than the hashbased for scheme.

So given that I would say in terms of snark currently hashbased schemes is a more mature even though we have thing a lot of new and very exciting result in the last word as well but in terms of folding I think the glass based folding schemes is really promising in the sense that the prover is already competitive with hashbased folding but the verify complex is much smaller which is very important when you do do need to prove that the folding verify was done correctly. Mhm. >> So you have to make sure the folding verify circuit is small enough. That's my personal perspective. I don't know whether people agree with me or not.

>> In the combination when you start putting folding and lises together, do you have to rethink the entire thing? Like when you were talking about using the Peterson hashes, I mean this is kind of where my mind went where it's like, well, why don't we just use why don't you just swap it out? But if you're using lattises, you're not use like are you using them in the same way that Peterson hashes were used or are you like kind of reconstructing this entire thing? >> Yeah, we are actually doing thing in the middle. So it would be nice you can just switch and hash with add hashes, right? And then do everything the same way. But then if that's so easy then we don't need to spend so much time to come up with it. We would already have it when we have Peterson based folding schemes.

So the key challenge of achieving this in the last word is because this so-cal commitments is kind of more restricted compared to Peterson. So we have some extra constraints on this item commitments in the sense that it is secure only if the opening is no norm. By no norm I mean that every elements of this vector or the witness are some small values and this is not a constraint in the pet hashes. the P hashes the pre-image can be arbitrary field elements. So that means if you want to do folding if you fold two witness together this witness the norm will blow up. So first question is how do you control the norm blow up after

the folding >> this is the first challenge and the second challenge is that the prover also need to prove that this witness opening are no norm. So this is not the case in the pis and hashes. So it adds more overhead and complexity for prover which also needs to run some range proof to argue that the opening of commitments is ln norm. So these are two main challenges compared to pisbased ellip or ellip curve based folding schemes >> and that's why it's harder to design but I would say still they have some have many similarities. These two type of foreign schemes they have many similarities because they all based on

kind of homorphic commitments. >> Yeah. At the end of the day, you know, we crytographers have one trick is to take two things and a random number. >> Yes. >> Multiply one of the things with a random number and then add everything together. >> Yeah. That's the universal trick. Not only folding, right? >> Maybe we should actually talk a little bit about what folding is actually offering. Like why are we designing systems like this? Like what are we trying to achieve? Is it faster? Is it cheaper? Is is one side faster, the like does approver go faster but the verifier slower? Like are we running into tradeoffs? I'm just curious like maybe let's start with just folding and then like the lattice folding part. Exactly.

I think that's a very good plan. So first of maybe we can review what folding is for those audience who are not familiar with. Fing is basically a mechanism or a protocol that allows us to reduce the tracking of multiple MP statements into a single MP statement. For example, if you want to prove a million step of Fibonacci sequence, we can chunk it into many small chunk statements and fold them up into a folded chunk statement which is much smaller. So this basically is a way for us to efficiently reduce a large problem into a smaller problem and then solve this small problem. Is it similar to parallelization?

Like can you use that term to describe it or is it different? It's kind of similar but kind of more like mathematically reducing some large problem into one like divide conquer and and parallelism they are all kind of similar notion but this is another mathematic uh primitives okay >> to to do that and I think also why we need it right why why we think folding is a really nice primitive why is the direction for the future for dealing with scalable computation I think there are three really nice feature about folding The first is exactly the simplicity. So folding typically the protocol is much simpler than a moistic or full-fledged snark because basically what it does is

just to commit each MP statements witness and randomly combine. So the verifier just generate some random scalers and combine the commitments and the prover just randomly combine the witness correspondingly and we just comp compile this many input statement into one combined statements. So first is simplicity that's much easier to implement and much faster as well. >> Mhm. >> And the second nice feature is that folding also allows us to convert it and be transformed into a succin proof system. So I would highlight that folding itself does not give us a succinct proof system because the verification work is actually linear but it can be transformed into folding into

a succinct proof system using this compiler in in IVC and PCD which is by recursion. >> So essentially what you do is you fold this recursive statements. This recursive statements not only check the application logic or computation but also check that some previous folding step was done correctly and this is the reason why we need to embed the folding verify circuits into this proven statements and fold them up. >> I always wonder when you say that like the recursion part is this happening before the folding or postfolding >> long before the folding actually. long before the folding. Okay.

>> Yes. Actually this idea start from recursive snark when the folding doesn't exist. >> Oh yeah. >> So initially we have snark and people were thinking can we like recursively prove snark like we can prove some proof is correct. >> Yeah. Proving proving proofs is recursion. Basically it's snark using a snark to prove a snark to prove a snark. >> Yes. Exactly. And this idea was already proposed in 2008 by Paul Valian. That's long time ago already. But at that point they are only focusing on recurs recursion this snarks. I would say at that point is only of theoretical interest >> because the recursive circuits for snark verifile is actually pretty expensive.

So no one would actually use it. But this has been changed since this Halo paper has been introduced and also the followup of Nova and the BCMS 21 has introduced and therefore is much simpler than Snark varile and by combining this idea of recursion together we can actually obtain much more efficient constructions. >> Yeah. By the way, it's funny cuz Valiant had this snark vnark idea to do IVC >> at a time where snarks we weren't even sure if they existed right like >> oh yes >> back in 2008 we're still uncertain can we do them in theory can we do them in practice at all like it's >> the term snark had not been defined yet I don't think that was 2012 remember >> at least that's what we said on stage

Nico at the zik summit >> that is what we said on stage I might regret >> but I think it's the first time it's written in a title and it was like >> yeah absolutely There was the notion of succinct proofs and the notions of proofs of knowledge but calling something a snark and making it a thing you know came later. >> Mhm. Yeah. I also do want to mention a third really important feature for folding compared to full-fledged snarks which makes it quite unique and quite important when we want to deal with large and streaming computation is the basically the streaming friendliness which is very important. So if you think about we we have some really large task like ZKVM or pro some verifiable machine learning if you only have spark usually

what you do is you start the computation and you finish the entire computation and then you generate some computational trace and weakness for this entire computation and only then you can start doing the proving. So the the proving can only start at the very end of this stage which is kind of wasted some time right >> but folding allows us to do better in the sense that you don't have to start doing folding while you finish computation you can just start it while you're doing the computation you only need to get some partial results then you can already start doing the folding and that's pretty important for this large scale computation like I think analogy is that when you watch the video like watch YouTube video you don't want

to buffer the entire our video first and then watch the real video or >> which is what we used to do when you download from like Napster or something. >> Yes. Yes. >> For us oldies out there. >> Yes. But now we get get used to YouTube, right? So it's it's more pipeline is much better experience. >> Interesting. I think in my initial question it was sort of like there's also this question of like what part of the snark does recursion and folding help with? So, does the proof time go down or does the verifying time get affected? Yeah, I'm just curious if there's like a trade-off at all. Is it harder to verify a folded scheme actually?

>> Yes, I think the main motivation is prover time. Okay. >> And it's particular for and also memory I guess both memory and prover time but particular for those large problem. So if your task is not very complex, if you're just proving single transaction or just proving a hash, you don't bother to use folding. You just do a simple sigma protocol or snark, that's good enough. >> It makes sense only when it comes to a really large problem like ZK virtual machine >> or like verifiable machine learning. In this case, it's not that easy to use a monolithic n to prove it efficiently. So you had to split this large problem into a smaller problem first and then use snarks and folding is exactly a very

efficient way and a scalable way and as well as memory efficient way to reduce this really large problem into smaller problem >> and I think I remember when it was first shared it also is really good for certain types of problems which are like repetitive like you want repetitive steps you don't want like dynamic circuits and lots of different like you want something quite consistent. Exactly. So for example, if you want to have a CPU, right? You don't have like custom circuit. You want to have CPU. Well, each time just run a single instruction and folding is perfect for this. Well, each chunk statement just one single instruction. And I want to mention two things. First is that first we do this for folding is because

folding is perfect for this uniform computation. So if this computation satisfies property which is kind of iterative it perfectly fits for the framework folding but I do want to mention that recently there's a paper called mangrove which actually can reduce some arbitrary computation into many uniform computation and after that you can start doing the folding as well. >> Cool. >> So it's more general than that. >> Okay. And then now let's go to that second part which is like lises. So you're introducing lises. Is approving time made even more efficient like which yeah again which part is affected and is there any trade-off when you introduce lises does any part of the process get slower >> yeah very good question so initially our

goal for use lises is not only for postcom security it's actually we want to accelerate the proofer we want to make proof even faster than elliper based fling schemes why because we have some really nice commitment in the last war as well I do want to clarify that the original itai commitments that was invented in 1992 is actually not that efficient because it's based on some integer lices >> but later it has been adapted and optimized in the ring setting like polomial ring setting by vadim Chris per alon roson and Daniel Micho around I think around 2006 or humbling yeah maybe 2006

>> so after that the commission becomes more efficient s they basically the complexity goes from quadratic to cosine linear and it's much faster than that and also highly paralyzable and moreover you can use some small fields to instantiate so that makes is extremely fast so that's the one of the motivation for using that kind of commitments >> so in summary we have plausible postcom security but and in theory we might also get even fast prover so that's really nice that's why we have some motivation to study Yeah, >> I'll add another piece of motivation actually with elliptic curve commitments, you have your witness, your circuit lives in a field.

>> Mhm. >> And then when you do commitments, you put them on an elliptic curve. >> Yes. >> Right. And then when you want to do this recursive step of checking your verifier, you now have to write statements about the elliptic curves with your field. So you have this weird recursive thing happening. Yeah. >> And this is actually quite painful to do. It makes your circus very big. And that's why we had these cycles of curves that were very painful to deal with that caused bugs. And so even back when Protoaur and Nova came out, we were all thinking, wouldn't it be nice if we could get rid of these cycles of curves? >> And can we use things like lises to do that?

>> Yeah, that's a very good point. Are there any downsides to introducing lises? >> Yes, definitely. Like whenever you do something, there are some tradeoffs. >> Okay, good to hear. >> No free lunches. >> Yeah, no free lunches at all. And especially in our first generation of lice fing schemes even though they are pretty competitive they are becoming practical they still didn't beat the state of the art of of elliptic curve schemes the reason is that as I mentioned before we actually are dealing with a harder problem right we have to deal with non blow up we have to deal with proving that norm alone norm so this are extra task make the construction of last based phone schemes

harder and that also adds complexity of the fing schemes. For example, in the first generation of lattice fold in order to prove that the norm are low are small. You have to first decompose the original witness into multiple witness vectors which are even lower norms and only then you can run some so-called sum check protocol to prove it. And that means the provers's work is more because they need to commit to more vectors. Suppose initially you only need to commit to one vector. Now you have to commit say like 10 or uh 16 vectors which is more prover expensive. So even though add commitment itself or rim based at the commitment itself is more

efficient the work you have being done is actually more. So the speed is actually not faster than elite curve based fing schemes. So in order to make it more efficient we really need to have a more efficient range proofs >> and that is the bulk of lattice lattice plus. >> Yeah >> and I think what you cover in the whiteboard sessions right? Yes, exactly. >> It's funny when and this is actually bringing me to the whiteboard sessions themselves because in that you mentioned a few like lookup works in that context of like range proofs, but I was confused why like you you sort of said like yeah CQ does something with the range proofs, but I I always thought of them as being pretty separate. Is there a connection there between like the lookup table

lookup argument work and the range proofs? And if so, like what is it? >> Definitely. So if you think about this ranch proof is actually a special case of look up arguments right because what you want to prove in a ranch proof is you want to prove that certain value is in certain range but this range itself is also a table it's just a special table includes the all the values of this range so that means if you have a look arguments that you also have a range proof as well >> oh wow >> for some reason I feel like that never really came up on the show so that that was also So like as I was watching the whiteboard I was like you know I was putting my hand up but you know it's a video and I wasn't actually there. I

wasn't part of the recording but like you know I it's like the moment where I yeah I had this question I was kind of confused but this is helpful and it makes sense actually that you just choose like the lookup of just a certain range basically. >> Yes. Yeah. Range proof. When you think about range proof you all think as a special or even simpler problem than lookup. >> Are there any other ways to do this range proof? I know that you have two iterations of latis fold. There's also this paper called Neo that we should mention that also does folding based on latises. >> I was wondering yeah all the techniques there super different super similar and is there a lot more like to explore?

>> Yes. So I think the lattice based setting the range proof is slightly different from the other ellipurbased setting and currently we have two main idea or three main ideas I would say. First is doing decomposition and second is to do random projection which is the idea using labrad and third is the idea in lasso plus which is called luminomial encoding while you just uh use some kind of restructure of polinomial ring to prove some lookup relations. All this are having their pros and cons and I want I want to mention that recently in this new paper I'm I want to discuss later we have also have a new last space

for scheme which has a new range proof which is kind of combination of projection and monomial encoding that makes it much faster and much simpler. So Neo I think the main contribution of Neo is I guess it's not ranch proof. It uses this paradigm of de composition of last fold as well >> but it has some other really nice uh like properties and contributions in terms of supporting small field and encoding the constraints in a more natural way. >> Mhm.

>> So I think they'll use de composition to do the range proof. Are there any other trade-offs or downsides to using lattises or to combining folding and lises? >> Yes, and this is something that I think will have connection to what I said later in terms of the new work. So beyond this proverhead, this verify overhead is also an issue. >> Okay, >> even though it's much better than hashbased phoning scheme is actually still worse than ellipurbased phoning schemes. Ah >> so the reason is that you have to run this f shame circuit. For those who are not familiar famir is a way to convert an interactive protocol into a non-interact protocol by generating this

verifier challenges using a hash function on the transcript. And in last setting this transcript is much larger than ellip curve setting because these it commitments are larger compared to ps and hashes. is each ATI commitments can be as large as in as 4 kilobytes or even 8 kilobytes and you have if you have many commitments to hash inside the transcript then this complexity of just doing the familiar hashing is already pretty expensive.

>> Mhm. >> So the one of the questions can you remove this famir circuit in the verifier to make the recursive circuit much smaller. >> Mhm. By the way, for comparison, the Pisonson commitments, Pison hashes are like a few bytes, right? >> Yeah. 32 bytes or 40 48 bytes, I guess. Yeah. >> A few orders of magnitude difference. >> Yes. >> Yeah. >> This is kind of another definitions question, but you mentioned it in your whiteboard and actually Vim mentioned it in his as well, the SIS. And you you already have defined it today in in the interview, but can you talk about what that actually is because it comes up every time you're talking about lattises?

>> Yeah. So, SIS or shortest integer solution assumption is kind of a bridge between this really fundamental lattice problem and the cryptographic applications. Okay, >> so it is a cryptographic assumptions which is saying that given a randomly generated matrix A, it's hard to find a small vector X such that when a * X you get zero. So if you don't have any constraints on this vector x, you can actually very easily solve this equation, right? Basically there's just a bunch of linear equations and then can solve it. That is the easy problem. But it turns out when you add this small

constraints that you have to make sure this x is no norm or like every element of this factor is small. This turns out to be a really hard problem and we have a reduction that if you can solve this problem you can solve some really hard lattice problems in the high dimension lises but in this case is this one of these you know cryptography moments where you want it to be hard. >> We do. Yeah. Yeah. >> Like you want it to be very difficult because you don't want it to be breakable right? >> Yes. We want it to be really hard. >> Okay. It's just funny whenever like the SIS problem, it sounds like something that we're trying to solve, but that's not the point. It's like, no, no, we like it. We want it to be hard.

>> Yeah, we definitely want to be hard. Otherwise, like most of the lattice cryptography will collapse, I think. >> Got it. >> Yeah. >> But by the way, it is a problem and we do want people to try to solve it. The more people try, the more we know it's hard. >> Yes. So it's like if the SIS problem was solved that would be bad for lattises but maybe good for like you know general safety and security because we would know this wasn't hard enough. >> Yeah. And that would be a really breakthrough like very very important result if we do have these results >> and the feeling though is that the qu like quantum computers can't break it.

Maybe feeling is not what we're looking for. The the assumption is that you can't break it with quantum computers. I mean it is at this point you know a general feeling or a general sentiment like that that is just how we work. >> Yes. First I don't have a really good explanation on why it will be against quantum computing attacks but the thing is that we have gone through 30 years or more of cryp analysis of this word and this is one of the most mature and timetested assumptions that no really good attacks on top of it uh even for quantum computers and there are many really and talented researchers they are

basically just working on crypton analysis on lattises >> trying to break them >> but uh yeah trying to break them and we don't have a really good solution yet >> huh when you decided to start working on lattis fold in that time between protostar and that interview we did and lattisfold and lattisfold plus what happened in lattises that changed that allowed you to start using them you sort of mentioned earlier on in the episode that like two years on you started to see oh we can actually do this but what was It was it like the Labrador work?

Was it something that came out? Something that changed? >> Yes. So, I think it's just we didn't spend too much time on it at that time >> and then you looked and you're like, "Hey, we could do it." >> Yeah. I think maybe it's some kind of prethought like when we think about this problem when we think about folding, we always think about folding. We never think about decomposition. So that's why we think there's no possibility of control norm after the folding. But it turns out if you fold if after folding you decompose first and then you fold and you actually actually control this norm. And this is the first step that the change of mind mindset makes it possible. And the second is this range

proof. I think the range proof is kind of inspired by both inspired by labrad as well as samch. >> Okay. because I'm previously I was working a lot on sumche and it turns out sumche is a really nice protocol to help you to prove some relations and turns out this range proof relation is one of them can be covered and so you can actually use sum check to give a range proof for that and moreover this range proof has subnia verified complexity which is very important for in the folding case the reason we cannot directly use labrad is exactly because the verified complexity of labrad is actually linear there which is not enough for folding to be used.

>> So it's like a sort of a convergence of a few different research threads that meant actually now is a good moment for us to really dive into this. >> Yes, exactly. >> It's an area that needed someone who was from the folding world to go and look at all these Lattis works and put things together and make it work. And that's exactly what Beign and Dan did with Latisfold. I I I think I in the past have sort of talked about like lattis fold as like a continuation after Labrador, but I I feel like I've been corrected on that too. I mean, I'm guessing it's taking some influence from it, but it's not really the same kind of lattice. Like maybe can you just describe like where those research threads diverge? This is a Labrador Greyhound and then Yeah. And then sort

of the lattice fold work. I think the labrador one is mainly for arguments like uh succinct arguments in sense they they want to prove argument system that has small proof directly proving this relation. So in terms of crypto primitive they are slightly different from folding >> and the followup greyhound is kind of a optimization to labrad which improve the verified complexity of the scheme from linear to square root. M >> though it's still worse than poly logarithmic. On the other hand, I want to mention there are also some other work called the rock and paper and scissors and also recently rock and roll.

>> Oh yeah, >> there are another line of work for lice based arguments that not only have small proof sizes but also small verified complexity. I think it's poly logarithmic verified complexity. However, they are compared to labrad, they are less concretely efficient, but I do think there are many new works follow-ups that try to make them more practical as well. So that would be the first line in terms of arguments. >> It's funny the rock and roll I I saw that for ZK mesh. It came out really recently right?

>> Yes. So it start with this rock paper scissors and rock and roll is kind of optimization and followup to that work. >> Okay. I'll have to include it in a in a new edition. Very cool. Okay, that was really great. Thanks for sharing that kind of distinction. This has been something I wasn't quite clear on. I really thought of it as like a continuation, but you know, just like lattises as a theme were becoming more relevant and then I was like, "Oh, this is why." >> So, Vinnie, earlier you teased out that you had some new work coming up that also involves folding and a new way to combine folding skews to get snarks. Can you tell us a bit more about the motivation for this work and like what's happening in there?

>> Yeah, definitely. So I think I'll also partially mention this that the previous folding schemes especially last space following schemes they have some this kind of drawback of proving famir circuits. So f shamir circuit is pretty large in that sense because our other operation is pretty simple just the linear combination of ring elements. So this is the first reason that I want to remove this firmer circuit. Early this year I came across this paper by Ron and Lev and Dimry. They come up with this really elegant attack towards the GK based proof system.

>> Mhm. >> So to give a a little bit background GKR 2008 is a very elegant interactive proof system. So initially there are interactive protocols meaning that online phase the prover and the verifier needs to communicate to check certain kind of arithmetic circuit computation was done correctly. But it turns out we can also make it non-interactive by using the this fia heristics that generates the verified challenges using the hash computation of the transcript. And then we even have some kind of security proof for that in an idealized model. Well, we treat this hash functions as some random oracle meaning that this basically just some random

function that you can query in a blackbox way. But it turns out what this attack is showing you is that whenever you instantiate this hash function into a real world concrete hash function, it turns out the scheme no longer is no longer secure. And particularly they're able to generate a valid proof for some false statements which break the soundness of the system. Mhm. >> And the main idea of enabling this attack is because it allows the prover to generate a proof for certain statements where the statements is proving some fosamia heristics inside the statements. And the reason why why it is important to do that is because it

allows the prover to generate to predict this verified challenge inside circuit which given this power they can be exploited to generate a fake proof for some force statements. >> This is you know a result that we knew from back in the day like protocols that are secure in the random oracle model are not always secure in the real model when you change the random oracle for a hash function. But at the time we only had, you know, examples for very weird protocols. Yes. >> Like you have to really come up with a protocol that's really designed on purpose to break.

>> Right. And then this recent paper earlier this year was like the first time that there was a natural protocol that was out in the wild that people used that actually suffers this problem. >> Yes. >> And like Ben is saying it's part of the attack was to do fetch inside the circuit. And that's I think where you're going is like exactly what's happening in folding. We do fashion inside our circuit. But was did that mean that all of a sudden the works were less secure and you felt like you needed to do a new paper to like figure out how to make it more secure or were you already more secure because of some other feature? So this is indeed an attack to a real world system but that's not a mid attack to all the recursive snark system. Okay, >> is only working for this GKR based

system but not immediately working for other P system like Fry, Stark, Plunk, uh, Spartan, Hyperplunk and so on. >> However, it's still worrisome, right? >> Yeah, it opens the door. It says it's possible. >> Yeah, it shakes our confidence. >> Yeah, it change the confidence of it. And especially for recursive snarks because recursive snark is exactly doing the same thing in their attack. their attack is exactly crucially in exploits this fact that you can run this famir verifile or famir hashes inside circuits and that power gives you a way to attack the scheme.

>> Mhm. >> So that give I think give less confidence on this kind of a framework of doing recursion and convert the phone scheme into IVC or PCD using recursion. >> So did you fix it? >> I wouldn't say it's fixes. I just uh like try to remove this attack surface like we don't we don't prove any f shamia circuits okay in the in the statement if that's the case it's much easier to handle this kind of attack because circuit logic is much easier to audit you just make sure that it never runs this fashia hash functions or random instantial random oracle inside circuits >> but in the in the previous framework is much harder to audit because anyway you have to do this right so you don't know

whether there's some kind of really tiny changes that make it tackable or not. >> It's almost like back door in the style of the KRS attack is indistinguishable from what the circuit is supposed to do and so that's super hard. >> Yes. >> Okay. So this new work gets rid of fat mirroring. How how do you do that? >> Yeah. So this new work is called symfony. So maybe before before what it is retrieves I want to mention this why this names. >> Uh there are two reason for this name. The first reason is that if you look at symfony right like this paper is actually inspired by many previous works >> many elegant papers previously if you think about each paper as an instrument

then what we do here is try to just harmoniously combine them together and play all this instrument together to get a symphony it's >> beautiful yeah that's one reason why I call it a symphony and uh the second reason is that I try to advocate a new way to do the folding which is just folding only once or twice. >> So you if only fold sing like fold for single times. So it's a kind of symony. It's a single folding type. >> Nice. >> Yeah. So the main idea or main contribution of this paper is try to advocate a new framework to do the folding and convert the folding into a proof system by two steps. The first step is to do high arity folding rather than low arity folding. Uh what does it

mean is that we want to just to run these folding steps once or even or just twice but in each step we'll fold a lot of statements all together into one. >> If you look at the previous schemes we only fold two inputs or three inputs. I think usually less than 10 inputs into one input. The reason why we can only do that in the previous scheme is because the verified complexity is extremely large. We don't want to add a lot of overhead on the verified circuit complexity >> and the verifier depends on the number of things we're folding together.

>> Exactly. So it's actually a linear relation. So if uh you fold two inputs then the say the complexity is 2 * x. >> Mhm. Then if you fold 10 inputs then the complexity verified complexity will be approximately 10x. So if you fold 1,000 inputs will be extremely large. It's like a 1,000 time blow up on the verified complexity. So that's the reason this kind of approach was deemed impractical in practice before. But it turns out we changed this status quo and we found that actually it is possible to do that as long as you can remove the FIA shame circuit outside the proven statements. So that's the first contribution we come up with a new

herity lad space for schemes but which to verify complexity excluding the fashionir circuit is extremely small even for really large inputs like thousands or tens of thousand inputs. And the second step is to come up with a way that compile this folding hierarchy folding into a new proof system which indeed does not need to embed this familia circuit into the proven statement and that solves two issues right the first efficiency issue we don't need to prove this large familia circuit anymore and second is solve this kind of security issue we no longer have this attacking surface for uh exploiting or conducting these KRS like attacks So that's basically the two main

results. >> So what's the secret sauce? How do you do that? How do you have a snark that from folding that doesn't need to prove recursive statements? >> So actually this is very simple idea. It is built from this commit so-called commit and proof snark. I wonder if I've heard about this. It's a special class of snarks for which the prover can commit part of the witness beforehand before you prove something online. >> Mhm. And then later you can prove a relation that involves both this committed data and some online data >> I guess without doing the commitment inside a circuit right because that's kind of what we're trying to avoid.

>> Exactly. Without doing the commitment inside circuit and that makes it much more efficient as well. >> So let me give a concrete example on how it is used in another paper called Veritas which is another paper of I and Trisha and Dan. >> Oh we've mentioned it a lot on the show actually. It's about proving edits on pictures right? >> Exactly. Exactly. So in that example, if you have a digital signature for some original high resolution image by taking a photo, right? You have some special camera which has a special chip.

Whenever you take a photo, the chip will assign this photo to make sure later you can verify this photo is taken by a human being rather than by by an AI. But later if you want to publish some edited images like if you want to crop the image into a smaller one right how do you prove that this crop photo is coming from this uh designed original photo right in this case commit and proof snark is really useful to do that what you do is just to prove that this online witness which is this cropped photo is a valid transformation of the previously committed witness which is the signed original photo and you only need to prove this transformation you don't have to prove this commitment opening relation and you also have this

signature for the commitment that has been generated previously. So this is one application of commitment and proof snarks and we found that it actually have more application for that in our scenarios. So we come up with a new way to make use of commit and commit and proof snark to turn the following scheme into a non-interactive arguments without embedding fear shami heristics. Yeah, a few questions come up immediately which is which commit improved snark do you use? Like is that also going to be postquantum? And then the next question is if I'm going to use a snark to make a argument you know can't I just use the snark as my argument from from the beginning like do I gain efficiency by

introducing folding in there? So the CP snark is quite general you can use any CP snark you want but it is only possible postcon secure if you use a postcon secure commit time proof snark. Mhm. >> The command proof snark itself is not postcom secure. This compiler will also not be postcom secure but it does have a lot of generality and flexibility on what kind of commit proof snark you can choose. For example, you can choose hashbased. You can also choose kg based point IOP based snarks. >> Mhm. Can we stay in lattice land and have a lattice based one?

>> Yeah, that that was going to be my question. This I was kind of like is there still lattice work involved here? So the lights work mostly are in the folding side. This CP snark uh we kind of take it as black box. If we have a really nice lip space commit and proof snark, we can also use that as well. But currently most of the last space snarks they have pretty expensive verification complexity. So that's why for now we prefer to use hashbased or kg based schemes. But if there are even better last based snark coming up, we can also use that as well.

>> And the second what is the second question? The second one was you're telling us about a compiler, right, that takes a folding scheme and a snark and constructs a snark. And so I'm wondering, well, if I had a snark to begin with, >> oh yeah, >> can't I just have a snark? Like, do I gain something by having folding plus snark? >> So, we do need a snark in this compiler, but the point here is that the snark's work is much smaller than using snark to directly prove the original computation. >> Mh. Because originally you have a really large computation which say is like millions of input statements. But what you can do is compress this million input statements into one statements using the folding first and then just prove that this last statement is

correct using a snark and also prove that folding was done correctly using a commit proof snark and both the commit proof snark and snark's proving time is only related to this folding statements or this folding verification complexity which is much smaller than the original task you have. So that's the reason why you still care about folding because it gives you much better memory efficiency and time efficiency. >> Would that answer your question? >> It does. Yeah. >> Cool. >> It kind of reminds me a discussion we had with Abishalat and Mateo from Google when they were talking about why they chose to do GKR plus Lihero. And Mateo has this quote of like some check plus

something is always better than something, you know? And so it sounds like we're doing something similar here, right? Folding plus something is better than something on its own. >> Huh. >> Exactly. Exactly. >> Are there any other techniques in symphony? You sort of just mentioned samshack for example. You talk about like all of these instruments coming together and and playing together. Yeah. Is there any other kind of influence that you can mention? >> Yes. So first this kind of framework I think is pretty easy and simple but I think is really impactful. I wish this could be a path forward to change what we think about folding. And that leads to more scalable proof system and it's also more robust and secure. And in terms of technical part, the folding

scheme we achieve is also very interesting is a new last space based phone scheme that does support this kind of a vision of using higherity folding. Right? So the reason that it can support this largeity folding is because we do have a much better range proof than before. So the idea is the following. Previously in last 4 plus we come up with a way to do the range proof in a direct way by using this polinomial rings right the high level idea is that you can embed this range values into the coefficients of polinomial and then to check a value is inside this table or inside this range to prove that with certain rotation of this polinomial the con constant will match these values. So

this is a high level idea. Uh it's very elegant idea and if you want to range proof a long integer vector you just need to generate another monomial vector and commit it. But in the last four plus you have what you have to prove is a coefficient matrix are in a low range in low norm which is pretty large. So you do need to some handle extra machinery called double commitments folding double commitments. I won't talk too much about that but it's kind of very complex the protocol though elegant to prove it and what we did is we fully eliminate this overhead and uh we also make this monomial embedding much easier to give a very high level idea the one sentence summary is that the main idea is just

instead of directly proof the range of a really large matrix what you can do you can just first compress this large matrix a little bit by doing a random projection ction you compress this large matrix into a one vector or one column. So you compress this by a factor of D and after that you only need to do ranch proof for this projected vector rather than the original vector and for that you just need to run a monomial commitments compute a monomial commitment once and that's enough and you fully eliminate the second step of double commitments and also uh even in the first step you don't need to compute D commitments where D is the number of columns of this matrix you just need to compute one of them

>> so and this single commitments also very easy to compute. It's just some kind of ring additions. So in some what we can we can get is we can almost get a range proof for free and this is a very efficient folding scheme that lies in the symfony. >> Could you plug that range proof into the you know latis fold and latis fold plus sort of folding scheme and get like lattis fold plus plus? >> Yeah you can say that. Yeah basically that can be supported. Yeah, you can just switch this range proof and use this as well.

>> And that's exactly basically what we did in in this paper like mainly what we do is just we switch the range proof and make it much simpler and faster. >> This is the first technical point. This already suffices for most of applications, right? If you have a really good folding scheme that can fold 1,000 inputs in one shot, then you can already support many application which needs to compute thousands of input all together. But what if you want to do more, right? Suppose you want to prove billions of risk five instructions.

>> Mhm. >> In that case, maybe you want to fold for million number of instances or statements. In that case, is is it okay to still do this? It turns out it's harder because if you do millions of input statements, you have to randomly combine a millions of commitments and witnesses and that itself already leads to a pretty large non-blow up. So to compensate for it, yeah, you have to use a larger modulus and also some larger high dimension. Basically, you have to increase the security parameters to make it secure which make it less efficient.

So bigger field and more proof of work, bigger matrices, bigger commitments. >> Exactly. >> Bigger everything. Yeah. >> Yes. Yes. So it turns out we can actually also support slightly higher folding depths. So you think about that this million statements is a matrix. Okay. Is a square matrix where every cell corresponds to a statement. And what you can do is that you can first compress this matrix into a column first in one step of folding which involves the length of this square of the folding arity. Right? So it's only 1,000 arity folding. And after you have this column vector you compress again horizont or vertically and compress it into a single

cell. And this is the final folded statement. And if you look at it, we have been fold a million statement into one cell which is one single fold statement. >> But what we have done is just folding twice where the first folding is a 1,000 folding. The second folding is also 1,000 folding >> and that's enough. >> I wish we had video here because Vign is illustrating the directions of folding very well. >> That's getting lost to you auditors. >> Yeah. So that's the basic idea at a very high level.

>> Mhm. And uh if you want to support really large arity folding, you can do this in two steps. >> Could you have even more dimensions? >> Yeah, I think you can support higher dimensions even though my paper doesn't doesn't mention this because I think for all the real world application folding twice would already be sufficient >> but I think the idea can generalize to more depths as well. Yeah. So you go from a rectangle or square to a cube and then like four dimension cube and five dimension cube. Whoa. I think you mentioned, Biny, that this paper should be out by the time this episode comes out. So, we'll definitely add a link to it in the show notes. And yeah, maybe there'll be other material about it as well. We're almost at time, but I I

wanted to ask you a question about kind of like diving back into research. >> Last time you were on, you were actually working at Espresso, so you sort of like left Stanford as far as I could tell, but then you went back. What was it like kind of I'm I'm just kind of curious like what is it about doing this kind of work working in these kinds of groups that made you go back? >> Yeah. So I've spent like four amazing years at Espresso as one of the most happy four years when I was there. It's really great to work with Ben and band there. The reason I switched to academia is because like even in espresso even though I also do a lot of engineering

work I'm also really interested in research and always been so I was thinking whether there could be more opportunity to focus on research and I met Dan right Dan is a amazing advisor one of I would say one of the best advisor in the world and uh he offered this opportunity for doing postark and doing research and I found this is a really good opportunity And I think it's also one of the most correct choices I've made in my life. >> So yeah, that's the reason I come back as a postto with Dan and do research here.

>> I also noticed preparing for the episode, I was reading back, I think on your website or your bio somewhere that you actually had Rachel Lynn as one of your adviserss. >> Yeah. >> Yeah. So she was on the show recently to talk about IO and like a whole history of of that line of work. >> Yeah. >> Have you ever like delved into that line of work at all? Yeah, Rachel is amazing is amazing advisor and I also listened to that episode recently. I'm really happy that yeah, Rachel has a has great presentation and uh she's good at explaining everything.

>> So I didn't do anything about obscation even though I think it's a really promising direction. is very interesting and a theoret kind of grow in the cryptography world because if you have IO you can really do a lot of things and we are kind of approaching this right like currently we already have theoretical construction and we're trying to make it practical maybe in 10 years we can even run run a real program that can be offiscated uh but we don't I don't have a paper in IO with Rachel but I do have some other paper like in a bliss ram with Rachel uh which is a great experience a research experience with Rachel as well.

>> What do you think of IO? Like I mean you sort of say it's interesting, but like is that is that a space you might at some point spend time in or if not why wouldn't you? Like is it is it too theoretical? >> Yeah, my personal interest is more like having some really mathematically deep problem but also have some immediate real world impact. Okay. Okay like snark is a or postcon cryptography is one of them and currently f is also one of them for IO I think is a very beautiful problem uh in terms of theory right now and I hope that it can be really practical in the future but at that point I will change my mind and I switch to IO as well but on the other hand is

also very hard question I think is like doing research on purely constructing IO is a really complex process and that's why People consider Rachel's work to be really like impactful and influential as well. >> Mhm. Cool. That's such a neat connection, Nico. I'm glad you brought that one up. I wouldn't have I wouldn't have known, but that's that's a it's a cool link. >> Before we wrap up, last time at the end of the Protoar episode, you left us with an open question, right, about like can we do >> folding scheme from folding schemes from lasses and two years later you're back on with an answer to that question. Uh so to you know continue the cycle.

>> Yeah. Oh, what's the next open problem? >> Open questions that you think you'll come back, you know, in two years with an answer to. I guess in my mind now a new really interesting open question is that so before symfony we don't even have a full security proof for folding based narc right because you have to instantiate random oracle inside circuit after symfony we do have some security proof in the random model for use folding >> but now the question is do you really need random oracle can you use kind of some other more sound and more robust assumption to come up with a folding based nerf. That's a really I think it's a really challenging question and uh I

encourage people to think more about it because even in this current framework I think it's already sufficient in practice because we don't have this attacking surface of KRS for proving familia inside circuit but still we don't have a standard security proof and if we instantiate this random oracle into into concrete hash function in theory still you have attacks right >> so the question is whether we can have more solid foundation for this. I think this is one of the very interesting question. And the second question I guess is whether you can have a fully succinct lattice based snark that is a really efficient even beating the hashbased snarks. Currently we don't

have such a solution yet. We have labrad which has really small proof sizes but the verified complex is pretty large. But there's no signal saying that this is impossible. So maybe in the future we can have even much better last based ner compared to hashbased ns. That's something I don't know yet. >> Let's book a date in two years and we'll see you then. >> Yeah, I'm pretty optimistic. Nice. Well, Penny, thanks so much for coming on for giving us context into the lattisfold work, giving us a lot of background. I think of this episode as a little bit of a compliment also to the whiteboard sessions of both you and Vadim that focuses on this work and then also thank you for introducing us to the

symphony work because this is yeah this is the fresh stuff. It's it's always good to to hear what you're thinking about. >> Yeah, my pleasure. It's always happy to be here and communicate and have conversation with you and Nicole. Yeah. >> Cool. I want to say thank you to the podcast team, Henrik, Rachel, Tanya, and Hector. And to our listeners, thanks for listening.