Episode 349 - ZODA & The Accidental Computer

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact [Music] online this week I chat with my co- host Nico and GMO as well as Alex Evans all three of whom are working at Bane Capital crypto with Nico having joined the firm quite recently in this conversation we revisit the concept of Da or data availability we talk about

how works like Freda helped Nico gon Alex to explore systems that mimic some of the characteristics of fry and could be used in a DA context this has led to their work entitled Zoda standing for zero overhead data availability and we spend the first portion of the episode talking about that work Nico then becomes my co-host partway through and we interview Alex and GMO about their work called accidental computer it was really fun to get this group back together again hope you enjoy it I want to make a quick note about disclosures you may have noticed that at the beginning of certain episodes I'll let you know if I have some relationship or connection to a project that we're interviewing in this case I do have a disclosure I am an adviser to Bane

Capital crypto as we just launched our new website I have been able to include A disclosures page for myself in there you can find Investments that I've made as an angel advisory roles that I've taken as well as a link to the zkv website where you can find Investments that I've made through zkv you can find all of that over on the website zeron knowledge. fm/ disclosures and we've added the link in the show notes now before we kick off I just want to share a little bit about the next ZK Summit it's happening in Toronto on May 12th applications to attend just opened space is more limited than usual this time around as our venue caps out at around 400 so we are encouraging people who really want to join to get their spot secured early it is invite only and we

do prioritize previous attendees and long-term members of the ZK community so if you're newer and you really want to join just aim to apply early for a better chance of getting a spot the application to speak can be found in the same form the deadline to apply to speak is March 15th for more info check out ZK summit.com we've also added the link in the show now here's our episode on Zoda and The Accidental [Music] computer today I'm here with two of my co-hosts Nico and GMO and my friend Alex Evans hey everyone welcome back to the show what's up hey good to be back hello hello I'm very excited to catch up with all of you and very excited to dig into

the work that you have all been doing together we're going to start this episode a little bit with like how did this work come about how did you working together actually come about and then we'll dive into two specific Works one's called Zoda and one is called accidental computer that's very good I'm so glad that name caught on honestly it's so good so GMO back in the end of your episode you actually had started to explain Zoda um but that was like a jam-packed episode and we didn't get a chance to really dig into it so probably for the better well well also yeah I guess now time has passed

you'll you maybe can even like contextualize it better I think it was quite fresh when we recorded that um yeah let's let's go back to the beginning of this like where first of all where did the spark for This research come from and all three of you are the co-authors of this work so yeah how did this start so very early on the first Tinder of an idea started I had introduced risk zero which is a team that we work with at BCC to Celestia because Celestia was looking into outsourc provs for inclusion into their data availability construction and also looking at proving the correctness of the encoding as well as other things and so it was more of an informal conversation between a couple technical

teams and I remember somebody at Celestia I think it was Jacob arlock messaged me saying wow I didn't realize that we were using a lot of the same techniques under the hood in other words read Solomon encoding some things and hashing some things and I yeah that is actually quite interesting these are seemingly unrelated things but they're using some similar techniques that seem somewhat Universal but that was years ago and I filed it under mildly interesting so there was a Tinder there this was what 22 this would have been 22 maybe 23 maybe early 2023 so it was just filed under there I think maybe G you and I spoke about it briefly and just it was kind of funny but really where that started to become more of a an ember if not a flame was we at BCC were having a

conversation which with with what was then the geometry research team Kobe Nico Andrea way J gersa and we were just jamming on like what would it like should we work together let's explore this what's the idea here we share a lot of similar interests similar ethos and we like each other we hang out including on this pod and the various conferences so what would it mean like could we could we combine forces here would it be a disastrously terrible a or great idea so we're like okay first thing we should do is we just get together and like talk about what everybody's working on and so we go through the list we talk about some things we're working on really captured our attention was Nico had done a lot of work including actually with

rero and others on Fry and I can let him talk about that briefly but the thing that caught my eye was he was looking at this protocol called Freda that had been recently published and he was talking about essentially a couple optimizations on it that he was working and that idea that G and I had filed away somewhere in a Dusty cabinet resurfaced in that so I'll let him talk about what he was looking at cuz that was the impetus for us to look more closely into this yeah Nico what were you working on then yeah so back then with r zero we were trying to get like a a soundness calculator inside like their protocol so like you would set your parameters to run R zero and see like how secure you are and

that's great but that sort of forced us to really go into like the security analysis of fry and at the same time there's this Freda paper that comes out that says like hey you can use fry to do data availability that's quite surprising and really cool and they go further and they say you can use sort of any IOP of proximity I just sorry I just looked at fry for da Freda got it okay it's a very cute name yeah that's good there is a footnote in the paper that says this paper is named after one of the singers in ABA and has nothing to do with the fact that we do fry for da so you can take it up with them okay who who who published that work so this

is work by Matas Hal Anderson Mark simkin and Benedict Vagner which groups is that coming out of uh it's a mix of the ethereum foundation and then uh Matas I think works at ZK security oh cool and Mark at the time was I think a postdoc at arus so super interesting work and there's restrictions they have definitions of like criteria of what ipps you can use and their criteria a bit odd uh or not like standard compared to what we know they also say like we can only work for very uh restricted parameter regimes and so part of the work I've been doing since then is clear up these criteria and extend to wider parameter regimes and that translates to

like 2 3x efficiency gains and so I was chatting about this to a and guo and we're talking about this construction and they're saying like why is everyone on this network every light note downloading the same thing this feels wrong on which network on risk zero or on Celestia yes which one yeah so the work Freda is a followup to another paper called foundations of data availability sampling same three authors and here they're trying to take a cryptographers look at what is Da okay so if I was a cryptographer how would I model the setting we're in for da uh and what are the security properties I want that's interesting just okay one sec

before you continue here because like was Da coined by conceived of more like an engineering side of things and now research was trying to codify it is that sort of what you're saying so da was described more as a distributed systems thing we have a lot of computers they're all connected some of these are strong some of these are weak mhm the weak ones want to know that they can download data without downloading it yeah and it's purely like and that's the data availability the you're sampling to see that the data is there but you're not actually getting the whole data taking all of it and yeah and so for them they described it as a distributed systems problem like okay these computers are connected how should they behave and

given these sets of behaviors what guarantees do we get a cryptographer would say like all right there are no computers whatsoever there are these idealized parties they have access to magical Oracles in the sky they want to query these oracles and output a bit zero or one zero being I think you're lying to me one being I think the data is available and the cryptographer wants to know what's the probability of outputting one when the data was not available okay so we have da we have two ways of describing it and in cryptography land this is how it was described foundations of Das paper okay and then they say well what you can do is you run fry as if you were doing a

snark so many rep of the Fright protocol and one of these repetitions you actually pick a piece of data you want to know whether or not it's available and so what ends up happening is all these light nodes will download the same you know 49 repetitions and everyone downloads a 50th that's slightly different H I don't know if I follow this I I I can make a bit of an addition here so in data availability one way to look at it is just mechanically what is happening M so what happens is we have some data possibly a lot of data that any small computer shouldn't be required to download but ideally all computers should know that they could in principle

download it so mechanically what we do is we'll take that data and we'll create some redundancy using an eraser code or an air correcting code yeah and then we will have people sample components of that redundant encoding of the data okay and if enough of them sample that thing randomly then across all of them just by talking to each other and nobody else they can decode the original data just by coordinating with each other in order for this to be secure we need two things to be true one we need the encoding to have been done correctly because if I create fake redundancy or I create a

bunch of junk no matter how many people sample that thing we won't be able to recover anything certainly not anything meaningful or consistent the second thing we need is of course enough people in the case of data availability systems these are called light nodes or like clients actually physically sampling the data such that we can Define security collectively over that number of individual sampling what's happening often times is that that latter set of folks Works actually almost universally in the interactive setting right there's no way to non-interactively prove that data is is available you need to actively go out and Sample for yourself yeah so what Nico and we were observing

was we were downloading a bunch of samples of this data symbols from that redundant encoding non-interactively yeah and we were downloading maybe one additional one interactively okay what was happening in this framework was that let's say the four of us wanted to download sort of among the four of us ensure that between us we have enough enough of the underlying data to be able to reconstruct it so we each download a snark and then we each download a little bit of additional random data and the snark between the four of us we're downloading the same thing so we're not really learning any new information across the four of us we're each

learning the same thing okay so the core Insight or at least original idea of this was could each of us instead of downloading the snark download interactively a couple of unrelated components and the question is can we do that in a way that's secure and if we do it what are the efficiency gains if I download different data from you but get the same guarantees that I would have gotten under a non-interactive construction now I'm a little stuck again though because you mentioned like Nico you talked about like multiple instances of fry and then one fry that's different for people Alex you've talked about like a piece of Randomness that's

different for people is it the same I see G pointing a lot he wants to say something G wants to say something yes the answer is they are the same thing um indeed Nico was talking about you run fry and then you'd run one more instance of fry where you randomly pick Alex is talking about just forget fry Fri is useful but otherwise kind of like you know just it's useful for guaranteeing that the things you got are correct but it is otherwise you're just collecting pieces of data Maybe the like even simpler version of it is like imagine you have like you need to collect like 50% of coupons so you have like 100 things you need to collect 50 of them to you know reconstruct the original data remember that Alex mentioned these

things were rly encoded what that means is that you instead of needing to get everything to rec to have the piece of data which you would have to do if you didn't do this encoding you can instead do this redundant thing such that if you have 50% of the all the data that is good enough and then do you that over and over and over again so that you need less like 50% time 50% time 50 like do you kind of get to like no well so not not yet so you need the 50% to recover the data um but the the difference is I don't know if you remember what like Alex and Nico were saying was like hey you know what you what people do in this Frida setting or in this Foundation setting is they download the same like think about it as like little boxes

right they download the same like 49 boxes and then pick a random new one okay right or let's say it's fewer than that let say download the same five boxes and then pick a sixth one that is a random one right obviously it's going to take way more people to sample 50 distinct boxes if we do that than if everybody samples six unique boxes every time so that was the observation the observation is like why are we doing everybody down in the same five boxes out of you know 50 that we need and then down in one new one instead of being like cool like we could just download all like whatever boxes we want we just need to download Enough of collectively and just have any of them do that huh here's a very silly way to look at it let's say we each Download 50 50 boxes

between the four of us so in total there's let's say we get lucky and the four the distinct one that we each download is indeed distinct we don't fall on the same one by accident in here Theory here we can't coordinate so sometimes we get unlucky and we download so we have different information we have different box in the current construction or at least the construction that we looked at originally all the 50 box so we would Download 50 boxes each yeah and let's say we each downloaded one novel box each yeah right so across the four of us we would only learn of call it 54 unique boxes across the four of us despite the fact that we collectively right downloaded 200 h by the way are these

still like samples from a larger set let's say there's 400 in total and we need to get any 200 it doesn't matter which specific 200 but any 200 or so would suffice to recover the original data got it now we want to be able to Across the four of us efficiently get to 200 right let's say we can coordinate here for the sake of argument so we know that I sample this so you don't sample the same thing in the current construction we would download let's say 49 of the same stuff and then we would get a couple more so we get to whatever that is 53 or whatever the right number is right so we would have each download collectively download downed 200 so we had enough bandwidth to download full 200 that we need but we actually are

quite a way off from our goal because of this inefficiency now if instead each downloaded 50 distinct ones we actually could get there if we were to cordinate and of course there's a little bit of luck involved and practical protocols so it turns out that just by doing this by just doing our queries interactively which again we assume that nodes are interactive in the case of Da because we can't prove da non-interactively just by aaging that existing assumption we've created a much more efficient Network so the first paper we put out or at least note that we put out on our blog at BCC was just how far can you take this idea and what's the efficiency and it turns out depending on what the protocol is it could be 10 times more efficient to 100 times more efficient I love how every time we explain this we sort of

auctioned up the number of boxes you're like all right let's start you need to get 50 boxes no no you need to get 200 boxes yeah yeah okay so in total though there's 400 you need to get 200 yes in order to get get to to be able to kind of guarantee that you're doing this correctly and the question here is do you each do the same 50 or you do different 50s because if you each did 50 you're only getting what is it like uh 1/8 of the entirety you're not actually getting to that halfway mark which is what you're aiming for but all of yeah that's that's right like if everybody does the same 50 you're always doing 1/8 right exactly okay so you're always screwed there I mean you have you can do

a extra but you need a lot more people that are doing this little extra in reality everyone would be doing 200 I guess or two like 199 right like before the fix you would have been doing more or you just would have had less good security before the fix everyone would do 50 okay and one extra and we would need way more than four people to cover the whole 200 oh I see but you would all do the same 50 all the time or would you all the time and that's what Alex refers to as the snark and that's what I refer to as the same fry and then do one different fry okay I mean I'm learning a little bit even more about da here too like I haven't visited this topic in a little

while and I didn't know how it was built on that like numbers level interesting so there's two observations here the first observation is that we must in the data availability setting work in the interactive model normally in snarks we actually start there and then move to the non-interactive itive model through things like Fiat Shamir the second observation is that we need to Define security collectively no one node has enough bandwidth to download in this case our example all 200 symbols or we wouldn't be doing data availability to begin with so we need to Define security across let's say in our example on our call Four nodes here Each of which ideally download something like 50

symbols maybe a little bit more because again we could get unlucky and if we don't coordinate fallowing the same symbols mhm so leveraging those two observations and that we're already in this setting could we create a more efficient protocol so that was the first exploration that we did yeah and this is a blog post we have uh sampling for proximity and availability and the key idea of that blog post is somewhat cute which is if you look at what we described earlier with how mechanically data availability protocols work they take some data they encode it they hash it and then people open up components of that data and if the network successfully responds to their quick iies they accept and if enough people accept let's say all four of us accept then with some probability we will have

recovered the original data which is hopefully a high probability and then you look at how something like fry works well what do you do you take some data you encode it you hash it and then people sample that and if the network successfully responds to their queries and the verifications pass we accept and it turns out that this idea of sampling which we do for proximity in the case of fry and sampling which we do for availability in the case of Da protocols look almost identical H and you mentioned using fry but like is fry interactive naturally is that like one of the characteristics of fry is that why you used it so usually like many sync proofs are defined first

interactively and then made non- interactive so actually almost every you know Prov proximity check or whatever you want to call them like uh usually starts out in the interactive setting and then we use like fun tricks like the F trick yeah uh to like make them unattractive so um but it's it's funny it's like it's like we're like going back into the cave right like normally it's like we start in the cave and then we like go out and make the thing non interactive because we want a short proof of the thing but now it's like no no no wait wait like we we shouldn't do that stay yeah like like we stay interactive exactly exactly or even make it interative the reason we looked at fry in the first place or the Freda paper looked at fry in the first place is because as Alex was saying say when

you do da you have to encode like put in redundancy and then people download and they need to check was the redundancy put in correctly so this is why these tests of proximity as G mentioned like fry like learo are interesting because that's literally what they do they check that something was encoded correctly but like kind of going back to that initial question like is fry always interactive or is it just like can be interactive or it's optional it's described as interactive at first okay okay it turns out most of the time we want a non-interactive version of it we want like a short proof so we use it in a not like we'll we'll do something to it fere in order for it to be non-interactive like in every way that we talk about it

on the show I'm assuming it's like used off or not in every way but in most cases it's used in a non-interactive way yeah I think the only case where it is used somewhat interactively is when people have been trying to do proofs on bitcoin and then they spread the proofs across different blocks and use like interaction in that oh okay but we're bringing interaction back baby it's becoming cool again let's go that's this whole bit so interaction in our case actually is a superpower because we already have we already have a very large number possibly upwards of thousands or millions of nodes that are querying interactively so we already have them they're just kind of sitting there ready to query interactively and

instead we give them this non-interactive proof but if we actually let them do their thing of qu quing non- interactively we get very significantly more efficient protocols quering interactively you had a little slip there yeah of quering interactively interactively correct I stand I stand corrective so the other thing by the way that we don't even get to that much is actually and this is an an episode that you ge you Anna GMO and Justin Taylor did is that the interactive setting is actually a little bit better in many cases because it is a bit more secure we lose a little bit of security often times in going from an interactive protocol to a non-interactive protocol this is a benefit we don't really explore much in our work but actually is true and that by going to the interactive setting we often times don't even lose that much security though we

should talk about some of the constructions and so forth because the definitions make it a little bit tricky but often times in the snark setting the interactive protocol is typically considered more secure actually and I don't know Nico was it with you that we did the nethermind interview I don't know if you were the co-host on that one nope I don't know who I did that with but I had them on and they talked about that I think it was like the danger like or the F Shamir affecting the security of of fry so I I'll try to dig that episode up because that was all about exactly this this issue interesting okay so I think we've done some good background on da on Fry thanks and on just interactive fry or an interactive is it a interactive proof was that right to say or an interactive proof let's

move on to like Zoda what is this an extension on this observation is it an extra build like what is this work yes so it is an extension MH but I I think I've actually had this rant on the show and I believe it was at leased with Justin theor but also maybe another cases which is historically for succinct proofs or ZK systems or everything like that right we're focused on proving like General things right like our life revolves around being able to like prove arbitrary computation and one of the questions I posed repeatedly is are there useful important and interesting computations oh yes for which proving is very cheap

so normally when we do like a standard computation like a bunch of work has to go from turning that computation into like a proof right and that work is like thousands if not tens of thousands if not sometimes even hundreds of thousands more work than it is to do the computation you want to do in the first place like right which is like you know something simple whatever you know it might be checking a bunch of stuff or whatever so one of the things that like repeatedly comes up on this is okay but you know there's a bunch of stuff like we don't just like do General computation like life isn't just like a general computation like life isn't just like an arbitrary computer program right like we do a lot of very common things a lot all the time so can we come up with

very good very fast very efficient specialized proving systems for these specific types of operations that and and specifically when I say like very good very fast and specific I mean essentially and the coolest thing would be can we do it in such a way that proving the thing costs no more or only like negligibly more than having done the computation itself and number two that it also means that you don't have to transmit any more data right like you can just give the original thing that you were going to give to the person that's good enough H what are you trying to make smaller here though like the computation to prove or the thing itself so both I'm trying to make smaller the amount of computation necessary to prove

the thing right ideally you to to like compute the thing you have to actually compute the result right the question is can you ALS can you not only compute the result but also prove that the result was computed correctly in roughly about the same time like with no additional computational time spent doing this latter step right normally the this latter step this lad step of taking a computation and proving its correctness is often like a thousand to 10,000 times more expensive than the computation so question can we do it with nearly zero difference right you need to prove that the computation was done correctly which requires a lot of work and then you need to give somebody a proof that proves to them that the result that

they're getting is the right result that's right so could you just download the result yeah and do the computation can the proof be as quick like how close to Computing the underlying thing can you make the proof and how close to just receiving the result can the proof size be that's right would you call these things overhead and say that you have zero overhead per chance by chance so yeah so if such a thing were happened to be magically possible one natural name for it would be a zero overhead thing right in other words doing the computation and doing the computation in a way that is provable like gives you zero overhead over the original thing it's like zero a

zero overhead operation so the starting point for this was fry which was pretty close so if we looked at Freda which we just described it was quite close in other words if you look at what you're doing in the da protocol you're encoding and hashing again you're looking at what you're doing in Fry which is the proof of encoding is your encoding and hashing so you sort of merge these two things but fry also requires and we don't need to get super deep into this the audience that'll be familiar with fry will will know what I mean when I say this there's a couple of intermediate folds that you have to do for fry that everybody needs to download that present overhead in other words the four of us each downloading those folds just tells us something about the

correctness of the original computation but nothing really about the data itself it doesn't help us reconstruct the data and also prover needs to compute these folds it's not too much overhead but it is some overhead so the question was can we do better that's the question we started with and what ultimately led to the exploration of Zoda is do there exist can we take this idea is fry is almost there but can we take it all the way there to something that truly has as close to zero overhead in terms of compute for proving as well as proof size for receiving the result does Zoda still use fry or is it like replacing fry is it just like playing on the ideas that fry introduces or looking for characteristics that fry has and then

creating something else so yeah it's it's playing on two ideas the Freda idea and and in turn the idea from the previous paper which is foundations of data availability which is like look there seems to be a lot of similarities between these proximity style checks and the things that Celestia does anyways and you know so it's it's been on that idea and this the second idea of you know that we were talking about which is the original piece work like does this thing non- interactively we can leverage interactivity to make it a lot faster and a lot cheaper uh and then also plac on this like latter idea which is okay you know in some sense like those protocols still have this this overhead these intermediate steps that only serve

to tell you that something is done correctly but like otherwise do not serve any other additional purpose and that we call that overhead right because in some sense it is a proof that only serves to help you realize the result is correct but it is not a proof that actually tells you new points along this like you know little doesn't tell you new boxes right but how does it relate like I guess I'm still trying to figure out like are you using any part of fry just let it like are you literally replacing it completely for this case specific like you're you just like noticed a characteristic and you're like we're going to create something different but that like cuts out all that overhead that doesn't is not necessary but we'll have this one is it just the interactive characteristic did you then go looking for just like other

interactive light protocols or something like that yeah so so fry itself is like one instance but you could put many other protocols in there and this was not our realization this was a realization from the previous paper which led to Freda okay but the question now is like okay but all those protocols also still have overhead right they still have like in other words you have to kind of s the separate proof so we had to it was like a bunch of things that merge together to make kind of what we call Zoda so Zoda uses a different scheme which is not fry it is something you know maybe familiar because I rent about it a lot in the uh show called The herrow oh um and he variations on that theme specifically um so not yeah like some something that's kind of different from

what's out there but like similar in spirit same ideas so we had an episode with the Le hero team who I guess built Lee herrow that you're describing I I think some subset yeah or yeah some version of it but like maybe we should explain what that is why is that different briefly and I'll I'll try to dig up that episode too if people want to learn about that I think it's a good one too because the minute you start describing the hero you can also GMO just say that you noticed that celesti was basically doing this exact thing yes nice so Lear is a very beautiful kind of crazy simple observation it says cool I have a bunch of vectors right and these vectors are maybe encoded maybe not if I take a random linear combination of

those vectors and the result of that random linear combination is itself close to a code word in other words it's like mostly correctly encoded then it is possible to conclude that each of the individual original vectors were themselves close to a good encoding H it's like a nearly stupid I mean I would argue it's even a stupid observation I would say nearly stupid it's actually stupid is like that's exactly the work you do when you encode a square in Celestia so to construct these redundant encodings you first encode you know you take your you take your data you put it into a matrix you encode each one of

those columns mhm right and then you take a r like not a random but you take a linear combination of the rows yeah right so unfortunately you can't see me waving my hands in the how describe what you've done you've created like a you've done the The Columns you've shown the columns and then you've shown the rows y okay you're creating a little hash hashy thing yeah you creating you start with a little square you now have a bigger Square yeah and the only observation here that Zoda essentially does is instead of you know multiplying it by kind of so when you you extend in the columns and those are code words so those are like part pieces of a code if

they are correct when you extend by the rows what you're doing is you're taking not a random linear combination but you're taking a linear combination of these codes so what if we can squirrel away just a little bit of Randomness to make that linear combination actually random M and if you do that now you're good right because if that linear combination is random by definition the herrow tells you that like checking a small number of those entries is good enough and you are good and so the point is right like all we did was we changed the way we constructed this Square you know by extending down and extending right and then squirel away the like

proof quote unquote into the data itself it's like kind of the the philosophical way of thinking about it such that the proof is the data like the data itself is its own thing that carries its own proof of its correctness yeah it's messed up that's M mind it's very weird like you got to like drink something or smoke something or really like if you get can get very deep with this but the point is like it's very weird that you can construct a thing which is its own proof of its own correctness is this a characteristic of Le itself or is this something you're like as you're using bits of it you're creating something that does that is that Zoda so this is this is Zoda yeah Zoda itself so Le hero

is overhead because Le hero the point is when you take this random combination you have to actually give the verifier the output of the linear combination uh the cool part about Zoda is that it actually squirrels that proof away into the its own data okay right which is again very weird like this is like not obvious and kind of magical but you hi you hide the proof in the data in a way yes but in in such a way that the data is still useful to you right like the it's still data it's still like data that is good to help reconstruct the original piece but the proof is in the data okay but is there then a verification process to that like does how does a verifier I I don't even know if that's what you call that agent here

but like okay so how does a verifier look into this data we we call them Samplers to distinguish them from the non interactive setting but you know for fun uhhuh the idea is very simple is you know normally what you would do is you would download some rows and some columns right the only thing that you have to do here is when you download the rows and you download The Columns you just check that the linear combination that is claimed is actually correct and that's enough so instead of just downloading rows and columns you also perform this additional check that says like are these two are these columns and these rows consistent with each other with the randomness that I got and that's what the sampler AKA is looking for yep and that that's enough to guarantee if they download

Enough rows and enough columns that everything is good right when you say guarantee everything is okay here we're saying guarantee that the encoding was done correctly you still need to have enough Samplers to sample enough data to make sure that it was available yes like just to make sure what the guarantees are and just going back to celest so Celestia was doing some version of this but with a lot of overhead leara was doing was doing something else but it had overhead I basic I'm trying to figure out like is there an efficiency gain on both fronts here or are you like mimicking what Celestia already does with a new system yeah we mimic what Celestia already does and build in to what celesa did the Le hero proofs okay

you do a tiny bit more computation than Le hero this is like doing multiple Le hero proofs but it turns out that all these multiple proofs is what your Celestia sort of full Noe computed anyway so we looked at it and we we just noticed that so we we started out looking at this exploration of okay we can add interaction to a free to a fry Bas scheme to reduce the overhead substantially and then we're looking out there being like okay if we use Leo for example we had written this note on logarithmic randomus with and Leo with GMO so we're familiar with the protocol and we looked at it we're like okay just like fry this thing has a little bit of overhead and that you need to download this random linear combination and then we look at Celestia and actually they almost taking multiple of these random

linear combinations anyway indeed enough of them to be able to reconstruct the original data just from those so if we're going to be downloading these random linear combinations we might as well download different ones so that across again the four of us we might have a chance of decoding the original message just from those so we looked at it and we're like guys did you know you were running 99% of a Leo prover already Yes and their response was we have no idea what AO is that's so cool I like it when that happens like mine's kind of converging but from different places interesting yep so the only thing to make it 100% is this Randomness that guo is describing

is in the encoding process itself you weasle in this Randomness and now these columns function as themselves these proofs that you were previously getting so you needed to download those things anyway now they're also telling you something a little bit more cosmically interesting about the process of encoding Itself by the way my conclusion here is putting numbers into squares is magical yes to the point where it's too magical for human brains to understand and this is why we have le hero and Celestia doing pretty much the same thing but no one realizing that it is because it was all just so dense it's like this description of these Protocols are so dense yes we're actually just toddlers at BCC putting numbers in

little squares and yeah Square you guys make the same thing obviously naturally you know okay you keep saying something here you keep saying numbers in squares what is this like this the square is the Matrix is it this is the Matrix representation like represent your data as a matrix and then do things ons call it Square yeah yeah when it's a matrix that has like the same length on each side it's a square Matrix okay so here's maybe one way to look at the upshot which is one way that we were thinking of doing this and actually when I said I introduced rero and Celestia back in early 20 23 or at some point in 2022 whenever that

was what we were thinking of doing was Celestia was building this Square so they were encoding a bunch of they're taking this data they're putting it in a square they're encoding the rows and they're encoding The Columns and then they're hashing that whole thing and then people are coming in and requesting random entries of the square if enough of them get enough of them then the data is available MH what we were thinking of doing is taking that process and shoving it inside of a general purpose proof like R zero so what was going to happen there was we were going to arithmetization What If instead of you downloading some

samples and a proof that thing coding was done correctly the samples that you were going to download functioned themselves as proofs of their own correctness creating a more efficient protocol so we went from two encodings that we had to do and hashes that we had to do to just one that we would have had to do anyway the way to contrast this is normally again to GEOS point if we were to take let's say an optimistic role up that does a general purpose computation what happens is we need a lot of people to reexecute that computation and alert these low power nodes that some fraud has occurred often times we can take that protocol and make it into a ZK rollup let's say where one person or some set of people compute a proof and send it to everybody and that way they

know that it's correct sometimes that can have the advantage of lower latency but it requires somebody to take on this massive overhead of computation often thousands maybe even millions of times more than the original computation itself in this case going from the optimistic system which is what Celestia does today to the validity provable system does not involve any additional almost very marginal additional appr work I just wonder in the way you described this though was this like in building this do you see it as like this replaces what Celestia built or is it like now you can deploy Celestia in Risk zero EAS like easily like because you mentioned this risk Zero part of it like would you actually be using this in any way in their system now this was like

the old system right where you like take a computation you do a bunch of work to get that comput to prove the computation is good and then you like do it this is essentially cutting out all of the mechanics of compiling this computation down and proving it because what Celestia is already doing is essentially proving itself so this is the this is why it's essentially also zero overhead is like if you just do what Celestia is doing with a just one tiny change for free you get verifiability you get this ability that the data that you download itself tells you something about its own correctness yeah and we mentioned Celestia in this example just because we know their system well we work with them we're investors Riso similarly and this is where the germs of these ideas came

from but it's sort of a generic observation in that ethereum as well also creates a square of the data and codes The Columns and codes the rows in their case they use something like kg which from in terms of proof size has extremely low overhead as well so we expect this to be somewhat generic it's not a Celestial rero specific thing it's just a more General observation that encoding and hashing in some sense doesn't need to be proven as much with an external system it can carry with it its own proof without requiring a bunch of people to do too much additional work funny I'm just going back to me asking what a square is and you guys calling yourselves toddlers I start to feel like

a bit of a toddler what's a square like there's like the same size on each side by this is a technical terminology I'm actually glad I'm actually glad I asked because now you used it a lot but this is how they call it if you go through the like celester dos they call it the data square the square square the data Square well in general it is like a square Matrix is the like good terminology you know the technical term so now Nico I want you to sort of join me on the like host side of the table sounds good and I want us to interview Alex and guo GMO you today are not the host you were on the guest side of the table um you've been demoted down here with Meo I know that's right we all we all gotta like

you know remember we started sometimes um I want us to talk about accidental computer and great title maybe let's start like is accidental computer taking the Zoda idea and then like building on it or is this a different work actually I have a very leading question for you Anna which might get you to the conclusion of accidental computer okay um are you familiar with how something like plunky 2 works or plunky 3 yeah yeah so they do like I don't know not right now sitting here I'd probably have to like refresh a lot but okay I know you do because we've been through the the ZK whiteboard sessions and this kind of stuff appears okay in there for what it's worth I don't know if I know what

this does so I'm ask I'm like do you want me to explain it I don't know that I can do that just sort of you know what are the two components that we blend together to get a snark God okay uh polinomial commitment scheme and an IOP yeah amazing the things I learned in the Whiteboard sessions and then we've been saying like oh we can use kcg as our po commment scheme or we can use fry yeah yeah so here's another case where we're using fry Freda said if we're going to do fry anyway use it for da MH so now my question Anna is like could we recycle our fry like in plunky too yeah so wait you start to go back into

what is this again the the fry is the polinomial commitment scheme right so you're using the standing iops and now you're instead of fry you're using soda take it away boys this is like one of Alex's truly deranged ideas actually I did this idea come before Zoda some version of it came a little bit before Zoda because again we were using these same polom commitment schemes in both cases and we were sampling first blog post was sampling from proximity and availability the idea of what we're calling The Accidental computer is could you sample for proximity availability

and validity all in one go so given the fact that we were taking some data encoding it hashing it and sampling it that's exactly what we would do in a polinomial commitment scheme based on hashes for example friy would be one example Leo can function as a polom commitment scheme so given that we were going to do this work anyway could we indeed squirrel away not just the proof of the encoding but also more General proofs remember we said earlier that would talked to some teams and asked them if they knew they were running a Le hero prover for the proof of encoding they said no indeed they weren't just doing that it turns out they were running the prover for General

polinomial commitment scheme that could apply to much more General computations and huh we could utilize that to get more efficient snarks defined over the data that was posted to the data availability layer and that's the original exploration that we went on for this most recent work wow so the title accidental computer comes from two facts so number one is like when you construct Zoda actually it's a little bit complicated to like actually get kind of a general comp stuck in there just because of the way Zod is constructed so we use a little bit of a variation on it so the point is this this variation actually enables you to do kind of essentially construct a

polinomial commitment scheme in like a standard way but the reason we call it ACC computer is Celestia which is again the impetus for this particular work has been trying really really really hard like literally trying so hard to make sure that they don't accidentally create a general purpose computer right because that has a buch of security vulnerabilities it has a buch of like random stuff in it like that are really hard to like audit there's a bunch of mechanics around it would also make it slightly a competition to ethereum which I feel they always distinguished themselves in by by not being General computation environment like by being pure da by the way ethereum 2 in the context of the data availability layer they've created a separate system that's

not a computer for what are called the blobs we want to have the computer sort of in a separate laned Environ with its own fee markets and its own system and then separately we want to have this really dumb simple system that's not a computer TM definitely not a computer but turns out to be very close to a computer oh wow correct it is the the equivalent version which I I jokingly say is like you you started like you know by building like a like a motorcycle or like a scooter right and you accidentally built like a Lamborghini right like I don't know how that happens but the point is like you start with what seems like the dumbest possible thing it's like look man I'm taking a piece of data I am like encoding it and then I am like asking

people to take little pieces of it right if enough people collect those great like we're all happy and then all of a sudden like by literally by having accidentally done this encoding you have like essentially created an entire computer that can be used to verify arbitrary computation so this is very so this is hence the title accidental computer it's like under all of our noses like this entire time like what ethereum's been doing with blobs what like Celestia has beening with da all of this stuff like is actually itself a essentially general purpose computer that you can use to verify in computation so so the title we started just by the way as a bit of a joke we had added it in there and then we shared it with some Celestia folks we shared it with some ethereum folks just mostly almost a troll and then I removed it

another version and there was actually outroar about that like they should you should put it back in and so we did can I ask to explain a bit more how the computer comes to be because at this point like we have our leero leg da thing we know that it's also a poal commitment scheme so as I do da myself as a sampler I'm evaluating a polinomial great how how does that make a computer so indeed what ends up happening when you're proving a general purpose computation is that you do have to as you mentioned earlier you have to have this IOP component and then you have to have this polinomial commitment scheme component there exists some protocols for which the construct currently works

though we conjecture it may possible to generalize this to other iops but there exist specific iops that start with a general computation and or a specific computation usually could be something like matrix multiplication for which there exist very efficient protocols so they start with the result of the computation and then there's a couple layers of what are called sum checks that reduce the output to a claim about the input which the claim about the input is just an eval valuation of a multi-linear polinomial at a point which again is exactly what we're doing when we're sampling for data availability we are evaluating a polinom at a point if we gather enough of those evaluations we can recover the original polinomial so now the idea is can given

the fact that we're already doing this work anyway can we just leverage it securely as part of a general proof in other words let's plug in modularly an IOP on top of this thing ideally one that's super efficient that's based on Su checks could be linear time all this amazing stuff and the hard work with which is this slightly more expensive thing of encoding and hashing and so forth can just purely be outsourced to the data availability layer Maybe here's a helpful analogy or a helpful comparison I should say so previously what we were doing is let's say we wanted to prove that a particular computation was executed correctly so if I give you some input to some circuit I give you some input X you compute that

circuit you say that the output is y and I want to prove to a bunch of that I did that correctly and that the underlying data is available because proving it that it's correct doesn't suffice if I withhold the data for instance you won't be able to reconstruct everybody's accounts for example and withdraw money so we need two things for a secure rollup we need to know that the data is available and we need to know that the computation was executed correctly so the latter we usually do with a with a snark that could plug into a ZK rollup and the former we do with a data availability system so we try to merge these two so what we do today for example would be we take that data we encode it as part of the data availability layer and then people sample that thing then we could prove

that the encoding was done correctly by plugging it into a general purpose snarc doing an encoding hashing the thing having people sample the thing then we need to prove correctness so we take that data and guess what we do we encode it again and then we hash it and we have people sample that thing which is just mag like we are doing the same thing three times in this case so the observation of Zod is what if we do it two times and the observation of what we're calling The Accidental computers what if we just did it one time once H okay I have another toddler question um this is very toddler though because like you're using the word computer and yet everything you're talking about is like proving some it's

like it's it's it's all it's I don't get where is Computing happening like like what is your definition of computer in this context yes so it is like a little bit of a yeah no this is actually a great question right like like we're using computer in like a little bit of a loose way right like in some sense there is Computing happening but the Computing is is a it's like this notion of verifiability right like anybody can you can take a a general computer program right prove only this small part right and then the rest which ideally is very cheap to do and all this stuff and the rest the data availability layer does the rest of the compute and

verification and proving and all that stuff right so hence hence the accent computer is look take any program you like it could be just simply you know transferring Balan between people or it could be all the way as complicated as a general video game or something and instead of you know like proving every part of the thing was done correctly constructing these proofs sending them out to people then afterwards performing the data availability sending those out to people all this stuff it's like wait all I need to do is perform this tiny little part and then post the rest to Celestia or whatever da or dour right and now we're good like you have now accidentally allowed everybody to verify that your general purpose game program

thing is correctly done I think in all of these examples of like where's the compute happening is it in a separate environment that you're just proving things about is that what you're expressing so some portion of the compute is happening at the Celestia or ethereum or whatever data availability layers and in fact oftentimes the more expensive part of the proving work is being done by these systems in encoding and hashing some data then there's a separate part of the compute which is you could think of in your analogy before as the IOP part typically some sum checks that are happening by what we call in the paper a rollup prover H so so and that could be cheap

it could be expensive depending on the computation but typically I for specialized computations that's cheaper than committing and hashing to the underlying data the relative expense of course differs so that's how we think about it we think about today aover would have had to do that work so the rollup prover would have had to do the IOP part reduce it to polinomial Commitment which they would have had to commit it commit to ahead of time and then they need to open that commitment so anything involving the polom commitment now gets pushed to the data availability layer and only really the IOP part including all the stuff that would require sort of the these encodings and hashes and so forth is out of their hands so just by virtue of using this system these provs

accelerate they become a lot cheaper to run I can tell that I I have this like old info about how ethereum execution runs that constantly interrupts when we're talking in verifiable land and I I this is something I don't know how to square which is like account systems and balances and these like balance and and there's things happening to them and things are moving around and then you like I mean I really learned all of this stuff I learned like computer science quote unquote whatever I know here through ethereum so it's like very confused and not like I don't have this background of like how Computing really works but I'm trying to square this is

why I'm I feel I've said this a bunch of times I'm constantly confused when it's like this verifiable compute and like I don't like I still don't get where is the execution happening I get that you're proving stuff on it or you're saying like this is what this is but I'm like but is the comput isn't the computation happening somewhere else like isn't I think of execution as computation maybe that's my mistake I don't know yeah yeah so so what's what's interesting is like in ethereum land as is today you know as it exists right like computation execution and verification are the same thing same thing exactly right so let's just take a simple example right you you have accounts I'm

going to take even even more abstracted version of ethereum you have like some accounts and they are like paying each other right and what you would like to ensure is that nobody's balance is negative after everybody has paid everybody there's two ways of doing that number one is you just record everybody's transactions right and you just run the you know the Deltas between every every payment and then just check at every Point nobody has anything less than zero right and nobody's paid more than like they have available and therefore nobody has rece you know all this stuff right so there the execution and the verification the same right like how do I verify that everything is correct well I just like run the whole thing run the execution yeah so far good what happens in verifiability line is those two things are now split right

there is like a notion like computation is like now a weird term right because like what we thought what we think of as a program is like now either from the perspective of people looking at the you know like verifying this thing it is a proof and from the perspective of people proving this thing it is a construction that they have to like do yeah right but it is like there is computation happening in the former in the sense of like the output of all of these transactions you know being non- negative or being um sorry your balance is being non- negative at every point is like a thing somebody is like doing and checking but the prover is doing certain compute and the verifier is doing certain compute right and execution and

execution is like in some sense the prover is doing execution right but in reality like what they care about is this construction of a proof mhm right like the the execution is kind of irrelevant like all you just want to show is that this thing is correct yeah right and so it runs on like local machines and then you prove it like this is what I literally don't know where the thing runs that's my problem always like does it run on a blockchain does it run AC a decentralized ledger with like State accounts or is it like run in a separate environment and then you're just constantly proving stuff like like the rollups I get yeah but it's the minute ZK VMS and I I get it if I keep the like execution environment is like this bubble that lives outside and you just prove into a blockchain about it

but then what where is the bubble maybe this is my issue where is that here the bubble is in the rollup it's like well there's two there's two bubbles but number one is in the rollup you can think of it as like it performing like the small part of the proof but it's is it being proven on the entire like is is that like every single client node running a an execute like this is the thing that I think is or is it just like on some centralized Cloud Server this is the cool thing about the verifiability this is the cool thing about proving it is that it doesn't matter where it runs yeah so as long as I can verify a proof that it was done correctly I don't care where it was run I don't care if it was run on could be run on your own laptop

could be run on your laptop it could be run in the server it could be run by the most evil horrible person on the planet that I trust exactly zero but it doesn't matter because I have a proof and nobody can take that away from me yeah exactly exactly exactly exactly so yeah this doesn't really answer your question about where it happens but the answer is everywhere everywhere same time that's right right so I do have a question since we were saying all right in the typical rollup setup you have one prover could be the most evil person they do the execution in their head they give you the proof and they post the proof on ethereum L1 and now you have all these ethereum nodes who are going to run the verifier and they're all going to execute the

verifier and then they're going to come to the conclusion we all agree this proof was correct cool now in The Accidental computer case the person verifying is just someone sampling for data right mhm so is there some kind of consensus amongst the people who have checked the proof or is it like one you know you're each in for your own and no one kind of agrees whether execution was done correctly there's two ways to look at this so one way to look at this is you could do it in a way that is described typically as Sovereign rollups in other words that these proofs are just being passed around in a PTP layer and every every full node light node whatever you

want to call it like downloads these verifies them and then does a little bit of a additional sampling which will tell it that the PCS openings are correct and also that the data is available assuming enough other people are also sampling and that's perfectly reasonable construction and indeed that's probably the most natural one for some of these systems like Celestia and others that are amendable to these types of constructions the other one that's just as natural is you could imagine the IOP part having its own non-interactive proof that you could post to some what are called settlement layers you could post it to a theum L1 or somewhere else M and then you verify that part now of course that part will only tell you that the computation is correct in so far as the PCS opens to the right place and

then for instance you could imagine sampling in order to achieve the ladder guarantee separately so now you know for instance that the first part is correct and also that the data is available and that the PCS open so therefore the whole thing was correct and available you could also go back to the fully non-interactive model which is you do the PCS and IOP in the very traditional way and post that to an L1 and then do data availability sampling separately that's that's an option as well we don't discuss exactly how to implement these things because there exist multiple ways of doing it the main thing that we focus on for this work is just giving a concrete sketch of a construction and it could be implemented in a variety of

different ways where you do interaction where you don't and there's actually quite a quite a lot of Rich design space I think around that that is starting to emerge so one question we got often with Zoda and I'm sure you're going to be getting with accidental computer is was this implemented and how fast is the Prov like does it deliver on the promise yeah the implementation is coming soon TM but there there might be some spicy uh numbers in the near future could this already be out there by the time this airs should we look for it hope to it maybe oh yeah that's right yeah yeah I guess it's going to be two weeks so tweet it maybe you could tweet these numbers as well you they haven't already been observed I think you're being backed into a commitment Gamera I know I really

am I better better have the pre-image for that thing before I say anything okay good so yeah the answer is hopefully it'll be out by then interesting or by the time you're listening now dear listener yes okay so this is maybe something that's coming next but is there anything else on the road map in terms of this like line of work and actually even before I say that like I thought I saw Celestia post something in their Forum about possibly using Zoda like is this going to be incorporated into existing systems what's going on yeah we're looking at a lot of components of the system and there's lots of Interest this is of course early work and there's lots of work still to do there's questions around can we make node sizes very very small while preserving zero overhead can

we in the case of The Accidental computer work over more General arithmetization and iops and efficiently approve more General computations there's other questions and can we eek out further efficiency in settings like census and the like and so there's been quite a bit of Interest people have reached out to us and work that we're doing independently as well in those areas so stay tuned where we've been chatting with teams like Celestia a couple Folks at ethereum and a couple others around it so it's early research still and we have this is generating as many questions as it is answering at point but we're certainly having we're certainly having a lot of fun doing it that's great well thank you guys for coming on the show being guests and hosts like thank you

both being guests and hosts cool thanks guys all right I want to say thank you to the podcast team Rachel Henrik and Tanya and to our listeners thanks for listening [Music]