Episode 386 - Pratyush Mishra on Tiny Proofs, Folding, Low-Memory SNARKs and More

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 chat with Pratush Mishra, assistant professor of computer and information science at the University of Pennsylvania. We catch up with him on the research he's produced since the last time he was on the show back in 2021. We discuss the topics and themes that he is covering such as working on snarks with tiny proofs with

Garuda and Perry. Folding schemes based on hash functions with his work arc, IOP aka the proximity proofs work with fix and facts, lowmemory snarks, snark applications outside of blockchain and much more. A lot of these topics will be familiar to longtime listeners of the show as his work weaves in and out of some of the most cuttingedge topics in ZK research today. So, it's great to catch up with him. Now, before we kick off, I just want to share that we've launched season 3 of the ZK Whiteboard sessions. The ZK whiteboard sessions are produced by ZK Hack in collaboration with Bane Capital Crypto. This series goes deep on some of the key concepts in ZK. I've added a link in the show notes.

Be sure to check out these videos. They are a great way to learn about the fundamentals and techniques powering the ZK systems we often discuss on this show. Also, if you're looking to jump into ZK professionally or just looking for a new role, I wanted 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 Pratush Mishra, assistant professor of computer and information science at the University of Pennsylvania. Welcome back to the show, Pratush. >> Thank you, Anna, for having me. Yeah, it's wonderful to be back after quite a while, and I'm very excited uh for today's episode. >> Very cool. For this episode, I have Nico as my lovely co-host. Hey, Nico.

>> Hey, Anna. Hey, Patrice. Looking forward to chatting about some nice snark research. Yeah. And I'm happy to have you here, Nico, because I think in this episode I have this sense we're going to go deep into a lot of research papers. >> I have a whole list ready to go. >> Yeah. Perfect. Very cool. So, the last time we had you on, Pratush, was back in 2021. We covered the Arcworks library and before that we had you on for Zexi. But just going back to our last episode, Ark Works, it's been a very important component of the ZK space, and I'm just wondering if it's still an active project, like yeah, what's your connection to it?

>> Yeah. So, and yeah, still a co-maintainer of Arcworks. I definitely have less time than I used to as a PhD student, but yeah, we have my students working on various parts of it here and there and some folks from other universities also contributing >> actually. And I want to hear sort of what's happened with you professionally as well because last time you were on, I'm pretty sure you were still a student at Berkeley. So yeah, what's what's been your path now? You're an assistant professor. Tell me how that happened. >> Yeah. Yeah. So I think last time I was on was in 2021.

I wrapped up my PhD in September of that year. So I think a few months after that podcast and after that for a year and a halfish I was alo working full-time as like a cryptography research engineer kind of a mix of both. But then in 2023 after that I started at uh the University of Pennsylvania as an assistant professor and that's where I've been since since then. >> Cool. What's the department like there? And is there some some sort of group you're part of? like what's the sort of ZK scene like there?

>> Yeah, I think we actually have quite a strong uh cryptography and computer security group here at Penn. So, in terms of other than me, there is Sebastian Angel. He's another professor who works on cryptography and has done a lot of work on more of the maybe applied side of zero knowledge. So, yeah, designing new kinds of zero knowledge schemes for specific applications. We might touch on one work that we've done together maybe later on. And uh we also have Tal Drain. She's on leave right now, but uh she's like a kind of a legend in the field of cryptography, but she's done a lot of work on threshold signing for example. So I think it's of interest to listeners of this podcast.

And I think yeah, we're actually looking to expand the group broadly in computer security. And outside of that, the department has folks basically in every area of computer science. So, it's been it's been really fun. >> I've also noticed you have been doing a lot of collaborations with like Benedict I feel over the years and you have some other I mean Howard, Allesandro, there's a few people I see you've collaborate a lot with. Who else would you list as your kind of collaborators? >> So, yeah, Aleandro was my adviser. So, I think the collaboration there is makes complete sense. I think we started working with Benedict. So there was this program at the Simons Institute in Berkeley that Alessandra had organized um I think blockchains and decentralizing society or something

along those lines. It's like a semester long program with some workshops and one of the focuses was on proof systems. One of these workshops was on proof systems. I think uh Benedict was visiting up from Stanford for that semester. So that's when we kicked off the initial work on accumulation. So we saw the Halo paper and we were like what's going on here? We just try to understand it. So that's how the collaboration with Benedict got started and yeah that's been continuing since then. Other collaborators so I guess Ian Myers I think who you had on the podcast recently.

>> Yeah. >> So collaboration with him actually started way back in 2016 or 2015 or so. He had already worked with Alessandro on Zeroache. And so then we would like when I started my PhD, we started exploring follow-ups to zero cash. Uh so we had this one paper on micro payments and then I guess the next main paper was Zexi. >> Mhm. >> And then since then, yeah, we've had a couple of Yeah. follow-up works like Hecaton and also some ongoing work which will hopefully be on Aprint this week or so.

>> Oh, cool. Maybe by the time this airs. >> Yeah, hopefully. >> Nice. So I think I mean there's a lot to cover. We in disc sort of prepping this Nico you kind of put together some themes. I picked out some papers. >> We sort of merged them into a bit of a a plan. >> So we're going to probably go through some of these topics that you mentioned and obviously we're going to hear more about the collaborations you've been doing along the way. I do have just one question and I don't know how you want to answer it but like what have you been up to since 2021? you sort of talked a little bit about where you're working, but like what are the themes that you think have really stood out to you? Yeah. What what are the lines of research that you're

following? >> Yeah, that's a good question and something I think I'm still figuring out myself. Yeah, I think in general the ZKP space has been moving yeah very fast and kind of diversifying and broadening and there all kinds of different >> directions that people have been taking on like from protocol design to application to like everything in between. So a lot of my work has been on ZKPS and I guess since my PhD I've kind of broadened out beyond maybe these elliptic curve based SNS is what I really focused on during my PhD and I've started to work with more hashbased SNS and error correcting code based SNS.

>> So that's been one direction another direction has been essentially trying to investigate properties of ZKPS and snarks in kind different kinds of computitional environments. So when you have low memory for the prover or when you have I don't know lots of machines and you want to do distributed proving. So basically moving beyond just the standard I don't know server single server style proving seeing what's possible in that space. Beyond that also we've been looking at like applications of SNOX both in maybe more blockchain oriented applications but also in uh kind of non-blockchain settings uh

because I think you know snarks are kind of a perfect fit for the blockchain application space where you have you know you want sometimes the privacy property and snarks are perfect for that sometimes you want really the succinct integrity properties and snarks are again perfect for that but I think in general outside of this kind of perfect match between blockchains and CKPS in other areas of computer science it's been a little bit difficult to provide like a value proposition for snark so I've been trying to figure out various problems in computer security which would benefit from the kinds of guarantees that snarks can give you >> nice that idea of zk sort of accelerating past blockchain I I mean we've seen hints of it we've seen it in any sort of overlap with AI systems

>> sometimes the blockchain's just not even involved there. Do you think I mean it's it's interesting you're saying like we like ZK couldn't really find its place within the other realms of computer science but do you think ZK is now and Snark development do you think it's at the point where the performance is good enough that it's actually a viable option is that what's changed kind of >> yeah I think that's certainly one component if you go back five six years ago were just too slow for kind of non-trivial real software that people ran on their computers So that's improved. I think you know there's still quite a ways to go and people uh like there's massive industry now devoted to that aspect of uh improving snarks but I think it's also a question of do

business needs outside blockchain actually need the kinds of guarantees that snarks give you. So in blockchain it's kind of the entire point is not to have to trust anyone or to like really minimize your trust in certain entities but in the real world like in in the nonblockchain world not real world cuz blockchain is very real but but in the in the non-blockchain world people are maybe okay with just signing a business contract and saying that okay if you don't satisfy this particular part of the the agreement then you will have to pay this fine or you know you will uh this kind of remediation procedure or some other kind of mechanism to to handle that. So you have kind of other ways to enforce that

kind of uh trust requirement. So there's a lot of cases especially you know businessto business where this might uh you might not want the super strong guarantees that snarks give you but there are plenty of problems in computer security which you know you still need these kinds of guarantees. So I don't know like for example today if you download some software off the internet and run it right you don't really have any guarantees that it's not going to do anything bad right so if you can give a proof that this software adheres to certain kinds of you know it only does behavior within some realm of allowed behaviors that would be for example a guarant allow you to develop more secure systems to deploy software more securely

maybe reduce kind some kinds of mechanisms that we have right now which impose efficiency overheads like sandboxing of virtual machines or things like that. >> So, so there's things that you can that computer security focuses on which so far we've tried to develop alternative solutions for where you know the strong guarantees of of snarks can at least we can hope that they can provide some benefits and I think the time is coming we're coming to a time when we can start investigating and looking into that direction.

>> Cool. Mhm. It's almost like we're finally at a point where we can stop looking at how to make better snarks and just look at let's use these like where can we use these? >> Yeah, partially. I think that's certainly one direction we can or approach we can take. I I think unfortunately we're not quite there that we can just like throw a snark at a problem and it'll just work. I think there's still room for doing like kind of intelligent protocol design where you take the application, look at specific characteristics of that workload and then go back and use that to inform your protocol design.

>> By protocol, you mean the proof system? >> Yeah, the proof system. >> Yeah. So, I think we're seeing this with ZKML where people are designing specialized protocols for the machine learning workloads and I think that kind of approaches is very fruitful. still >> mhm >> we semi dismissed the idea of making better snarks but that's not true and Patrice has been working a lot towards making better snarks >> so some of the topics I have outlined is you have works on making tiny proofs like and by tiny I mean like graph 16 or smaller you have work on folding or what we call accumulation from hash functions there's more hash functions in the land of like fry like protocols or protocols that take on that functionality you were telling us before the show that you have

and actually during this intro that work on like low memory environments. How do we improve? So I think those are the main ones we want to hit in that realm of like improving snarks. Where would you like to start from Patrouch? >> Good question. Maybe we can start off with the tiny proofs cuz I think that may be more self-contained. >> Okay. So to give a bit of context, I guess we've been using, you know, Grath's famous Grath 16 proof for a while now. >> As the name indicates, it dates almost from 10 years ago. And back then Yens growth proved that like this was the smallest proof that we could get except not really right. Could you help us qualify that statement and how you got to something smaller?

>> Yeah. So draw 2016 is kind of this legendary proof system that we all know and love and it still powers many many applications >> today. Yeah. So like yeah Yens in that paper he proved both the construction and also he gave this kind of barrier which said that maybe this is the best something like particular barrier is the best you can do. So concretely the construction it I'll be a little bit technical gets a size of two group elements uh G1 elements and one G2 element in your pairing friendly elliptic curve and the result from so that was the the construction and the lower bound or barrier says that the best you can do is a snark with one G1 element and one G2 element if you are

constrained to the kind of construction or construction paradigm that the GR 16 proof system uses. So this is the kind of paradigm which goes back to the first maybe I would say completely efficient snuck which is GGPR 2013 or the Pinocchio >> construction. There were follow-up works like PCTV14 but essentially all of these works they follow this paradigm called constructing a snark from a linear probabilistically checkable proof or LPCP. >> Mhm. And growth essentially showed that if you take this approach, the best you can do is a snark with one G1 element and one G2 element. So that was kind of a benchmark that he had set. Um >> and his paper didn't actually achieve

that that barrier. So he had two G1 elements and one G2 element. So it was kind of an open question to see whether by working in that framework you could achieve even that lower bound. >> Mhm. So that was an open question for I think it still actually is an open question, >> right? So the paper you have I think titled Garuda and Perry does it not resolve that question? How come it's still open? >> Yeah. So that's a good question. So what we did was we said okay this this seems like a hard problem. So let us not try to solve exactly that question and we will make our lives easier by using a tool that we've since figured out how to apply to snarks which is working in this random oracle model. M >> so today essentially like after maybe

after 16 we got this flurry of works which try to construct proofs using a different approach which relies on polomial interactive oracle proofs and polomial commitment schemes and combines these to achieve first an interactive argument and then you apply what we call this fiat transform which basically gives you a non-attractive proof okay and the fashion transform it basically says instead of interaction I'm just going to derive the verifier messages using a hash function or a random oracle. So this is kind of the approach underlying plon uh Spartan Marlin essentially every proof system that uh we use in practice today maybe outside of GR 16 >> uh every proof system uses uh kind of

this in this direction and the interesting thing to note is that GR's lower bound does not apply to this model. So once you start invoking the random oracle you don't have this barrier anymore. So what we did in Garuda and Puri well we didn't actually first of all set off to solve the problem of uh designing very small proofs that happened as a happy accident um which we can dive into in a bit >> but yeah specifically the there's like two snarks in that paper is the one which achieves a smaller proof size >> but it works in a modification of this polomial IOP plus polomial commitment scheme model and invokes a random oracle to bypass this this barrier to avoid the barrier here. So I'm curious now what

was the goal of this paper if not making tiny proofs cuz that's how I like conceptualized it when I sort of read it but yeah what was the hidden goal? Yeah. So this this paper actually started I started thinking about it when I was still at Alo and kind of the motivation there was actually to understand custom gates better because at the time this was like I don't know 2022 early 2023 or so people were starting to deploy custom gates but it was always very tied into the plunk ecosystem but I guess like everybody had their own variant of like okay we have our own custom gates and here's like our own variant of like this plunkish way of writing constraints and I was like

there's got to be something here which you know we can extract out and distill and figure out like what is kind of there must be some orthogonal component because at the time like before that we really everybody was using R1cs >> and >> it wasn't clear that you know this new idea of custom gates or things like lookups can be integrated into R1CS and I think as a as a result people like moving away from R1CS Yes to to towards these plunkish constraints for the more flexibility for the larger flexibility that they offered but I thought okay maybe there's you know I wanted to understand it better and see what was like the core there so I try to initially I guess the work on guran pari

started off by trying to take something like spartan or marlin and add support for custom gates in there and basically trying to create a version of R1CS which supported I guess more exotic gates beyond just a standard multiplication gate. So we were investigating the line of work and we had some ideas which didn't really give us anything particularly exciting from I I would say research perspective >> and also right around that time I think there was this paper which came out >> is it the CCS paper? >> Yeah. So from I think Shrinat Riyad and Justin I think Justin was yeah Justin Taylor >> that came out and it had essentially all of the ideas that we wanted to explore

on that front and essentially yeah they were able to demonstrate that okay there's nothing specifically plunkish about these custom gates and lookup tables you can take those ideas and port them to work in the to a generalization of R1CS and often times actually maybe get better efficiency See because Spartan for example is a very efficient proof system. So anyway that that's kind of uh you know where we stopped thinking about that particular problem or like that line of thinking and then what we maybe started investigating was a slightly related question which is that okay so now we know that you can have generalizations of R1Cs which have support which can support custom gates lookups. Yeah.

>> Yeah. Exactly. And then we also saw that okay if you have something like Spartan or Marlin or things like that you can extend those to support or this kind of generalized constraint system. But what we wanted to do was to maybe take that idea and try to port it back to these trusted setup snarks and see if you could design trust or maybe circuit specific trusted setups snarks to be concrete >> and see if those could also be generalized to support these custom gates. M >> and that's where the investigation initially started. This is like what ended up becoming Garuda. >> So one of the snarks in Garuda and Puri and we were able to show that actually yeah you could get a snack which is even faster than cross 16 for the circuit computations by leveraging things like

custom gates but even actually for plain R1CS. >> Um so we were able to like tie in or bring in like some check- like techniques into this circuit specific trusted setup >> world. Uh but that eventually led to Garuda and we were following that direction and then one day I was cycling back from work back home and then I was like how far can we take these ideas in this paper and then I was like stopped at a and this is like a very vivid moment for me. >> I like that. >> I had like a Eureka moment but I was like stopped at like a traffic light and I was like wait what if you did this you moved away from multilinear polomials moved to unity polomials and then got rid of one group element. I don't know

like what was going on in my head at that moment but I went home and I started writing down and I was like this this should work and then that became pur and that was essentially led us to have a snark with just two group elements and but not quite growth slower limit we also had two field elements in there are these now the smallest proofs that we know specifically parry >> that's a good question I think in very recent work from Liam Egan he was able to reduce the proof size of pari further so P we get two G1 elements and two scalar field elements.

>> I think in Liam's work he was able to bring that down to just one field element which makes that the smallest snark. >> Was that Glock? >> Yeah, I think so. I think >> but is that in the designated verifier setting? So the core idea like the construction that he analyzes and proposes is in the testing and verify setting but the technique can be ported to the public verify setting as well and it like ports in an idea from GR 16 into par to to get rid of that one field element. Mhm. So in a very succinct way just to wrap up wrap up this topic on Garuda and Perry, could you maybe explain how using the random oracle benefits sort of the existing way of making snarks from like growth 16 etc.

>> Yeah. So roughly the idea is that we start instead of starting with the approach that growth 16 takes which is these linear PCPs, we go back to the PIP plus PC scheme approach. And one key idea is that if you look at snarks like Marlin and Spartan, they have two components. One which proves the R1Cs matrix vector multiplication and one which does the hard product check. >> In GR 16, that matrix vector multiplication is kind of encoded in the trusted setup which is why it's circuit specific. >> So we kind of combine the two. So we say we're going to use the circuit specific justice setup to do the matrix vector multiplication and then we're going to use standard POP for doing the the hand product or custom gate check and this required us to generalize polomial

commitments to also allow us to enforce some linear constraints on the committed polomials and leading to like a new notion of PC schemes but essentially like that's the the highle trick which uh we did we combined the two lines of work to kind of take the best from both. >> Really cool. >> Nico, shall we move on to our next topic that we wanted to cover? >> Yeah, I think it's a good time to do so. The next one on the list was folding from hash functions specifically. >> Yeah, folding with hash functions. I mean, we just had Beigny on the show and we were talking with him about folding.

We kind of did a redefinition of folding, but in the context of lattises, >> I mean, lattises build themselves as postquantum secure. My first question to you using folding with hash functions do you get that postquantum securess as well or is it a lesser postquantum secure like how does it compare? >> Yeah. So so the postquantum security guarantee that you would get here is very similar to the postquantum security guarantee that you get for other hashbased snarks like frybased snarks. So it's kind of exactly the same guarantee. In the case of hashbased snarks, people have done the leg work to actually prove that you do get this guarantee. We have not done it so far, but adapting the existing work should

not be like a massive lift. >> So are these all the works that revisit things like fetchir and merkel trees in the quantum random model. >> Yeah. So in particular I think there is this work in 2019 I think from KZA Manohar and Spooner which shows that applying this BCS transform to IOPS gives you a postquantum secure >> argument. I suspect the same ideas can be lifted to the folding constructions as well but yes so the high level bit is probably you don't have any reason to think the answer is no.

>> Okay. How does it stack up? Like are you following the lattice stuff as well >> at a high level? I'm not so familiar with the low-level details, but yeah, I think the the key trade-off between or like the maybe difference between the lattice work and the hashbased work is I suspect that you could potentially get better efficiency in the lattice based setting compared to hashbased accumulation or folding. But I think that this comes at the expense of relying on lisbased assumptions >> versus in hashbased setting, you're just relying on hashes. So there's like a slight trade-off there. To be fair, I don't think I've not kept up with like the latter based schemes too much, but at least to my knowledge has not been an

implementation of the hashbased accumulation or folding schemes. So the concrete efficiency I think is still >> questionable. Okay. >> Yeah. Up in the air. >> It might be a good works inspiration if anyone's looking for it. >> Yeah. I was actually curious with these hashbased schemes. So we also have and a lot of the ZKVMs out there that are hashbased do something equivalent to folding or like accumulation just by doing recursive proofs. So like a proof of a proof of a proof. And usually the promise with folding is my folding verifier is going to do less work than my snark verifier. So when I do this proof of a proof or this fold of a fold, it'll be cheaper to do in a circuit with hashbased accumulation. I'm not sure. Is it really true that the hashbased

folding verifier is cheaper than the the snark verifier? That's a good question. So I think it depends on how you adapt or use accumulation inside your system. >> So today like how the ZKVMs do recursion is that really the most expensive part of the recursion is handling the part of the proof which corresponds to a proximity check or the polinomial commitment opening. if you want to >> take that perspective and that kind of is what often times ends up dominating at least asmtoically and I think concretely as well the cost of doing this recursion and today if you move to a very efficient proximity proof like let's say were

>> then the gap between were and accumulating the polomial or the proximity claims or the polomial opening claims will not really net you much of a efficiency benefit um like you will go from lambda log login hashes or Merkel tree paths to lambda Merkel tree paths which is like a factor of four which is not small but not >> not one yeah >> it's not one and it's also like not something which necessarily leads to you rethinking your system design and like changing how you implement things come with other trade-offs which we can get into in a second but on the other hand you know if you look at things like nova they have this really nice nova hypernova things you know followup works they have this really nice property that

all you need to do is you need to commit to the witness. You don't need to even if you have like very c like fancy custom gates, you don't need to commit to any additional vectors which might increase your proving costs. Once you start going down that route and designing your system from the ground up to really just incorporate those techniques really you will only have to open commit to an open one Merkel tree path inside inside your recursive proof. So this kind of like leads to I guess maybe what we describe in our papers as two benefits of accumulation of folding. One is that your size of your recursive verifier gets smaller and also the work that the prover has to do just to even prove your original computation excluding the recursive part that also

gets faster. Uh so you get both of these benefits. >> Mhm. >> And now like if you're just trying to throw an accumulation into an existing system, you probably will not get the faster prover benefit. You will get the smaller verifier benefit. But as we discussed that is like a little bit less compelling that the faster proofer benefit. But if you design your entire system from scratch to leverage these properties you will or like the benefits of accumulation then you you can get concretely I suspect much much larger speedups than just doing naive recursion.

>> Mhm. >> The work that sort of showcased some of this research at least the one that you know we we noticed was arc accumulation for read Solomon codes. Can you share a little bit about that and how like what you found and >> Yeah. Yeah. So the starting point for that was actually a little bit prior was this paper called accumulation without homorphism which tried to first investigate accumulation for I guess hashbased accumulation. Uh and the scheme that we constructed in that did have some limitations. It it was like the first scheme which did hashbased accumulation but it had this limitation that you could only fold or accumulate up to like some fixed pound. So when you

set up the system you would say okay I can fold I don't know 10 snarks or 10 proofs and then I'm done now I don't have any soundness guarantees even and moreover your efficiency would worsen like if you increase the bound you could increase the bound like from 10 to 20 but now you're every step you're paying like 20x as opposed to 10x. So this was the initial work and then so arc is basically I will say really a a brainchild of uh William Wang who's a student of Benedict's at NYU and the key insight came from looking at >> was it stir >> a stir >> ah >> yeah which essentially said that like the the core problem in accumulation without homorphism was that we were doing these kinds of spot checks to

check that the folded output was consistent with like the inputs and we were incurring some kind of soundness error which kept growing over the number of foldings that you did. And the key insight that William had was that I guess William and Benedict had was that you can actually leverage techniques from stir to avoid that loss entirely. avoid that additional soundness error by leveraging techniques developed in in stir >> and that allowed us to get yeah kind of what you would want out of an accumulation of folding scheme which is unlimited number of foldings for those that are curious there's also a follow-up paper

>> called linear time accumulators which kind of does the same thing but uses ideas from were >> so you know stir were is an improvement on were by improving the exact ideas that helped here for accumulation And so the natural thing to do then was to say like all right let's improve that technique also in the accumulation scheme. >> Yeah. So there actually two works. So one from Benedict and Alessandra which was which took arc in in one direction which led to this paper warp which is linear time accumulation and then my group here also. So my students and I we also had an alternate way of constructing this linear time accumulation scheme. So I guess like the thing that was left to do from ARC in some sense was that ARC worked with read

Solomon codes which mean meant that you had to do things like FFTs which lead you to have like this analog and prover time and also place constraints on the kinds of fields that you can work with. You need FFT friendly fields. Uh but recently people have developed these things called linear time encodable codes which offer O of N encoding time as opposed to O of N login encoding time. So basically both warp and this work fax they say okay let's take arc and try to fix this or remedy this n login and prover time overhead and bring it down to linear time by working for linear time encodable codes. So, so yeah, just expanding on your comments >> right actually I'm really happy that you mentioned facts because that also comes from a paper fix and facts that almost does the link to the next topic I wanted

to talk about is you also have works on proofs of proximity so we talked about stir were but you have fix and I guess in a way we've been talking about this duality every time there's an improvement on one side you can port it to the other >> uh it makes sense that you would have a paper that looks at both at the same time right >> yeah yeah so yeah we can segue into talking about proofs of proximity So I think we've vaguely mentioned proximity claims and like how these are the main bottleneck in snarks but just in like one sentence. So today like when I construct these hashbased snarks usually what the prover does is it encodes its messages using some error correcting code and then one part of the protocol is to prove that these messages actually are close to like valid code words.

Okay, so this this portion is called the proximity proof. And so I guess really what kickstarted the efficient hashbased stock revolution was this protocol called Fry which we have you guys have talked about multiple times on the podcast and everybody really in Snarkland has heard of I'm sure >> but this is like the first protocol which kicked things off and then I would say that we kind of >> yeah we used it just kept getting used >> there was like deep fry there's a little bit of variation but yeah it was really only with were or stir which one came first Nico go as it were >> stir.

>> Stir. So it was Yeah, it was only really with stir where we saw this like step change I feel. >> Yeah, exactly as you said Anna, right? Like we ran with it, we applied it but then we didn't really see too many new constructions. Then we had stir in I think 2024 which gave us some glimmer that okay we can do better >> and then like we saw like a flurry of works in like the small small proof setting. we saw like a flurry of works. There was Basefold uh and then like recently there was Blaze which kind of showed that okay you don't actually have to stick to just working with these read Solomon codes. So you can try to do proximity proofs for like small proximity proofs for other kinds of codes and in particular blaze does this for at least linear time encodable codes

which as we talked about you know they only require linear time to encode as opposed to quasi linear or n login time for resolment codes but like essentially blaze show that okay you can get for particular kinds of fields IOP interactive oracle proof of proximity or p where after you apply your fat shimir and local trees and all of these things you can get something with proof size. I think it's lambda log squar n hashes something like that. >> Everyone at home is following and they have the there's some topics in mind and they know exactly why this is good.

>> So lambda is a security parameter but yeah so basically it's scaled with like log squ and but if you look at the race solomment side what stir and war were able to do was to bring that down to like like login log log n time lambda hashes. So basically reducing it by this factor which led to like a concrete improvement of like 2 to 3x which is important when you want to like put these proofs hopefully on the blockchain. Uh so essentially what we did in fix was try to see can we port these same benefits over to these linear time encodable code settings and so what we took was this core idea which had appeared in blaze and maybe a couple of predecessor theoretical works which is code switching. And we can talk about that in a little bit if there's not other questions that you want to go over

first. >> I mean, I definitely want to keep some time for the non-blockchain applications because we did tout those early earlier in the show. But yeah, curious about maybe a few words on on how fix applies code switching. Does fax do it too? >> Yes. So both fix and fax do code switching. So essentially like the summary is that re Solomon codes they have this really nice structure which allows you to do things like folding in fry very efficiently but linear time encodable codes they generally don't have this kind of nice structure. So code switching is basically this technique which says okay we don't have the structure. What blade is going to do is kind of just prove that our code words are actually close to the code.

We're going to design specialized proofs for this task. So Blaze does that in one way and in fix we take an alternate approach. to design new code switching techniques and also show that existing code switching techniques can all be put in like one framework which allows you to do code switching for a large class of linear time encodable codes and kind of brings over these proofsiz benefits that you got with store and were also now to these linear time encodable codes and then it's kind of culminated in this very recent work which went up on e-rint which allowed us to kind of even get rid of the log login factor and get proof size of like lambda login hashes What was that work?

>> So this is a paper called query optimal IOPs. Um >> ah this is the IOPs. Okay. Interactive Oracle proofs of proximity. >> Yes. So we actually show that kind of this is the best kind of proof size that you can get for these proofs of proximity which is why we called it optimal. Um but it's mostly a theoretical work for now. I don't think the ideas would lead to concretely better proof sizes. >> What do what does fix stand for? like they look like acronyms. >> Yeah, great question. So, we kind of took inspiration from the Fry name. So, Fry was like fast read Solomon Oop.

>> So, we just were like fast IOP via code switching and that became >> okay via Okay, so that's what it is. And then the other one would be fast a >> accumulation >> accumulation. Okay, >> it's not too creative. I would say it looks cool in short form. Yeah, it's like sticks and stones or like fix and facts. Kind of what I was going for. >> Nice. >> Very briefly, you talked about code switching, but why do we want to switch codes? >> So, the idea is that I can go from a claim about basically like this code word is close to code one. Uh I can reduce that to a claim about you know code this other code word is close to a claim in code two. And now code two can

be either like a smaller size code or it could be something like a read solomon code for which we already have existing IOPS. So by being able to switch you know claims from code one to code two we're able to kind of make progress either by reducing the size or you know being able to invoke tools that we already do. So this fix kind of does both. We use code switching to reduce size and then once it's small enough we directly invoke something like uh stir or word. >> I see. And so in that case we don't care that we're doing readman codes because the problem is already smaller than the original one.

>> Yeah, we invoke it like enough invoke the size reducing code switching to get us down to like n over login size and then at that point read solomon codes at linear time. >> So wrapping up on our topics of making better snarks. The last one that I listed or mentioned earlier was how do we get proofers for snarks in an environment where you have like restricted memory. So I mentioned this because you have yeah a few papers. Exactly. What's an example of that setting? >> Yeah. Yeah. So I think that's a very exciting area that people have been starting to focus on recently. But it's really motivated by applications where you want to produce proofs on very constrained devices like let's say your

web browser or your phone or maybe even more restricted than that maybe to the extreme you can take it like on a UB key. Can you do proving on a UB key? >> Mhm. >> That would be really cool. We're not there yet. Um but yeah in generally kind of this lowmemory proving is focused on trying to do proving when your prover has only a small amount of memory like trying to prove maybe large computations in that small amount of memory. I think it's become interesting recently because for a long time we were focused on improving prover time but now we have made good progress on that. So now we kind of end up being bottlenecked by the amount of memory on a single machine or device. Okay. Right. So, we've had Mu on

the show from Lgerero who very proudly advertises that Lgerero doesn't need much memory to run the prover. So, I was wondering is it a solved problem or do we want to go smaller and smaller and smaller? >> Yeah. So, so Mu's work I think is Lehhatron was the underlying proof system. So they they do like a very clever system design and proof system code design which allows them to get this kind of prover which is called a streaming prover which we can talk a little bit more about later >> but I think at least as far as I understand the downside of that approach is that you end up with a linear time verifier and at least for leero and I'm not sure if this is inherent to this approach it might be at least for leero this also gives you like a square root

proof size which might be fine for a lot of applications concretely but Yeah, it does mean that the verifies linear time in the original size of the computation. I think once you start caring about smaller proof sizes and very succinct verifiers, it's I think it's still an open open question which yeah, we've been a lot of groups have been trying to make progress on including my students and I >> what are some of the breakthroughs that have come around to allow for this low memory snark construction? >> Yeah. So I think I mean in some sense we did already know one way to do this very efficiently which is via recursion. >> Okay. Okay. If you do recussion or holding then you only ever pay for the size of one step as opposed to >> the entire computation.

>> Yeah. Like I think Mina back in the day was always kind of you know was very small. >> Yeah. And then that gets you like small proof sizes. >> The downside is that with recursion and folding in general we don't have a very good handle on the security in some sense like we're proofs of security are only or soundness are only for like a constant number of steps which is not how we use these things in the real world. >> Yeah, this is also something we mentioned, by the way, on our recent episode with Bingi. >> So, for those interested in more details about the security properties, I really recommend that episode.

>> Yeah, we'll link to that. >> Yeah. Yeah. And it's kind of also become more of a concern, but like this attack on GTR based proof systems, which >> cuz you need to use hashes inside the circuit. But anyway, so >> those things work. They do have certain both theoretical limitations >> and security ones. >> And security ones. Yeah. I think I think in generally it's also interesting to see if you don't want to go for recursion like what is the best that you can do are there like some barriers that you run into so I guess in that vein what we try to do I guess my students and I is to construct kind of these monolithic SNS we're just trying to prove a full circuit instead of breaking it up into chunks and proving each chunk separately and there we had two approaches the first approach is this

paper called scribe and the idea there was that okay even on many devices which do have limited amount of RAM or memory. What they do often have is like a large amount of disk space, right? Gigabytes even in like your >> entry level iPhone. So what we did was designed a prover where instead of storing all of the provers staked in memory, we were able to store it on disk and we made sure to design protocol in such a way that accessing that memory was efficient. So normally access accessing the disk was efficient. So normally accessing disk is like way slower than accessing memory like 10x at least but the algorithms that we designed were able to kind of completely

mask the overhead and in particular we designed like this version of hyperlunk in this model where the proofer state is on disk >> but the overhead compared to inmemory proving was like 10%. >> Okay. >> Is this what you described earlier as a streaming prover? Yeah. So streaming prover Yeah. It's actually a entire area of research in theoretical computer science and streaming algorithms. >> Nice. >> But a streaming prover is yeah a further restriction of this which just says that this prover is only allowed to have some small amount of memory >> and it can access the witness and the circuit description via stream. So sequentially it can read like the first bit of the witness and then it has to throw it away and drink the next bit and so on and so forth. This is a very

restrictive model. What P said was okay you don't have to throw it away. you can just write back that bit of witness or whatever you processed to disk so that if you need it again in the future you can read it again. >> Mhm. >> I guess streaming provers they actually are slower than the memory intensive ones. But with our construction we were able to kind of both asmtoically and concretely bring the overhead down to just 10%. >> By the way, is that why you called it scribe because it's streaming and it's also allowed to write? >> Yes, it's scribe because it writes down. >> Nice.

>> What's the second approach? So, so the second approach actually is to stick to streaming and this was this other work called the time space trade-offs for subject. Um, so the subject protocol is like kind of now the work costs of all efficient snarks essentially. >> Yeah. >> But the algorithms that we use for it, they kind of fall into two categories. either use a very small space but then you incur like n login proving time which concretely translates to like a 30x overhead for the sum check or you use like a linear amount of space and you take linear time which is the best you could hope for.

>> Sure. Uh so we were trying to investigate okay like what if you have a middle ground like you use like not tiny amount of space like a medium amount of space can you do better and so the predecessor like maybe the inspiration for this was this paper called blendy from Alessandro's group at EPFL then my students and I kind of picked that up and you know we reached out to them and we were able to say okay are the results in blendy the best you can do they were also like only for a particular class of some which is not actually how we use it in protocols. So we were able to generalize that to actually how we use some check-in protocols and showed that yeah you can do better than kind of the two extremes that I had mentioned

earlier. you can get something which is almost as fast as the high memory version like I think in practice only 2x slower but using I don't know like 100x less memory for large sizes >> and we also I think the cool part is we were able to show that kind of this is the best that you can do if you want to use a particular amount of memory you must incur let's say this 2x overhead you can't do better than that which I think is >> kind of a rare occurrence in snocks we don't usually have these kinds of lower bounds So these two approaches both lowmemory snark constructions are either of them similar to liarero or to other systems that we've maybe talked about on the show.

>> I would say you can take ideas from Learo and apply them here and maybe hope to get like a better system overall. >> Maybe some limitations of Lehero can be lifted by using for example our time space trade-off the new subject algorithm. Actually concretely like there are some barriers to what you can do with leerero style systems where you have these hashbased streaming snarks I'll paraphrase you must either have not small proof size like not poly loarithmic like tiny proof size fry style proof size >> you can either have that or you can have streaming provers you can't have both at the same time >> so like if you take this kind of scribe model then you can actually do both or we think that you can do both this is

like some follow-up work that we're working on And we're hoping to show that you can actually get both very small proofs and lowmemory provers. >> Cool. >> So yeah, I think that's like a interesting direction for people to investigate and uh in the future. >> So I think we've covered the work to date in some of these themes that Nico you first presented and Prushi brought up. There is another category that you were talking about at the beginning of the episode which is like nonblockchain the sort of move away from you know the problem space that we we mostly talk about on this show. What are the kinds of things you're doing over there and and yeah I'm assuming there's also some collaborations happening there. Yeah,

maybe you can share a few of those initiatives. >> Yeah. Yeah. So I guess like all of the things that we talked about so far are very much on the snack construction side. Yeah. on like the other side on application front I've been looking at with some collaborators at maybe non- strictly blockchain applications I think they have applications to blockchain use cases as well but yeah like uh one direction has been uh this is in collaboration with Sebastian who's a professor at pen on proving that if you have some kind of committed document that it actually satisfies some kind of structure so for example it's a valid JSON document with a particular entry or it's a valid C file L or something along those lines. So anything which can be

captured by a contextf free grammar. >> Is it like proving a certain language or like is it saying this is written in XYZ or is it more general than that? >> Yeah. So in general it's proving that it matches the specification or format of a particular document format. So like looks like a C file or looks like a JSON file. And the applications for this you know we discussed a few in the paper. Some of them kind of relate back to very blockchain adjacent applications. So like ZKTLS right now when you get a response from the server you just assume that it's a properly formatted response and uh you know the email field in the response would always be at the same location. But you know if the server you know who is does not know anything about

your application changes the response format even a tiny bit suddenly now maybe all your guarantees about your ZKTLS application go out the window. Yeah. >> Similarly for things like ZKL login or APTOS keyless which rely on like particular formatting of the JWT tokens. >> Yeah, >> we can add some links to that. We covered that on the show with a couple of those teams. >> Yeah. So where coral would come in here would be that you actually can get a proof that now this response from the server or whatever actually matches this exact specification that you wanted. So you can get like a stronger guarantee that way. Does it also prove statements about the contents of the file or just the formatting?

>> Yeah, so you can prove that it contains I don't know nested two levels deep an email field which has uh I don't know pratush at pen.com or whatever or pen.edu has the email there. >> That's cool. The title of this work coral fast non-interactive zero knowledge cfg proofs is cfg this contextf free grammar. Is that what that stands for? Yes, it's context grammar and it's just like a followup work I guess that Sebastian's group has done previously on regex or proofs of regex matching which people have also used in very blockchain adjacent application contexts.

>> Yeah, I was interested to see authors from Brave as well on that paper. So the the browser company are they looking into these sort of ZKTLS proofs like is that why they're here? Yes, I think Sophia who's was the co-author from Brave, she and her collaborators have been working on some CKTLS work and so she made that connection and that link between Coral and this limitation of existing CKTLS protocols >> that sounds like that would be really fun to explore with them actually. This is like, you know, a team with with users who are now it's like the the browser producing the ZKTLS unlike most of the teams that we've talked to which are ZKTLS teams kind of approaching browsers potentially as customers.

>> Yeah, that would be really cool. >> So you mentioned this is an extension of previous work from Sebastian's group and I now remember there's a paper called Reef. Is is that the one that's being extended? >> Yes, that's why we called it Corora because it generalizes Reef. It's very nice. And so it uses Nova, right? Like deep inside it. >> Yeah. Yeah. So yeah, it's uses like our modifications of Nova. >> I'm curious what other non-blockchain applications have you been looking at or are working on? >> Yeah. So I think one exciting one slightly different from Coral is we've been working on this proof for verifiable database queries or this proof system for verifiable database

queries. And the idea there is that you have a database owner who provides a commitment to the database you know which contains whatever you would have I guess in a standard database and then you could have client and server who interact and whenever the client wants to make a query into the database the server can now provide a guarantee that hey this is the result of the database and moreover here's a proof which shows that this result is correct okay and I did not cheat in answering your query and this is verified with respect to that commitment to the database that was provided originally. So it's like the highle application and there's been a few works on this previously. The first one I think was this verifiable SQL back

in 2017 or so from Yupang Jang who's now. But yeah, I think the line of works they incurred relatively high overheads even for I would say not too complex queries and for not too large databases. So we have this kind of ongoing work which tries to reduce that overhead a lot and I think we're able to get subminute I don't know proofs for complex queries on like I would say fairly large databases. >> Interesting. Yeah, I remember seeing a paper by Mateo Campanelli on on that topic as well. Uh, and so is this what you're saying was sort of advocating for in some contexts it might be better to design our proof systems with the

application in mind rather than using the snarks that we already know and love. >> Yeah. Yeah. So that's exactly where that comment was coming from. Yeah. Yeah. Yes. So because what what we do for this project is actually we design very specialized like POPs essentially for >> the core like uh SQL operators um like joins and selections and group buys and all of these things and because of that and by not going via the circuit approach I think we're able to get like orders of magnitude speed ups compared to like a circuit based approach and throwing a state-of-the-art snar at it.

Just on the topic of where this might be used, and I don't know if this is the correct link, but a few episodes ago, we did an episode on turnkey, which was like a TE solution. They talked about like not trusting the database. >> And I wonder if something like this could be helpful in in their situation. >> I don't know if you've like I I might be making a connection that isn't there, but I don't know if you've heard anything about that. >> I did not listen to that podcast episode yet. I It's on the backlog. Um I think I think in general like there's lots of applications where this would be helpful. There is one blockchain application which I think is being explored by some industry folks.

So I think Lrange labs this was like what they had started off trying to do basically >> trying to provide like you you view the historical blockchain state as a database and then >> because smart contracts it's very expensive to give them access to this historical state. you instead just give them a proof that here's a state and here's a proof that the state is valid with respect to the I don't know commitment to this to the blockchain to the blocks or whatever. >> So this is the whole co-processor narrative from a while back right? >> Yeah kind of yeah so that that's one application that I think space there's a company called uh space-time labs or something like that.

>> Yeah that's been around for a while. >> Yeah. So they've been looking at this application and >> there's also a company called provably. So this material paper that I mentioned I think is with co-authors from provably and that's also what they do. >> I see. Interesting. Yes. So I think that's like a very interesting application because you do actually have very constrained verifiers. Another application that we've been thinking about for this system is basically to give you like a proof of deletion. So like in a non-blockchain context like under GDPR if I make a request that you delete my data >> right now you have to take the company's word for it and auditors have to do like a really expensive job of like checking this or they just you know do some spot checks but now you can have the company

give you a proof that here is my database and here's the updated commitment which I'm going to publish for everyone to see and I now I can prove to you that your entry is not in my database anymore. >> That's so cool. I mean, this this sort of makes me think of the ZKID cases where they talk about like removals or what is it like >> revocations. >> Revocations. Exactly. But this seems even more general purpose what you're describing could be used for so many things. Yeah, that's so cool. >> Yeah, we are very excited about the project.

>> Nice. So I'm I I think in general kind of these non-blockchain applications they motivate both like designing snarks for applications and also kind of the low memory proving because often times now the focus or the proof generation I guess device is not a beefy server anymore but is like as a client phone or browser or whatever. So I think I'm excited for progress in in that direction. in that direction. We're actually investigating everything on all of the topics that I mentioned.

My students are keeping me very busy. >> Cool. >> Yeah. Essentially, all of like the projects that I mentioned are the hard work of my students in my group and my collaborators and I'm mostly there as like a figurehead. >> I wanted to ask you, this is sort of a last question about like your move to professor to assistant professor. Are there ZK focused classes happening in the cryptography departments at this point? Like I'm just or is it like a chapter in a larger class? Like I'm just curious how it's sort of spreading into education.

>> Yeah. So it's actually both. So I teach cryptography which is like the broad course and in that I have a portion at the end where I teach CK. Actually the last time I taught it I taught like a very simplified version of the proof underlying NOVA. I don't know how many of my students understood what I was saying. Uh >> it's like a cutting edge one to start with. >> Yeah, it's actually it's simple enough that you can explain it, but it's actually good because they can like feel like they're at the cutting edge of uh research and I also teach in like the other semester kind of a proof system oriented class which actually >> we just finished up one of the lectures before we were recording this.

>> Cool. But yeah, that one talks about both the applications and design of of SNOX. So it's like that's more oriented towards PhD students. >> But I know at other places folks are also investigating more like a mix like where they >> talk about other crypto as well and that's oriented towards undergrads. >> Dan Bonet told me last year I think that he was doing a ZK course for the first time and I think he's doing it again like next semester. I just think it's that's quite amazing you know. I think at first it was a footnote and like maybe a cryptocurrency class or something, you know, like something and then it's a chapter and maybe a lecture and now it might be a class for some for some people. I think that's so exciting.

In your courses, in the work you're doing, are you also touching on any of these more advanced cryptography topics like FHE, MPC or IO? >> Not in my course. No, but I know other folks who do who do like even in the applied courses they talk about FHE and multi-party computation. Very cool. Patrice, I want to say thanks again for coming back sharing with us all of the work you've been doing since 2021 and it's a lot a lot of different directions. So, it was really fun to sort of go on that journey and it does sound like I mean there's overlap between them too. There's clearly like through lines. So, thanks so much for sharing that with us.

>> Yeah, thank you so much for having me. It was a wonderful time. Thank you both. It was great chatting. >> Cool. And I want to say thank you to the podcast team, Rachel, Henrik, Tanya, and Hector. And to our listeners, thanks for listening.