Episode 345 - Latest ZK Research with Dan Boneh

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online hey so I'm still technically on break from the show but as I mentioned in my last weekly episode I do have the plan to release one or two episodes this fall well this is one of them this week I catch up with Dan Bonet for an update on the ZK research problems and ZK

themes he and his students at Stanford are working on the last time he was on was over 2 years ago so it felt like a great time to bring him back on the show we had a lot to discuss we covered Lattis based snarks ZK in the FHA context extensions on the content Providence work he presented last time he was on the show updates on zkl we talked about folding co- snarks and much much more now before we kick off this episode I wanted to highlight for you the ZK jobs board there you can find job offerings from Top teams working in ZK there are always new jobs being posted so check out the link in the show notes and find your next job working in our space I also want to let you know about zck online 5 that just kicked off this

week ZK hack online is different from the the hackathons we've hosted this past year first as the name suggests ZK hack online is an event that is completely virtual and second it isn't a hackathon it's a format that we pioneered back in 2021 and we've been running ever since it consists of a 4-week workshop series with a CTF like puzzle hacking competition running in parallel we also are hosting a virtual ZK jobs fair to wrap up our event after the final Workshop this is our fifth edition and the event will be running until December 17th so come join us and get to know the zck community to learn more head over to the website over at

zack. deev join our Discord and jump in all links can be found in the show notes now Tanya will share a little bit about this week's sponsor today's episode is sponsored by Alo a new era of decentralized privacy preserving Computing is here Alo a layer one blockchain powered by zero knowledge cryptography recently announced their main net launch now developers can build applications that take advantage of ao's unique combination of permissionless programmability and privacy start by learning their domain specific programming language Leo write and deploy your first ZK application at leo.org or head on over to al.org to learn more about their technology and

what you can build Alo this is zero knowledge without compromises so thanks again Alo and now here's our episode today I'm here with Dan Bonet hi Dan welcome back to the show hey Anna great to be here nice so last time you were here on the show was actually November 2022 it's been a solid two years since you've been on the show um and in that episode we covered what you were working on at the time which was very exciting zi research topics both on the cryptographic side but also on the application front I'm going to add a link to that episode in the show notes just to I don't know if I ever told you this but it's actually one of our most

popular episodes and it's been cited by a lot of our listeners as one of their favorites um so yeah it's really great to have you back on to continue that conversation and to check in wow very cool I will say this too like some of the work that you mentioned in that episode also still stands out very much to me like we talked about I think it was the first time I was introduced to this idea of like using ZK in image Providence to show that like a finished picture that's been transformed comes from an original image and I believe it was the first time at least on the show that we talked about collaborative snarks which also has become quite relevant today um we actually I did an episode about two months ago with the

TSO team who are focused just on collaborative snarks so that's also cool that you know now there's teams working on it yeah it's become a big topic and actually we're going to discuss collabor snarks later on in the episode cool so yeah maybe to kick off what's new with you in the last two years you know what what kind of research have you gotten excited about what are you working on you know there's a a lot going on in the space I have to tell you that the space is so much fun to work in uh there's just uh so much activity all the time I actually looked just before the the show today I looked uh in 2024 I just was just curious how many papers are were published on just unfolding just you know kind of a sliver of the snark space just unfolding schemes and I found like

17 papers on ePrint just in 2024 that's uh it's a lot of papers and a one a lot of wonderful beautiful ideas that uh that come out so there's a a ton happening in the space I guess in in recent um months there's been a lot of work on new code-based snarks um new multi commitment schemes the whole field is transitioning to uh relying much more on some Che some checks than traditional things we've done before uh so there's kind of also a bit of a transition in in space and so yeah there's like new folding schemes coming up all the time maybe we'll talk about some of those later on in the show things like Ark and nebula and others and so yeah there's just so so much activity even in the code-based uh snarks you know things

like Bas fold and Blaze and and and all the other uh schemes that are coming up so maybe we'll we'll get to discuss some of those uh later in the show but actually um I wanted to start with um something very specific I wanted to start with actually the the question of how do we build snarks from Lattis actually before we even do that why would you build snarks out of lates like why would you start to explore that space in the first place yeah that's a great question okay so first of all I guess there's sort of four types of assumptions that are being that are used to build snarks yeah or maybe more generally four types of assumptions that are used to build polinomial commitment schemes so we have uh snarks and polom commitment schemes from pairings we have

them from discret log so I guess from pairings we have kcg and their variants from discret log we have bulletproof and its variants uh from hash based schemes you know we have and many many other types of hash based schemes and then the fourth category is luses yeah and from uh and lates we also have it turns out narks and polor Equipment schemes that uh that one can use um and yeah so there's these four families yeah pairings discret log hash based and lates and so yeah so you ask why why Lattis is well you know the first answer that comes to mind is well L are post Quant believed to be postquantum secure so you know so if we build something from lotuses maybe we'll make them um we we'll get a snark that's postquantum

secure of course the hash based uh snars are also postquantum secure so all the all the four that I mentioned pairings and discret log of course are not uh but hash based and luses are believed to be postquantum secure but it turns out there's another reason to try to build things from luses and potentially we might actually get better performance yeah and we'll talk about that in just a second do you also need like the lattice based snarks I think when I've heard them referred to it's actually been in the context of these FHA combo snarks where like they or they they want to use FHA and that's a different kind of math and if you had strong Lattis based snarks you could use them better with like the FHA models yes amazing amazing amazing that's an amazing question Anna

that's exactly kind of where uh where we're going um but we'll get there in just a second so so we'll see so first of all I'm glad you brought up fhe so fully homomorphic encryption it's uh kind of one of the magical powers of uh of luses that we can build encryption schemes that support uh arbit arbitrary computations if I had to S summarize why lates lead to FH schemes the one sentence summary is that um lce encryption systems have a very fast decryption algorithm and it turns out if you have very fast decryption you can do something called bootstrapping and that actually basically leads down to the path of fully homomorphic encryption yeah so if we had other ways to build

encryption systems with super fast decryption algorithms we might have other ways to build to build F yeah so the dream of course is always to come up with faster and faster way ways to build F actually I should probably say that one more time because uh this is kind of an important point that it's not clear that the way we currently build FHA systems is the only way to build FG systems there could be a completely different path that we haven't discovered yet that might lead to much more efficient and scalable FHA system so this is kind of a challenge to the whole audience you know um it's great to try to think of other ways to do it but let's come back to uh to luses from uh to snarks from from luses um so let's see so there there are a couple of

systems that have been proposed over the last uh last year or two I guess one that's uh gotten a lot of attention is a system called Labrador so Labrador maybe one way to think about it is uh it's sort of adapting the bulletproof type work to the lattice space uh and the reason I say it is because it's also kind of a folding like mechanism and in fact uh in Labrador uh the basic Labrador the L the verifier runs in linear time in the size of the statement sort of like as it does in bulletproof okay yeah so it's a kind of a a succinct proof a short proof I should say but the verifier is not very fast it runs in linear time uh as opposed to logarithmic time which is what or log Square which

is what we would like so uh one paper that uh uh came out recently is called the Greyhound which actually tries to build a polinomial commitment scheme from from Lis and what they do is they kind of take a two-step approach they reduce the verifier time to root n using you know kind of uh a technique that's that's been used before and once they have uh now a PCS scheme a polom commitment scheme that takes uh the verify root end time to to verify then they apply Labrador to get a short proof what's interesting is they they kind of get um they're able to then do commitments to fairly large polinomial so for example maybe just it's worthwhile just saying the numbers like if you want to commit to a huge degree

polinomial a degree 2 to the 30 so it's a billion degree polinomial they get a proof that the evaluation proofs are about 53 kilobytes so not terribly short but also it's not that long for such a high degree polinomial and verification time is about 2 seconds yeah so again not terribly fast but uh 2 seconds I guess is is reble what's interesting is uh if we compare it to like hash based narcs let's say the F based mechanisms for pooms of degree say 2 to the 26 you know these are kind of polinomial that people use f to F to commit to uh the verifier is still about 10 times slower see yeah so the lattice verifier is slower than the F verifier it's better

in other performance in other measures but the verifier is a little is a little slower and this is all Greyhound still this is Greyhound yeah yeah yeah so yeah it's a very it's a very interesting uh commitment scheme from L's and so the fact that the verifier is still somewhat slow makes this a little bit difficult to use in recursive schemes where you do have to run the verifier inside of the uh of the circuit and so there's definitely more work to do there so um the reason I bring it up is this is kind of an area where there there could be potential for a lot more Innovation so this is something that's uh maybe people would be interested in looking at but why am I talking about L based NC so so uh in some sense they they haven't uh been adopted into the snark World

directly but because when you try to build sort of a monolithic snark from from luses you know it's not as maybe um as great as what you would get from other schemes but it turns out surprisingly luses are great for uh for folding for folding schemes yeah and that's kind of uh what we started looking at this is the scheme called the Lattis fold uh this is a joint work with B Chen B Is Amazing by the way he's also applying for academic positions so if you know of an of an available academic position you should jump all over him because beanie is really is really quite quite a creative and amazing researcher in this area is B from from espresso well this is beign who formerly from espresso and curently my postdoc in okay got it nice

uh indeed uh yeah but he's done a lot of work in the space uh maybe maybe you you remember uh protostar and uh well and a lot of many and many other we had him on the show actually I'm pretty sure he's been on the zge podcast so I'll I'll find that episode too and yeah he's also a co-author on bfold and Blaze and lots of kind of exciting exciting development in the space um so yeah so let me talk a little bit about lot of fold so in lot in uh and when you do folding um like in Nova and hypernova I'm sure you've had you've talked about Nova and hypernova and variants on the show what happens is basically those schemes rely on what we call a hom homomorphic commitment scheme right where I can commit to some message m i can Comm commit to some message M

Prime and then I can add the commitments and get a commitment to M plus M Prime yeah these are called L linearly homomorphic commitments and typically the homomorphic commitments that people use is what's called a pedison commitment yeah so pedison commitments they're based on multiscalar multiplications and so uh that's that's what these schemes typically use but it turns out we have another linearly homomorphic commitment scheme and this one comes from lisis yeah and the scheme is actually kind of a classic commitment scheme is called the I Tai commitment scheme I based on the I Tai hash so the II hash in its simplest form is simply a matrix Vector Product Where The Matrix is wide and short yeah so it's a very wide Matrix that doesn't have that many

rows in it and so you can see if you multiply the matrix by a vector what happens is you take a very long vector and the output of the Matrix Vector product is a very short Vector yeah so it's compressing this is why it's a it's actually a collision resistant and then you can use it as as a commitment scheme and because it's a matrix Vector product uh it's additively homomorphic okay so that's the II hash it's a very simple hash uh to describe where does that come from like when was that invented and where like is it from a different part of math and now has been brought in or yeah where is that from oh yeah yeah well it was invented by itai back in the late '90s okay and it was invented for yeah in a completely

different context for a completely different reason actually I love it when that happens that's so cool yes indeed indeed so in fact uh yeah the snark space uh borrows from a lot of different areas of mathematics from pairings discrete log elliptic curves and uh of course hash functions and codes and and and maybe now some uh some lates too so we have this very simple hash it's a just a matrix Vector product uh because of that it's linearly homomorphic and so the question is could we use it for a folding SC yeah so we have a we have a way to commit in such a way that is additively homomorphic so potentially we can use that to fold the problem is that the it hash is is a little difficult to use

yeah it sounds great yeah we have a commitment scheme it's uh it's fast but it's a little difficult to use why is it difficult to use it turns out it's only Collision resistant when the inputs to it are low Norm yeah so the vectors that you hash they have to be short vectors okay if you allow for arbitrary length vectors it's trivially not Collision resistant yeah that's that's easy to see but if you uh if you restrict the inputs to be short vectors vectors that that have a low L2 Norm yeah they're they're short uh then it turns out it's actually Collision resistant in other words it's hard to find two short vectors that will map to the same output okay and from that you can build a Comm commitment

scheme and as we said it's additively homomorphic so great so uh we can throw throw this into folding right so folding as we said is basically based on on adding commitments and the verify all it does is it just verifies that commitments were added correctly so we can throw that into folding and you can say we're done yeah but that doesn't work okay but why wouldn't it work then yeah so it's great question and uh in fact it turns out that uh when we fold what we do is we multiply one vector by a scalar and we add it by a random scalar and we add it to the other vector and so folding sort of inher makes the vectors be large increases the norm of the vectors yeah because folding inherently means you take a random

linear combination of things and taking random linear combination causes things to grow in Norm yeah if you multiply a short vector by a constant you get a much bigger Vector yeah and as a result you can't just use directly th hash directly for folding yeah so that's that's kind of it doesn't just work okay so we need to solve this to do something to it or transform it or yeah exactly so you have to do you have to do some sort of a norm reduction process yeah exactly you you can't just do folding on a on on uh these committed vectors because pretty soon they will go out of the r out of the interval where the hash function is committing and then things will no longer be secure so yeah so what we do is basically we uh we apply a norm

reduction step yeah and this is kind of again very common in the FH world we borrow a technique from the F world where we do this step called decomposition where the way you reduce the norm of something is you decompose it into smaller things you represent it as a sum of smaller things and so what you do is you want to fold two instances each one of the instances you decompose into multiple instances and now you fold all those instances together and you end up with one instance that's guaranteed to still be to still be low Norm okay yeah so that's kind of the the basic uh folding mechanism that's kind of problem one but problem two this still we're not done yet because in Pro problem two is that the the prover has to prove prove to you that the initial commitment that

they gave to you in fact is a commitment to a short Vector yeah so in addition there's a process in in lce fold where the prover provides a range proof to prove that the commitments are commitments to short values and you kind of put these things together and you can actually get a folding scheme from from uh the II hash yeah so I'm oversimplifying of course there's a lot a lot of uh steps involved but effectively you get a very efficient um folding scheme from from the I hash yeah so our our our motivation originally was just to get a postquantum lattice based folding scheme surprisingly though you know but just because the it has turns out to be so fast this actually could be a competitive folding scheme so not only

do we get something as post Quantum it has a potential for do for being even uh well performant so there's actually a company is implementing this now so hopefully I was hoping that by the time we do this podcast I'll have running time numbers for you but everything takes longer than uh than you expect um and so we'll know hopefully we'll know soon uh you know how well this actually works in practice I have a question so the first change you had to make like the norm reduction step does that add a layer to this construction like you have or multiple layers and does that slow it down like does that sort of cut into what makes it so fast yeah it does actually so you know of a sudden instead of just folding two things you decompose and now you fold multiple things and in

addition you have to do an range check yeah so if it was just as simple as replacing pson hash with an i hash everything would be 30 times faster okay but that's not that simple you have to do a few more steps and that actually slows things down of course and the question is you know do we do we lose more than we gain or do we gain more than we lose yeah that's the sort of thing that we'll only discover from an implementation so hopefully you know we'll have uh numbers soon now I should say we're actually working also on an improvement to this so you know the story never ends with snarks there's always way to optimize and improve so you know stay tuned there's there there are improvements to Lattis fold that are that are coming um so so that's all kind

of nice and fun nice but then some something really interesting happened so it turns out because we can now do folding schemes using lates it turns out that the that the rings that Lattis fold uses are exactly the same rings that are used in fully homomorphic encryption wow yeah so that was kind of a bizarre that was a bit of an un that was that a surprise or did you design towards that like was that actually an accident or yeah I guess when you use lates it's kind of a natural thing to use those rings and it turns out those rings are also useful in fhe I see yeah maybe I can I can claim it an accident but really it's uh you know it's one of those things where you can only go one way so you end up uh doing the same things that are also done in FHA is it

because they're like they're borrowing from the same initial like it's kind of coming from the same math yeah same underlying math so you kind of end up with similar algebraic structures yeah so not it's not not not too surprising I suppose but the cool thing about that is is that there's a as you might know there's actually a lot of work in the FHA space now to build custom asex to speed up FHA so this is like everybody's waiting for this supposedly this coming year in 2025 we're going to start seeing asex that speed up fhe wow and the claim is that you know maybe that will speed up FHA by by who knows a factor of 10 a factor of 100 people throw out all sorts of factors but until we um we see the actual asex we won't we won't actually know um so yeah so that what that means

is really uh surprise surprise you know ltis fold can actually benefit automatically from the as6 that are being developed in the in the fhu world um which is kind of interesting but it turns out that brings up a connection between fhe and Lattis based Nars that I wanted to to highlight so one of the issues with FHA one of in some sense you could say it's a limitation of FHA is if I ask you to compute on encrypted data that I give to you the question is how do I know that you did the computation correctly right maybe claim that you did a certain computation on the encrypted data but maybe you did a different computation and the what you send me back is just garbage I see that when I decrypt I'll get garbage right sense it's not that they can see it it's not

that like because it's encrypted so it is like the Privacy is kept intact but it's more that the action that's been done on it could be exactly false or so it's not a confidentiality problem it's an Integrity problem how do we know that the server computed what I asked it to compute on the encrypted data yeah in some sense this is always brought up as a limitation of FH you know there are situations where it doesn't really matter but in in in some cases you would like to basically have integrity on top of the confidentiality so what do we do how do we get Integrity gee if we only had an Integrity providing tool yeah and that's exactly a snark totally yeah so the F world is kind of interested in providing Integrity by actually running a snark on top of the FHA yeah so what

will come back is when you send encrypted data to the server to compute on the Ser will do the computation and send you back the encrypted data along with a proof that it did the right computation yeah this sounds a bit like just this idea of the untrusted server and needing to interact with it it makes me think a little bit of the kosnar world even though I realize like the kosnar is using its goal is to keep that privacy like if you send the information you want proved to an untrusted server the Privacy is revealed and that's kind of the challenge that coars are trying to take take care of here you're using a snark to prove that that untrusted server is acting right exactly exactly actually we'll get to the coars actually

in just a second it's a very very good connection very very preent right so yes so uh so snarks can be used basically to prove that FHA uh was carried out uh correctly and so there's kind of interest in uh for example in Zama in in implementing snarks on top of FHA yeah so you run the F and then you run the AR on the FHA computation itself and so you know folding schemes come to come to mind and in fact folding schemes that are friendly to FHA would make a lot of sense and in some sense ltis fall because it uses the same rings as FHA the two kind of play nicely together so this is something that uh people in the F world are looking at and and then this is kind of one I wanted to jump to the

other way the other direction which is kind of where Co snarks come in so so far we talked about how snarks can be used to authenticate FH computation it turns out that fhe can also help the snark world so how can they help the snark World well this is where kind of Co snarks come in so in a collaborative snark maybe the secret witness that we're trying to compute a proof over is shared across multiple parties yeah maybe naturally the data is already shared across multiple parties and together they're trying to produce a proof that something is true yeah this comes up you can imagine a lot in the banking world where maybe um you know multiple Banks share that like they each have a view of the of the transaction

graph in the world they're trying to prove a global statement about the transaction graph so together they're trying to produce a snark uh that something is true but they're not allowed to share the with to send the data to each other so they need to collaborate in order to produce uh the snark yeah so there's a long line of work on collab collaborative snarks I guess this was started by uh I guess Alex oir and me and and followed up by by a number of works as well and basically how do we get uh collab snarks to work and we do that using using basically NPC yeah so we use multi party computation to um to speed up the snark generation process and it turns out this is kind of an unusual situation where NPC doesn't add a lot of overhead yeah because most of the snark generation

work can be done locally even if the data is shared it's very unusual but this is a situation where MPC is quite efficient it doesn't add much overhead above uh the snark generation in fact sanjum gar actually has some work that shows that not only doesn't does NPC not harm snark generation it can actually speed up snark generation because now you have multiple machines that you can potentially use to generate the snark yeah yeah so that's pretty that's pretty interesting but so how where does FH come in yeah is is FHA replacing the MPC in this construction yeah yeah you got it exactly exactly so so one one thing you might try to do is say well maybe each one of the parties that holds a

share of the of the witness maybe what they can do is they can encrypt their witness under an fhe send it to a central server and now let's think about what is the central server doing so now the Ser Central server has a bunch of FHA encryptions of the witness and it wants to generate a snark on top of the witness so now what it's going to be doing is it's going to be running the snark prover on encrypted data on the encrypted witness how does a verifier though in the end State ever verify back to like it can't verify what was in the encrypted data it has to trust the FHA no no no not not quite not quite so what will happen is you know maybe we should give use a simpler example one way to describe this is we have a

witness that's shared across multiple parties and we use FHA basically to compute on the encrypted witness to compute an encrypted snark but now once we have an encrypted snark that's not useful for everybody for anybody because it's encrypted so then what will what will happen is the parties that actually ask for the snark to be generated will do a threshold decryption of the encrypted snark and they'll get the snark in the clear I think I I followed like you've encrypted it using FHA and then you've sent it over to a snark and all it's making a proof of that encrypted data to and and like the the final thing is a proof that could be verified but to me a verification of that only goes back one step right it only goes back to the the

prover of the encrypted data it doesn't go all the way back to the clear data ah okay so let's let's actually explain it using a maybe a simpler setup yeah so I can maybe I jumped I jumped two steps okay so let's say we have a simpler setup let's suppose Anna you have a you you have a a witness and you're trying to generate uh a snark you know that witness satisfies a certain property okay and let's suppose it's you're you're like a weak device like maybe you're like a you know a cell phone or maybe you're running inside of a wasm virtual machine you don't have a lot of memory you don't have a lot of time okay um what you could do is you could generate the entire snark locally yeah but that that might take uh some effort that might take a lot of memory on your

on your part instead what you could do is you could take your witness FHA encrypt it and send it to a remote server yeah now the remote server could run the entire snark prover on the encrypted witness yep yeah and what the remote server will get from that is an encrypted snark an encrypted proof MH yeah it will send the encrypted proof back to you and now you can decrypt it and get the proof in the clear ah the whole goal of this is the sort of being able to use the untrusted server to do the proof generation exactly I get it okay because I think I was I think I was confused as to like the goal of this but the goal is just to be able to use that computation power yeah actually there are multiple goals here so we can let's

let's go over them one by one so if if you're if you're like a weak device and you're trying to create uh a snark you could generate the snark yourself but then you have to do the entire snark processing the SN the you run you have to run the entire prover yourself okay alternatively you can encrypt your witness under FHA send it to the server the server will run the prover under the FHA send you back the the the encrypted proof and you'll decrypt it so now all you're doing you the client all you're doing is you're just encrypting and decrypting yeah so now supposedly you're doing much less work this is of course a lot harder for the server the poor server has to run the entire snark under fhe yeah right and that's actually where the interesting research problem

uh starts okay yeah so maybe just uh to take this back one step and connect it to collab collaborative snarks in the world of collaborative snarks what happen is the witness is distributed across multiple servers and they don't collude the servers don't collude with one another and they they run an NPC to generate a snark here uh effectively they could all Outsource snark generation to a single server so you don't need this illusion assumption you have a single server that generates a snark but now the single server has to do much more work because it's doing uh proof generation under an FHA but are we imagining this like this untrusted server also could be like an incredible machine with the A6 like it you could beef that up so it could handle it ah

potentially yeah exactly potentially uh yeah that would clearly be have to be a very powerful machine what's interesting is there has actually been a couple there have been two papers on this idea uh now unfortunately these papers don't have system names to it so I can't quite refer to them by by the system names where people can just look it up okay but there are two papers on ePrint that actually talk about using FHA for uh Computing snarks um I'll say one is from uh sanjar's group and one is from ver Catan's group what's interesting is they use uh for example I'll mention the latest paper they they use as the snark system they use fractal and as the FHA system they use what's called a generalized bfv fhe yeah and

I'll just say the claim in the paper is that uh for a million constraints yeah so not too big but you know a million constraints it's still a million constraints the server can do this in about 20 minutes yeah so they can generate the server can generate a snark proof on an encrypted witness in about 20 minutes you know and and the the cool thing is the client doesn't need to do the client is just encrypting and decrypting that's it so I'm not saying this is something you should run out tomorrow and Implement because this is still you know fairly theoretical fairly longterm but what's interesting here is maybe there's there's an opportunity for to to design FH systems that are especially compatible with snarks with snark provs so that the FH computation on top of the snark is not as expensive

as it could be so yeah I just wanted to mention it as kind of a interesting interesting direction for uh for for future work potentially that might make it easier to generate uh snark proofs on on clients with where the the client now just has to do encryption decryption rather than just running the entire proof generation process is the prover on This untrusted Server that's creating a like a a proof in fhe somewhat is it actually using any of the lattice based stuff you talked about before are these very distinct works oh no no this would this exactly that's exactly right yeah so the FH right now is all about lates yeah so presumably the snark that we would like to use would also involve

similar algebraic structures although the work that's been done so the two papers that I mentioned so far is to do this don't actually use lates they're they're more in the interestingly they're more in the hash based uh uh snark world would it be helpful to be lattice because then if you did create like the better Hardware you could take advantage of that like for both because you'd be basically like optimizing the hardware for lattice based everything potentially yeah so again I don't want to get people overly excited about this because this is still very far away yeah it's not clear exactly how this is when this will be useful how this will work you know is it really better than Computing the snark locally uh but I guess in a situation where the witness is naturally distributed across multiple

parties you could think about using a collaborative snark to do proof generation or you can think about using a collaborative snark using FHA yeah where they all Outsource the computation to a single server the single server generates the encrypted snark and then the the participants jointly decrypt using this using a threshold decryption yeah so this is just potential architecture so the future don't run out and immediately Implement these things um these are right now these are still just research directions so last year I feel like I had many conversations about folding but at the time it was like folding only worked in the pairing based kind of world and I heard that some of the folding work was

starting to transition into hash based that people were experimenting but here you almost see like folding breaking out even from there that like the you're starting to see it combined with lattice and the things that that opens up like it's it's a technique that yeah I sort of felt had been relegated to one part one quadrant and now we're seeing it being used everywhere oh folding is going to take over the world I mean the folding is a really really important technique that uh you know it basically allows you to to break a very large proof into many small proofs yeah and and kind of do them all all these pieces do them all all at the same time actually it's interesting that you mention folding in the hash-based uh world because there I want to mention

there's there's been kind of a pretty interesting development there's a paper called arc Arc just recently posted on ePrint it's by Benedict prou Wilson and William uh and that actually allows you to do folding without homomorphic commitments yeah remember how we talked about folding required homomorphic commitments so you either use pedison hashes or I Tai hashes and Arc basically allows you to do folding even though you have a commitment scheme that's not homomorphic specifically it's for hash based what's called hash based accumulation yeah so for hash based schemes um these will also be postquantum and uh and they're compatible with much of what's being implemented today and and so Arc I think

is a that's a pretty important step in the world of folding because it does does allow folding to to also happen on these hash based schemes and so for example if you need to do proofs client side on a low memory machine folding is almost the only option available to you and you know potentially using Arc you could actually do that using a hash B scheme rather than a than a additively homomorphic commitment yeah so it's good to keep in mind Arc is a pretty interesting paper I think all right I think we've covered a lot of ground on the folding and the FHA yes but what else Dan I know there's always many there's multiple research threads that you're always kind of exploring at the same time so what's next yeah so let's let's pop up a LEL I guess maybe we

started a little technical so maybe we can pop up and talk about uh more application applications of snarks so there actually two two applications I wanted to talk about um so one is I wanted to revisit actually the work on using zero knowledge to fight disinformation and particularly to prove image manipulations yes but maybe before we do that I'll very very briefly talk about some some recent work that we did on ZK in the machine learning world oh yeah cool and so the traditional zkl question is the following right you I have some data and you have a model I want to send you my data and I want you to evaluate your model on my data and send the resolve back to me but in zkl you also send me a proof that you

evaluated the model correctly yes yeah you didn't take a shortcut or so on so the the point of zkl is you have a committed model and now I have some guarantees that you evaluated the committed model correctly on the data that I sent you yes it's a bit similar to what you described before words like something's happening in the FHA context you want to prove that it's being run correctly and here in this case it's the ml model the sort of blackbox that they're using you want to prove that they're doing what they're saying they're doing exactly exactly they have a committed model and they want to prove that they evaluated the model correctly with respect to the commitment there there lot bunch of libraries that actually do ZK ml U ZK proofs for ML uh in reason in a reasonable amount of time

what we were interested is is the following question suppose you use you use a machine learning model to decide some some critical things like to decide you know who gets a mortgage or not yeah so you send uh your bank your financial data to the bank the bank run runs a machine learning model and decides whether you get a loan or you get a mortgage or whatever yeah based on the financial data one thing that uh people worry about in this context uh is fairness yeah how do we know that a the same model was run for everybody like how do maybe the bank ran one model for you and one model for me and you know now we're treated we're treated differently yeah so that is something that zkl actually helps with because everybody you can the bank can prove

that all the results are always done using the same committed model right that's what zkl does it's the same committed model that's applied to everybody's data but that's not enough how do we know that this model actually is fair ah so they might have run the same model but it maybe there's something in that model that I guess are you looking for bias yeah yeah yeah exactly so here we're kind of borrowing a notion from uh a whole area called algorithmic fairness so algorithmic fairness is a huge area of research basically how do we test that machine learning models are are actually fair in particular the the notion we're using is called what's called individual fairness which says that similar people should be treated similarly mhm okay so what you'd

like to say is basically you know the bank didn't make his decision based on your gender only or didn't make his decision based on your ZIP code only yeah uh the bank is kind of fair yeah so if you if you and I are similar the model treats both of us in in a similar way well so guess what so we have a system called fair prooof that what it does is when you submit a query to the model you submit your financial data to the model the model comes back with a proof saying yes I used a common model to evaluate your query but I also Pro to you that for your data the model is fair in other words it would have given you the same decision even if you changed like your gender or your ZIP code or other sort of protected characteristics

is it to get that proof though do you have to run it again like do you have to kind of run it with variations and then prove that the outcome was the same so what you need to do is you need to look at the geometry of the model and so you look at the data that the data point that I send you you look at a box around this data point and you Pro prove that in this entire box the model would have made the same decisions everywhere so it's not just a m a matter of querying a couple of other points it's proving that in the entire box everything would all the decisions are are the same yeah so we call this Fair proof yeah it works actually quite well you know not it doesn't work for like uh you know uh chat GPT style models but it does work

for like relatively simple models like what are used for financial decisions um and so yeah this is kind of opening up kind of a new dire for zkl in that you don't just prove that the M was EV valued correctly but you also prove certain properties of the evaluation like fairness so one thing you like you might want to do is uh kind of prove like a universal fairness of the model right that the model is fair for all possible inputs but that usually we can't do yeah these models are so complicated that we can't kind of give a universal proof that the model is fair everywhere okay what we can do is given a particular query we can say first for this query the model is fair yeah that's why the proofs have to be done sort of

online for every query we have to generate a proof that for this query the model was a evaluated correctly and B the response is fair yeah in this in the notion that we defined in this model like is there something that like the ml the ml side of things the ml researchers were already doing to do this kind of verification that we're borrowing or was this all like the whole construction is coming out of your lab that like they were not checking this and now we need to check it for the first time absolutely so this this notion actually is very closely related to what's called a notion of robustness for machine learning where you want to argue that small changes don't change the results this is what's known as robustness what's new is the the ZK part of it yeah

so robustness is something that was sort of checked offline not shared with anybody and now we can actually using ZK we can send it back to the to the client and say look this actually there's a proof here that the model um treated you correctly I see had it been like human Auditors doing that check how well actually right now it's not done but you know what's interesting here is I just want kind of the the the listeners to think more about there are many applications of ZK to ml that maybe we haven't explored and for example proof of fairness is one one thing that uh that uh there is to add yeah there's probably other things in fact we're

working on other other things that we can improve about a model and so maybe the next time I come I can talk about I can talk about that sounds good um so yeah so there's definitely definitely interesting connections between between ZK and ml basically proving that models are used are used adequately yeah that space I think will continue to to evolve so that's on the zase on the ml side I want I wanted to go back to to images because that's I think as you said as you can see that's also something that I'm very excited about y so maybe it's worthwhile just recapping how ZK is used for proving image manipulation MH or image Provence too yeah showing where it comes from yeah exactly um so let's just do a quick quick uh reminder for folks

uh so there's a standard called ctpa stands for Content Providence and authenticity uh where cameras have secret Keys embedded in them every take every time you take a picture of a of a scene basically the camera will sign the scene uh and then as a result a viewer who looks at the image can tell oh this image came from that camera and it was taken at this time using you know this location potentially and the camera was in this and that configuration when it took the image and so it gives you sort of Providence that you know this is a real this is an image from a real camera and by the way what's in what's a new thing that's happened since we last talked is that even the Gen models now will issue a c2p attestation yeah so for example dolly when you ask it to

generate an image for you the image will come with a c2p attestation which is which is pretty interesting and is it saying this is generated by AI That's like it's actually saying okay and because I think when we spoke about it last time we were talking about image Providence more like as a defensive measure against AI like that you could prove that you know a photo had been taken by a certain device by a person by using this kind of zkps through every transition every transformation in this case like the AI itself is also saying like no no this is AI and so then if you were to transform that using zkps you'd also be able to prove that it's AI exactly that's exactly right yeah so so it's image Providence whether you TI it back to a real camera or whether you tied back to

a gen model you'll know where the image came from that's the point so I I think that the hope is that uh maybe in 10 years you know every every piece of content will have some sort of a Providence attestation attached to it and content that doesn't have Providence attestation to it basically will be dropped on the floor yeah So eventually I think everybody will cuz you just can't trust it you don't know where it came from yeah so it sounds like everybody will eventually uh race to generate these uh these Providence attestations and that's how we'll deal with uh you know having some trust in the content that we're consuming yeah we'll know where it came from and you you're predicting 10 years I think be like I have a sense that we'll for sure

see these things before the 10 year mark but I think what you're what you're hinting is that like in 10 years it's like almost everything will need to have it well okay 10 years is to be honest out of ha I I don't know why I said 10 10 years but uh let's just say it's it's at some point yeah at some point I mean I think we we're sort of waiting yeah we're waiting for like the common devices that we're already using to just come with yeah like attested sensors and there are these attested sensor cameras and now microphones there was like one built last year to at a hackathon and I mean they can put it into these devices but it's like the need has to be there especially if there's any extra cost to the consumer like the consumer needs to to want that abolutely and I know the

experiments are there but so far it's not like in everything although I've had this thought like what if Apple just put it in you know like the cell phone companies where you take so many photos from your cell phones like why not add that little attested GE wouldn't that be a good idea yeah right yeah so far I don't think they're doing it but it would change a lot I think if they did at least on the real person image Provence side of things very true So eventually maybe we'll live in that environment now now by the way I should say there are some issues with c2p it's not that's like the technology basically signs uh images that the camera or the Gen generates but you know this is this is not a this is by itself is not enough there's a lot more that goes into ctpa

let me give you just one example like maybe you have an open- Source model that you want to use to generate images well open source models can't sign anything because they can't maintain secret keys so what are we saying are we saying that open source models will not be allowed to generate at images anymore you know so that's that's not good we have to have a solution for open source models too um so you know but those those are there are ways uh there are kind of engineering ways uh to deal with this so hopefully uh things will get worked out there of course there are always other issues with c2p for example you know what if somebody steals the key out of the camera right maybe I buy a camera I kind of take it apart and I'm able to get the key out now I can issue

fake uh ctpa attestations you know we have to deal we have to to deal with that somehow and so ctpa contains includes revocation mechanisms and you know it's it's a very it's a large field let's just say but it's not as simple as just signing images there's a lot more to it than just signing images um but here for this conversation let's just focus on the ZK aspect okay so what does how does ZK come in well ZK comes in when you want to include this in a newspaper article right so you have a a camera that takes a picture of an event the picture now has a signature attached to it but the news newspaper editor hardly ever uses the the picture as is in the article what they will do is they will resize the image you know they'll make it smaller maybe they'll blur some

faces the color yeah maybe they'll change the contrast exactly change colors by the way interestingly uh red eye removal is not allowed I just found that out it's kind of interesting from what the Associated Press the Associated Press is not allow red eye removal yeah that's that's considered too much but you can blur some faces if you want to you can maybe crop part of the image so there's always changes that um the editors actually do and then they put that image into the article the problem is now the newspaper reader will see the edited image and they can no longer verify the signature yeah right because you can't you need the original image to verify the signature but they don't have it so uh what we did is with this is with work with Trisha data and actually also with bin Chen uh we have a paper in

this upcoming Oakland this is something that we uh we talked about this two years ago we we actually even published this two years ago and there's been other other groups have also worked on this um but but uh what's new is I I wanted to just tell the listeners about a cute trick that may be useful to you too so the problem in building ZK oh Sor sorry I forgot to say what the ZK proof is proving so what the newspaper editor will do yeah what the newspaper editor will do is it will remove the signature the ctpa signature from the image and instead it will you know blur and crop and resize and all that and then it will attach a ZK proof that says that the edited image MH um came from a properly

signed ctpa image yes and the only modifications to the properly signed image is this blurring and cropping and resizing and so on yeah these allowed Transformations yeah so now the reader instead of verifying a signature they'll verify the ZK proof and they have some guarantee that uh the image uh of what what the image Providence is usually when I've heard this described to it's sequential so you wouldn't actually you'd like you blur it you create a proof that that blur came from that the image was coming from the previous image with a blur and then the next step would be like and you're cropping so you do another proof kind of proving back have you heard about it ever being combined yeah it's a good point honestly we we also do it one step at a time oh you do

okay um but there's no reason why you can't you can't combine those yeah so it's just mechanically it was easier for us to to do things one step at a time but it could also be it could also be combined but but here's the problem so so naively the the thing you have to do is you have to prove that the image Transformations were done correctly but you also have to prove that the original image was properly signed yeah now the problem is these cameras they will generate a shot to 56 of the image now these are huge images yeah they're like you know the Leica camera that does CPA it's a 60 megapixel camera so doing sha to 56 of a 60 megapixel image inside of a snark circuit

that is death that's really quite difficult okay yeah that's really that's really quite slow uh so forget the image manipulation just verifying that the original image was signed is actually quite difficult yeah so that's actually what the paper is about yeah so how do we get uh signature verification to run quickly inside of a snark circuit interesting what's the name of the paper uh it's called veritos okay Veritas image manipulation proving image manipulation in ZK yeah it's on ePrint and it will be be in the upcoming Oakland conference um yeah so maybe I'll just quickly uh share the core idea so one idea is basically well let's try to improve the hash function let's build a hash function that's as fast as possible and guess what it turns out a hash

function that's really good for this is a lattice based hash function whoa back to lce so cool lates yeah lates are just very fast they are very fast and they're very convenient for snarks to work with um so that's one way to do it so instead of shot 256 let's use a latus and then we can actually generate signatures we can verify signatures inside of the snark at a reasonable cost but it turns out there's even a better idea where we can take all of signat signature verification out of the snark circuits yeah and this is a trick that I want your listeners to to know about so the trick works like this so imagine what the what the camera does is instead of signing a hash a shot to 56 of the image what it will do is it will sign a PO

commitment to the image yeah so let's let's let's unpack that a little bit so what we're going to do is we're going to treat the image as basically 60 million pixels yeah we're going to treat them as coefficients of a polinomial we're going to commit to that polinomial the commitment is going to be very short yeah and then the camera will just sign that commitment so what the camera has to do is basically compute the polinomial commitment of the image and then sign that Pol commitments okay now you can say well maybe this is too hard for a camera to do and maybe you're right maybe maybe my Lac a camera can't do a PCS of a large image but certainly open AI can yeah so the Gen folks that need to generate ctpa images they can definitely um use a PCS of the image and

sign that PCS okay the Pol commitment of the image now why is that helpful well it turns out now the ZK proof just has to prove image manipulation it doesn't prove anything about the signature oh the signature can be sent all the way to the client W so it's a signature on a commitment so you send the signature and the commitment to the client those are all succinct yep yeah and it turns out magically you know using plunk you know trickery basically you can the client verifies the signature outside of the snark and it turns out the snark just verifies that the data that was signed actually matches whatever the snark circuit says and the snark circuit is

just about image manipulation now do you get to skip the Transformations though or do you do you still need the proofs of each transformation no you still need to do the proofs of the Transformations what we save here is you don't need to verify the signature inside of the snark I see yeah and this is kind of a useful trick that people should know about that if you sign a PCS of your message then there's no need to verify the signature of your message inside of the snark yeah yeah and that basically speeds things up dramatically that's a that's a major major Improvement yeah so now all us now we're actually working on Providence for videos and the fact that we don't have to generate we don't have to verify signatures for videos inside of a snark it's a big big Improvement changes everything yeah changes everything

actually I don't know Dan if you've heard of this I think there's another work on video that's come out called Eva um it's actually from one of my co-founders at zkv and I believe they're also tackling this realm so awesome this fantastic fantastic to here and we would love to collaborate with them yes cool cool great nice yeah so always uh this is why this space is so much fun there's lots of ideas floating around and uh it's wonderful to collaborate with everybody totally and it's fun it's kind of I mean you definitely see people go on research projects and then they start to sometimes converge around some solution or architecture or they've they've actually explored very different Realms like I don't think this one this one seems to be focused more on like

IVC uh I don't know that it's doing anything with the lattice stuff so yeah well of course always always lots of ideas floating lots of room for collaboration this is why the space is so much fun yeah um Dan I know that we have sort of reached the end of the main topics we wanted to talk about today but are there any like miscellaneous experiments that you would love to see people doing research on or other threads that you're just maybe starting to explore but don't have deep work on yet yeah yeah absolutely in fact is we could go on and on and on I was going to also maybe talk about accountability in in cryptography but uh maybe we'll leave that actually for next time it's a lot of interesting uh work around that around that uh maybe a good

way to uh to conclude since we're at time is I wanted to mention that actually in the spring I'm starting a a new course it's called applied zero knowledge basically it's going to be uh you know from no knowledge of zero knowledge proofs all the way to how Z kvms work and folding and so on so we kind of take the students through the whole journey uh should be a really fun course to teach I'm excited I'm looking forward to to uh to doing that what I wanted to uh to share is that uh I wanted this is going to be an applied course so there will be programming projects while the students will actually have to write code that uh uses uh or generates snark proofs what I wanted to share is that our community

has made snark proof generation so easy using the zek kvms yeah that now I can't give a programming project to do it because it's too easy yeah it's too bad you know because because of zvm it's not become so simple to generate proofs that that's not an interesting project to do anymore so it has to be the applications so yes of course we'll do programming projects on applications but I also want the students to understand why these proof systems work and why they're sound and so I think what we'll do is we'll do uh programming projects like ZK hack where we take a proof system we deliberately Break It We remove some of the checks in it and then the students's role is to actually come up with a a theorem a statement that is incorrect

but they're able to produce a proof that the verify will accept so they're able to produce uh proofs for incorrect incorrect statements yeah and this is a great way to actually learn how proof systems work and that's exactly what I guess ZK hack is all about yeah one of our projects I'll I'll actually I'll just make a highlight because actually ZK hack online is about to start as we're recording it and by the time this airs it may have just started um for anyone listening who's who wants to maybe get a taste for what you just said Dan for this sort of broken protocol and trying to figure out you know how to fix it so zck does this puzzle hacking competition it's the fifth time we run it it's a multi-week event Series where we do these puzzles every week and there's like a competition to discover

the bug fastest and and do a write up um so I'll add a link to that to the latest which is z hack 5 I'll add that in the show Notes too and if anyone's listening to this later like after the event has already aired we have an entire page dedicated to these types of puzzles as well and actually Dan we did one last year we did yeah that was a fun one in this case do you imagine the students designing these or would you design them and then they have to do something to them um yeah probably we'll do a combination of the two yeah so hopefully by the end of the quarter we'll have a whole bunch of ZK hacks for you who that that you you can use in future ZK hacks that would be so cool nice but anyhow I thought it was kind of entertaining that

now the world of ZK has progressed to the point where just giving a project to build a EK proof is too easy too easy um and we need to do something something different interesting um I think we have one last thing to tease uh as some of the listeners may be aware the ZK whiteboard sessions season 2 are currently airing we have six of the core modules and Dan you have a bonus uh module coming later this year and so yeah I just wanted to like let the audience know that um yeah I don't want to give anything away that's my problem I don't really I'm tell I'm saying it but we're keeping it sort of Under Wraps but there is going to be a module coming

later this year sort of to wrap up the season two of The Zeki whiteboard sessions yeah I'm having a lot of fun fun putting it together so hopefully it'll be a useful resource nice and actually if anyone I mean I'm assuming a lot of folks might who are listening know this but you also were you did the the first three modules in the ZK whiteboard session season 1 um I also would add a link to this in show notes like for me that was my onboarding into the technical even though it came out years after I started the show and years after I was talking to cryptographers and it was like the first time all of those words were put together in one I'm like oh that's what they meant you know like watching those videos were so helpful wow amazing in your course do

you think are you still starting from that place or would you say the space has evolves so much that you kind of like how do you start teaching ZK today look I mean the reality is that this our space has uh expanded by so much that now you can teach multiple quarter courses on on uh proof systems there are also multiple ways of teaching proof systems you know there are Theory courses on proof systems there are uh applied courses there are very Hands-On courses there are like multiple even ways of teaching this material um so yeah but you have to start from the same point you have to start from zero right you have to explain what ZK is what what it's for um and why actually the the most important thing I would say is to

explain why has it become such a big topic like why is it all of a sudden so useful why is there like so much demand for uh for snarks whereas other cryptographic Primitives you see you don't see as much demand for yeah and the reality is just snarks let us do things that we can't do any other way yeah and that's why they're so important yeah if you want to scale ethereum you know the world of ethereum kind of converg to l2s and potentially snarks play an important role there totally well Dan thank you so much for coming back on the show for this episode and giving us an update into the topics that you're researching what you're interested in

also the course that's coming up this spring yeah thanks so much for for sharing all of this yeah I know this has been a lot of fun and uh I hope uh you guys enjoyed it and happy to do it again thanks a lot and to our listeners thanks for listening