Ron Rothblum on Fiat-Shamir Attacks, Flock and SNARK.fast

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, Kobe and I catch up with Ron Rothblum, professor at Techneon and researcher at Succinct. We last caught up with Ron on the show back in 2023.

And in this episode, we had a lot to cover with him. We discussed the Fiat Shamir attack. He worked on his polomial commitment work with Blaze, TensorWitch, and Bolt, as well as Veil, a native hashbased way to add zero knowledge back to succinct proofs. We covered his most recent work on Flock, including its role in the Ethereum Foundation's move away from Poseidon. We then explore Snark.fast, a collaboration with Igen Labs, Succinct, the EF, and Espresso. This open competition holds the flock verifier fixed and challenges the wider community to use their AI agents to build a faster prover. And the results have been well beyond what he expected.

We close on where he wants to take this next with Flock V2 and a binary field ZKVM as well as his long-standing goal to get ZK proving to be as fast as computing and what a world of fully verifiable computation might look like. Hope you enjoy. Now, here's our interview with Ron Rothblum. Today, Kobe and I are here with Ron Rothblum, professor of computer science at Techneon. He has also been working at Succinct since 2024. Welcome back to the show Ron.

>> Thank you. Great to be here. >> Hey, Kobe. How are you doing? >> Hello. I'm good. >> This episode came together a bit because of the phenomenon of snark.fast, something I had been seeing a lot about. I was talking to Kobe about this and we realized that Ron, you're behind this, you're working on this and we also hadn't spoken to you in a long time. So, we thought this was a great opportunity to bring you back. But then in planning this, we realized, yes, hopefully we get to snarked out fast, but there's a lot of other work that we should cover before. Maybe you can share with us a little bit of what you've been up to since you were on the show last back in 2023.

>> Yeah. So, I think something that was personally exciting for me is back in 2023, I was kind of like very much a theoretician, but starting to look at questions that were becoming sort of like increasingly motivated by practice and uh seem to be potentially of influence to practice. And back in 2024, I thought, you know, this thing might be useful. Let's sort of put my money where my mouth is and try to see whether it is actually useful. And I ended up joining uh succinct working with them on building a ZKVM SP1 and trying to both like see whether my kind of ideas coming out of theory can help in the design of

ZKVMs. also for me personally to learn more about what happens in practice try to use that to get like more and interesting questions to to work on and had a blast been working with succinct and amazing people at the same since then >> now I'm I'm curious what the difference is like I mean when you talk about these problems coming up do you feel like it's is it a faster iteration do you find problems quicker are there different kind of problems that you're finding >> so both uh different and It makes the articulation of what is important much more clear because when you have like someone who is actually running something they very immediately tell you what is what the issues are with it

>> and that kind of like very directly says what are the most important problems for them and then for me as a researcher if I can now like articulate it as a clean problem and try to deal with it with the tools that that I know or or can try to reason about it that makes it much better rather than theations perspective which is sort of to invent a new problem >> which with a nice story around it which is great. I have zero objection to that. I mean zero knowledge the notion of zero knowledge came out of doing stuff like that for sure. >> Um but it makes life easier a little bit when someone comes along and you know says here are my issues with the your proof system. Uh can you make it better that it's like super concrete and you can like immediately start think of the

solution. when you were more on the theoretical side, did you find you sometimes went down paths that like really actually led to nowhere? Like that's sort of what I could picture could happen if you're not getting that constant feedback loop. >> So really depends on the notion of nowhere. So >> so a lot of lines of research that I did in theory I think led to what I think is like nice and beautiful theory but not necessarily to something that was deployed in practice. But I don't think that should be the definition of especially for theoretical work whether like immediately become something practical is not the right lens by which to view it cuz going back to this example of zero knowledge if that's the lens but with which you were to view it then you know it would be a grand

failure from the 80s until until now and I don't think that that's right. M so I would say that you know some of the theory work just led to like theory that I liked and papers that I think I find interesting maybe others do as well. Then there's other parts where you kind of like you invent a new problem you fail to solve it and then you're kind of like sad but then mainly you then like kind of pivot you kind of find a different twist on the problem >> um and try to solve that. that that is sort of a big flexibility that you have as a theoretician that you don't have as a practitioner where you cannot really like change the rules of the game.

>> Once you made that shift over to working at succinct, what was some of the first work you focused on? Were you already there when you worked on the Fiat Shamir stuff or had that been work from before that just came to a conclusion while you were working like by chance at succinct? >> Yeah. So, okay. So the fiat stuff I had done for many years actually touched on it even in the previous episode. So both finding ways to securely deploy fiair and attack it. So trying to pull that from both ends. So those were questions that I worked on basically since my PhD for a good like decade plus and that continued when working at succinct. I

think one work that you've done in 16 early on was the work on jagged polinomial commitments which is very motivated by the kind of structure that exists in ziki VMs and specifically how SP1 is structured. So that's probably something that you might have not worked on before. >> Yeah, absolutely. That was that was uh something new. I think the way that happened is kind of so when I joined succal stark uh univariate techniques and like my my theoretical research was much more

based on what's known as multiar polinomials. So there's two main classes of polinomials that people like to use are either unified polinomials or multiar polinomials. I would say that my work even before joining succinct was very much in the multilinear uh regime but succinct was kind of working with these like traditional univaried ones and they were telling me sort of the problems that they run into and every problem that they described they were saying oh if we were using multilinear instead I have five different solutions to it and this was kind of like repeating again and again like multiple times but it's hard to convince you know they they were very invested into uh univaria techniques >> a lot of the field was yeah >> a lot of the field right so like all ZKVMs back then were using univary techniques so that was kind of the

state-of-the-art two years ago everyone was all the ZKVMs were using univar techniques and there was only like initial there there was kind of a feeling that maybe multilinear is the next thing but it was only a feeling the tipping point I think where I managed to convince them is when we and this was in collaboration with like wonderful people at succinct we came up with this jagged polomial commitment scheme which is a way to kind of like redesign or like change the layout in a sense of how the computation trace is encoded in in a ZKVM. So in a traditional like ZKVM design, you sort of have like it's really think useful to think of it as an analogy to like an actual chip or

processor. So you have like different parts of the chip devoted to addition, a different part of the chip devoted to multiplication and so on to the different instructions and kind of the traditional design in some sense encoded each one of them separately. And what we did with the jagged polomial commitment scheme for which like the multi-linear techniques were an enabler is in some sense to lump up all the chips together if you like sort of like package them into like one thing jointly >> which just makes things uh much more efficient. Huh? >> The univariat work was that like the Starks chain of thought? Where does Binias and stuff like that fall? Were they also univariat?

>> So binius their kind of like novelty was sort of switching to binary fields historically their their novelty was which were used in a lot of of theory work by Ellie Benson and and myself and so on. in practice. I think Ellie had like also done some work in practical binary fields, but kind of people had kind of ditched that and they were pioneers in that sense of like pushing binary fields. I think initially in their first version they were still working with binary fields and univariat. >> Okay. >> And it took them a little bit of time to switch over to binary fields multi-denure.

>> Was it around the same time that you worked on the jagged polomial commitments do you think? I think that's the right ballpark, but uh I think it was done sort of independently. >> I want to go a little back to the Fiat Shamir work because we I don't know that we've ever I don't know if we've covered it on the show properly and I feel like it was quite it created quite a a shakeup. I feel I feel like we've probably mentioned its existence, but I don't think we've done a deep dive. Hopefully, we can do at least a short one here because I feel like it had such an impact on our ecosystem when it came out. So what was that work fat shamir?

You did mention this you sort of said this you you had mentioned this in the previous episode that you you sort of had a hunch that there was a way to do something an attack but you didn't actually do it at that point. So yeah tell us a little bit about how that came together. >> Yeah so maybe it's worth like quickly recapping what feature mirror is and then like describing the the attack. So, so frame mirror is this way kind of amazing way to compile an interactive protocol and make it non-interactive which is extremely important especially in like blockchain usages where you want to kind of like just post the proof and forget about it. You don't want to be online in order to prove stuff to people. But on the other hand, when we design protocols, it's really really really powerful and useful to design

them as interactive protocols. So the idea is the following. So you have an interactive protocol and it's an interactive protocol that has the feature where the prover sends a message and the verifiers responses are just like tossing some random coins and reporting their values. So no like smart messages from the verifier and what the firere transform is saying is that instead of actually letting the verifier toss random coins the verifier will just be replaced by computing by evaluating a hash function. So the prover sends a message rather than waiting for a response from the verifier. Uh we just like run the prover's message through a hash function get the verifier's message through that. So we don't actually need to wait and can continue and generate like all the proof messages in one shot.

So that's the transform and question that has been kind of quite open for decades now is whether this thing is secure. There has been sort of both positive and negative evidence but it's very much still open in general. >> Okay. But I think was was the work you did specifically on when you add recursion and what the impact is on fat shamir once you do that. >> So not quite. So let me talk a little bit about the negative evidence because I think maybe maybe prior to our work people weren't super aware of this but for quite a while uh before even before our our work with this I'm referring to work from last year with Levvenov and Demitri Kotovich um so even before that

we knew of examples of secure interactive protocols that have the the feature or bug that if you apply famed the result is totally broken. Okay. >> Oh, >> okay. So, we had examples of such protocols, but they came from from theoreticians and I think were very highly contrived. So, these were examples of protocols that people sort of intentionally came up with >> just for the purpose of showing that the mirror doesn't always work. >> Okay. >> And when I told people about this, their typical response was, "Eh, you know, our actual protocols don't do the stupid stuff that would make them break." And that was kind of like people's feeling I think previously. I think I was already like so this was like last episode that

that I was on was 2023. I was very much in a mindset that this is a concern and in particular I had a work from a few years before that showing an example of a sort of half contra protocol where it's a natural protocol but one of the components in it is contrived. Oh >> okay. >> And that led me sort of be very wary of the fact whether it is actually secure or not. Anyway, that was sort of the my state of mind prior to this work with with Levven and and Dimmitri. What happened, I think this was like maybe end of 2024 is that actually the Ethereum Foundation was interested in like studying the security of Poseidon.

>> Mhm. >> Maybe we'll touch about Poseidon later on. uh again but they had this uh bug bounty that they wanted to kind of show attacks against Poseidon and there was you know like you got some bounty for finding the collisions in Poseidon some other bounty for some other thing and then the very last field was like find an attack against fat shamir using Poseidon for any protocol of your choice and I was like you know I have contract protocols that I can break I can make a lot of money but being a nice guy I didn't I didn't I didn't try to make the money instead I just told them, hey, you know, you might want to like change your bug bounty to from protocol of your choice to non-contrived protocol of of your choice,

>> something in production. >> Yeah. Or or or or even something like less contrived in some sense. I was actually happy to see their response, which was, you know, they weren't really aware, I think, so much of the contrived examples and they really wanted to understand these things better. And that sort of started my collaboration with Lev and Dmitri where we started to look at actual protocols that are deployed and sort of realized that this major one that's based on on GKR is actually insecure. >> It was insecure when used with Vietir. >> Yes, exactly. So it's an interactive protocol very natural one that was actually there were a bunch of research papers on optimizing it. There's polyhedra who had a system called

expander that uses it. What was the name of the system? >> GKR. >> Oh, just GKR. Okay. Yeah. Yeah. >> GKR and R happens to be another offblown guy who's my brother. >> Yeah. So, it's based It's not quite the textbook GKR, but it is sort of the way that GKR is viewed nowadays in in practice. >> Yeah. And GKR is used like everywhere. So, it's definitely, you know, if you demonstrate an attack there, it's very very important. I feel like when this came out though for me like sometimes these cryp analysis papers come out and I just don't actually understand how dangerous this is like how threatening is this to existing systems and I think this fell in a similar one where like there it it through it sort of threw ripples through our ecosystem but like

did it force change or was this was this also in a way like theoretically something could happen but because these systems and the way they're built they're still safe. So I mean I I wrong you can say more but like it was serious enough that people had to make changes in their implementation. >> Yes. >> But what what changes could they make because aren't you saying like Fatamir doesn't work with GKR >> right? So I should say like Polyhedra had their system that uses it. They they made a change. They were even nice enough to give us a bounty. So certainly they took it seriously >> in terms of the change. One thing that the attack relies on. So GKR is a protocol. It's sort of like it's for proving correctness of a circuit of a certain bounded depth.

>> Okay. >> And in our attack, it is crucial that the depth of the circuit for which you're proving stuff >> should be at least as much as the hash function >> with which you're using fat mirror. >> Okay. >> And the way it was like implemented there was no restriction on that. But one way that sort of like a mitigation if you like for which like if you introduce it then we know don't know how to attack is if you ensure that the depth that the hash function is kind of deeper. than the depth of the circuit that you have. So that's what they did. They just like force the hash function to be kind of deeper than the circuit that they're proving.

>> Can you choose the depth or do do like hash functions automatically have a depth like you were talking about Poseidon and stuff like could you change a parameter in Poseidon? So you could still use Poseidon and it would be secure. >> So the easy uristic for increasing the depth is just to chain a bunch of the hashes. So like do a Poseidon of a Poseidon of a Poseidon and you would expect that the depth if you do like 10 Poseidons in sequence you would expect the depth. So of course like the natural way to do it makes the circuit 10x deeper. >> Mhm.

>> And the hope is that there is no like way to like clever way to avoid that. So but I should say that this is very much just like a mitigation so that we don't we we can't show an attack but we also don't know that an attack does not exist. >> Okay. what what actually broke like what between GKR and Fiat Shmeir was breaking what was what did it do wrong >> it's the interaction between them it's kind of the attack leverages really a featur an clear feature of GKR so the reason why people want to use GKR is that enables you to commit to less data >> okay >> so it's kind of like you you you commit to less data but you you implicitly commit to it but you don't have to actually commit to it and that is the feature of GKR that's the reason you

want to use GKR >> and that feature is also what enabled our attack. >> Wow. What did your brother say about your attack? >> He he was super happy. >> Okay. >> I mean, so and it's really using an GKR in a way that you kind of really shouldn't. >> Okay. >> But I don't think it was obvious in in hindsight. It's it was sort of not obvious back then that you shouldn't. >> Interesting. So I want to give an example of protocol that is extremely contrived. It is secure kind of in an interactive sense but if you apply fatir it's broken. I think that gives sort of a flavor of what's going on and I think like simple enough that I might be able

to describe it in like a few minutes here. So again super weird and contrived protocol but it's going to be a secure one until we break it. So here's the protocol. There's a prover and there's a verifier. And in the protocol, forget, it's not even important what we're trying to prove. But in the protocol, the prover is going to be sending a message. >> Mhm. >> This message, let's call this message M for message. And we interpret this message as the code of a program. Okay? So code in your favorite language, let's say Rust or whatever. The verifier receives this message M. It's and it's code, right? So it it runs it.

>> Mhm. And not only does it run it sort of when the program starts running it expects an input and we're going to feed as an input to this program M itself. Okay. So we are running M okay >> on input M. >> Weird but why not? You know it's it's a legitimate thing you might want to do if you're coming up with a contrive protocol. So we run M on M. We wait for it to sort of terminate and at the end it prints out a string. The string should be 100 bits long. We take the string and additionally we sort of toss a 100 random coins and we see whether our 100 random coins exactly match the output of the M ofm.

>> If so, we accept. If not, we reject. That's the entire protocol. And we want to say that it's sort of in this protocol, it is extremely unlikely that you will ever accept. And the reason is that sort of m of m is a weird thing but it's determined once you once m once the prover sends m of m is fully determined >> and now there's just like a fixed string of 100 bits you compare to like a 100 random coin tosses the probability that they're the same is 2 to the minus 100 extremely unlikely. So this is a secure protocol in the sense that you would never accept.

>> Mhm. >> But let's think what happens when you do fat shamir right. So the idea in famil is that instead of tossing coins, you replace the coins by a hash function. So how will we derive our 100 random points? Let's call them R r. It's 100 bits long. How do we derive R? We apply a hash to what do we apply hash to the previous thing the prover which is M. So R is now just equal to H of M. Now to make the verifier accept, all the prover needs to do is find a message m so that m of m which is you know what the verifier does is equal to r but r is h of m. So we need to find m so that m of m is equal to h of m. Can you think of an m that satisfies this?

>> It's going to be like zero or one or something like that. >> I think I think Kobe might have an idea. >> I've I've seen the I've seen the presentation in this form already. So I won't spoil the answer. >> No, no, you have to. Okay. So I'll spoil the answer. >> Could be H itself. >> Oh, >> so think of like if if M is H itself, then M of M is just H of H and H of M is also H of H. So they're the same. >> And the verifier will always accept. >> Ah, >> this type of technique is called it's very much related to technique known as diagonalization, which is sort of like you're forcing a program into itself in some sense. So that's what happens here.

As you can see, it's a super weird contrived protocol that you wouldn't expect to happen, which I think really contributed to why people thought that, you know, it's not a concern. >> Crazy. What would it actually allow what would the attack allow a user to do though in this case? Like does it halt the system? Does it does it have full access? It can do whatever it wants under the hood. Yeah. It lets you do like the worst possible thing you can think of as someone who's who's into proof systems, which is to prove that a false statement is true. >> It's true. Therefore, >> you make a false statement. I claim that, you know, it's it's night outside even though it's day.

>> Um, and I can provide you with a proof that my false statement is true. Wow. >> And you're going to accept it with probability one. >> Yeah. If you were to use it in the context of a blockchain, I can prove to you that, you know, I'm a multi- trillionaire and you would believe me. >> Maybe one thing that it's important to note, you know, maybe obvious to most listeners, but this is very distinct from what we see around fia breaking all the time, which is usually just the wrong way to to use f in practice. For example, when people forget to put some inputs in fetch because you need to include all the different messages the prover like this is an attack on fiachamir itself. Oh

>> wow. >> Right. So this is you're sort of using fiaamir as as advertised as you're supposed to um or as we thought you were supposed to and nevertheless it's insecure. >> Yeah. And it it does like cast a doubt about you know the fact that we're still using future mirror throughout. >> Um we should be somewhat worried about that. I think just very recently there's new work by Jako on further extending our attack to more settings. So in general this is a topic of of concern. >> What could be used instead of fiat shamir?

>> So one option is to use fiat shamir but use it securely. So there's been a large body of work that I also worked on which is to to do famil but use it in particular way and use it using particular hashes for which we can prove that it is secure. >> Okay. So rather than you know a uristic usage which is very common in practice there is huge body of work in in theory saying you know we're unhappy with the uristics we want to prove uh that fia shamir works under concrete assumptions say learning with errors or or or stuff like that >> we've made like tremendous progress on this it is still quite far from uh being practical I think but that should be

that should be noted beyond that we don't We don't have a lot unfortunately. So one option is to switch to interactive protocols. >> That would suck big time. >> Yeah. >> Um so really this field really relies heavily on fameir and I think um I hope to see much more research dedicated to >> either breaking it or trying to gain more confidence in it security. Actually just maybe for our listeners can you list some of the work and the names of the papers that you just talked about like so the initial fiat shamir and anything that's come since >> so the the firm attack which was about a year and a half ago was with leaves sukanov and dmitri kvtovich previously I think like this entire like

diagonalization idea came from really super influential work by ran kaneti oatri and shahvy I think originally from 1994. >> Oh cool. Um it was considered quite controversial. It's called the random oracle revisited. >> Um so there's this uristic called the random oracle which is saying that you know our hash functions are so good we should just treat them as though they're purely random even though they're not. >> And that uristic has been very useful on the one hand on the other hand what this CGH paper back then it's been 30 years now showed is that there are examples of protocols which are secure in the random oracle model but become insecure once you instantiate it.

>> Okay. And this entire line of like feature attacks are all instances of that. >> Cool. All right, we should shift gear because there's so much work we wanted to cover. I just found out before this that you were one of the co-authors of Blaze, which we had mentioned in we did sort of a survey of all the, you know, major ZK work that's come out and yeah, that one was in there. Tensor switch, Bolt that you actually worked on with Kobe. We you also presented Veil. So maybe we can do a quick run through of those and maybe share which like what's the grouping there what's the line of work and what's kind of different.

>> Yeah I think blaze tensor switch and bolt are quite related to each other. So maybe let's start by discussing those and then we can talk about the other ones. So all three of them are you can think of them as what's known as a polinomial commitment scheme or hashbased polinomial commitment scheme which are ways to commit we've I'm sure this has been covered multiple times on the show but this is a way to take a really large polinomial or or data encoded using a polinomial commit to it using a tiny commitment so that later you can prove evaluations of this polinomial >> and these kind of like polom commitment schemes or PCS's form a really important component in essentially like all snark constructions. So getting them to be

more efficient is extremely extremely important. >> Yeah. I I think like even even more than like being very important it kind of became the standard of how you construct stuff like before they came around sometimes snark kind of intermingle components together but at some point there was this abstraction of polinomial commitments that just became kind of the standard. So yeah >> I'm blanking just one one question were and stir and all of those are those also polinomial commitment schemes >> absolutely and fry >> do they come after and fry was before >> I think maybe blaze was maybe concurrent to were if I'm not mistaken >> uh I think stir may have been someone before that >> okay cool yeah just to help us sort of

frame that are they using very different techniques I I'd love to hear the comparison there >> I think the main uh source of comparison and that maybe touches is on like stuff we discussed also in the previous episode is sort of all the hashbased polinomal commitment schemes rely on error correcting codes >> and the thing that is sort of common to fry and stir and were is a reliance on the read solomment code. >> Yeah. So all of them are polomial commitment schemes built around the read solomment code and the read solomment code is fantastic big fan but there are other other codes that in some senses are better >> and these three works that I've worked on blaze and tensor switch and bolt all come from this like trying to use better

error correcting codes to get better PCS's. >> Kobe I feel like you should step in here since you you are one of the co-authors of Bolt as well. No. Yeah. I think like it's it's super interesting. I mean, we also big fan of Brit own codes and we can even talk a bit about what's being done to make them even better today. But yeah, it's super interesting to see what are the trade-offs you can take. I think um you know some codes are better in some respect. So we can talk about like maybe proofing time getting much better. Maybe you pay in proof size and that's something that is sometimes sufficient or even favorable in some other settings. There are settings like the

blockchain space where maybe you want to minimize proof size because everyone has to read it. But there are some settings that maybe you just want to send the proof to a number of parties of chain. So in those situations proving time might be much more important. Then there are codes like for example uh the one we used in bolt that are much more suitable for something like that. >> What was the code? >> So it's kind of a code that we came up with even though it's like heavily influenced by by prior work from coding theory. We called it a sketched code.

>> In a few words the idea so it actually relies on read Solomon but as a component. M >> the idea is that in some sense you you take your your message eventually you want to encode the message but what you'll do is first you take your message you kind of like hash it down but not in a cryptographic sense but think of it just creating like a shorter digest of the code in some way and encoding just that digest >> your overall code word will now be the encoding of the digest but also the original message itself at a very like high level why does this work as a good code you can I think so what what is a good code even? So good code should have the property that if you take any two distinct messages even if they're just

like a little bit different they differ only maybe on one bit you want their encodings to be extremely different. >> Yeah >> that is sort of a key property that you want for error correction. So why does the sketch code work well? Well let's think of like two messages. If from the from the start they are very different from one another since we are uh releasing them as part of the overall code word then we're fine. we don't need to worry about anything. They're different. Everything is good. >> Mhm. >> So the other extreme case is when they're very very similar. What you can show is that for two messages that are extremely similar, you need you want to set up so that the sketch or digest that we talked about before should also be distinct.

>> Doesn't have to be like super distinct but just like not be the same. >> Do you have to amplify the distinction or it doesn't it's okay if it remains close? >> It's amplified in the sense that the digest is smaller. So you took like two messages that are different from one another. >> Mhm. For each one you separately sort of compute its digest which is smaller. It should be like much smaller maybe like a tenth of the size or so. And you just want to say that you know the difference is preserved. So if it was if they were different before they are still different even though some information was lost right because it's smaller. >> Okay.

>> But you want to have the property that if originally they were just a little bit different then that distance is uh that difference is still maintained when you compute their sketch. >> Mhm. M >> and if that difference is indeed indeed holds once you apply your good error correcting code read Solomon or whatever that uh distance will be amplified. >> Ah okay >> and the the nice thing here is that you're using read Solomon code on something that is much smaller. So let's say a tenth the size of the original message. So you're paying like the read Solomon cost is 10x smaller.

>> Okay, you can just execute it much faster. Ritz want a bigger message is naturally smaller and that's what you see in Fry and we and other constructions. >> Yeah. So maybe like also a good way to like think of comparison between the the were line of work versus ours is where you want to put the emphasis on prover efficiency or verifier efficiency. >> Okay. >> So the line of work that uses sort of these like fancier error correcting codes is really about prover efficiency. We want codes that have a faster encoding time than read Solomon like the sketch codes that we did with with Kobe.

By the way, this is joint work with the amazing Andraovich uh as well. >> Big shout out. So that line of work is emphasizing then coding time and prover speed whereas the world line of work is saying you know what we're going to be encoding using read Solomon code but we want to make verification and proof size as as good as possible. M >> the the nice thing is that the these two lines of work can really like live together in harmony. >> Oh yeah. >> Via this idea of proof composition. >> Because when you're doing a proof composition, you might start off with a proof that is, you know, has like a bolt type of proof that has a really good prover, but only like an okay verifier, but then rather than actually using that verifier, you you recurse or you prove that verifier using something like Were

>> cool. Uh so you you inherit the super fast proving from bolt but the good verification from were >> so when when blaze were or bolt stir like when what's the Frankensteining combination of these? >> Yeah I think I would really love to see that deployed in practice. We do in the both benchmarks we saw very good performance. I think it's very promising and I think it's sort of like super exciting to try to see that actually deployed. Yeah, I I think it's like it's a very practical thing. I I'm very happy with the results that we got there in the sense that you know I said maybe proofs can be larger but they're not that much larger.

>> It's also raising new questions about proximity gaps that I find really exciting. So I also hope people will look at on that as well. So proximity gaps for codes beyond resolvment code. >> So like another work that I just mentioned before but you're saying is quite distinct from the blaze tensor switch bolt is veil. You presented Veil at the most recent DK summit. Tell us a little bit about that. >> Yeah, so Veil is this also like really exciting project I I worked on with friends from from Succinct. It's sort of like a way to turn your favorite hashbased proof system of some particular form to be uh what's known as ZKZK.

>> Uh really hate that term even though it's amusing, but so I'll try to stick with just zero knowledge >> aka private, right? Like adding >> Exactly. Exactly. add adding privacy back. So, usually uh when you don't have it, you only have succinctness, so you have short proofs. >> But in a lot of settings, we actually want to have very strong privacy guarantees. And zero knowledge is kind of like the the the strongest one. >> Traditionally in say SP1, the way we would get zero knowledge is by taking our succinct proof and then recursing or composing it with something like Gross 16 to get zero knowledge that way. That comes with some caveats. Maybe one of the most notable ones is that gross 16 is not postquantum.

>> So we wanted to have sort of like a native hashbased zero knowledge solution and that's that's kind of what veil does. So we have a proof of concept showing what sort of like that the overhead is kind of quite small both in terms of like prover time proof size and so we're looking at the sync to kind of like deploy that and really into SP1 as well. >> Cool. We should talk about flock. This is something we did cover on our episode with Benedict. We went into some detail about how flock came about. I feel this summer, I think it came out in June, but this summer there was a lot of conversation about it. Also, I think you listed, you know, the AI the AIs you were using as co-authors almost or like

helpers, which I think is quite novel for a research paper. Most people are not saying even though it's clear that it's being used, they're not necessarily overtly including them. Um, we did go into detail on that, so I will add a link in the show notes to Flock, but that episode came out in June, I think, or July. It was quite a like it was a few months ago. So, I'd love to hear what's happened since, and if there's new work or, you know, what what have you discovered about it since it's been released? >> So, I don't think we actually uh listed the AI as a co-author. Maybe we should have. Okay.

>> Um, but but >> maybe it wasn't allowed to do it. So, >> yeah, I don't know. But we certainly so I hadn't done coding for like coding in the sense of like programming in a very long time. I think Benedict may have done a tiny bit, but we went like this like extremely assisted by AI implementation >> for for flat who certainly lot lots of credit to to AI with flock. Flock was discussed in in the episode with Benedict I think just very recently but it's kind of like a proof system for batch proving of boolean computations. I think this was actually maybe also like a feature was kind of foreshadowed a bit in the previous episode that I was on where I talked about my interest in proving boolean circuits

>> which is really coming out of a theory perspective. >> But then with with Benedict we started looking and and with his amazing student William Wang we started looking and trying to see you know looks like trying to look at the theory work and making it practical is is useful. Let's try to look at that as well. And that sort of led led to the plot project which I think has sort of like gotten yeah has been maybe like well wellreceived and drawn a lot of attention. And even like much more importantly than that I think it has really generated a lot of like new ideas and followup work that I'm super excited about and and I I feel like kind of re-energized the field a little bit.

and maybe we can discuss the follow is that Ethereum Foundation decided to switch from Poseidon to one of the boolean hashes. Yeah, >> I think prior to Flock, it was kind of unclear that we could have like sufficient like we could do this efficiently enough >> and I think uh Flock and also a lot of influence previous influence from from Beineas showed that this is indeed possible and this is sort of a gigantic shift which I'm happy that Flock contributed to.

>> Oh, interesting. I didn't realize that. I mean I I thought that the switch had to do more with like the worry about Poseidon, but that I guess what you're saying here is that there's like there's an alternative proposed already or it was shown that you could use these like existing hashes in a fast enough way so therefore switching away from Poseidon was even an option. Is that true? >> Yeah. Yeah. So it I think it sort of happened more or less in the same time that because of some new attacks, people's confidence in Poseidon started to be a little bit shaken. That was on on the one hand and the other hand we saw that like something that I think was very unexpected a year ago maybe is that we could use traditional hash functions and proofs and make it performant

enough. >> Yeah. Yeah. >> So the combination of you know we are kind of like worried about Poseidon plus seems like the other alternatives are are good enough is really what enabled this change. >> Crazy. At the same time you have this is something we've wanted to talk to you that it kind of what prompted this snark.fast like this sounds like a cha you're and I really do need this to be explained to me but what it sort of looks like from the outside is like it's a challenge. You're sort of saying hey can you improve this system even more? What are you trying to do with it? And like why do you need to do that if you've already created flock and this is usable? Like what what parts of flock are you trying to optimize? And maybe I maybe I don't even understand what

snark.fast is. So maybe you should explain what that is first. >> Yeah. So snark.fast is collaboration between us at succinct together with iigelabs who's really leading it. Ethereum foundation and and espresso. >> Espresso is where Benex is at. And the idea sort of I think they were also kind of excited to see flock and the like very positive reaction that it had >> and they were interested to see you know can we further improve flock because >> but like on what level like just making it faster or making it safer >> faster just faster. >> Yeah. So I've like been very very very focused on this question of getting extremely efficient proving. I think I find it like super exciting. It's been on my agenda from like theoretical works and like 2020 and and even before. So

I'm extremely interested in the the the cost of proving. I think even back in 2020 had this paper called proving as fast as computing and that has been sort of my agenda ever since. >> Yeah. >> To get to that and with flock we made a lot of headway. We got like very efficient proofs but I don't see myself ever being satisfied with how efficient proving is and the point is really so it's there's one question of you know how efficient can you make it as a basic scientific question that I'm really interested in. Moreover though, I think that even if you make it, you know, fast enough for Ethereum, fantastic. Super happy for Ethereum. But if you can make it even faster, maybe it enables new applications that we can't even dream about because, you know, we think, you know, that it's inherent that there is

whatever overhead to proving which maybe we don't actually need and maybe with some new breakthroughs we can get rid of >> and enable things that we could not even imagine before. So I would not say that >> flu is definitely not the end of the road. It's very much the beginning and the question is you know what more can we squeeze out and snar that fast is an sort of like AI focused way of of trying to improve that zk is as well let me say maybe a few words about the snar that fast idea so what they were saying is you know so flock is a proof system right there's a prover algorithm and there's a verifier algorithm >> and it's it's you know pretty performant or quite performant >> but let's say you know let's keep the

verifier fixed because the verifier is what guarantees your sort of like your completeness and your soundness which are the the key properties. Can we you know replace the prover from flock with a new prover that's even faster. >> Mhm. >> That still convinces the verifier you know of true statements and because flock is sound you know it's not going to be proving false statements. >> Okay. >> Hopefully. Right. So the point is you know just think of the the flock prover as an algorithm. Can you make that algorithm faster? Yeah, that's that was sort of the question that that this brings up though is like why wouldn't secure like could you get something very fast but somewhere under the hood it's broken or is just the structure of flock such that you wouldn't be able to actually like convince the verifier if

it's wrong or if it's insecure. >> So it really depends on what broken means. And I want to separate here between completeness and and soundness. So soundness of of flock or in general what it says as if if you're holding a false statement no one should be able to convince you to accept it. >> Okay? >> Right? In particular not a snark.fast prover not a snarkfaster not snark.f fastest no one should be able not to convince you of something that is false. So that is doesn't matter you know what like faster prover you come up with it will fail.

>> False statements should not be provable. Okay. It will fail. >> So in that sense there is no like question of security. >> Yeah. >> Um with snarf.f fast or anything. As long as the verifier is fixed, >> there's no question of of soundness. There is no question of of completeness. So completeness means for example that uh true statements should be provable. >> And there it's a little bit more more difficult to guarantee this >> with not that fast. What we guarantee is that that sort of like for random inputs you can still accept. Something more ambitious you could try to do is have prove that the changes you made don't change the input output behavior of the prover and that is I think in ZK Golf Kobe and others were targeting that so

they they have like stronger completeness guarantees. Another thing that I'm a little bit worried about is that these like crazy fully AIE projects without so much supervision is you know there's a potential for our AI overlords to insert malicious code >> into the prover. So that's like another concern >> that you should have. Having said that, the results there were really breathtaking. I think I I thought it was like pretty clear that they would get like using like this like crowdsourced massive AI for sure there's better engineering than what we did with our you know our agent and like small amount of tokens and I was expecting you know 10 or 20% stuff like that. They actually got to I think two and a half or 3x.

>> Oh wow. So this is like pure engineering. There's no change to the protocol. >> So pure engineering 2 and a half to 3x. I think initially like one of something really interesting that happened there is that pretty early on the AIS noticed that so we were running the benchmarks on Macs and pretty early on they noticed that the Macs have a GPU that we weren't utilizing. Not because we not because we didn't know they're there but more of like when we tried to experiment with them a little bit they didn't work well. >> Yeah. Turns out the AI knew how to utilize them much more and that was that contributed quite quite a lot and >> amazing.

>> I think like when people realize that they saying ah you know snark that fast was really like just about that. >> Mhm. >> Something that's kind of like again super interesting is that more recently there's been an x86 like an Intel based snark. fast using an Intel uh server does not have a GPU and now they're over 3x better than our flock implementation. >> Oh, so cool. So they're finding all sorts of ways to sort of extract more speed. So that one the one the example you just gave with your Mac is like there's yeah some untapped hardware that they could just access and you hadn't been able to sort of loop that into the to the flow.

>> Uh I mean we tried a little bit. we got like overheating stuff. So, and like the GPU very quickly like overheated and stuff, but so a lot of I think the contributions on the Mac were finding like right scheduling between the CPU and GPU and stuff like that. >> Interesting. >> And that led us to think that you know the big part was the GPU, but then all of a sudden the Intel version without without a GPU managed to get that as well. So really >> where did they optimize? What was the optimization on that front then? Was it just like I don't actually understand what they're optim like what's how do you speed this up like how where do you achieve the speed like the hardware example makes total sense that's very obvious but like how would you do it otherwise >> so very smart engineering so for example

things that are very costly or they're sort of like going through scanning through your memory so if you can find you know if your algorithm your your protocol requires you to like scan through the memory once do something then scan again do something else if you can find a way to just like go through it once and do both at the same time. That's going to save you a lot of work. >> Okay. >> Of course, we were aware of this. We tried to do it. The AI just does it much much better. >> Yeah. I think like the just allow you to experiment much more. So, I think when we when we were talking with Benedict, we discussed this a bit around this know what are the anchors that you can have that would allow you to experiment while making sure things are still fine. So

verify is an amazing anchor because you can basically experiment with almost everything and making sure that the system is still secure and I think modern computers just have a lot of components inside them that you can use that it's just very hard to experiment with especially when you have other things going on and there are caches there are GPUs there are different ways to like set schedule tasks between Um, and AIS can just experiment with all of these different ideas that you have just much more broadly. And >> the the the infinite patience is very very powerful.

>> Yeah. >> Who's behind these agents? Like are they different labs? Are they different companies? Are they individuals that are like and like what is what are those individuals actually doing? Like could I just do it? Because it seems like I it should you should need some expertise though right? >> No. So the expertise is going to snark.fast. There's a link there. Copy paste this to your agent and let the agent run. And >> I mean that yeah that's one way. >> But I I think isn't that like what most people are doing? >> I I think so. But I know that there are definitely some people that are trying to bring uh some of their knowledge or some of their like list of resources and expertise.

>> But you know just add head it to the prompt. I feel like the expertise would potentially help get the agent there faster. Exactly. >> Which is not what you're testing. You're trying to get snark fast. It's not about how fast the agent figures it out. It's how fast they can make >> the flock uh protocol work. >> Yeah. But but in terms of like a utility of your of your tokens, you kind of want to uh >> potentially pointing in the right direction could help, but also the AI can come up with its own direction. Yeah, by the way, one one cool thing about Snarkfest that I've seen that was happening where people were optimizing is that, you know, sniper.fest is for specific hardware and I don't remember exactly what they targeting, probably like an M3 processor and some people don't have access to that specific

processor. So, there was one of the AIS that built a simulator of the processor so that they can participate and see that they have a submission that would be accepted, you Wow. >> I was actually worried that maybe one of the AI somehow got control of the snark.fast website and is just like reporting false numbers. Uh cuz you know that's what it's optimized to do. >> That's what Yeah. I mean how that was my question is a little bit like how do you actually judge how is this competition being judged? What how how is a leaderboard put together?

>> Right. So, so actually that's like a nice feature of in terms of like trying to do like AI assisted like engineering and speedups is that for approve systems is a good use case because what happens is basically someone comes along and says you know what I have a better prover >> now you can test it you can just say you know I'll run it on random inputs and see whether it makes the original flux verifier from June accept >> on you know many many random inputs if so we accept it as a valid prover and you know we measured how much how how much time it takes over many experiments. We see that it's faster.

>> You get to be the new leader. >> Who's measuring it though? Is it you guys? Is there like submissions and there's like a person doing this or is it also all automated? And >> I'm sure it's automated, but I lab is kind of running that part. >> Ah, okay. And this is on their platform, Yukon, I think. >> Yeah. >> Okay. I feel like I kind of want to explore what Yukon actually is because I don't really get what that environment is that it's possible to do this. Is ZK Golf also there, Kobe? So yeah, zik golf is about uh optimizing let's say circuits. Okay, >> so you have a description of a circuit, you have a specification, let's say of some function of a hash and you know what is the correct way to to write the

function when you write it as a as an algorithm. And now the question is how do you make sure that the circuit that you're writing is still safe? It's still sound, still complete. And there is this language a lean based DSL that Ziki security has worked on for some time called clean that allows you to express the circuits in that way and express what it means for them to be sound and complete. M >> so one thing that uh both Tamir and Ron messaged us when they saw Zik Golf is that they said hey okay you guys launched ZK Golf with circuits over prime fields and that's nice you can optimize some stuff there we already

like saw a lot of really great results from the eyes optimizing circuits there what about binary fields and what about the circuits that are flux shaped they have like a specific >> shape that needs to be satis displayed. Uh so yeah, we we also added a couple of circuits that have that that are binary fields to the fox shape and that already got nice results as well. So I I'm sure that uh you guys spent a lot of time already optimizing with AIS the circuits that you guys put in the flock paper and some people pointed their AIS maybe with some knowledge. I think I think actually this is the instance where I've seen

some people try to put their expertise inside as well and yeah there were like tons of percentages of improvements over the circuit the the circuit descriptions that were already in the flock paper which was nice. So that's like another way to improve the the flock proving performance not by the engineering of the prover itself not like the field operations but actually just changing the circus themselves on some specific problems. So are these like complimentary competitions then? >> Uh these ones? Yes.

>> Okay. >> And we're going to incorporate both of them into like the new version of luck. >> Oh cool. In that episode back in 2023, you did leave us quite a few Easter eggs for research and ideas, things that you were excited about. And I'm curious like, yeah, what do you have for us this time? What are you thinking about? What is what is on your mind? What do you think might like breakthroughs that we might see in the next few years? >> Yeah. So, so Easter eggs may sound like it's sort of intentional that I know all the stuff that's coming. I didn't, but I I sort of like maybe have like >> some good uh some some good hunches. Um, so I'm not sure I'm going to do as well, but I can tell you the things that I'm excited about uh now.

>> So, one thing is sort of like where do we go on with Flock from from here? And we're actually working on a Flock V2 and it's all kind of like open source and you can see listeners can follow the the development, but we're trying to kind of like get more functionality out of Flux. So, the original Flu was just about proving a bunch of hashes. We'd like to do be able to do much more. So proving a bunch of hashes is kind of a a lot of like what is the interesting stuff that we want to do in many applications. But there's also a lot of like other logic that we need to support and flock currently only supports very limited logic. We want to do much more support uh recursion in flock and we can kind of already do that in this upcoming v2. Uh

maybe things like signature aggregation that ethereum is really interested and in general sort of seems like any postquantum hashbased future should rely on. So that's something pretty immediate that we want to we want to do with flock a bit more long-term something I'm really excited about is doing kind of a flock based ZKVM and actually at succinct that's exactly what we're planning with the an upcoming version of SP1. So probably like >> V7 of SP1 will be kind of binary field and flock based which kind of all the lessons we learned both from the prime fields and from flock incorporated into ZKVM which I think can be extremely performant. So that's something I'm I'm really excited about.

>> Every time I hear binary fields, I think of Binas and this makes me kind of wonder what is the connection point here like are are you extending Binius? Is it different? Are you combining something that they've done as well? >> So we're very much following in their footsteps and in the usage of binary fields but I think adding to that sort of like our expertise in arithmetization new ideas and overall you know their ideas were fantastic. we're we're building on them and trying to to do even better. One thing that I think is exciting and an enabler is the fact that Nvidia recently added support in their GPUs for binary fields.

>> This is something that did not exist before. I think it was released in May of this year. And prior to that, that was kind of the showstopper and I think a key reason why binary fields were not adopted for ZKVMs. now that they have it. Plus, we've seen the amazing performance of binary fields that I think that's sort of like where we want to go. >> Wild. It's like the ZK GPU idea or the A6 that we had been talking about years ago. It kind of has been dropped a little bit as a narrative, but it's like now maybe we don't need one. This will be the equivalent.

>> Yeah. I mean probably an ASIC would be uh even faster than than a GPU but it takes like such an effort to to build it and you can >> based on the market demand maybe that will happen but just just based on like the performance we're seeing on binary field GPUs I think it'll be really really good. >> That's cool. Uh any other prophecies? So I'm not sure about prophecies but like the other sort of the flock SP1 is like a very concrete kind of like engineering and applied question a bit on the more like scientific thing and touched about it before I have this sort of like I've been very passionate about this question of proving as fast as computing >> and I think you can attack this question from different angles like a bit more theoretical a bit more practical with

flock it was very practical we were looking at you know what is the wall clock time for approving a bunch of hash hashes versus computing them. And we got it down to like ballpark of like 200x. So proving hashes is like 200x is only 200x slower than just computing them, which is uh may sound like a lot, but it's like way way faster than what we had thought uh previously that what we could uh target. And I think it's like super interesting. I should say that this number you have to like be careful about what exactly it means, but let's not not do that here. And it would be like very cool to to to improve that using you know that that number is even like before snark that fast and zk and new ideas that we have in flock v2. So

trying to push that idea further would be like super super exciting I think. >> So if there's a 200x overhead you are I guess your aim is to bring that down to like one one x or par. >> Yep. Yeah. Yeah. So get it down as as much as possible. >> Yeah. Um maybe there's an inherent uh limit of the universe that proving cannot be exactly as fast as computing. Showing that would also be cool. Uh but otherwise, you know, full steam ahead. Let's let's just make our proofs like extremely extremely fast. And I think this can enable just like new applications that are hard to even like imagine right now.

>> Yeah. What could that do though? Like so if you have like it would it almost just be like the minute you send any operation there's an there's a proof there's or there's like a zk element to it and like what does that even do? What would that open up? >> Yeah. So taking the things to really to an extreme if you can get it down to like one in the sense that as you are computing stuff for free you can also generate a proof of what you computed which is like very much a dream scenario but let's let's go with the dream. It means that all computation in the world is verifiable. anything that anyone your agent anyone else's agent anything that anyone does yeah >> you can compare it to like if you have a baseline >> verify very very cheaply that it was

done correctly and this could include like machine learning training and inference and you know any computation so I think like getting this overhead down will really just like open up like brand new use cases that are beyond our imagination >> crazy yeah I guess this I mean this does sort of make me realize how much of computation is not verifiable right now that like we're relying on these sort of external tools and like this would be a total game changer if you could actually map back everything especially because we also now have the tools >> external tools and just like general general trust you know we're getting software from big companies small companies we are running them >> seem to work okay but but kind of who

knows and if we could get like assurances especially as like more and more of the software generated as by by agents I think that's really interesting >> also because humans can't verify that so well. So this you almost like you're going to need something. >> Yeah. And then especially when things become even more formally verifiable like you mentioned in the like in a recent episode with Alex Odeir like the overhead of proving le theorems in snarks is very far from 1x but if we get there that will that will definitely be different worlds. Cool. Ron, thank you so much for coming on the show uh sharing with us sort of your update since our 2023 episode, your move to succinct, your work on polomial commitment schemes all the way to flock

and snark.fast. I'm so glad we got a chance to cover all of that. Yeah, thanks so much. >> Thank you so much for having me guys. >> Yeah, and uh thanks for for joining us for this episode. I I always really enjoy working with you and your work has been so influential on this space. It was great that we could talk about at least some of it. >> Cool. >> Oh, thank you so much. That means a lot. Thank you. >> All right. I want to say thank you to the podcast team, Rachel, Henrik, and Tanya, and to our listeners. Thanks for listening.