Episode 322 - Definitions, Security and Sumcheck in ZK Systems with Justin Thaler

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, Guillermo and I chat with Justin Thaler, associate professor at Georgetown and research partner at A16Z. Last year, he published a blog post called The 17 Misconceptions About SNARKs, which made waves in the ZK space. And in this episode, we revisit a few select points. We then dive into Jolt, a new ZKVM, which had been

initially described along with Lasso in 2023, and has recently been implemented and is open to contributions from the community. We talk about how his work on sum-check protocols influenced this work, how it compares to others in the space, and more. Now, before we kick off, I just want to share a little bit about ZK Hack Krakow, an upcoming IRL hackathon happening May 17th through 19th in Krakow. ZK Hack is an educational hub and another project that I'm a part of. We actually mentioned that on this episode with Justin because Justin's been running a long-standing study group over on the ZK Hack Discord. But ZK Hack also does IRL events, and as mentioned, the next one coming up is on May 17th through 19th, and it's happening in

Krakow. We already have an amazing group of hackers set to join us, some fantastic sponsors offering prizes, a great venue, and we're hoping that this event, like our previous hackathons, showcases the next generation of ZK applications. So, if you're in the field or looking to jump in, I hope you'll join us as well. I've added the link in the show notes. Now, Tanya will share a little bit about this week's sponsors. Aleo is a new layer-one blockchain that achieves the programmability of Ethereum, the privacy of Zcash, and the scalability of a roll-up. Driven by a mission for a truly secure internet, Aleo has interwoven zero-knowledge proofs into every facet of their stack, resulting in a vertically integrated

layer one blockchain that's unparalleled in its approach. Aleo is ZK by design. Dive into their programming language Leo and see what permissionless development looks like, offering boundless opportunities for developers and innovators to build ZK apps. This is an invitation to be part of a transformational ZK journey. Dive deeper and discover more about Aleo at aleo.org. Namada is the shielded asset hub rewarding you to protect the multichain. Built to give you full control over sharing your personal information, Namada brings data protection to existing assets, applications, and networks. Namada ends the era of transparency by default, enabling shielded transfers and shielded cross-chain actions to protect your data

even when interacting with transparent chains. Namada also introduces a novel shielding reward system. By holding your assets in a shielded set, you help strengthen Namada's data protection guarantees and collect NAM rewards in return. Namada will initially support IBC and Ethereum-based assets, but will ultimately serve as a single shielded hub for all assets across the multichain. Learn more and follow Namada mainnet launch at namada.net. Today, Guillermo and I are here with Justin Thaler. Welcome back to the show, Justin.

Thanks for having me. Happy to be here. Hey Guillermo. Hey yeah. Justin, last time you were on the show, I introduced you as an associate professor at Georgetown. Now I think you have another kind of role we can talk about, which is research partner at a16z or Z. Sorry, that was so Canadian. But yeah, it's really great to have you back on the show, and I want to talk about what's happened since you've been on. Sounds good. So, you joined a16z. Tell us a little bit about that. What What's it like working there and what are you doing there? Sounds good. Uh yeah, I think last time I was on was just a few weeks before I started full-time. Uh so, I got started there uh right when the research group started. Um they ran like a few months

after, you know, like day one. Um summer hit and the group was, I think, four people to start and they brought in um a whole bunch of visitors for the summer. Uh really spanning the the blockchain, you know, uh discipline. Bunch of cryptographers economists even political scientists. Um mix of PhD students and and professors. So, I was there actually just for about half the summer. And it was you know, super exciting. Just like drinking from a fire hose. Um I guess Tim Roughgarden, who runs the group, was was trying to model the summer after the Simons Institute for the Theory of Computing at UC Berkeley.

Uh that runs these like, you know, semester-long focuses on on a research topic. Um and and also there it's like just like there's so much activity. You just like can't keep up. Um you have to actually be careful you have time to like talk and think and do work rather than just like consume the content that is uh you know, occurring and being produced. Um so, that that that was just a great experience. Uh kind of sucked me deeper into sort of efforts to, you know, deploy these SNARKs. Deploy these ZK proofs. Yeah, I think it it sort of cut both ways. Um you know, excitement in this technology was uh you know, already high and and rising. So, I think there was a lot of interest both in the firm to have someone with my expertise there and I was super excited to be more

involved. Um so, I I started full-time in January. I'm on I'm on leave from Georgetown right now. I'm still able to sort of get my my fix for for teaching. Uh I'm still running my my reading group over Discord on the ZK hack channel and uh planning to start a a brand new fresh pass through through my book soon. Hopefully in the next couple weeks. So, I'll I've been off Discord for a few weeks, but I'll get back on and and sort of announce that soon. And yeah, it's it's been a wonderful it's been a little over a year now. Um going on a year and a half.

And you know, the there's there's so much just excitement about blockchains and and snarks in particular throughout throughout the firm. You know, my my colleagues in the research group are are wonderful and I've gotten to work very closely with this engineering team that's there as well, which has also just been like a dream come true for me and that's sort of what's led to the recent short implementation that we'll probably talk about today. So, I'll say more about that then, but it's just been a wonderful experience overall. Who who's on that team with you? Are there any names we know? Yeah, I mean some some of these folks actually I know some folks from your group presented at ZK10.

Yeah, yeah. So, so you you probably know very well Joe Bonneau who's a he's kind of a generalist cryptographer. He kind of co-authored the first book as as I understand it on kind of the science of blockchains and you know, the cryptography underlying blockchains in particular. Yeah, he's been on the show before too actually. I had him as a guest. Yeah. Yeah, and he's he's done really groundbreaking works like you know, introducing the notion of VDFs and you know, with colleagues and and things like that.

So, Valeria Nikolaenko is on the team and she does a lot of work with signatures and MPC and you know, he uses snarks as well in in some of her research. And so, we kind of form like the the cryptographers of the group. And the the others are are economists. So, there's Tim Roughgarden, there's there's Scott Kominers who's at Harvard Business School, uh Pranav Garimidi and and Miriam Baroni. You know, so Tim Tim and Scott are are faculty. Um and uh Miriam and Pranav are sort of full-time grad student level uh researchers uh essentially. And uh but you know, there's like no separation at at all in the in the group. Um you know, kind of everybody is uh works together

and and and the same. And uh yeah, we we also have uh you know, Dan Boneh is closely affiliated with the group. Um and uh Yeah, yeah. I know he's always He's been He's been involved with this for a while right? Yeah, yeah. So, he's he's not full-time or anything like that, but he's closely involved. Um you know, we we talk to him weekly and he visits over the summer. Um and there's also a political scientist uh closely affiliated with the group, Andy Hall. We started to get him for 1 day a week. Um and he he works a lot on like governance uh of of, you know, DAOs and and blockchain protocols and stuff.

Um and I expect the group to uh continue to grow and and add more areas and branch out as we go. You know, a post-doc Yoav Sagi New is uh is joining soon. And he while he's very broad, but he does topics like consensus research and and things like that. Uh so, just a a wonderful group and the, you know, works very closely with other parts of the firm that uh it's just been a fantastic experience. I sort of can't believe, you know, my luck at getting to be a part of it. It sounds like there's also an engineering team. And actually the the folks who've spoken at ZK 10 at ZK Summit 10, I don't think you've mentioned them yet. They're the folks who work on with like on Jolt and stuff.

Who are they? How big is that team? Yeah, so um so, there's an engineering team. Uh I think it's roughly the size of the research group. So, I think I listed, you know, depending on who you count, like six to eight people. And the engineering group is in that vicinity. I've never actually counted on my hands. Um got it. And yeah, that So, that you know, they they have dual roles just like the research group doesn't doesn't just do research. So that you know that they help the portfolio companies a lot to the you know to the extent possible. They also work on developing open source tools you know for the whole community to use all sorts of other things in the firm as well.

And so it's been a real real pleasure to you know have Joe kind of be one of the main sort of open source efforts and to be involved with that. Yeah, it's just been very exciting and and productive I think. Cool. You just mentioned your book proofs arguments and zero knowledge proofs. I want to just sort of mention this before we dive into any of the topics we wanted to cover today. I think you run three cohorts of a study group in the ZK hack discord. I know last time we had you on the show we talked a lot about that and like that book and and where it came from and where it was at. So I'll definitely link to that episode if people want to just learn about this book you've written or actually you called it a mono what was it called?

monograph monograph monograph but we we could just call it a book now I guess that it's been I like I think it's a book now. I think it's officially a book not a monograph. review three times. So some form of peer review so I know what what you mentioned in that episode was that you like like doing these study groups you actually get to see how your how the book is interpreted by people who are reading it for the first time often and through that you've been able to to make it like refine it and change it. You were just saying you're going to run another one. This is very cool. I just want to kind of highlight that cuz I think people are going to be into it.

How long is it again? Like the how many weeks? How many weeks? Yeah, I mean it varies based on like basically how many off weeks we need to take but um Oh, I see. One pass through the book can normally takes about like eight months it seems at this point. Wow. Oh, oh okay. Okay. This is like this is like not messing around type thing. So I I apologize. I've never done one of them. I did like a very very short session at some point which was like 3 days or something. a short you did a study group mini. Yeah. Guillermo. Uh Justin's additions. Justin's proofs arguments and zero knowledge proofs are the ZK hack study group like maxi.

Yeah, I should do that. I should just one of these I should just do it. It'd be kind of fun. it might be the longest one. We did do there was a group that did the Moon Math manual and they also spent like at least 6 months, but I think yours may still be the longest running one and definitely the longest Who's writing Moon Math? Well, it's it's a book that was produced by the Least Authority Group and Mirko was the author. Um but they like our in our group they've just read through it. So like, you know, there's a there's a facilitator and together the group kind of reads a chapter every week and then gets together. They're actually running the Moon Math manual again right now.

And the whiteboards study group. There's a lot of study groups going on in ZK hack if people aren't aware. Definitely go check that out and and I guess Justin, if you're going to start yours off soon, this is kind of the perfect time to let people know. So sometime in May I plan to start it up again and um one benefit of actually coming to the sessions or uh we try to record them and get them on YouTube although I don't actually track if they make their way to YouTube or not, but um you know, there there are a lot of questions about like what people are actually building, you know, specific systems and things um which isn't discussed as much in the book or you know, certainly the book can't keep up to date with like, you know, the the many changes to you know, what people

are building uh like every month or or so what so forth. So you sort of get that benefit and uh you know, I I do my best to keep up and give accurate answers. It's it's hard if you with how much things changes, but uh yeah, so that's that's a benefit of the sessions over just reading the book I think and also the book is now already, you know, out out of date in certain ways. Um so that's another another benefit. Interesting. Um since you've been on you also published this essay called 17 misconceptions about SNARKs. And I feel like that really made the rounds in our community.

It affected I mean it definitely impacted me a little bit. Like you I mean the first point is using ZK to mean succinct. I think it was the first time for me at least it was very clearly articulated that we've been saying it wrong when we say ZK SNARKs we're often actually describing SNARKs that are not ZK. And yet it's all been lumped under the ZK umbrella. We've talked about this a few times on the show and I think there's kind of now like an acceptance of we're still going to keep using the term. But I think you were the first person to really for me at least like make that distinction very clear.

Yeah, so you know, I think um I was not the first person from my perspective, right? I was I think people were talking about this before I you know, put it in the post. Um I guess one point I'm not sure I had heard much before that you know, which is maybe my main concern is that you know, ZK has a precise technical meaning about basically protecting privacy of the witness. And so my main concern is is that one day you know, someone calls something ZK it's not ZK. And so there's like a privacy leak. And and that's really my my main concern. I mean I do think um it it's helpful to be precise about like what property of a proof system you really care about and often it is succinctness

and not the the ZK property. Um I also just like the word succinct, but I know it's like not going to you know, that's not going to catch on uh quite the same way ZK has. So I think succinctness has I mean it's emerged a lot more. I think people do use the term more since since you've published this blog post and yeah, definitely in the last year. But yeah, I think it's that big umbrella term ZK still seems to hold. Yeah, and I so I I expected it will and um it's I don't think it's the end of the world as long as a more people are aware of the way it's being used, right? I mean, I've also like talked to people who, you know, know nothing about SNARKs and got very confused about this. So, that was another another concern.

Yeah. Um and you know, so if there's more awareness, um I guess that can help. And also like now I think people will say ZK and then be more prepared to clarify that they don't mean ZK. And that that can also help. So, I'm not like going to be super rigid here, but I think it was definitely useful to say something. I think I think the like crappy version of this that I have in my head is like ZK, the acronym is like a different type than like zero knowledge. Right? Like ZK the acronym is like Mhm.

it just means like vaguely everything. Uh unless it's combined with a secondary thing. But like when you say zero knowledge, you really do mean zero knowledge. That's it. You know, I actually haven't heard that before. So, that uh that distinction. So, uh maybe maybe I'll feel I'm going to you know, now every time somebody says it, I'm going to think like did they say zero knowledge or did they say ZK? And maybe it'll be be okay. Yeah, yeah. Well, now it's like a now it's like a people problem, right? As opposed to a It's like what what kind of person is this, you know? What Who would say that, right?

Looking at these 17, I will not go through all of them because well, first of all, some of them were too in the weeds for I don't fully understand all of them. But but I do want I I went through and I highlighted a few of these because When did you publish this this blog post actually? It's like a year ago, right? Yeah, something something like that. I remember it was a couple months before, you know, the Lasso JOLT papers came out and those are already 7 8 months ago. So, yeah, like a little under a year ago, 10 months or something like that. Yeah. I sort of mentioned the first point which was using ZK to mean succinct.

Another point you made was sort of the SNARKs versus STARKs, which I also think in the time I mean I think it was already happening when you wrote this, obviously, but I think in the time since I think that blending of those things and that sense that like neither you know, I think I've asked this on a recent podcast like which one wins and it's like both or neither like they're just they're a mix in a way now so it's it's hard to make that distinction. Yes, and I think I think they'll sort of get blended even more as uh with recent developments with like you know Binius now having you know a polylogarithmic uh proof size without recursion and and things like that. So, you know, if they blend enough then, you know, that that then the whole I guess concern goes away

that I I expressed in the in the post. Um but uh at the time and even today, you know people often treat them distinctly and you know, when they're they're not really because all of these are deployed non-interactively, which does make a a STARK technically a special case of of a SNARK and of course people use STARK to also mean a a particular protocol as opposed to, you know, any uh protocol satisfying a class of properties, which is, you know, really how the term was defined in in the research literature. Um I guess my my two biggest concerns, one was mentioned in the post, which is the acronym STARK in the research literature actually doesn't specify if the protocol is non-interactive or interactive. Okay. And um

whether it's non-interactive or interactive drastically affects the appropriate security level of the protocol. And so, I find this kind of very uh I I almost call it dangerous where if you if you talk about what's the right security of of STARKs, is this, you know, number of bits of security uh appropriate? Uh well, firstly, bits of security is a is a sort of underspecified term, but even ignoring that, the answer is completely different depending on whether it's deployed interactively or non-interactively. But today, they're they're exclusively deployed non-interactively. So, that that was one concern, you know, something I didn't say in the post that that I keep encountering since the post, people think STARKs also encompasses post-quantum security, but the term as

defined says nothing about post-quantum security. Um anyway, I mean, I I think that that you know, this distinction, which is not really a distinction in practice, has caused a lot of confusion. I'd like to stop the confusion um Okay, but which one do you choose, Justin? What do you call this thing now? So, I mean, my preference as I said in the post, as long as these are all deployed non-interactively, a STARK is a is a transparent SNARK with certain efficiency properties. So, let's just say SNARK, and if you want to emphasize that it's transparent, let's say it's a transparent SNARK um and let's kind of leave it at that.

That's that's my view. Obviously, there's going to be all sorts of disagreement about this. It's pretty controversial topic, but I I actually have a well, two questions for you as yeah, I I feel like a SNARK and STARK have become like tasting notes, you know? It's like like you use it to like gesture at something that vaguely feels like appropriate, but it's not quite like a real distinction in any like, you know, deep way. a wine reference, Guillermo? Me making wine references in public? That's crazy. Tasting notes? Absolutely. No, I would never do such a thing. A hint of oak.

Yeah, it's a nice bit of lightness right here, you know? Um but I I do I do want to like I'm I'm curious about this notion. I And this is probably really obvious. It's not super obvious to me, which is you said that STARKs in the non-interactive setting have non-obvious security properties. Again, you know, explain it to me like I'm a I'm a 5-year-old that happens to know a lot of math, but is otherwise an idiot. So, right. Okay, so I I I think you're asking about this distinction I was drawing between appropriate security levels when a protocol is deployed interactively versus non-interactively. Yes. So, and which one is more secure actually in that?

Yeah, I mean, it's not really a more or less secure. It's um it So, let me let me just explain. So, um when people refer to bits of security for a SNARK, okay, roughly what they mean is the logarithm of the minimum number of steps computational steps required to attack the SNARK. So, to find a convincing proof of a false statement. Okay? When people say bits of security, when they're talking about an interactive proof system, essentially what they mean typically is what is the maximum success probability that the prover can achieve on like any given run of the protocol, like regardless of how long it runs for.

Okay? And even this can vary a bit, but so it's like with an interactive protocol, it's like, you know, no matter how much work the prover puts in, it might be the case that it has like a one in a trillion chance of of convincing the verifier to accept a false statement. And you know, the that probability is so low because, you know, at the very last second, the verifier chooses a random value, which the prover just doesn't know until all his messages are sent, right? Correct. So, in that in that setting, it might be reasonable to have the prover have like a one in a trillion chance of tricking the verifier, you know, because basically because it doesn't know if it's going to succeed until it actually runs the protocol. And you know, with probability one minus one over

trillion, the verifier rejects and like everyone in the world sees that, you know, this was a cheating prover and got rejected, right? Whereas in the non-interactive case, you know, the the attack can happen silently, like kind of offline. The the prover is just sort of doing in its own head like a kind of a linear search over possible proofs to until it finds one that the verifier accepts. So, it's just very different settings. And And so, in this non-interactive setting where, you know, the attack happens silently in the prover's head and no one knows it's happening, Uh know, I think you really want like minimum 100 bits of security if you're protecting anything of value. You know, if you really want the attack to be truly infeasible today and have a little bit of buffer in case better attacks are

discovered. Uh you know, I even prefer more than 100 bits of security, but I won't complain about 100 bits. In the In the interactive setting, could be totally fine to be, you know, way, way, way fewer number of bits of security. No, sure. Yeah. Right. In the interactive setting, right? Like what is it? One in a trillion is good enough, right? But in the non-interactive setting, it gets So, I I see So, the the the point fundamentally difference is like one can carry an offline attack uh in the non-interactive case. Pretty much. That's the difference. Right. Uh versus in the other one, like you in a pure probabilistic sense, right? Like this the sampling is happening independent of whatever you do. So, you're you're screwed.

And so so that that is the argument for saying, like, "Hey, look, we might want to extend uh the amount of security for the the the offline case or the non-interactive case." Right. I think, you know, every everyone agrees that, like, you know, 40 bits of security, that's like one over a trillion, uh is is like completely insecure in the non-interactive case. Uh but could be totally fine in the interactive case. So, I'd really like a you know, a term, you know, to be precise about which of the two cases we're discussing because I think security is way more important than performance. Um and as I prefer the term to be precise about that. And you know, technically, the Stark term is not precise. And actually, I think that had confused discussion

significantly. And this This is one of the I I started looking more closely at what people were doing in practice at you know, as at my first summer at A16Z, you know, and I I wrote this blog post. I actually had a couple people reach out to me after the post. Uh not not the 17 misconceptions post, another post about security. Um saying that they they thought that some Starks had been deployed interactively and hence, you know, 80 bits of security was plenty, plenty, plenty, plenty, a huge amount of security. Um and that was not true. And if these if these individuals didn't know what projects were doing, like no one does other than the projects themselves, right? I mean, I found it actually quite disturbing that, you know, basically

these things were ostensibly protecting quite a bit of value. Um and actually nobody knew apparently what was really the protocol was doing. Uh so that was um that sort of inspired me to try to talk about it. I see. Makes sense. I'm going to keep going through this list with the highlights. Sounds good. Uh number five was SNARKs targeting R1CS cannot support lookup arguments. I'm assuming that this is potentially in reference to the work that you then started to do on Lasso.

Um partially. I'd say this um this one kind of fed into a paper I have on customizable constraint systems uh which predates like Lasso and Jolt. And actually, you know, is is for ZKVMs is actually rendered irrelevant by Lasso and Jolt uh basically because Jolt avoids constraint systems almost entirely. The constraint systems that it does use are so simple that it really doesn't matter what kind of constraint system you use. Uh we use R1CS, but like really it's they're just like those simplest constraints you can come up with. You can kind of use anything. But the customizable constraint systems paper was sort of pointing out uh a couple things. Basically, known sum check-based SNARKs, Spartan in particular, just sort

of directly supports not only R1CS, which is how, you know, it was described for R1CS, but like, you know, you don't need any new ideas. Uh you just have to understand the protocol and you'll see it actually can prove statements about much more expressive constraint systems. And that's sort of, you know, CCS, customizable constraint systems, are sort of what we thought was the cleanest and most expressive constraint system that, you know, something like Spartan could prove statements about. But yeah, there there there works that were um you know, developing some sum-check based SNARKs, um, also looking at uh, non sum-check based SNARKs for R1CS, and sort of didn't let the sum-check based SNARKs uh, for R1CS have access to the lookup arguments. Right? And so, they they, you know, claimed significant

speed improvements um, over, you know, something like Spartan uh, when I think the speed improvements are really just due to the fact that they didn't let Spartan use lookups, and they did let, you know, the new stuff use lookups. Okay. So, uh, that's that's the point I was trying to highlight there. And, you know, now of course that Jolt is all, you know, sum-check based and, you know, uses Spartan for R1CS and everything else is lookups, I don't think that, you know, any of this is is unclear anymore, but at the time of the misconceptions post, I think it was unclear.

I should also say the sentences I'm saying, you you are arguing in this article that these are incorrect. That SNARK targeting R1CS cannot support lookup arguments is an incorrect statement. Right. Yeah. Another incorrect statement that you believe is is incorrect is believing that Fiat-Shamir transformations generally lead to no major loss of security except when applied to the sequential repetition of a base protocol. That actually has come up on episodes since. The Fiat-Shamir transformation as a place of potential security loss.

Uh-huh. And that was that's just interesting that you that you brought that up back then. Even for me, can you can you like uh, like unpack that sentence in like a nice way? I I I think I know what it is, like I can map it to something that I understand but And just to say it again, like the the misconception that he's saying here, people believe that there is no loss of security when using Fiat-Shamir, but that is incorrect. Yeah, so I'm happy for the opportunity to say something here because actually I think the blog post uh, this is sort of buried in the post, it's very technical. Uh, I think it's really good to speak about it right now. So, Fiat-Shamir can lead to security issues in two ways. Okay, one is basically like it's just not implemented right.

And this comes up over and over and over again and I mention it sort of as a PSA in the post, but like people have been aware of this for a long time and somehow it the mistake kept happening. For Fiat-Shamir to be secure, you have to Fiat-Shamir hash anything that the adversary might control. Mhm. And often people don't do that and that makes it attackable. Okay? And so people will call that weak Fiat-Shamir. I mean, I think we should just maybe just say like that's not Fiat-Shamir, like don't do that, but we people call weak Fiat-Shamir. I heard that, yeah. But like I've heard it just like used. Do people just use weak Fiat-Shamir sometimes?

Yeah, I mean I'm not sure why anybody would intentionally do it just because Fiat-Shamir hashing is like rarely a bottleneck, so I don't know why you would want to kind of risk. You know, I think the general message for practitioners is like when in doubt hash it. I mean there are some settings where, you know, if you're hashing like a whole description of a constraint system and the constraint system has no short description, like that can be really gross. But typically it's not a bottleneck, so like when in doubt hash it. If the adversary might control it, hash it. And so that, you know, that's really just a bug that some practitioner, you know, some papers, you know, forgot to write down like, you know, hash this as well. And so, you know, you know, people implemented like the paper word for word and so Trail of Bits, you know,

discovered, you know, this bug in a bunch of SNARKs. And you know, depending on context, um the this might or might not be a completely catastrophic vulnerability. Paul Grubbs and and his colleagues had a paper, Paul Grubbs is a faculty at at Michigan, recently you know, looking at kind of a systematic look at like SNARK implementations and found, you know, this this bug like all over the place and I believe I actually found another exploitable deployed deployment of this bug. Anyway, so that is one major way Fiat Shamir can lose its security. That is not what this item of the post is about. Okay. This item of the post is about the fact that even if you do implement it correctly, the number of bits of security in sort of the in

interactive sense of the protocol you're applying Fiat Shamir to, you know, to make it non-interactive, uh you know, often people just assume that you know, the Fiat Shamir protocol has the same number of bits of security as, you know, the interactive one you started with. Right? And as we discussed before, like these two words, bits of security for interactive and bits of security for non-interactive, don't necessarily mean the same thing. But, um yeah, so they assume it's the same number. And it's not it's not always the case. Um and so, there's really like a a canonical example where there actually is just a catastrophic loss of security uh even when you implement Fiat Shamir correctly, which is you take a protocol with like one bit of security, you amplify the number of bits of security

by repeating it in you know, sequentially, you know, once, then twice, then the third time, then the fourth time. Right? Uh that drives the security down to say uh 128 bits of security if you repeat 128 times. And then you Fiat Shamir that. That won't be secure at all. And like people do know that. Is there an easy explanation to see why it's not secure? Uh there's a simple attack. It's sort of called a grinding attack. But like basically in the interactive setting, the prover would have to sort of get lucky on all 128 uh repetitions all at once. Has to get lucky all at once. But once you Fiat Shamir it, you can sort of attack the first iteration like independently of all the others and it'll only take like a couple of attempts to to succeed, you know, to find a convincing proof just for that

iteration. Uh I see. And then you can continue grinding the rest. Yeah. It's like you defeat one and then the next and then the next and you don't have to get lucky all at once. Got it. Right? And so, but I I think people generally think, oh, well, that's the main thing to be worried about if you're not doing sequential repetition, you know, and you you do strong Fiat-Shamir and not weak Fiat-Shamir, you should be fine. This post is pointing out that there's a really subtle and amazing attack, um, which I learned about from a paper of Attema et al. and through the folks from Nethermind, which, uh, I have a paper with, um, which I'll sort of plug briefly, but I think they discussed it on this podcast at some point.

Totally. I was about to say, this is where I think we covered exactly that. And we'll try to dig that up, the Nethermind episode. Yep. Wonderful. So, I just recently talked to a couple experts recently who were like blown away by this attack. Like they they literally read my post. They didn't quite understand the attack in the post, and then I, you know, sketched it for them over email, and they were like, oh my god. Um, so, this is when you take a multi-round protocol, and it's crucial, like there has to be two or more rounds. So, the attack doesn't work if it's like a, you know, just two messages. Got to be like, you know, three or four or more messages. You know, say say it has 64 bits of security, you're not happy with that, um, you know, because if you Fiat-Shamir like that's not secure,

um, so you repeat it in parallel twice to get 128 bits of security. Okay. Right. And then you Fiat-Shamir that. Okay, so this is not sequential repetition, it's parallel repetition, and then Fiat-Shamir. Okay. That doesn't work. So, here's a very first dumb question is, what does it mean to Fiat-Shamir two parallel instances? What is the initial hash? Right. So, so the parallel repetition of of the base protocol is just a new, you know, interactive protocol. Forget about Fiat-Shamir. So, it's like you have a protocol with 64 bits of security, you want to reduce that or improve that to 128 bits of security. So, rather than like running it once and then running it again, you're going to run it twice, sort of, you know,

Yeah, like simultaneously or something. Yeah, exactly. That is a new interactive protocol. It does It has the same number of rounds as the original protocol, unlike the sequential repetition where you would have doubled the number of rounds, this is the same number of rounds. Okay, now Fiat-Shamir that. You know, that's just an interactive protocol, it makes sense to Fiat-Shamir it. Fiat-Shamir that. That will be no more secure than if you hadn't done the repetition at all. If you hadn't done that parallelization, basically. Right. If you hadn't done the repetition, like literally the repeating it once, as long as if you started with a two-round protocol, you repeated it once uh like in parallel, you know, so so there's two repetitions in parallel, and you Fiat-Shamir, you might as well repetition at all.

Interesting. Okay. Um and and again, the attack is very simple. Uh it roughly amounts to attacking the first repetition on its own. You sort of, you know, use round one, like the first verifier challenge, uh to attack one of the two repetitions. And, you know, you only need like about 2 to the 64 attempts before you, you know, defeat one of the two. You're not going to defeat both of them uh at once. You're only going to defeat one of them, but then you still have another round left to attack the other repetition. And I know, I know, you can't you don't get all the details when I'm saying this on the fly.

Um but I'm going to try to go back to the misconceptions post and add just I think a little picture of, you know, the you know, the two rounds, you know, rounds repeated. cuz the point is like, okay, like fundamentally what's going on is like you know, these sequential constructions versus parallel constructions can always be reduced to just like instead of kind of attacking this like much larger space, like uh square of the size, actually what you're doing is you're doing something two times the size. Right? Because of the fact that like you can you can exploit this the the structure of it such that like, you know, instead of having like many parallel instances, each of which is independent, in reality what you have is we have a single instance, which is like sequential. And they they are all fundamentally like sequential in some way. Right? And so

like it just requires that you attack like a single independent instance, and so you only need 2 to the 64 at any point in time. Yeah. Or like attempts or whatever. that's the right yeah, that's the right intuition, yeah. And so you know, and the general message of of you know, this part of my blog post, I mean mainly it's it's uh it's a PSA because this is like a huge foot gun where someone at some point is like going to blow their foot off unless everyone is aware of it. Um the kind of the right way to use Fiat-Shamir in in practice is to first show that the thing you're uh applying Fiat-Shamir to satisfies a stronger soundness notion than like just standard soundness um called round-by-round soundness. And this captures the intuition that if the prover in in the interactive protocol

kind of has to get lucky all at once like in one round, like it can't sort of get a little lucky in the first round and then a little more lucky in the second round. see. You know, that then when you apply Fiat-Shamir, it's fine, you know, there's no loss of security. And so with the with the Nethermind folks and you know, my postdoc um Alex Block and and and others um we we showed that like FRI is round-by-round sound. Uh it actually hadn't been shown before, so we actually didn't know you you know, in the random oracle model that like Fiat-Shamir's FRI was was sound. It's not that I actually thought it wasn't, but it you know, we should know that it is at least in the random oracle model. And then actually um you know, some a group from StarkWare kind of showed the same thing uh

basically the same result around the same time. Um and you know, with the with Nethermind we had some other results that um you know, other things people were doing um that you know, potentially could have been attackable because they had more than one round uh are also round-by-round sound. And so you know, it is all it's all okay, right? There was no like new attack in the protocol. We were just sort of you know, showing that Fiat-Shamir was safe when it hadn't actually been shown before. Here here's a a very quick dumb question before we go on to the next point is what what is like the intuition for round-by-round soundness? I know you you said like oh, you can't get too lucky and then like essentially you can't like get lucky in one and then get a little bit lucky in the next and then like at

some point like that adds. What what is the like more clear definition of it? I don't know if there is a definition for this. Yeah, I I guess that is most of my intuition. I mean, I think it it sort of rules out this, you know, sequential repetition canonical example. You know, and the if the prover just have to, you know, it has a probability of half of getting lucky in the first repetition and then, you know, a half of getting lucky in the second repetition and so on. And so, you know, it can kind of get a little bit lucky in each repetition. Uh and that's exactly the situation where this grinding attack on Fiat-Shamir works, where, you know, yeah.

Um and round-by-round sound basically says that that grinding attack can't hap- can't work. Got it. Got it. Got it. Got it. Cuz it's just essentially like the definition is explicitly to rule this like particular attack out rather than like That's my interpretation of it. That's my Yeah, that's my intuition. All right, I'm going to move on to misconception number 14. 14, all right. So, we are we are skipping like as I mentioned, I'm just I selected a few of them. I've two more. So, just before you mentioned Binyas briefly, number 14 was the misconception is the key to better performing SNARKs is working over ever smaller fields.

Mhm. And did they prove you wrong? What happened there? Great. Great. So, great. So, this predated Binyas. So, a little context there. So, um Binyas uh was at least partially inspired by Lasso and Jolt and this post predated Lasso and Jolt, right? So, at the time, you know, the this was really uh sort of a fight between elliptic curve based SNARKs, meaning you know, the commitment scheme uses elliptic curves, so the field's big, and um you know, like hashing based SNARKs and you know, using Fry in particular and the you know, the field is small.

field folks. Yeah. Like the Plonky3s and stuff. Yeah. Yes. Um and and so, you could have summed up a lot of my points, but not not all of my points by, you know, me just saying like, "Hey, curve-based SNARKs can be faster than the hashing-based SNARKs like even though they work over big fields and, you know, JOLT sort of proves that correct, right? Because it's, you know, at least as fast as the current, you know, like hashing-based EVMs or what have you." But there there's another point I was trying to make, which is that in certain applications, you really don't want to work over the small field because the statement you're proving is sort of natively defined over a big field. And this is In particular,

this comes up whenever you're proving a statement about elliptic curve cryptography. And so, I think, you know, the the main application people like always have in mind now is like ZK-EVMs. And and there a big bottleneck is like Keccak hashing, say. But if not for that, like another big bottleneck would be proving knowledge of digital signatures. And and so, if in a world where the hashing wasn't the bottleneck, the signatures were, you actually probably would want to work over, you know, the big fields.

And you could imagine a world where what, you know, one day we're able to get, you know, work over whatever field we want when we want to and and glue everything together. And then what I'm saying would would be right, like big parts of the SNARK will work over a big field. And then I guess the final thing I'd say is, you know, just the underlying techniques that led me to try to make this point. And really I was like trying to push back on what I thought was, you know, just a general idea which, you know, has validity to it, but it's just been taken too far, right? But the the techniques that kind of led to the points I'm making, you know, the sumcheck protocol and all all of these things, they led to to Binius, right? And so, what Binius has done in my in my view,

and I think this isn't a controversial view, is it's sort of taken the small fields to the extreme where now the characteristic is two. And I actually don't like the small fields term, it's small characteristic. So, ultimately you work over 128-bit field, but it's like, you know, you do as much as you keep as much of the prover's work as possible over the the the base field or something like that. So, wait, but like, would you still stand by the fact that going back to the statement, the key to better performing SNARKs is working over ever smaller fields being incorrect? That was what you were saying. Do you Do you sort of Would you adjust that? So, I would say two things, okay? So, one is it depends on what what you're proving, right? And like this this whole thing about proving statements about elliptic

curve, you know, cryptography, it's not like some isolated application. It's like, you know, half of blockchains is just like proving you know digital signatures authorizing things, right? And like today's digital signatures are based on elliptic curves. That's like That's not like some small thing, right? Um so, it depends on the application. Also, you know, like these these folding schemes that get uh you know, the overhead of recursion very low, what that what that basically means is you can break big computations up into really tiny pieces, and you know, prove each piece separately, and aggregate the results, and uh the aggregation step won't be the bottleneck because, you know, the folding lets the recursive aggregation be so fast. Like that can be really important if like, you know, prover prover space is a major concern for you. There's been efforts to

also do that with uh with hashing-based SNARKs, but they they still have downsides. So, you know, uh that's another reason the curves could stick around. Uh so, I I don't think the matter is settled, but I will say I'm like more bullish on the small characteristic fields thanks to, you know, the Binius advancements than I was, you know, when this post came out, you know. Cool. Yeah, cuz that one that one when I was going through it definitely got the Oh, that that got the most pushback, I think. Yeah, that one got the most pushback. But, um you know, ultimately, I think the developments since then have sort of uh fleshed out what I had in my head a little more. Like I couldn't talk about um you know, like Lasso and and uh and Jolt, which I did in my head at the had

in my head at the time. You know, they have these nice properties that while they work over big field, the prover only commits to small values, you know, like numbers between 0 and 2 to 20 or something. Like that's a significant performance boost for the techniques that do use the big fields and you know, heavily exploited to see the performance, you know, out of Jolt that we see today. Um, and that was something I couldn't talk about in this misconceptions post uh, that I can now. So that that was something that was in my head that I didn't didn't wasn't able to say in the post. Was one other thing that maybe didn't factor into your thinking then what like was sort of where hardware would be at or were you thinking about hardware?

No, I wasn't thinking about hardware too much. You know, that the small characteristics field does sort of uh, push that point forward heavily, I think. Yeah, these fields are are nicer for hardware. I mean, you know, when I was um, thinking about performance comparisons like to the extent that existing SNARKs are are using vectorization in the small fields like I I had that in my head already. But um, you know, I wasn't thinking too much about FPGAs and uh, and ASICs uh, which these small fields also seem friendly to especially characteristic too.

I mean, I I will say right like uh, what is it like Apple Apple ARM has like an instruction for multiplication of two polynomials that like that are like whatever represents the value in data or something like that, right? Like that's like a I think it just like exists on every like Apple computer and iPhone, which is like pretty cool. I think it's for Reed-Solomon encodings actually is what it is, but but it has it has direct applications of course to to potentially like some some of these types of like ZK proofs. So Yeah, so yeah, even even on these CPUs uh, you know, because AES uses um, the field 2 to 128, you know, they have built-in operations. Um, they they don't use the same basis for that field that Binius like to use, but you can still leverage it things like that. The

statement that just came out of my mouth I had no idea about uh, you know, 10 months ago. Um, that only came from talking to the the folks behind Binius, right? I you know, that's way deeper knowledge of hardware than I I would have any idea of. Yeah, yeah. I'm going to see if I can find the like ex- instruction, but it's definitely like in the Apple manual somewhere. It's not even that for AES, actually like for like small multiplications of polynomials, cuz I think it's specifically for like QR codes or something like that like particularly. It's some sort of like syndrome decoding type thing. Uh it's very weird. I I did I did not know about this. I think I posted about it in the Discord sometime, but it's like, you know, there's many messages there.

It's fun to just piggyback over these these things that came into the hardware for like totally different reasons. That's it's nice when you can take advantage of it. The uh the last point was number 17, which is and I think this might still be true. The misconception being SNARKs are performative enough today that they should now ossify. Do you feel we are any closer to actually getting our our standard SNARK or or any sort of like subset of a SNARK becoming a standard? So, I I do. Um so, first let me say I I think since this post came out, it's uh made clearer or more concrete like kind of just how slow I mean, that's my terminology. You could say exactly how

how fast or slow a lot of SNARKs are. And, you know, in my view, they're too slow, right? Um for a lot of their intended applications. Uh but, I also think they can get a lot faster still. Um so, I'm I'm still hearing this uh this view that, you know, there's some more performance juice to squeeze, but it's not much. And, you know, we should start focusing on uh hardware speed ups, focusing on standardizing SNARKs. And, I'm actually quite optimistic now that we can reach a point where uh that might make sense quite soon. I didn't I actually didn't think that would necessarily be the case uh when I wrote this post. But, I I think we can actually So, you know, as as I've uh said very

recently when discussing uh like like Joe's performance and other other ZKVMs, uh you know, I think like a ZKVM today is 500,000 times or more slower than just like running the VM without the ZK part, which means to sync as we've uh, talked about before. Um, and and but I actually think we we can get down to about 10,000 times slower rather than uh, close to a million times slower and fairly soon. And then I think it it won't be too slow.

Um, and then then then I think it will make sense to focus on hardware and, you know, um, if not standardizing, um, I you know, I've sort of have mixed thoughts about standardizing, but you know, it's going to take a lot of effort to kind of reach a high level of confidence in the bug-freeness of various implementations. Uh, these are very complicated cryptographic protocols. I mean, people know what I'm saying that the Ethereum Foundation is launching a competition with $20 of prizes to push this forward. And so, it'd be a lot easier if we sort of converge on not the right SNARK, but a right SNARK, so that that effort doesn't have to be repeated over and over and over again. I mean, hopefully we also get better at making the effort like lower and reproducible. Uh, anyway, so,

um, yeah, but you know, my view as to that final number 17, you know, that SNARKs are are too slow and can be improved and and must be improved. I uh, you know, is only stronger held view today for me than than 10 months ago. But it sounds like you think we're closer to being able to to ossify at least a little bit, at least like hit a step like a a step change where, you know, we probably not forever, but like for a period of time we kind of like all start using the same thing.

I do. I mean, I might be overly optimistic, but um, and we could talk about this a little bit later. I mean, I think some of the recent discussion on Twitter, uh, especially like following the release of JOLT, might give the impression that there's more disagreements than there actually is and I'm actually sensing like a a shift where certain views or you know techniques I've been advocating for for a very long time and like getting very little traction on actually people seem to be coming around to and if if they do then you know of course I have a view of what I think is the right you know the right approach and if if people come around to that then great you know then then we've converged. I

mean I also say you know it's never going to be like one size fits all like I think for large enough statements they'll be a right way to do things but you'll still have settings and I've been encountering them in certain applications um where you know the statement being proved is pretty simple like if you you know you can describe it in a couple million constraints and you want the verifier to be really fast and there's no there's no room in the application to you know kind of aggregate proofs or you know prove many of the statements at once you really have to just prove one small statement and you know have the verifier be fast and the proof small and in that setting like my preferred techniques don't necessarily help or you know make the

verifier cost too big and recursion would be a bottleneck or something like that so you can't you know like recurse to bash the verifier cost down so that will always be an issue it's never going to be like just like one snark for everything Right. but you know you know most applications like the statements are at least somewhat big and then I think we can converge in at least those settings. It's funny cuz right now like everything is like super general purpose right and like like we're just like throw the kitchen sink at it like we want like this thing to work for everything but one could imagine like the existence of specific protocols for things that are very common that are extremely efficient like you can prove a sync certificate for it and then verify a sync certificate you know in some like very very efficient way and

like a secondary problem. So I it is kind of interesting. I feel like like like right now it's just like the this is like the the Moore's law thing, right? It's like CPUs. Like CPUs just got better and better and better and so no everyone's like why the hell do you need anything other than a CPU? We just like wait two years and like this thing gets infinitely better. But at some point we're going to probably develop the GPU and like the you know the FPGA version of this where it's like okay no we need to do like this one thing very efficiently cuz we do this one operation linear algebra or whatever 50 million times. Let's get good at that and like you know defer the a succinct proof of that or a ZK proof or whatever you want to to that like you know special device

for the one specific case where it turns out to be extremely useful. All right. Well now I think it would be a really good time for us to talk about Jolt and maybe Lasso and Jolt. I know last year when you announced this work you were kind of you shared it in a pair. I think it would be great to go into both of these. So Justin, what is Lasso? What is Jolt? Great. Yeah, I think Lasso it's sort of a technical hammer. So I don't think we have to talk too much about it but in back in August or when we sort of announced Lasso and Jolt like Lasso was implemented and Jolt wasn't. So what is Lasso? It's it's a it's what's called a lookup argument and there's sort of two ways to view a lookup argument. They're completely equivalent but one is it lets the prover

an untrusted prover commit to a bunch of values and then prove that each of those values lies in some like predetermined lookup table, some predetermined table of values. Okay. A completely equivalent way to look at it and they really this is equivalent to a variant called what I call index lookup arguments but the the details aren't super important is it's it's a way for a prover to prove like very efficiently that a bunch of committed values are all the outputs of a simple function. So it's like the prover commits to, you know, a billion values and then very quickly proves that, you know, for for each value that's committed, like that actually equals like f of x i, you know,

the i-th committed value is f of x i, where, you know, f is known to the prover and verifier and x i is also committed. Okay. So, I, you know, I actually prefer the second view, although it's sort of I think I'm the only one who takes that view. With that view, it's just it's a really efficient SNARK for like super highly data parallel computation. So, evaluating the same simple function f over and over and over and over again. Okay. Now, what what Jolt is is something called a a ZK VM, specifically for something called the RISC-V instruction set.

It's a SNARK that lets a prover prove that it correctly ran a computer program on some on a witness, where the computer program itself is specified in like RISC-V bytecode, RISC-V assembly. And so, this idea of designing a ZK VM for RISC-V was was pioneered by a project called RISC Zero, which had like incredible foresight to see the major benefits of using an instruction set RISC-V that was not designed by like SNARK researchers, but rather designed by the computer architecture community, and came with all sorts of great tooling and, you know, compilers and things like that.

And so, Jolt is basically, you know, just another way of proving like the same statements that RISC Zero is like already proving today has been proving for, you know, they a year or a year and a half or something like that already. So, just just so you know, Justin, I don't know if you know this, but like I mean, I'm I'm an investor in both RISC Zero and succinct through ZK Validator and as an angel. And I think Guillermo, you also have I'm I'm also an investor in RISC Zero. We know we know that we know that that group quite well. But actually, I just want to stop you because just before you jump into Jolt in more detail, I actually want to ask you one thing about Lasso and these lookup arguments because I feel like there's been this line of work.

There was I I don't know what the first part of this is, but it's Kalk and CQ. I know that that's like one line. Is Lasso in the same line of work? Is it an addition on CQ or is it using is it for something else? Is it it's is it coming from different like a different track? Yeah, great question. So it's inspired by that line of work. I don't know whether to call it part of that line of work or not. So essentially we we looked at that line of work. All of those works starting with Kalk Well, okay. So none of them use the sumcheck protocol and some of them seem very specific to KZG commitments in particular and you know, it's not clear that they would work when KZG commitments don't use Fiat-Shamir. It's not clear that they

would work if they did use Fiat-Shamir. So we basically we looked at what was going on in those protocols and we said, well, let's use sumcheck. And Okay, and change it for that. Okay. It's like Justin's favorite tool. It's like, how about sumcheck here? RIGHT. AND THIS IS AND by the way, this is um you know, in my view I've you know, I've been trying to get people to to use sumcheck for for a long time. It's kind of going on 15 years like before I even like knew what SNARKs were really.

I was working on half of a SNARK, you know, so SNARKs without the commitment schemes. And you know, if I'll be thrilled if people just start like reaching for sumcheck. Like they don't have to use Jolt or whatever. I mean, obviously it would be even better if they if decide to do that, but as long as people start using sumcheck, I'm thrilled, you know. So Cool. Yeah, and yeah, so so we particularly took inspiration from Baloo which clearly had sort of a a matrix vector multiplication going on in there and then we you know, like use sumcheck to prove that matrix vector multiplication and the way we did that was very similar to something that was happening in the Spartan paper from, you know, the

2019-2020 era. Uh, and we just have like a few more observations on top of that to, uh, you know, squeeze some extra performance out. Uh, make basically make sure the prover only commits to small values, not not big values. So, that's that's Lasso and and and it sort of comes with some some other nice benefits like, uh, you know, if the for a lot of the tables, look up tables people use in practice, like Lasso is sort of unique. Like no one has to commit to the table. Um, you know, I think anything using that doesn't use the SumCheck protocol is, uh, not going to have that property. So, that's that's Lasso in a nutshell.

Got it. Very dumb question here before we get too far. You said, uh, it only makes sense for like a simple function F. How do you quantify the simplicity of function actually? What does it even mean to be simple here? I I I know you did early work on this in like a very specific way, which is like like polynomial, uh, like degree of weird Boolean functions, but I'm just curious what it means here specifically. I I guess the way I'd say it is one way to view Lasso is it from the verifier's perspective, it is a reduction from evaluating F many many many many times, you know, like once per lookup, to evaluating F just once. Okay, and really it's not evaluating F itself, it's evaluating the multilinear extension of F, but whatever. Um, basically you want F to be simple enough

that that multilinear extension evaluation is fast for the verifier. Cuz there there are some functions F where that multilinear extension evaluation would be like extraordinarily expensive. Um, and so it's a very technical notion of simple. So, it's something like, if I may, it's like the support of So, it's it's the number of non-zero coefficients in the multilinear extension is like the complexity of the function that we care about here. Is that right or is that Yeah, and it doesn't have to be in like, you know, uh, it could be in any basis. So, coefficients in whatever basis. It just needs to be some quick evaluation procedure. Having few coefficients in your favorite, you you basis for multilinear polynomials is is one uh way to do that.

Yeah, I mean, you know, it turns out that like all of the tables that we need for Jolt have this property, so no one has to commit to these tables and things like that. Mhm. Right. Like like bitwise operations certainly will have this property and things like that. But but like yeah, when you could imagine like much more complicated operations to have a sparse basis, you might need like a very complicated basis in which you're doing all of the work in the reduction or something. Yeah. Yeah, and then to this like new basis. In a in a in a in a theoretical sense, this is not a practical protocol, but there's like a section buried somewhere in the Lasso paper.

Like it's a sort of any function with small circuit complexity, it has some reasonably low degree extension that can be quickly evaluated, right? I was going to say, this feels like right up your your OG alley, right? Like this is like like defining the complexity of this feels like Well, kind of Yeah, so so this has always been a sign of a thorn in my side where, you know, my favorite protocol is for the verifier to be fast, you either need like the multilinear extension, like I said, things get nice for the prover if you use multilinear extensions, but the verifier is going to be fast mainly if the multilinear extension is quickly evaluable. But what does it mean for the multilinear extension to be quickly evaluable?

Um and you know, explaining this to people has you know, been a 15-year you know, thorn. Um Uh but it's you know, it's very related to you know, how like AIRs AIR constraint systems are sort of by design like very structured so that the polynomials capturing the constraint system are quickly evaluable. This is like completely analogous to that. Uh yeah, that's the gist. Okay. Okay. Okay. Got it. Cool. Let's go into Jolt a little deeper. You sort of put it in the same category as the Risk Zero ZK VM. You didn't mention it, but it would be similar to the SP1 syncs VM.

It's funny like I'm not actually sure like is Jolt the name of the ZK VM or is it the name of the snark system that you've actually created? Like is there any sort of cuz like for example, SP1 we know is using Plonky3. I actually don't know what Risk Zero's using. I'm guessing Groth16? It's a combination of a bunch of stuff I think. Okay, so firstly so so so Risk Zero applies a stark that they implemented sort of themselves to uh an air capturing, you know, the Risk 5 CPU that, you know, they also like implemented themselves, right? Um SP1 feeds an air that I guess they implemented themselves um that I think building on some other projects as well.

Uh they feed it to Plonky3 and then Plonky3 is sort of the the the stark for the air the uh the stark back end for the air that they feed to Plonky3. Okay. With Jolt, um I would say Jolt is like the ZKVM but like uh agnostic to it's really the polynomial IOP in the ZKVM if you will. So, you know, I I'm very happy to switch their polynomial commitment scheme in Jolt, you know, to something like Binius say and still call it Jolt. Um I'll call it Jolt with Binius instead of Jolt with, you know, Hyrax commitment or Zero Morph commitment or something like that. Um so so Jolt is really the polynomial IOP, you know, capturing the Risk 5 um you know, uh CPU execution. And I can go into a little more detail about how that polynomial IOP works and you know,

kind of how it compares to uh you know, SP1's and Risk Zero's if that would be helpful. Would you say that's where a lot of the work that you've like the the sort of innovation is on this polynomial IOP side of things? Yeah, I mean Jolt really just is a polynomial IOP and like plug in whatever commitment scheme you want um to turn that polynomial IOP into a snark. Interesting. What are the differences, right? Like what is the difference between kind of sticking a a, you know, big brain Risk 5 virtual machine into like some like horrible representation versus this? Like why why is this representation so nice? Like I I thought so I I I ask very dumb questions but I'm just curious on this one. I Yeah, so I'll let me give a brief overview of of the Jolt polynomial IOP and sort of compare it to, you know, the

the pre-existing, you know, ZKVMs and and go from there. Mhm. So, you know, just as a CPU contains several components, like so does Jolt like really mirroring those components. And, you know, I think the the other ZKVMs probably function in a similar way as well. Um so, you know, a CPU just repeatedly uh runs like fetch-decode-execute, fetch-decode-execute, fetch-decode-execute, right? And then uh the only other thing going on in a CPU is like reads and writes to random access memory, basically. There's some registers in there, too, but I don't think you have those in the ZKVM.

Yeah, no, we do. We do. So, RISC-V Oh, you do? Okay, okay. Yeah, so RISC-V has 32 registers, like, you know, so we have the 32 sorry. Um but uh yeah, so the the registers are part of like the fetch-decode, you know, like execute is telling you like, you know, what are the source registers for the instruction, what's the destination register, you know, where should the output of the instruction be saved, and stuff. Yeah, people usually have been I know they stick those in RAM somewhere instead of actually having like some dedicated Yeah, yeah, exactly. So, ultimately, like, you know, the SNARK techniques we have to, you know, verify that the registers are being read and written correctly like are really no more efficient, you know, um waving my hands a little than just general random access memory.

So, like, there's not really a reason to separate the registers from the rest of memory necessarily. Right. There are, you know, there are some in the weeds reasons um that you can benefit from that. But anyway, yeah, so Jolt Jolt has the following components. Um okay, so first firstly, the newest thing in Jolt, I would say, you all be it sort of the one I'm I'm tied to like the least in sort of my my personal, you know, hopes and dreams or whatever, is uh uh the handling the execute part. We we do it purely with the Lasso lookup argument. Okay, so we say, like, if you need to evaluate this instruction on, you know, these inputs X and Y, we we just treat that as a lookup into like the evaluation table for that

instruction, which is exactly this view I was saying where, you know, lookup arguments are great for evaluating the same simple function over and over and over again, right? What what does a CPU do? Execute execute execute execute execute, right? So it's a you know, it's a match made in heaven. So that's that's how we handle execute is just straight up Lasso. You know, this lookup table is is enormous size, you know, 2 to 64 to 128, but it's so structured that we no one ever materializes the whole table and and so forth. And people were already doing similar things just without quite this perspective and without using some check, which I think is key to the you know, getting the the proof of performance really high.

So so that is one part of Jolt. We handle sort of the random access memory with what's called offline memory checking techniques, which also are quite popular already today. But again, we implement those offline memory checking techniques with some check. And we we particularly use something from Spice, which is a variant of something from Spartan. Anyway, and then finally I'd say we we handle like the fetch Well, fetch is again like a memory checking. We handle the decode part with R1CS. So we have this constraint system, which again, it's like a sort of minimal constraint system. There's something like 40-ish constraints per step of the CPU,

and I think there's like 80 witness elements, and then they're all very small committed per step of the CPU. And that's sort of doing things like you know, if you if you fetch the program counter from from the right memory cell, like you then have to sort of decompose it into several different fields or something and making sure we do the decompositions right. That's that's the gist. So that that's all a Jolt. And I would say the the main differences over you know, like existing ZKVMs in in my view, like of course I think you know the fact that it it uses the sum check protocol to like everywhere, you know, to to minimize uh you know, especially the amount of data committed by the prover is uh you know, that's that's really what

you know, what I'm like sort of personally connected to like what I feel like that the main takeaway I want from people to take from Jolt. The other things I'd say is um it does more is sort of everything is like R1 this very minimal R1CS and and offline memory checking. Everything is offline memory checking other than the R1CS. So that that's a powerful thing I think. I mean that that's where we get like you know, you can specify a new instruction for your instruction set just with like very few lines of Rust code and that's just like a very human readable specifying, you know, how you sort of decompose, you know, executing the instruction into executing sort of instructions on smaller inputs or

something like that. So I think that's valuable, but like you know, there's no so I want to be clear about something I guess um doing everything through lookups which under the hood is offline memory checking at least as the way Jolt and Lasso do lookups. I I think that's very powerful. I think for some instructions there's more performance to be had by going through a circuit implementation of the instruction. I think in most cases that performance overhead may not be worth the extra complication. It's like very very clean and simple to just do everything through these lookups. Um so I you know, I don't necessarily think like people will only do things through lookups like forever and ever from now on when they design ZKVMs but there are definite benefits to doing

it that way. It's definitely nice and clean and simple. You talk about designing a lot of the system around sum checks. Does that sort of hint that like one could also design a lot of systems like these systems around another paradigm? Like could it be a folding based ZKVM? Like could you just use another one of these techniques that people like to kind of build around? Yeah, so I mean, one thing I'd say is like the state-of-the-art folding schemes do use sum check in them, right? Okay.

You know, so that's like uh Hypernova and, you know, I guess uh the the Protostar like line of work is, you know, doing something sum check like, but not literally doing sum check. And so, I think a sum check more is like a hammer. Um and the main thing to be aware of when you use that hammer is that the the polynomials arising like under the hood in your protocol are multilinear or at least multivariate instead of univariate. And that has uh ramifications both in terms of what commitment schemes you can use, and um there's much more subtle ramifications that I think uh people are are slowly starting to understand. It's just It's just a hammer for, you know, designing SNARKs where the prover

commits to minimal amount of data is my view. Well, what I was what I was trying to say here is like, it's you know, if you're It's almost like you choose a track, and then you build around that track. I do kind of wonder if you could like, is there is there a a chance for you to share with existing ZKVMs? And the ones that are like with the with the RISC-V instruction set? Yeah, can you actually like mix and match You sort of mentioned you could maybe use Binneas instead of what you have right now, but like, how much overlap in what exists out there is there with Jolt? Or did you have to build it again, basically? Did you have to redo the whole thing?

Yeah, so I think you basically do have to redo the whole thing, um which is why it's, you know, it was a heavy lift for um Sam and Michael and Alin to build this proof system. Like, they really couldn't reuse much of anything. Um fortunately, they were able to start from Arcworks and and Spartan, but, you know, nothing nothing else really. Um you know, some curve libraries, too. I guess it's it's a little hard to explain, but like the you know, the fact that the polynomial IOP is just dif- different, you know, um it means you kind of have to start from scratch. The components of the proof system are the same like there is a polynomial IOP, there is a polynomial commitment scheme, right? But the polynomial IOP is totally different and the commitment scheme needs to be at least a little bit

different because it's multilinear instead of univariate polynomials, right? And this is maybe this is this is in the weeds, but like um people have been trying to like use fry as a multilinear polynomial commitment scheme, you know, so that they can they can glue things better, you know, together better, right? And actually okay, so an aside, but like I'll take this as an opportunity to to revisit I was saying before I think there's more agreement out there than kind of the Twitter discourse might lead people to believe. So there's a new proof system STWO that StarkWare is working on, right? And yeah.

There were just some new numbers presented at the recent, you know, ZK Summit and there was a ZK Accelerate event straight right after that. So I was looking at the STWO numbers, right? And like in my blog post about JOLT I had a pretty lengthy discussion about whether, you know, something like like proof system like SP1 would be able to do recursion efficiently if using like a SNARK-unfriendly hash function. And I was expressing concern that this like recursion, you know, with something like Blake as the hash function would be too slow and would bottleneck the prover.

And in in the presentation about STWO one of one of the presentations, there were very very very good numbers reported for proving Blake and I was I was worried all the say like what, you know, did I miss something? You know, have I, you know, like underestimated like the performance of of some proof systems? But it, you know, there was there was Twitter discussion like STWO is apparently getting mileage out of using a lookup argument that is using the sumcheck protocol that was inspired by Lasso and and quite similar in many ways to Lasso. And so actually, you know, these good performance results are consistent with like what I was saying in the blog post is I think you'll need the SumCheck protocol to prove these hash functions fast enough

that you can do recursion quickly. And so there there isn't actually any disagreement here. I agree with everything. Right? And and so yeah, I mean like you know, in my view like the key components of Jolt are just like everything it's like kind of exploding SumCheck to minimize how much data the prover commits to. And then it's it's handling as much as possible with offline memory checking based lookups. And you know, I'm I'm more tied to the SumCheck part than to the to the lookup part. I think they're both powerful. Yeah, so that's that's my view of what Jolt is and how it compares to the existing proof systems. And there are ways to glue it together cuz like like the Stew is like it's only using SumCheck I think in the lookups, right?

Everything else is based on you know, Starks and univariate polynomials. So there are ways to do it, but like I'm hoping the community sort of fully embraces SumCheck and like yeah, SumCheck through and through. It's not just one component of the proof system if that makes sense. Interesting. What's the plan for something like Jolt? So you've like done an implementation. Actually, I mean this is this was interesting cuz you announced it last year and then just recently actually I think the day of the ZK Summit we saw the announcement for Jolt again, but I was like I wasn't clear when I saw that. I was like what is that? I guess that was that was the implementation. That was like this is now ready to use. But what is I mean is this just like an open source library that you're sharing? What are you doing

with it? Yeah, so it it is just open source, you know, it's for anyone to use and build on. I mean there's a lot of building left to do. So right now it is you know, there's not there's not what's called continuations implemented. Right? So it takes like the entire execution trace of the risk five program and it just like proves it all at once. And that's very space intensive for the prover. So what people will typically do is they'll chunk up the execution into smaller pieces and kind of prove each piece separately and aggregate the results. So, you know, we don't have any of that implemented yet. We want to, you know, switch the Binius to the commitment scheme over to Binius and all sorts of other stuff. So, there there's a lot left to build.

We're kind of still figuring out the best way to go through that long process and you know, we're hoping that the community as a whole will, you know, contribute and and really I think the initial version of Jolt that we just released like there weren't great ways for the community at large to get involved. It sort of just needed like a core team to get it to this point, but I think now they're sort of, you know, a more modular path forward. So, we'll hopefully figure that out. But no, they are the word is very important to us that this is this kind of open source and you know, eventually you know, the the small team that that reached this point just like can't build all of it and can't like keep doing this forever and ever. So, it's very important that sort of the community, you know, as a

whole kind of get get involved and eventually probably take ownership in some way. We'll see. What I'm kind of curious why it's coming out of a16z research. That was that was also a thing where I was like you guys are building stuff and it's open source. You're sharing it, but like do you imagine spinning it out into something or is it really just like for the teams in your portfolio or is it just for the community? Yeah, I'm kind of curious what how you think about it. Yeah, no, it's for the community as a whole. I mean, it'll a16z will never monetize this. Of course, we'd love portfolio companies to to use it, but we'd love for everyone to use it. The perspective of people at a16z is that the the firm as a whole sort of succeeds

or fails based on the entire ecosystem. You know, it's not about any one project. And so, if if we can really move the needle for the whole ecosystem by sort of, you know, these sorts of efforts, uh, it's worth it. And so, I was very lucky to, you know, join the firm when I did. The engineering team had just gotten built up along with the research team. I managed to get a lot of interest and excitement from Michael and Sam, two of our engineers. You know, they didn't know anything about SNARKs. They had to learn it from scratch. Um, it's nice that, you know, I had this book that, you know, they could kind of get like a private pass through the book. Um, nice. I mean, the whole thing has been sort of unbelievable for me that they they've managed to pick this up and

implement it in and it was like just so much work for them. Um, but, uh, yeah, I mean, the hope is that it it it benefits the whole community, um, and we'll see how it plays out. I just love this. I can see this it's like you have been on a mission to make SumCheck the thing. And you are now getting it into the hands of people in a way I guess you maybe couldn't have imagined like a few years ago cuz you were really in that research area where you might have championed it in research, but you need people to implement it and buy in. And here you actually Yeah right.

This is the like spoon, here comes the airplane to like the child who like doesn't want to be fed is like, "No, you will be fed SumChecks." Right. And I actually I mean, you know, this whole effort like would have never happened if, you know, the Risk Zero had the foresight to I wouldn't know what Risk Five was when, you know, when when Risk Zero launched, right? Um, you know, the sort of the the interest, the fact that I was able to, you know, take like three engineers time cuz Noah worked on the, um, like the the developer interface um which was also a lot of effort. You know, to take all that time from a very small engineering team for like, you know, ultimately like not 10 months if you include Lasso in there. Like, you know,

the fact that just all these projects had already built so much and made so much progress, um, like it just can't happen without that. Yeah. So, anyway, I but yeah, as a as just a professor, I think there's no way we could have I I have gotten the engineering required to just sort of demonstrate that this this stuff really you know has the benefits that it does cuz you know engineering is is for as a researcher it's like it's a confounding factor right it's like something could be 10 times better sort of intrinsically but the engineering makes a 20x difference and you can't tell now you know Totally.

I could see that up yeah. Funny. Was there ever a moment as they were implementing it where you weren't sure if your like results would actually play out cuz like now you have some metrics that are good but like what if they hadn't been? Yeah you know I I won't say that I had like no stress at any time but you know like it was always the case that like so I had very detailed calculations like largely based on like cycle counts you know especially because we're using curve based commitments like everything the prover does is like field work Mhm.

or or just like you know plumbing stuff that you know like I sort of ignored in my calculations right so either you know I was making a mistake in my calculations or the plumbing was just going to be too expensive and I was pretty sure the plumbing wouldn't be too expensive so I either I had like a fundamental misunderstanding and my calculations were missing something really important or just like the plumbing is is is overwhelming and so until I either discovered a really big mistake or the plumbing was just seeming awful I was I was not not too worried.

You were not worried. Yeah but now Michael and Sam suffered through all of this without that faith right so I'd say even a month ago we were 5x 6x slower than today. Oh wow yeah. And so I said we we had like a functioning version of Jolts after like back in December and so I I thought that I was surprised how long it took to get the engineering in the state that it needed to be in but I never had a doubt it would get there but like I kept tell Sam kept saying like oh we're going to get like at most another 2x even even back when we were like 10x and I kept being like "No, we're not."

It's going to be better. And eventually it was. And it was. And it was. And there's And there's still something on the table there. So. Right. Yeah, it it is funny. The engineering does It's like you can test individual components, but it isn't until you kind of really really like put all the nuts and bolts together and like really make sure you oil every bearing and stuff and it's like clear that it all all works. It's very easy to like jump ahead the five steps, but like there's some real glass chewing that happens in the middle. Oh, yeah. Oh, yeah. And there you know with Jolt's like there's a lot of structure that you know existing libraries don't leverage. Like the R1CS we deal with is like super structured super you know and Spartan was made to handle arbitrary R1CS and we were just like It was 60

times too slow to begin with and you know we it took a while to figure out exactly why it was it was quite so bad, you know, why what what structure it was missing and things like that. So. Yeah, it's like materializing the matrices and like one row order versus column order will screw you if they're spot You know, like Like this is the kind of stuff that's like, "Oh, like Yeah, I mean of course it's like if you do it right it's going to work, but Right. but takes a takes real glass chewing. Right. And And I don't want to minimize like that stuff is super important. Um but I think there there is a perspective out there that like you just can't know how these things will run till you build it because of stuff like this. And I think that's too strong. I mean, you

know, it's always possible I just got lucky with Jolt and like you know this stuff didn't turn into like sticking point that kept us from getting where I thought we would go, but um you know, my my general sense though is that with enough glass chewing you will get where you think you're going if your your calculations were detailed enough to figure out what you know where you think you're going. And that that has been my experience so far. Cool. I really see this Justin now as like this mission just this like force of will to get this sum check out there in the world and it and it's and it you did it.

So, congratulations on that. Well, thank you. I could I definitely could not have done it without a lot of help along the way. So, let me express appreciation to everyone and uh yeah, I mean I I think at this point um I I get to work with a lots of new people who who, you know, weren't working on SumCheck before and uh you know, that's that's super fun and um you know, I I I just I feel much better. I feel like like I could disappear today and the community will wind up in a in a great place. Um you know, there there's so much ability and um motivation and capability out there and you know, I've been trying to sort of just point it in in what I think is the right direction and I feel like it's pointed now and uh and that's great. The

process can just play out. Very cool. Thank you so much, Justin, for coming on the show and sharing with us what you've been up to since last year, going through the 17 or some of the 17 misconceptions about SNARKs, and then sharing with with us Lasso and then now JOLT, and basically your mission to get SumCheck into the hands of as many people as you can get it into. I love it. So cool. Thanks for Thanks for having me. You know, I have pleasure to be here. Yeah, super super fun. Thank you. Thanks. All right, I want to say thank you to the podcast team, Rachel, Henrik, and Tonya, and to our listeners. Thanks for listening.