Episode 404 - Pushing the Limits of Proof Systems with Benedikt Bünz

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 speak with Benedict Bun, chief scientist at Espresso Systems and professor of computer science at NYU. Benedict shares an update on Espresso systems, how the shared sequencer architecture works now that the system is live, and what his team has been exploring. We then catch up on the ZK research front covering his recent results on hashbased folding with

works like ARC and warp as well as Golden a non-interactive distributed key generation or DKG protocol for threshold signatures. But the main new result we talk about is Flock a high-speed batch proof system for standard hash functions like Blake 3 or Shaw 256 that exceeds postquantum proving targets for Ethereum. All of this without needing hashes like Poseidon. A unique point about this work is that it was built almost entirely with AI written code. Now, first for Benedict, he explains how he and his co-authors audited mainly the verifier to confirm correctness, something that is uniquely possible in zero knowledge system security. So, this is a ZK researchheavy episode and I hope you enjoy. Now, here's our interview

with Benedict Buntz. Today, Kobe and I are here with Benedict Bunce, chief scientist at Espresso Systems and professor of computer science at NYU. Welcome back to the show Benedict. >> Thanks for having me here. Very excited for this. >> Hey, Kobe. >> Hello. >> It is very cool to have you back on the show. Looking back, you've been on three times, but the last time you were on was 2023. You were at the time presenting Protoar.

The first time you were on was bulletproof. The second time we were talking selective disclosure, the third time was protostar, but since then you've done some study clubs, but really it's been a few years since we've caught up on the work that you've done. At the same time, we have actually heard about a lot of the work through other guests or speakers at the ZK Summit. Like your name shows up on a lot of works that we mention. So I think it's great to have you here to finally kind of catch up on the work, the research, the, you know, the reasons kind of what are you excited about? what do you what kind of research threads are you trying to follow? So, I'm looking forward to it. Maybe before we dive into the research, I want to talk a bit about Espresso Systems and

your role there. Uh, last time we had you on, I think you were only focused on Espresso Systems. Now, you're also working as a professor at NYU. I'm kind of curious about how those two roles interact, you know, and maybe you can also share a little bit about what's happening in Espresso today. >> Yeah. So for me since 2023 so I started at NYU here in New York at in the fall of 2023 I'm a professor here in the Kurand Institute of Computer Science and I've built kind of a small small research group I have amazing PhD students and postocs and we're kind of focusing still on zero knowledge proofs but also other cryptography as it relates to you know blockchains but also

now AI and and you Wherever we find sort of I think the world like the research that I like to do is very much generally like sometimes in academia we like to stay in our ivory tower and you know the meme of you do research that like five people in the world claim to understand and maybe half a person actually understands. So I really am more excited about research that sort of sees the light of day or or at least has the the potential of having real world impacts and obviously zero knowledge proofs have been an amazing field for that and it's an amazing collaboration between industry academia applications and and all of these things and and I'm still

very much excited about that field but also some other things as well and yeah I'm still at Espresso So the chief scientist there, I hope we get to talk a bit about that as well. But yeah, that's basically what I've been doing. >> Yeah. And I know that you're not just saying it for the audience that it's real world impact because your things are widely deployed in some places. So that's really cool to see. >> Yeah. It's I mean sometimes to to you know people who are not in the field I explain basically that the biggest impact of my PhD is was making buying drugs online cheaper which is Monero Monero deployed bulletproof and dropped the transaction fees by like

>> 90% or something like that. I obviously I think that privacy technologies have have many impacts, positive, negative, neutral, whatever. And and I think Monero is a great project, but it's it's kind of a fun 5-second summary of my work. >> I do want to understand how cuz like when you were just at Espresso, that was your full-time role. Now you're also a professor. How are you balancing that? Yeah. Are you kind of part-time at Espresso? What are you guys working on over there? Yeah, I think those things really have like high synergies. So, let me explain to you what we're doing at at Espresso. So, like the core technical product that we've built is an incredibly fast consensus system.

>> Okay. So, the consensus and and we've recently, you know, we've worked with our amazing engineering team and Cartik Nyak who's a professor at Duke. We've worked together at at improving our consensus and now on you know on really cheap machines we can process like 20 30 megabytes per second of data in consensus with really really low latency. And so why why is that what's the product right like a consensus is is is nice and faster seems always better.

So what's the product? The product is so we started out basically as kind of a finality a so-called fast finality layer for rollups. So a rollup sequencer says, "Okay, this is my set of transactions." But then it takes like 10 minutes or an hour until they post that transaction on Ethereum. And until then, if the sequencer gets hacked, you don't really have security, right? Like you don't really you can't really use those fans. You don't get finality. Basically, what we do is like a very lightweight and and the consensus is designed to be incredibly lightweight. Basically, you can post these transactions on this lightweight fast finality layer and then

you basically get a stamp of approval that says these transactions are final. They can't change anymore. There's a consensus around it and so on. And now we're extending that actually and and one of the reasons why we've been doing a performance push is that now we're really going into the enterprise space. So, so I can't say too much yet, but we've been talking with big big financial institutions and they have very, you know, real world applications, you know, related to money market funds and and big financial products. And one thing that's very interesting there is that they really have, you know, they have a lot of data and a lot of transactions. you know, there's been the

DTCC has publicly talked about wanting to process like a million transactions per second and you know, sort of every single trade that DTCC is like they clear stock trades roughly speaking. So, so being able to process that and so we're in conversations with them and also other firms >> and this gets me back to, you know, sort of how do these things play together. So a lot of my work at Espresso is on, you know, for example, making that consensus system a lot faster and and you know, like using just the scientific method, you know, you have something and then you're like, well, does this make sense that it's that fast? You know, you kind of just ask the right critical question and we have an amazing engineering team

and you ask the right critical question. Wait, why is this part this should be faster? >> And then it's like a little bit more digging and then you're like, oh, okay, no, we can actually make this faster. And then you're like, oh, and then you had a real bottleneck and then you need to think around, wait, okay, this is a bottleneck that I didn't think about. Can we work around that somehow? And yeah, in that way there's actually a lot of parallels between like consensus engineering and and ZK proof engineering because there it's also like you think like should this be this slow? Well, no really it should be that part that's slow. So like let me dig here, you know, let me do some more benchmarks >> and so on. Are you though like producing the work that you're producing on the academic front? Do you use it in

espresso? >> Uh yeah, we've used some of it. We've been using VDFs and I think so one thing that we've been you know we've used a lot of cartics consensus papers >> and one thing where there's a lot of synergy now is that so I said Espresso developed a very lightweight consensus. So what does this mean? Well, unlike Ethereum, Solana, Bitcoin, we only agree on the order of transactions. The nodes don't actually execute the transactions. So, what does this mean? Well, it means that I know okay, this transaction happened first and then this transaction and then this transaction and then anyone can execute it, right? Because once I know the order of the

transactions, I can execute them and get the state. >> Mhm. But the nodes in the consensus don't do this by default, right? By default, everything just looks like data to them. >> They don't really care whether that data represents, you know, a money transfer or not. So, you need to pair that with a proof system. >> And what's the job of the proof system? Well, the proof system basically handles the execution. >> This is the sequencer component though, right? >> Yeah, exactly. This is the sequencer model. It's exactly the sequencer model. Um, so what proof system? Well, you can use people have been using optimistic proof systems. You can rely on trusted execution environments. You can do a hybrid of it. But obviously the gold standard for that is ZK proofs, right?

So, so now I think you know that that these ZK proofs are getting faster and faster like you know one of the motivations for this work was you know sort of the DTCC saying okay we want to process a million transactions per second and of course there my academic mind jumps into like wait is this even possible right like how many machines how much computing power do I need in order to produce these proofs >> and yeah I think like we'll get to maybe later but like we have some new work coming up on on you know sort of like exploring the limits of like what's the outandout fastest proof system that we could design >> originally I mean back in the day as

your the company that you founded had been looking at privacy like there was the whole privacy scheme I think we went over it actually on one of our episodes I don't think with you though I think with Ben and Jill but you moved away from that towards the shared sequencer model which I think is what you've launched with do you have any plans to put privacy back in? >> Yeah, I mean I think so the privacy model at at a very high level is called something called cape where basically you know it's it's private transaction but you can as you mentioned selectively disclose certain information to certain parties. I think it's you know maybe it was just slightly too early. M >> um you know I think now with the rise in the regulation around stable coins this

is a much more interesting model back then there were just so many regulatory hurdles around it and and privacy is is it's a difficult product because of >> for sure that you know you know because of the the regulation around it because of sort of user demands around it but actually as we're now talking with institutions institutional clients and institutional banks They really care about privacy. >> Um, you know, they really they're like, well, no, this is, you know, kind of the whole point is and they they care about it also again for regulatory reasons.

They're like, no, we can't, you know, like just put all of our data on some public blockchain. This doesn't doesn't work. So I don't think it will like come back as our main product, but like as an application, you know, that runs on top of espresso, it's certainly something that we're keeping in the back of our mind and and but also h happy to collaborate with others and and I think some of the ideas have been picked up. But yeah, it's it's kind of interesting how sometimes I still think it's a good idea, but sometimes, you know, it's right place, right time. I think especially for startups, that's a lot of the story.

>> Yeah. And I think it can take even different forms now. You know, like you say, you're working with big institutions, you're working with enterprises. So maybe it will not be the exact flavor of privac privacy that individuals would use, but they still really need it. So it will evolve into a different form that will fit those. >> Exactly. And and I still think I mean I do fundamentally this is my personal opinion I do fundamentally think that you know I don't want like right now blockchains as we use them today have worse privacy than our tradefi >> system right I can you know I I get your Ethereum address I see all of your transaction I see how much money you

have and like most people use like one Ethereum address or you know >> like they even use the same address over multiple chains right like it's really like it's convenient everything. >> It's very convenient and then it's like even linked to an ENS name. So I know that Kobe.NS I don't know I'm not to dox you but like then you know I I know I can find out information about you. Yeah >> and that's not I don't know like that's not what I want for my personal financial like uh freedom. I don't need maybe not for every application do I need Monero or Zcash level privacy. I think there's also very much a place for those. But I I I want something better than or like something at least on the level of TRFI where where maybe only a

trusted institution >> has you know some some amount of information on it and and yeah I I I still have hope and and know that we have the technology to do do something better there but maybe that's for others to solve. >> I want to move into the research topic. We sort of mentioned some of these past works on VDFs. Bulletproofs being a very famous one. Hyperplunk where I feel like I I think it was Hyperplunk where you started to veer into IVC. Was that the first one or was it Protoar where you started to do folding?

>> I think that's more Protoar. We actually had to work on it even before Nova. But you know, as always, uh when you don't put the name on it, uh you you you know, BCML LMS does not sound as sexy as Nova. Um but yeah, so but it was around that time where I got really interested in folding and IVC. >> Cool. Actually, this is kind of where I want to start the research conversation around folding. So the question I have is, is folding and IVC still your focus? How has has this sort of changed?

Because I will say this, we have covered folding a lot on the show over the years. Even more recently, we you know had been on talking about the lattises and folding. We had Prush on at the end of last year talking about the work that he'd been doing on the hashbased front. Actually, some work he he did with you as well. I'm curious about if that's still a research point. Like are you still exploring that or is that just sort of a technique that is being used across the board? Is that still the core of your focus or do you see it sort of pointing in a different direction?

>> So I think now I see it as as like it was it was and is a very exciting research topic. I think we've you know uh like a lot has already been said on on folding and and a lot of progress has been made there. So I don't expect the major like you know never say never but I don't expect the major breakthroughs to happen in that area. M >> but one thing that is nice about very high level you know folding techniques and and recursive group techniques is that you can you know compose things very well. So, so you know, let's say I have, you know, a fast proof system.

Like one of the things that I think is the kind of one of the many killer applications of folding and and recursive proving is that let's say I have a proof system that's fast on a single core, but now I want to run it on, you know, 20 cores, but really let's say it's fast on one machine and I want to run it on like 20 machines, 100 machines, right? I want to scale it up. And I think this is where, you know, folding and and various like that whole family of techniques can come in and and really, you know, like you can you can really get this perfect parallelism and perfect like, you know, the machines hardly need to talk to each other and and you can really scale things up. M

>> yeah I think that's that's sort of an important tool that that we have in our toolbox and that's going to continue to be uh important. >> Yeah. And I guess like depending on the use case it could even be no unrelated parties that compute this and eventually you can combine those. So that is this is interesting. Yeah. >> Yeah. Exactly. I think there's a lot of talk about signature aggregation where >> Yeah. like you know you have some parties signing transactions and then you want to somehow aggregate them in a in a treel like manner maybe you know there's a European node an African node an Asian node and whatsoever and then they communicate and you can really I

think there's still some things to be said almost more on a systems engineering >> side of like how do you orchestrate this like we know from a theoretical point of view okay there's perfect parallelism and and sort of everything should work out. But like how do you real world orchestrate these like many many parties? One thing that I think is interesting, I'm just going to throw it here. There's a research idea, maybe I'll I'll work on it, is like, you know, now a lot of times we, you know, we've been worrying about, okay, what's the fastest prover on like a hardware? But I think like one interesting question is like now it's like, okay, what's the cheapest prover, >> right? like like let's let's that's

let's let's measured in dollars you know like give me a budget and like how can I architect things on you know AWS or your favorite cloud to be like how cheaply can I prove you know this computation I think that's like a very interesting you know new measuring stick >> yeah that's a that's a good point like even when you're thinking about you know all the RAM shortage and the access to consumer device like what What is the cheapest accessible proving harder that you can use? So yeah, that's an interesting question, >> right? And and maybe there's like, you know, I think one thing that could be interesting is, you know, let's say like I don't know, I'm not an expert in cloud

pricing, but sometimes they have an over capacity. So they sell compute very cheaply. >> Yeah. >> So can you take advantage? And I think folding there again is very useful because you can break down >> your computation into really really small chunks, right? So you can say like hey dear dear Amazon or dear Microsoft or whatever XAI cloud or you know whatever the new new cloud is please give me your cheapest devices. I don't really care how big or small they are whenever they're available. I just like you know like sort of price optimize this for me.

>> Yeah. And then you know every time there's like some cheap compute I'm going to compute one chunk with folding and then I folding combine them in you know again like a treel like manner. And again I think that folding there is is is really and and that set of techniques is really beautiful because you know I don't it doesn't have to all be it's not like one monolithic thing that all the way like all the cores have to be active at exactly the same time. It totally is okay if you know part of it is proven you know a minute later than another part and you know you have one big machine and one small machine just depending on what hardware do you find on the street that's currently cheap. I want to go back to that idea just before

actually kind of the idea you're talking about here where there's multiple parties participating because obviously this rings the bell of like multi-party computation but it's different right maybe we should quickly identify that difference but the use case you're proposing is actually one of the use cases that you know uh multi-party computations often also suggested for but yeah let's let's define those >> so multi-party computation or the The I guess the definition is that we can compute some function together that you know where we all have secret inputs to the function and we learn the output but we reveal no information about our input

other than the output. So for example we could learn our average I don't know net worth without revealing you know to each other what our our individual ones are. It is a kind of multi-party computation but the difference here is that we're more kind of splitting the work and compute focused. So how can I basically use multiple parties in multiple parts of the world to combine you know to aggregate a signature >> versus MPC traditionally is a bit more privacy focused. So for example, it's used for threshold signing. So you know I have three out of five like a multi-

signature is really a farm of multi-party computation where I say you know three out of five people control this well it's but you could do much much much fancier things with that. So it's really it's it is a form of multi-party computation but traditional multi-party computation focuses more on privacy and this is really sort of distributing the work and I feel like the MPC folks have also defined it where like in MPC the computation everything that's happening is completely also obfiscated from each of the participants whereas what you're describing it's not you just said it's not really about privacy it's about scaling and compute and so that's not like the same >> privacy concept.

>> Exactly. Exactly. But they're certainly very related. So it's it's a very good question. Yeah. >> So you know in that IBC folding thread, what is recent work that you've released or co-authored sort of on that thread? >> Yeah. I think sort of the most recent line of work there in in the folding thread was was you know the work that I think Push talked about it here and then we continue to work on it. I I I guess a lot of that was with my PhD student William Wang here at NYU on so-called hashbased folding schemes. M >> so really the folding schemes traditionally like kind of the the original idea you know starting with halo was very much based on elliptic curves and in particular it's based on

this kind of beautiful idea that you know you can have two proofs and combine them into one proof and generally the only trick that we have there is you take a random linear combination between the two proofs and you use the so-called homorphism. You use that these elliptic curves are additive to then get kind of a randomly combined mirror proof. >> You need to do a little bit more, but that's the the very high level thing. So the interesting thing the interesting challenge with hashes was that hashes are very inherently they're not homorphic.

>> So if I hash the string one and I hash the string zero, I can add that. But that's certainly if I hash a string two and I hash the string three, there's no way that I can add the hashes and get a hash of five. >> Okay, >> that's not uh that's not how these things work. Certainly, it's not how they work. You know, in fact, there's some relation to to quantum computing. Like you don't want them to have this property >> because that's what could be broken by quantum computing. kind of what the that's kind of the the advantage that quantum computers use.

>> That's the the the >> the homorphism is the weakness. >> The homorphism is the weakness, right? It's it's it's kind of a it's kind of a way that the encryption is broken like that the commitment is broken which can be very useful but unfortunately it is also the angle that quantum computers can use to to exploit and break kind of the security properties that we have >> that hashbased work that you're describing though. So you you aren't focused on the elliptic curve side. You're you're focused more on this hashbased side. Is that ARC? Would arc be an example?

>> Arc is Arc is in that line. It's exactly in that line. So there's there's work called arc. There's this work called warp. Um >> yes. Okay. >> So it's it's that line. I think warp was the the latest one with William Jakamoenzi and Aleza. So the the key challenge in this whole line of work is that you can't do this homorphism trick with hashbased things like the same thing doesn't work. >> Mhm. >> So instead we kind of have to use you know we have to use other other tricks.

So you know the the basically the prover will claim this is the right random linear combination and then you can test that in fact this is the right linear combination and and you have to use some some tricks for that and yeah it turns out that still though once we've solved this problem a lot of the nice advantages of folding schemes carry over to the hashbased world. You never made the leap further to lattises though, did you? Like Beign or did you work on that stuff? Actually, I I don't know.

>> I've not actively worked on lattises, but this is I mean uh >> I'm just thinking cuz Beign, who actually was the last time I had you on, I think he was the co- guest with you. You had worked on Protoar together and he went you went this hash direction and he seems to have gone this lattice direction. Yeah. Yeah. I just I wasn't actually clear if you had collaborated again since then. No, we've not collaborated on lattice based stuff, but I I mean I think it's it's certainly very interesting and and I think that it's obviously good to have a diversity of proof systems and and lises are, you know, they're they're nicely in the middle where, you know, they have just enough homorphism to be useful for things like folding, but they don't have enough like uh or

they don't have enough >> to be broken >> broken by quantum computers. So that's that's exactly like like that's exactly sort of why people like lattises. They're just like exactly in that, you know, they try to be in that sweet spot. >> Cool. >> I think you know what intrigues me right now about hashes is that at the end of the day, you know, it's they're so they're so minimal, right? And I think if we can build something from like the absolute minimal cryptography that just has a lot of advantages, you know, it has both advantages from a security point of view. Like the more minimal the cryptography, the less likely it is to be broken. It has advantages from an implementation point of view. It makes

it sort of like relatively simple and and hopefully fast and in both software and hardware. So I think there are a lot of interesting things there but I mean I I I try to work on you know whatever is interesting and I'm sure I will be working on that as space the stuff as well >> eventually. >> Yeah. >> So actually going back to Anna's question about multi-party computation. Mhm. >> So you mentioned that threshold signatures or threshold computation is one of the use cases that are happening there and you had a somewhat recent work called golden on it. So yeah it would be interesting to hear more about that you know what is it why do we need another

kind of this kind of protocol. Yeah. So, this was a work with Chelsea Ko and Kevin and yeah, it was a basically it's it's a so-called distributed key generation protocol and non-intactive DKG. So, I think I'm sure a lot of people have heard of kind of multi- signatures and threshold signatures. So, you know, think of your safe wallet controlled by three out of five keys or something like that. And you know kind of the gold standard pun intended there is is that you have a threshold signature. So this allows you to sign the transaction and in the end you get a

like it looks like a normal signature and as long as any three out of five of them sign it's it works. And you know the same setup is also what's used in MPC it's it's very related to that and it has a lot of other applications as well. can be used for randomness beacons and so on and so forth. So uh these DKGs are very very useful. This these these threshold signatures and threshold like it's also used for threshold encryption which can be used in fronting production. So it has a lot of applications but one question is you know you need to share a so-called secret. So you know the three of us need to each have a share of the secret. So it means that let's say two of us can

reconstruct the secret, but no one individually knows the secret. >> So the problem is where do we get the secret from, >> right? So okay, we could ask uh Kobe to come up with a secret and tell each of us to share, but then he knows it, right? And he's like, "Oh, I totally forgot it." But like that's it's exactly the same as kind of the trusted setup problem that we have in in snarks or that we, you know, some snarks used to have. Exactly. Um, so the question is how do you get around that? And you can run something called a distributed key generation. So the three of us basically run a protocol and at the end of us we each get the share but nobody actually

ever had had the share. And >> interesting. It's almost like a reverse MPC where it's like MPC you're feeding input in and then the computation happens. Here's like a computation happens and it feeds it out. >> Yeah, I think that's that's exactly right. Right. It's like there's no inputs in the beginning and at the end we have a secret randomness. Yeah, I think that's a great >> You should write our introductions, Anna. That's a great way. That's great. >> Yeah. So, this this reverse MPC, so Golden in particular there, so there's a lot of protocols for this already. Um, but kind of what we were aiming for, the gold standard for it is is a so-called non-intactive DKG. So what this means is everybody just has to send one message

and then you're done, >> right? So there's protocols where we talk back and forth and you know a lot of interaction >> interactive. Yeah. >> Yeah. But then you know the problem is what if one party drops off, right? Then you have to restart. It's you know very finicky. It's you know communication is expensive. So the idea was to build a non-interactive one and and I think Grath had had one of those. I think Kobe you've done some work I think in this area as well or >> Yes on uh on group elements though >> on on group elements and and so our idea was to to design a new non-intactive DKG in kind of a a new way and and we used sort of a tool that Dan Dan Bet and

others had developed called an elliptic curve VRF and essentially the high level description or the high level insight is that normally in these DKG protocols I need to use I need to send Kobe a message right so I need to encrypt the message under Kobe's public key it turns out that you know these public key encryption schemes are uh somewhat expensive you know you need to do range groups they're just like a little bit cumbersome >> and what we realized is that the actual message that you to encrypt. It's like a it's just basically a short random

string. You know, I just really need to encrypt kind of my randomness in in just the right way. And we realized that, you know, we could do this very efficiently basically just using a one-time pad. Yeah. So, so this was kind of like a new protocol and and it it turns out to be very efficient. It under the hood it also uses bulletproof. So this is how I >> oh >> I think Chelsea came up with the first version and then she was like uh I need someone who understands your knowledge proofs can you can you help me with that and and that's how I got involved and and it was a very fun fun project.

>> Nice. >> One thing that's uh really appealing about non-interactive DKGs is like you said what happens if a party drops. So, what happens if they're even offline during the DKG? And this kind of like non-interactive DKGs allow you to to help them recover after the fact, which is super interesting. >> Yeah, it's I basically can just put like uh your message in your mailbox. I can just send you an email with your message and >> whether you open it today or like tomorrow it doesn't really matter as long as like sort of sufficient number of parties send their emails like the the one lazy person who didn't open their email uh they can still get it the next day and then they can still be

online. They haven't lost kind of their keys forever and >> they could actually access like their own. So that distributed key generation would still have happened and then you can like get or receive your part of that even if you haven't actually participated in it. >> Yeah. So you need it's it's sort of it has the same threshold properties. So let's say >> certain threshold you need or something twoirds of the people to send an email something like that you know you need you need like some portion of the people to send an email but you know for for like the the minority that is that is offline they can then later on as long as they've received their emails I'm using emails here to symbolize asymmetry

asynchronicity they can then get those messages and still recover their secret and then when the when the actual signing happens, they can be online and someone else might be offline. >> Yeah, it's a very good point. I don't think I've thought about it quite that way, Kobe. That's that's a great point. >> Does something like this get broken by quantum computers though if it's elliptic curve? >> This one in particular. So, yes. So, you asked about lises, you ask about, you know, this is certainly something where we are like it is absolutely broken by quantum computing. It's it's very much relies on on elliptic curve tricks.

>> I'll say two things about it. So we we'll first of all we are >> you know thinking about is there maybe a lattice based version for that. >> I I I don't think there's like this is again where you need it's definitely not an obvious one like it's definitely you know things things definitely get get a bit harder. So that's one thing we're looking at. I think the other thing that I want to say though is that with quantum computers we can get into the details but it's I my take is is you have to be very nuanced right so for example my public key that is on the blockchain there for anyone to see and to attack and break. I really want that to be postquantum

because it's like the most obvious target. >> Mhm. my distributed key generation that happens once and it's really between friends hopefully right like you're setting up a three out of five wallet between friends you know like that's happens once it happens today and after that it's you know maybe it's done right maybe that one is more okay to be pre-quantum than other things so I think there's like of course it's easy to say like everything needs to postquantum today. I think having a slightly more fine grained view of like this is the absolute number one highest priority

right now and this is like priority like 20 I think is useful and I I think that DKGs are not necessarily priority one >> at this point. I guess they have not been used in like very high critical areas, but like if if it got leaked or wouldn't it be actually quite dangerous? Like you'd be able to say you were able to break it and this is about signatures that you'd be using in a multi-arty and like a multi-IG yes context. You could fake three out of five and then you could sign things. I mean these are like these bridge hacks or socially engineered versions of that, right?

>> You're totally right. Uh I think that it's it's so first of all you know like the question is basically what's the exact scenario. I think for example if like if the only worry is that the three out of five security degrades to one out of five security that might still be okay right like maybe it's like >> three people in the company like you know three signers for wallet and like you know then it's like a defense and depth thing. I'm hoping that each one of them is honest, but like it's it's not great, but like it's it's better.

>> Like the attacker would still have to come from the inside. Is that sort of what you're saying? >> The the the calls coming from inside the building, right? Like >> Okay. >> Of course, you're right though. You have to be very very careful with these fine grain things because if I'm posting my messages, you know, on some public blockchain for anyone to see, right? Like doing the DKG, I'm sending messages, right? Right. And I said, I'm sending them over email. I could also send them post them on a blockchain. If they're posted on the blockchain, then you're right. Anybody could attack them and anybody who can see all of the messages can can recover the secret.

>> Oh, but you need a quantum computer potentially. So, whatever. >> You need a quantum computer, right? Like it's it's always a quantum computer. So, it's a it's a I think like I guess the only point that I was trying to make is that I'm less worried about shortlived things, >> you know, like where it's like, okay, just us communicating and small group than I am about something that's like potentially going to stay there for a long long time, used for a long long time on a public blockchain, everybody can see it. >> Yeah, that's that's yeah, that was my only point.

>> Yeah, that that's a good point. When you say shortlived things, it could also be a scenario where you use this for let's say to encrypt something and that this the cipher text gets opened anyway after a minute or something. Let's say an auction >> then maybe you can have some flexibility in those scenarios. >> Yeah, exactly. Like auctions, you know, this this has been very much proposed for >> validator stuff. >> Exactly. Front running protection. there. It's like, yeah, it's just like, >> you know, maybe this is more term and it's okay, but obviously like the the >> depends >> the defense in that and you know, like the goal would be to to build a a postquantum version of this and

hopefully, you know, some of the ideas carry over. >> Okay, let's shift gears a bit. So Benedict, you've done some very interesting recent work called Flock that's also in the hashbased realm. Can you tell us about that a bit? >> Yeah, so uh you know I I sent you guys a draft of the paper, we just submitted it and I hope I I by the time that this podcast come out, it's it's hopefully on on >> fingers crossed >> on your print. No, this time for real. >> It should be in the next CK Mash 2 then probably. Okay.

>> Um, so what is flock? So it's a it's a joint work with Ron Rothblum from Succinct and William Wang who's my PhD student here at NYU. And it's basically the the high level story is that we were you know we come more from a like a bit more from an academic theoretic side and we were like okay what is the fastest proof system that we can design? We actually started out with what are the theoretical limits for how fast a proof system can be? And the first question is how do you measure that? And really, you know, what we were thinking is like

well, okay, my CPU here, I have like a Mac Mini here, my CPU can do X gigahertz, but really, you know, you can think about some computation like it can do this much computation per second. How much computation can I prove? >> Like uh you know is it >> a million times slower? Is it 10,000 times slower? Is it a thousand times slower? You know like how much slower is proving on kind of same hardware than computing? Sort of a real like apples to apples comparison. And we first wanted to do theoretical work on it and we might still very much do that where we you know really go down into the numbers and and are like here you know what's the overhead of a so-called boolean

circuit but then we also like you know started to play around and and you know full credit to like coding agents and we're like hey actually we have some ideas here that that they this looks not just theoretical this looks really really practical let's try to implement this >> let's do another real world impact. Yeah, let's have another real world impact. Exactly. Well, and like you know, normally it's kind of the other way around. You first write the theory paper and then you write the practice. >> Yeah. >> Yeah. It was it's been amazing. And and kind of the end result sort of what did we measure? We were like, okay, what's the benchmark in the real world? So the benchmark in the real world, we were like, let's take a hash function, but not one of these hash functions that is, you know, designed to be fast for

snarks. Let's take like a real world hash function like Shaw 256 Blake Ketchuk you know that is designed to run fast on these hardware machines and see how fast can we prove it and kind of the headline number that we ended up getting I can talk a little bit more about the techniques that we used but is that sort of we are able to prove things about like 250 times like the overhead of proving is 250x so this is a single thread like it's really like a single CPU core comparison. So it's not like 20. You sometimes see these numbers and then it's run on like 200 GPUs. No, it's like a single core on this machine is like 250 times slower than CPU. This I

think it's very low. If you're maybe new to the field, it seems high. But you know what this also means is that if you want to prove as fast as you're computing, you're basically kn 250x parallelism. I think that's sort of the the the flip side of the equation. Mhm. >> Or you need sort of more structure in your computation that you can take advantage of. But yeah, our goal here was to build something that's super super super fast for this. And and another way to look at the results. So Vitalik had this blog post a couple years ago like 2024 where he said like okay what is needed for postquantum transition for Ethereum and he did some back of the envelope math and he said

okay we need to prove about 200,000 hashes per second and he was like with you know Poseidon that's possible you know like that's probably possible we probably can get there maybe some more improvements and so with Poseidon we were already there The problem with Prooseidon and these other hash functions is I like Googled you know writing this paper I googled like Prooseidon on e-rint you can like filter by attack paper and filter by Prooseidon and let me let me do it again I think there were like if I do this right now I find 12 papers right okay and you know a lot of them recently >> is that almost like there's 12 trip

wires that you have to be careful not to accidentally I think it's it's very much similar to what we talked about earlier with homorphism is that Poseidon inherently has more structure, right? It is, you know, designed to have structure so that we can prove it faster. But the same structure then can be used to at least attack it or weaken it. >> Huh. >> Right? So you know there's always in cryptography kind of this trade-off between structure which is useful and structure which is you know dangerous and can be exploited.

So you know the simplest way what would be great is if we didn't have to use Poseidon if we could use a hash function that has less structure that's more you know well tested and what we showed with flock is that we could prove I think this was on you know like Ron's M4 laptop you know on like a powerful consumer laptop we could prove like 500 or 600 yeah almost 600 blad per second. Um, so well above kind of the target that Vitalic set out. So what this means is now Ethereum just from like a pure proving speed perspective they wouldn't

like they could you know not maybe if they want to they don't have to rely on Poseidon they could re rely on Blake free which has much less structure and is much more standard >> uh and is also much faster in you know like sort of as a as a pure hash function on a CPU. So I think that's that's kind of that's fairly exciting. >> Yeah. And like hashes are everywhere. So there is one aspect of using these hashes like you said that are fast on CPUs. You know, Poseidon like it's awesome. It's also a bit slower on CPUs even though it's fast improving. But yeah, like hashes are everywhere.

They're in like state access and if you move something like Ethereum to be postquantum, they're going to be in signatures as well. So basically it's everywhere in recursive proofs. So having fast proving for hashes is really great. I I'll say two things to this. So one thing you know we we estimated kind of uh again talking about postquantum you know as you mentioned Kobe there's a lot of interest in moving to hashbased signatures both actually in Ethereum but also in Bitcoin.

>> Mhm. And so we kind of estimated that in Ethereum, you know, if they let's say they use Blake 3, then, you know, we could prove about what was it 3,500 transactions per second on a consumer level. >> So, uh, you know, which more than satisfies throughput or, you know, for for Bitcoin, you would imagine that they want to stick with Bitcoin is very conservative. So, they want to stick with things that they already use. So they would want to stick with SH 256 and for that you know we can prove basically a Bitcoin block which has like 5,000 signatures. So just the hashing in that block if it was all hashbased signatures

we could you know prove that in one and a half seconds on consumer hardware. So it's it's I really hope that this and and you know work and and followup really is like a real big stepping stone in like showing that fast proving and fast proving for hashbased signatures is like really feasible and that maybe we don't have to use these like it it really opens up the choice to use standard hashes and not these these customly designed hashes. I'm trying to place flock though in the like what is it comparable to? What would it potentially replace because from what you said it's sort of like it's just a

lot of hashes, right? >> So, so this is the target that we're proving. I think from a techniques point of view it is fairly similar and it builds on techniques from things like beers. >> Okay. >> So, it also is over binary fields. you know it it turns out that binary fields are very good for emulating like this these native computations. So one thing sort of the the the big I guess caveat or or you know sort of the technical caveat is that flock is for proving so-called batch computations. So when you do the same thing over and over again,

>> so for example, you have one hash function and you prove it over and over again, you have many iterations of. So, you know, we can we can combine that with like kind of a you kind of have your main power thing that can prove the same computation many times and then you have a thin kind of layer for input outputs and moving things around around when you want like the output of one hash to feed as the input of another hash. Fortunately though, so this is not as you know it's not for an arbitrary computation. So it needs to be a computation that has this structure.

Fortunately though many many I would say almost all of the computation that we care about do have this structure right so signature verification it's a lot of the same hash even you know sort of uh you could you know like in in virtual machines I mean I think there's like interesting follow-up work on can we extend this to virtual machine computations but even in a virtual machine you're kind of doing the same computation the same machine step over and over again or you have like some pre-ompiles that you're doing over and over again and so so it's really tailored for these computations and we focused on kind of hashes as as sort of

the first obvious target but I do think that there will be some follow-up work by us or others on like can we you know use these techniques like can we formulate other computations in this manner in this in this batch manner because I think that it essentially simplifies the problem a lot and it makes it a lot faster. That's one key thing where we get a lot of the speed up compared to prior work. >> Are you using folding or any IVC in here at all? >> So, no, but I think it could be combined with folding.

>> Okay. >> So, you could use or at least with IVC PCD. >> This almost sounds like is this like the vanilla first version and now you're going to start experimenting with a lot of the techniques that we've been exploring. like would you be able to add lookups to this? I know it's it's maybe >> that's a very good question. So there's no lookups here yet. U so with respect to folding I think that you can absolutely so one computation that also involves a lot of hashes is proof verification. So you can build basically like recursive proofs like the system itself uses a hashbased polomial commitment. So it can prove itself relatively efficiently which is exactly

what you need in these recursive proofs and these folding techniques. So I imagine that it you know these things can be very easily or it can be extended to work with like recursive proof techniques and then you know all these things that we talked about about like you know running it on different machines running it with different people having better parallelism. I think this should all extend to this kind of work. So this is why I was saying it's kind of a tool in the toolbox. But here now we focused on you know a single even a single core on a single CPU. How fast can that one proof?

>> By the way it is a proof system. >> Mhm. >> But is it ZK? >> It is not ZK. So uh that's a very good question. Uh this is definitely also one of the open questions. uh it at least is like somewhat you know challenging to get ZK without losing performance. It's not challenging to get ZK but like you want to get ZK without losing performance. >> Yeah. >> One thing you can do again using recursive proofs >> is you can kind of wrap things in the end in some zero knowledge proof. >> And are you talking ZK in the private context here? Not >> fully private like yeah. So it's not you know I guess it's it shouldn't be allowed on this podcast. It's not ZK yet, you know. Um, but it's >> Oh, we've we've ventured out to nowhere

is >> no I I know that the the So, it is not ZK yet. That's certainly also an open problem, you know, how to do that without losing performance. But this was really, you know, the goal was really like how can we get the fastest thing out there? And and the fun thing is that you know sort of Ron and I especially Ron comes really like we've converted him from a theoretician I think he would say this himself to like you know a practitioner like Kobe >> he's coding >> yeah I mean and like you know full disclosure like we this project would not have been possible without AI like it is amazing and in multiple ways. So first of all like we in the end we looked at the verifier like at one you

know funny funny anecdote. So I think there was a long time I don't know if a single line of code here was human written like it's just all AI written but it's not a you know it's not a like hey claude please implement this. It's like a very much an iterative process of like hey please benchmark this thing. Wait, this should be faster. Let's work on this. Like, hey, no, this should be faster. Like, let's, you know, here's some idea. >> Sounds like echoes of you working with your dev team. Actually, >> it's it's exactly that, right? Like, it's like, you know, I think it can really leverage someone, you know, I claim we have a pretty good algorithmic understanding of how the protocol should work and, you know, now we can translate that. It it kind of Yeah, it takes away the boring part of coding and and, you

know, does like you can only do the the very fun parts of it. But so so that was a huge aspect. But one thing that's also kind of a fun anecdote we were obviously that at some point we were like what if the AI is completely fooling us right like what if >> you know what if none of this is real. Uh so the beauty of zero knowledge proofs is that like okay there were you know couple thousand I don't know a lot of code written and we're like wait we can't look at all of this but we only had to look at the verifier like we don't actually care what the prover looks like as long as the verifier is correctly implemented the system is secure right this is like the whole

property of zero knowledge proofs or snarks is that all you need to trust is that the verifier is correct and secure. So we then like, you know, more manually looked at the verifier and made sure that we're not being fooled and and this is real and and it's also like and it it makes sense, you know, where the improvements come from. Let's say compared to Benius, we're like six to 12 times faster like, you know, six times faster compared to Plunky. Similarly, it really depends. So yeah, it sort of made sense, you know, where these improvements came from and and but yeah, what we did is we just looked at the verifier, which is kind of a funny anecdote of of zero knowledge proofs and AI.

>> Yeah, I think that's a great way to use AI and like I it matches my experience as well and as long as you have a good anchor like you said, you audit a verifier or maybe you have a slow proven implementation that produces the same hash or something like that. So as long as you have an anchor that becomes a really powerful loop that you can run. So yeah, I think that's a great way to use that. Yeah, you you can you can do a lot that that's awesome. >> Yeah, I mean this is like this project I don't know six engineers have a year or something like this like it's just like >> what it would have taken. How long did it take you?

>> I mean really like we've been thinking about these ideas and we've we've had a prior work called Tensor Switch. So we've been think a lot in this direction. I think Ron had been working with Kovi on like a very fast codebased thing called build like essentially like a month or two like it's it's really you know very very fast like from you know like starting to implement to basically making this a reality. So yeah it's been kind of very very fast but very fun.

>> You just mentioned Bolt. Did you use this in this project? And actually, can you describe what it is? Because Kobe, you're >> one of the co-creators of this, so maybe we should talk about it. >> Uh, I mean, I can describe it in a sentence, but but yeah, Bold really wanted to achieve really fast proving time, especially on the target machines that we used, which were consumer hardware. It was like a Mac Mini, an M4. And that's something that we've been able to achieve using special kinds of code like expander combination with uh read solmon and there we using a few different components. So some of the code or a lot

of the code have been optimized by AI. We had this like nice anchors that we could target which was cool. And actually we're using one of Benedict's paper as well. uh for sum of both. >> Which one? >> One that we haven't gotten to talk to you about yet and maybe we should which is called malperm >> which is about permutation arguments. >> What is the mole? Is it multiple permutation? Okay. Okay. Malperm. >> Yeah. >> We have a biperm. Uh >> okay. >> Yeah.

>> UniMerm. >> UniMerm. You shouldn't use uni isn't good but perm exists but it's not good. Okay. >> Yeah. Yeah. Yeah. But my understanding is that this group's use of the code that we created was not too big like it was pretty minimal. It was using an implementation of the liarto polinomial commitment scheme. >> Yeah. So we used the liorto. So we haven't like for let's just sticking with flock. So we we are just using kind of standard read solomon code. We haven't used bold yet. I definitely think that it can help. There's some kind of tricky challenges with it. I

think bold works from a technical point of view. bold works best over like uh GF2 to the 32 or something like this and we needed to work >> over exactly GF2 and sort of there's like a small technical hurdle >> that you know we need to overcome >> but yeah this could definitely you know speed up like we're using the gorito from Kobe so we're using you know a lot of techniques there we're not quite using bolt yet there's a technical ho to overcome I think it is overcomeable um surmountable I guess is the real English word and yeah definitely interesting to see sort of how much

extra bang that could give us. >> Yeah I I'll just give a shout out to Andrea which is like the Lily Heroid guy and >> most of the credit belongs to him >> and GMO. Oh yes I mean in the vault aspect but yes GMO and Andrea >> you just mentioned malleperm going back to that what what is so we said this is mult multiple permutation arguments or multi-permutation arguments >> no I guess I don't I don't know if it has a is it really an acronym >> it's really this idea so permutation arguments and you know lookup arguments they're very very related it turns about >> what? Wait, let's let's define

permutation arguments. Lookup arguments are really I mean I that's very clear to me. I actually don't have when you say it it doesn't I don't exactly know what that means. >> So permutation argument proves that you know I have a a list and and I prove that basically you know let's say the first input is the same as the third input. >> Okay >> and the fourth is the same as the seventh or something like that. So why is this useful? Why why would I care? Well, one of the key applications is that if I want to prove an arithmetic circuit, so this is a bunch of additions and multiplications, then I want to prove that each multiplication gate is correct, right? So I prove that left input times right input is equal to

output. I can do the same for the addition gate. But that's not enough, right? Because I also need to prove the wiring. So what do I need to prove for the wiring? Well, I need to prove that the output of the first gate is the let's say left input for the second gate >> or that the you know whatever like the third the the the left input for the fifth and sixth gate are exactly the same. So this is what we use the permutation argument for. >> Is this like a test like because of that characteristic of the first and the third being the same or the second and the fourth being the same or whatever like are you then using that characteristic to test the system?

>> Yeah. Basically, so you're you're proving that basically if I shuffle things around, right, if I swap the first and the third and I swap the fourth and the things, I still get the same thing. That's why it's a permutation argument. It's like I permute it. >> Yeah. >> And then I see whether uh the I get the same list and if I do that's exactly the test then yes this sort of the wiring is correct. So it is exactly a test. >> Interesting. Yeah. Yeah. So that's what people call like copy constraints let's say in plon where that's how they basically can carry computation over a long like a long period.

>> So then what's mole perm? So, Moperm, it's funnily enough, this started actually as like nobody really knows this, but we wrote in Hyperplunk, we had like one subsection um you know like oh can you do this permutation argument with basically the question is can you do a permutation argument with just a sum check like uh you know can you do it with with a sum check >> and I think basically Aleza uh asked us this as a question like hey oh this looks really cool but like you know we use some other permutation argument something that's more plunk inspired and

from like a paper called quirks and he was like wait could you just do like everything else in hyperplunk uses some checks could you do this step also using sound checks >> um it also has some other benefits like you need to commit to less data and you know it has better soundness so we then like Vinnie and I then wrote this this up in like a subsection of hyperplong I think after the paper was published like nobody noticed maybe and nobody cared but that's okay and and then you know fast forward I I had sort of this in the back of my mind sort of I was talking about it with Jessica and my student and and we also got Zach another student here involved and then we basically improved this original idea from

hyperlon a lot and it's a permutation argument that can also be used as a lookup argument that uses a sum check you know that's sort of like solely based on a sum check which makes it I guess the hope is that it makes it more lightweight it's actually you can view twist and shout which are these papers by by Sina and and Justin >> you can view them as they're basically the biperm version of of merm and so so so it's just some check based and it has nice properties in that it works very well over smaller fields and and just some checks and some checks are

fast and good and so that's that's kind of the short summary of malper >> nice for some reason as you described this the permutation arguments can also be used in lookup tables lookup arguments using some check I started to be like we should make zk proving systems bingo with all of these techniques and like when they appear I don't know how this game actually would work. But it's just so it's so interesting to see these techniques kind of reemerge. It's like I love that I love it when like a new one gets invented or like not even invented. It's usually like gets described like it's already there somewhere but we don't know why it works exactly. we haven't like analyzed it and

then someone pulls it out and then it starts >> and I think there's a lot of value in in the end you can always be like oh you know this was kind of like it's kind of the same like x and kind of the same like y and you know and in the end it's all polomials and you know whatever right it's all the same but I think there's like tremendous value in you know as you said pulling things out cleanly describing them you know saying like oh this is you propose a name we should call it this technique and you know this is what it does and I think that this is absolutely even if it's similar to something that happened before it's absolutely not to be dismissed and you know now has a has a

lot of value and and I think that's that's great >> by the way I just you just said it's very funny in our last episode with Wyatt Beno he actually quoted you he he just said I want to call out Benedict for this little piece of advice advice that he gave me at an event one time which was he asked you what are the key things about ZK and you answered it's just polomial evaluations >> which is funny we got almost that quote again very cool >> it's still true >> but but not true apparently but more new ones this time >> slightly slightly more >> that's funny cool so I want to say thank you Benedict for doing this interview with us thank you for updating us on all

of this work. I feel like we haven't really covered all of it. I know that there are other lines of work that we didn't get to. We kind of ran out of time, but I also want to thank you for defining some of these things that we do use often on the show. Yeah, just kind of outlining them. It's helped me at least to understand some of this work a little bit deeper. So, thank you for that. >> Yeah, thanks for having me. >> Yeah, thanks Benedict. Uh, like we said, we you've done a bunch of impactful work and it's always a pleasure to to keep up and you're doing also a lot of work. So, I'm sure that there are a bunch of things we haven't covered as well. Maybe next time.

>> Yeah. >> Yeah. I would love to be back. Thank you. >> All right. I want to say thank you to the podcast team, Rachel, Henrik, Tanya, and Hector, and to our listeners. Thanks for listening.