Episode 294 - Succinct Proofs and Linear Algebra with Guillermo and Alex

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week Kobe and I chat with Alex Evans and GMO my sometimes co-host about their latest research paper called succinct proofs in linear algebra this work includes notation and a framework which simplifies succinct proof construction and offers a toolkit of

useful techniques we walk through how these tools can be used to create a proof of security of the fry protocol which is also in the paper and how they may be used to better understand other systems as well our conversation covers how ZK is usually taught how the description for these systems have been evolving and how to make these systems even more understandable now before we kick off I want to highlight the upcoming ZK hack Istanbul event happening next month on November 10th through 12th just before Dev connect once again we will be hacking on ZK tools using ZK dsls and building new products that showcase what ZK and other Advanced cryptography can do this is a continuation from our spring event ZK hack Lisbon hackers and Builders will

get to meet the teams working on ZK learn new skills find collaborators and friends as well as imag new ways to use ZK in real world applications this event starts midday on November 10th and runs into the late afternoon on November 12th applications can be found at ZK istanbul. We'll add the link in the show notes and we hope to see you there now Tanya will share a little bit about this week's sponsor Alo is a new layer one blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a rollup driven by a mission of a truly secure internet Alo has interwoven ZK proofs into every facet of their stock resulting in a vertically integrated

layer one blockchain that's unparalleled in its approach Alo is ZK by Design dive into their programming language Leo and see what permissionless development looks like offering boundless opportunities for developers and innovators to build ZK apps as Alo is gearing up for their main net launch in Q4 this is an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at al.org so thanks again Alo and now here's our episode today we're here to discuss a new paper by GMO and Alex it's called succinct proofs in linear algebra hey GMO hey Alex what up hey good to see you so I think our audience is very familiar

with both of you actually GMO is a sometimes co-host of the show Alex you are returning guest uh we also have Kobe on this one as our co-host hey hey Kobe hello so I was thinking you've already introduced yourself a couple times on the show so instead of doing background We'll add some links to earlier episodes Alex where you were on maybe for the first time but for right now for our audience maybe tell us like what do you work on dayto day so I work on one of two things depending on who will have me on any given day uh we have an investment team and a research team and those teams collaborate a lot but they don't talk enough for them to realize what I've been pulling on them which is that on some days I'll be on the investment team and we'll have a

whole bunch of very dumb investment ideas people will realize that and say hey why you go do some research over with guo I'll go do that for a couple months have some terrible ideas for papers and terrible suggestions on existing papers that actually are good and then they remind me very quickly that I'm an investor uh and that I should go back to the investing side so until they these groups talk to each other I will be employed you will be ping ponged back and forth between research and investment he says this yet some of my favorite papers are definitely with Alex so it's it's fun to pretend you know I like the I like I like him pretending to be a researcher more than pretending to be an investor but I don't I don't get to have him 100% of a Time uhuh so it's actually more

like he's forced out of my hand unfortunately so yeah and guo I mean our audience is quite familiar with you and we're gonna be talking about a particular work today but what kinds of topics do you usually work on yeah so it's kind of funny being um you know my my my PhD and undergrad and stuff we in like physics and optimization Theory which is the realm of lovely continuous mathematics so things that things that make sense in my world are things like Finance where you can say sure you have a 1.36 925 to one amount of ether um things that don't make sense uh is is taking moduli of numbers so saying something Mod Five I could not could not proc that in my head uh so the point is

most of my work is in Defi and related applications you know things around meev sure maybe things around sometimes in privacy in indexes and things like that uh but the second that you you tell me something about a finite field or a module or Rings or something I I just sorry I just immediately like I I I shut down and throw an error uh to the reader so and yet today we're going to be talking about work that definitely crosses over into to the ZK space but maybe not those things this is what we're here to talk about it's like this seems like a little bit of a step outside of the usual which is why you're being brought on as a guest and not a co-host um let's start talking about

this succinct proofs and linear algebra what do this work what is it about Alex do you want to give the the high level I want you to give it you want me to do the honor so that's unfortunate so okay I I'll tell the back story of the paper I think maybe maybe we'll set up up the stage uh and then I'll get to what the paper actually is just it's very simple but so uh Alex uh got nerd sniped into zero knowledge and when I mean nerd snipe I mean like you know went down the rabbit hole of reading all these papers reading Taylor's textbook reading all these like very nice sources when was that when was it roughly over the course of the last year and a half and that's

in no small part your fault Anna and your fault Kobe for making this field more accessible to idiots like me so luckily uh there's a there's a beautiful thing about Alex doing all of this work which is that's the hard work of of learning a new field is uh having someone go read all of these papers right like reading all of these papers is is fairly difficult um I I I have strong opinions about how things should be written but I I think cryptographers have a very different style for example than than the style that I normally do and I actually find a lot of the papers like fairly different difficult to read so Alex went off and you know took eight months to go read all of these papers in like fine detail and then uh and along

with sources that you guys have put out and things like that and then it's got this very nice funnel of now I have like an oracle namely Alex Evans that I can query to like ask absolutely idiotic questions about zero knowledge ah and one of the things that kind of popped up over and over and over again uh is when Alex is explaining these things to me we kind of started realizing that a lot of it feels uh so so at a high level a lot of ZK proofs deal with things objects like polinomial um deal with objects like you know random linear combinations and things like that and as we were

discussing these papers there was this kind of taste in the back of our mouths that a lot of the objects were what what might call like linear algebraic and origin they weren't the polinomial themselves were were merely a tool to kind of understand you know at a high level like this system but they weren't actually like deeply part of the system itself I I I'll we can get to what that means in a second but and then the other thing that we realized is that there's kind of a set of different abstractions you know I think it's some point in actually uh one of the white board sessions Dan Bonet points out something rather interesting which is zero knowledge proofs can be looked at as essentially if I recall correctly some

some sort of reduction an IOP right and then afterwards some commitment scheme that gets kind of attached at the end of it PCS polinomial commitment scheme usually yes right so exact polom commitment schemes although there are there are of course others that you can get very fancy about but but the point is um you know that reduction is good and it's a it's a step towards one of the possibilities but in the middle there's I think there's we thought there was a part missing oo so in these constructions and this these like iops for example there seem to be these this notion of randomized reduction so a tool that happens is used over and over again in zero knowledge

this this idea that you use Randomness and interaction um to kind of essentially take a thing that you want to check and make reduce it to a smaller thing that is easier to check m right with this Randomness so this Randomness introduces like a notion of an error but that's okay because the error probability of error should be very low and so the next thing was it you know that's kind of independent of the cryptography itself so so even in iops there's sometimes a little bit of like Notions of cryptographic kind of ideas that are used throughout um and so we wanted to separate that cleanly and have just this small piece of randomized reduction studied there very carefully treat it as

its own abstraction and so the natural next question that Alex and I kind of thought of is what is the natural set of objects to look at for these randomized reductions there were some papers around this um which we kind of funnily enough discovered a little bit later as we were working on it which uh is one of by abam kapali which is uh algebraic reductions of knowledge there's one a little bit earlier by alander Kessa on uh I believe it was reduction of certain things to to module theoretic ideas but they focused very specifically on one protocol which was a su Che protocol um or a slight generalization thereof and we were more curious about the general structure of these kind of succinct proofs and so the

natural question is okay what what is the the abstraction we should use and it turns out you know to our knowledge the most natural thing to use happens to be linear algebra over finite Fields you can look at a lot of the tools that are used in succinct proofs and zero knowledge as kind of reductions that happen over these linear algebraic objects um and this suggests a number of other things like for example there's simple notation you can use to clean up a lot of the proofs uh and there's these nice abstractions that you can use to kind of construct uh these sets of of of proofs that end up being you know the things that we know and love so one example of that being fry before we get into all the Deep details which are

Super interesting who should be reading this work what are they trying to learn yeah in some ways this goes a little bit to a bit of our process in writing this in some sense this is a letter to our past selves in getting into the field in that we don't know a lot of cryptography uh but we do know a fair bit of linear algebra we've used it in a lot of different areas of our work Geo in particular he used it in so many different fields from physics to automated market makers and so in tracking our own journey through learning the core protocols and approaches in the space we wanted an introduction that wasn't just you know

hey here's the blue ball red ball kind of very basic introduction to zero knowledge nor was it on the other end of the extreme the type of thing that you might encounter in the phalor textbook or the great whiteboard sessions uh that you've done Anna but something that could get us pretty quickly from that very basic Foundation to starting to reason about the security of these very basic reductions that are ubiquitous in the field so what is the minimal set of things that we can use as assum assume knowledge that somebody with that assumed knowledge can now come in and do damage right can come in and prove things about fry can come prove things about complicated protocols likely hero and the like so going back to the who

just to continue on that it's you your earlier kind of selves but is there maybe another part of the audience that you're thinking of when you write this I mean I I think so a common thing that you study and undergrad mathematics for example maybe computer science is linear algebra right so in some sense the the paper is aimed at our past selves which is you know what do we know about finite Fields well it's linear algebra mostly works right and linear algebra as we know it mostly Works uh and that kind of place for anybody right if you've taken an introductory class in in linear algebra and there's a little bit of weirdness about it but uh have done you can also read this paper so yeah exactly so you should take

a peek at it kind of thing you know it's it's fun it's it's weird right because it's kind of surprising that it turns out to be linear algebraic in origin like like do you feel that people that for example don't know a lot about SE proofs should read it like with this give them good introduction to to some part of it or should they do something before that I think if you come from this field our objective is if you sorry excuse me if you don't come from this field and you don't know a lot about cryptography but you're a smart undergraduate that's taking linear algebra knows a little bit about probability Theory maybe you've heard about a finite field that we're relatively careful and keeping the characteristics of these things no pun intended minimal um you should be able

to come in and understand a basic set of tools and we hope that you take away these tools and as you go and scour more advanced components of the literature because these randomized reductions are great they don't get us fully to fully operational snarks on their own but if you get the intuitions and the basic reasons why these things work and take those with you as you go and read more advanced fully featured fully-fledged protocols in the literature that you can understand why things work without having to start from zero zero and understand all these cryptographic constructions that are often used in the presentation of these results and protocols I was thinking we could walk through a little bit of the structure of the work because as I was looking through it it reads very different from

a lot of the papers that we see on ePrint and because like like you actually Define in quite simple terms a lot of the things you're going to be using later so yeah I was wondering like it seemed like you know you're sharing these foundations you kind of just mentioned that like at the beginning so that people can actually do something with it but maybe we can share with the audience a little bit of like what what is your thinking on structure how are you expecting the reader to sort of participate in this it's kind of funny because the way that Alex and I and tud and Theo you know our co-authors right is is actually this is standard this is part for the course yeah right it's it's in some ways very different it's like a different culture uh from from that of

uh theoretical computer science so some theal computer science are actually more like this but but for the most part cryptography is not and so it's it's kind of funny it's um the the high level idea of papers like this and specific are more like look take my hand we're going to walk through like the basics of how things work we're going to make it as simple as possible right and actually that making it simple is actually quite difficult it took us a long time to get to this framework and in fact it took us so many iterations to get to this framework it is hysterical you can see notes of our early stuff that were a disaster I mean they were kind of unreadable even by us um and but the point is you know you what you want

to do is a paper like this takes the hand of the reader and says look you can trust us you can read this paper front to back and as you read it there's nothing that we're going to mention that we're not going to use later that's guarantee one you make to the reader and then guarantee two that you make to the reader is if you read this thing front to back you will have all of the requirements necessary minus the very basic assumption that we make about knowing linear algebra to go through the entire work right there will be no kind of hidden surprise to say haha actually this thing you know you can defer the entire construction is built such that if you start from the beginning and go to the end you build the tools that you

need to prove the later things right and this some people might say oh that's like similar to how you build lemus and then theorem stuff like that and it's it's true in spirit but the way it behaves is it's kind of funny it's you paper starts with here is you know basic linear algeb refunding fields and then section two is something like here are a bunch of basic tools some of the tools we'll use previous tools to prove their security some of them will not some of them are just going to introduce and then section three says okay we've now built up this fun framework the natural question for the reader is of course great you've done all this crap what can we we do with it and that's that's the thing that's answered is let's actually do something

real and and that structure you will see in a number of our papers but it's it's not super standard in cryptography uh personally I mean some of it is so there are certainly Lumas that are proven and then afterwards theism are proven based on those and things like that but but as like an INT an introductory notion it's not super common as far as I can tell no I don't know if Kobe disagrees with this he's the real cryptographer here but or if Alex no no actually completely and like when I when I was reading I was live commenting to you on telegram right and that was awesome thank you by the way for all the help that was great no no problem I was really enjoying it but like when I was reading it I was I was feeling that it was so methodically

structured that you also don't even bother reminding the audience or the reader too much about the dimensions of things because like the thing that you defined at the beginning is carried through throughout all the paper to have the same dimensions and the same uh the same use and it's super methodically structured so the reader cannot can confus like you can have a cheat cheat Che right next to you and it will be useful cool yeah you'll see versions of this in the Whiteboard sessions that we would do in the early parts of writing the paper we would go off and read protocols there'd be a change in notation somewhere in the middle of the

protocol and we would be filling the Whiteboard with question marks trying to figure out all right are they are we referring to this are we referring to that you know just the metap point a little bit on structuring of these papers I've fallen victim to the same thing you have Kobe not as a co-author but as a reader of Geo and tun's early papers that have a very similar structure to this I've noticed it with some other folks from Geo's lab like the Steven Boyd papers this is just sort of a meta comment on academic writing which is you read these papers and they're so innocent they're so Toothless and smiley and you start out with these really basic things oh here's a convex function don't don't worry about what it is we'll talk about that later there's a couple

of constraints and then you go like three three sections later of like very basic stuff like that and you're proving crazy things and it's like it's the experience of the reader of writing an exponential curve where you're eating your vegetables for the first couple pages and then you're like all right let's start doing some real damage and that's so different as an experience reading the stuff than reading for instance a lot of I mean papers in mathematics more broadly but in ZK in particular where you you'll have in the presentation of a very important result here's a Lemma you see the statement of the Lemma you you don't know what it means like you understand the theorem okay this if we could prove this that'd be pretty interesting but you see this Lon it's sort of oftentimes seemingly unrelated confusingly phrased and then

you know you go off you prove you spend like four pages proving it and that's awesome you get to the end it's like I understand why this thing works and then the theorem is like three lines cuz it's like basically a a trivial consequence of the Lemma and you know it's just this this thing where like all these disperate components sort of come to the end and you've almost feel like you've been robbed of something in the process and so this is our way of just creating a buildup uh and attention before build up a library of tools build up a library of checks and then at the end start doing things with them uh which as a reader initially I I was just so confused cuz I'd never seen anything written that way before once you get into it as a writer you almost can't

write any other way and it's my understanding that some people might not like that style uh I don't think it's for everyone uh we we were expecting actually get Fair bit of criticism uh on this paper that we haven't to to date received maybe it's been criticized in private um maybe the aing of this episode will finally bring those people out yeah no but they do think it's an very inviting style of writing so I liked it you sort of me so happy you mentioned this sort of buildup with the components and then the sort of meat of it you're you're using these components to prove the security and you choose fry but I actually wondered like with those foundational elements Could you actually

have focused on a different type of PCS or did you build this entire paper to look at fry like could you switch that out and then use those same components so the the aim of the paper is indeed to be able to do any number of protocols so for example we don't mention this like super deeply although Kobe did point this out is you you could use it to generalize the herrow for example or breakdown or any of these things yeah and and that justes happen actually funnily enough one of our very innocent looking you know tools is actually just pretty much exactly Le herrow so but the reason we chose fry uh is almost an accident the first is I had no idea I've actually haven't really I've read a part of the fry paper and I've read the main

parts but I've never read the proof of how fry worked uh and everyone I asked or not everyone but most people I asked didn't actually understand the security proof of fry so it was kind of a personal challenge to without looking at the security proof of fry try to prove its security of course it's a very weak notion in the sense of like the constant are quite bad but prove the actual security of fry without having ever looked at the original proof only knowing how the protocol works so that was it and that was almost accidental actually it wasn't even clear that this framework had the power to do such a thing until pretty late in the game I want to say was added maybe a you know that we've been working on this paper for how long nine months-ish at least maybe a year

something like that um every day for nine month just kidding yeah every single day I know GMA you have like 15 things happening at the same time here yeah no but this one was one that certainly in the last two three three months they picked up enormously I was kind of working on it day and night especially after after we realized that we for example you could prove the security FR using this framework it was clear that it was not just a toy uh but it was quite we I mean it's unclear if it is powerful but it seems powerful enough at least to to say interesting things going back to that point though could you then prove another and I'm saying PCS here as though that's how

you're proving fry but like could you yeah could you use this to prove something else in the ZK stack certainly yeah yeah I there's a lot of suspicions about you know this kind of randomized reduction this idea is used a lot in the literature so you could imagine kind of applying it very generally to a number of other things and using the same tools and then at the end getting the same bound as you expect um we haven't done that work I I mean I don't know Alex if he had any specific you're he's the one who actually knows ZK stuff I simply exist as a writing Aid you know GP we don't we don't necessarily link specific checks and randomized reductions to specific protocols in literature which is also

kind of part of the Innocence that I described earlier but that's right if you look at the literature A lot of the IOP components some check protocols with involving multi-linear polinomial uh zero checks polinomial zero checks in particular these types of things are examples of these types of randomized reductions you might do them in repeated ways depending on the protocol and in fact many polinomial commitment schemes are as well instantiated in this IOP like structure fry being a great example of that fry lends itself particularly well to this type of analysis because you are talking about linear Al breakout objects and this we're not the first to point this out right a lot of the early Fred papers and work have talked about this component of it we have just isolated attempted at

least to isolate just those components to create an intuitive exploration of what the thing is how it works I think for some other polom commitments particularly ones that involve heavy heavier Duty cryptography in order for us to reason about them in this framework we figured we would have to introduce heavier Machinery so especially when we're working over things like groups um and care a lot about the structure of those groups like The discrete logger the problem being hard in that group we we need to we need to provide additional Machinery um there are some examples in the literature which GMO talked about earlier that do this through a slight generalization of the linear algebraic framework to modules and modules over

Rings we could do that um and you could imagine this approach therefore starting to apply to things like bulletproof in product arguments things things of that nature that's so cool we felt in this first work that that would introduce just too heavy machinery in getting the reader to a place of hey here's a couple protocols that we use very often Su checks fry let's take a look at the types of approaches and randomized reductions that underly why these things work and how they give us the synness yeah yeah so cool I think it also has like some kind of increasing importance to to look at these kind of things

because you know people that have come from the growth 16 world or even KY G plong they're not used to thinking about these highly iterative processes with Randomness inside them and some checks and Fry are increasingly popular and it's important for almost everyone to know them now so it's something that you really want to to nail down well but I also remember that when I talked to you about fry in this paper I felt you were semi insulted when I said that the fry FR was the Pinnacle of this work and like the fact that you can prove

it uh um and like I think that uh I think maybe rightfully so is because you felt that the components that you've introduced in the paper are already so powerful to prove a lot of things so maybe it would be good to talk about the components of it sure so there's two main things that we introduced in the paper specifically that then build up to fry uh the first is a a weird notion of something called probabilistic implications this is not a thing that I knew existed and apparently it exists somewhere in like some weird data analytics literature or something like that but the point is what is a common thing that happens in zero knowledge proofs it's this fact that you

can take uh some statement a right and reduce it to a different statement B say uh and if you if you show that b is true right B depends on some Randomness then you show that a is true with high probability okay so in a in a sense that's kind of that's that's like a reasonable notion of logic right that's so a implies b or sorry B implies a I guess in this case is is a reasonable notion of logic but we have kind of a fuzzier version the version here is so there's some probability that if B is true actually eight might not be true right and so to deal with this we introduced some very simple notation which essentially lets you account for

all of the times that you introduce error in a given proof so a proof is simply a series of redu uctions from one statement to another and a probabilistic proof right is a series of reductions from one statement to another with respect to some Randomness where there's a probability that one of the implications isn't true if you take that as your foundation you actually get a perfectly reasonable logical framework uh that you can it's very similar to the way that mathematicians deal with normal implications a implies B and B implies c means that a implies C is a perfectly reasonable statement so there's an equivalent version of this in these

probabilistic implications so a implies B with some error probability p and B implies C with some error probability P Prime means that a implies C with some error probability at most P plus P Prime so the same Notions that we have in normal implications hold over these fuzzier probabilistic objects but you have this accounting term this this idea that like the probability as you kind of go might increase or might be added to yeah and it's funny because from there you recover the traditional implications by saying a normal implication is one that s with probability zero so one that has zero probability of failing right so

that's one of the big tools that we introduce in this particular framework and we think it might be useful to clean up some of the proofs um that you know are common in in things like soing proof systems and zero knowledge the other thing that we introduce is this toolkit that we chatted about with Anna earlier which is this notion that certain randomized reductions uh can be used to prove properties about objects so the interesting part about these is these are tools that you can kind of combine you kind of think of them as Legos so with this notation and these tools you can kind of literally take them right put them together and then just read off the probabilities of Errors of the final

protocol by just kind of sticking these things together um and so in some sense like what we've done is we've built this like hilarious edifice of like Legos where the first set of Legos tells you how to clip the Legos together correctly and the second set of Legos is like okay here are the pieces you actually get and we say have fun building an edifice of whatever you would like uh and at the end your reward isn't just I have some protocol I need to do some complicated thing it's I have a protocol and I can show that the security of this protocol is guaranteed because of the fact that I can take these implications and add up their errors in the way that we expect and then at the end I essentially by constructing this protocol out of these Legos have a also have a security

proof that comes out of it essentially for free and that's actually at a high level that's how we end up proving the security of fry it's you take three of these Legos stick them all together and then just recursively apply the same operation and at the end you get a bound on the probability of error based on the size or the number of rounds that you do for fry and that's a very powerful tool yeah that's cool it's weird it's weird that you can do it at all I mean it's not obvious no it's not obvious at all and actually you said like three of these Legos make up fry what are these Legos right so so the Legos are at a high level we have first is you you can check that a vector is sparse so if you have a

vector that has a bunch of entries you want to check that most of them are zero that's pretty you know and there's an intuitive way of doing it it says I'm just going to pick a bunch of random entries and I'm going to check if those entries are zero if all of those entries are zero if all of the entries I've randomly picked and checked are zero are indeed zero then the original Vector must have been pretty close to zero in the first place right yeah because you know if some elements are nonzero then you have some pretty high probability of catching those errors so to speak that's tool one uh tool two is is a little bit harder to explain but essentially it says something like if you take two vectors right so you have two long list

of vectors you want to check if they are close to some Vector Subspace you can do that by checking that each individual Vector is close to the vector Subspace sure but there's a smarter way of doing it which is you essentially take a random linear combination of those two vectors this is actually essentially learo um um and the point is if you take a random linear combination you've taken this harder set of questions which is checking that two vectors are close to a vector Subspace and reduce it to a simpler set of questions we're just checking that a single Vector is close to a vector Subspace right so that's part two of the formula and the third component is essentially this notion of a correlated basis I believe is what we call it or something of the like where

uh fry just happens to have this particular property because they choose polinomial but we suspect holds more broadly and that's not super important that's a little bit deep in the weeds but at a high level is just you need three major components to prove the security of fry you just in component two you used a term and actually used it earlier and I didn't stop you it was legero legero Leo something like that what is that uh so have you heard of breakdown no oh okay this is like this is like cool highle fancy knowledge I don't know how or Kobe do you want to you want to explain that yeah just at a at a very high level there are polinomial commitment schemes that utilize error correcting codes fry is one of them but you can imagine that

there's other ones that have different ASM totic characteristics and utilize slightly different techniques but it turns out these techniques are very much related this has been an area of ongoing development over the last few years Le hero I believe is a 2017 paper um that um has been iterated on by people coming up with new types of codes to utilize in the encoding procedure which is one of the most computationally intensive if not the most computationally intensive step that the prover needs to conduct during the polinomial commitment scheme um and papers like breakdown do that in what they claim is linear time and there's been a number of other iterations on top of this um including different

randomized tests so in fact a type of procedure which is very similar to the one that we have was published by Ben diamond and Jim Posen um in I believe it's something like Leo with logarithmic Randomness as the title of the paper so this been a very active area of research of are there other types of codes outside of fry uh that utilize error correcting codes which are very much in the in this type of thing that we like we can reason about in our paper because they involve simple linear algebra random reductions and the like and so it turns out that the same Frameworks that we use for this these components of fry can be applied to these other polinomial commitment

schemes fairly naturally cool actually yeah just going to do a quick throw back to an episode that Nico and I did with uh Ron rothblum about error correcting codes I can add that to the show notes we may actually have talked about learo and breakdown and I've forgotten I'm not sure um but uh yeah that might be good listen as well for folks perfect a major part of the paper talks about error correcting codes and linear codes and this this take a prominent part in the in the toolkit that you build so maybe it would be nice to talk about them a bit and introduce how how they're useful here right so I guess another topic that

we haven't quite discussed yet but is this paper essentially poses an so it it mostly proves but does not fully prove the following claim which is in most cases right when you have a randomized reduction you do something like you take a random linear combination of a bunch of vectors uh and that reduces a claim over a bunch of vectors into a claim over a single vector and one of the things that we've noticed uh throughout as we worked on some of the stuff is that actually you can replace this notion of random linear combination you can replace it with a very structured notion of Randomness which is if you have a big error

correcting code Matrix that has high distance um you can instead of picking a uniformly random linear combination you can pick a uniformly random row of this generator Matrix for a code of large distance and use those like that those numbers as the coefficients of a random linear combination so that's far more structured right so for example there's a tradeoff between how you know the amount of Randomness that you use and the proof size right and so this lets you this notion of structured Randomness lets you kind of have a slider tuning knob that says okay how how much Randomness do you want in your protocol

versus how much soundness there do you want to be able to achieve um and so this particular structure notion of randoms is a second thing that we talk about a lot in the paper which is almost everything that we know in ZK K doesn't need to have either uh the powers of Randomness so 1 r r 2 whatever where R is a randomly chosen number That's a classic notion of Randomness that's used throughout or the second notion where it's you just uniformly randomly sample a bunch of numbers um it's actually give me any error correcting code Matrix right pick a random uniformly random row and there's your Randomness what we suspect is a really powerful notion because it it allows you to do a number of you know potentially reductions that are cheaper or simpler or more efficient than

otherwise and it's surprising that it kind of works but almost everything except one conjecture uh seems to carry over and exactly the way you expect I don't know Alex if you want to talk about it but yeah one thing that is it might be worth clarifying here because I think a lot of folks that will have read things like Leo and Fry and breakdown and there's been a lot of excitement around these things recently will refer to error correcting codes as the code you use use let me give you an example in the case of those are familiar with the hero take a row or in our case because we're linear algebra unfortunately take a column uh and extend it using an error correcting code um and then take a linear combination of

the things you extend and test some properties of of it at a very high level right so that's when people talk about a correcting codes they refer to that sort of procedure right that you do like you take up something uh that's really small you extend it into something big and you test a couple entries of that bigger thing and then through that it's actually quite magical that you can then infer things about the small thing we utilize a similar thing but the way we the types of codes that we're referring to here are have a slightly different function they the same codes roughly right you could use the same codes but they have a different function so just as in the latter step of the protocol you take a uniform random linear combination of these en code these code words right and then test

them you could take any you could en again encode these again using some random generate like a Rand and then sample a random row of a generator Matrix which could represent any code right so when we talk about our correcting codes we're not talking about necessar we are talking about extending for instance the original message and Performing the first part of these protocols that I think the many listeners would be familiar with we're referring to the second part which is the random testing that people do um could be could be done with in many cases arbitrary linear codes so we have this conjecture that many of these procedures that are used in protocols

like Le hero and like breakdown would in fact work when using general linear codes now we know they work when using a uniform you know take Taking uniform Randomness and taking a uniform linear combination of the rows columns whatever your your choice of um of looking at this is the conjecture that we have is that this type of procedure is actually more General nice and so we I'm taking us back way back to the first part of the podcast where we asked about who the audience is there's a secret part of the audience here which is people that know error correcting codes really really well yes uh that may not know

cryptography at all that we are desperately trying to nerd snipe into giving us their time attention and effort into Sol conjectures like these and we think the the resolution of these types of problems have very very interesting implications for the efficiency of error correcting code based PCS schemes and the efficiency of all our snarks if we're able to get them to pay attention to snarks so this is something that you both have accomplished very many times Anna and Kobe in in creating educational material that allows people from other fields to start figuring out where their particular Edge and knowledge base can contribute to the field we're calling on

people from the ER correcting code side of Academia and practice to say hey we have interesting problems for you all if you want to come check them out that's right I think yeah I think that's beautifully put I think that's exactly the right way is this is like the nerdiest Easter eggs possible is what it sounds like right now is this what this is okay roughly speaking the answer is yes uh the secret to to nerd sniping people to not let him even know they're being nerd sniped oh that's the big brain play it's not even that secret because guo has gone to try to find the famous professors in the field of error correcting codes has been

knocking on their doors at Stanford and telling them about the gospel of snarks and ZK and you know at first I think with many of the existing works if you were to come in and tell them about our Lord and savior snarks and why there work could be interesting here we might have gotten a different response but in some ways we the way we frame this problem intentionally is for people like that to be able to access it and see what damage they can do that's right I love this it's such a meta it's like a conversation you're having in an academic context which I know nothing about but I love it I love that you're like operating on these levels through this paper it's so cool yeah it it it also this also All Points deeply to a

conversation that we had a long time ago an while we were mostly sosed oh about things like no no just I mean in recent an episode uh specifically the one where we had sake oh yeah and like how how writing happens in mathematics and like the cultural factors around it it's uh yeah might be might be a fun one it's a link that actually GMA you and I I mean we've had a threat we just when we had David Wong on we kind of continued on that thread of just like how you communicate and all these like levels that people are trying to communicate on so you use Randomness a lot in the paper like basically everything is about know randomized reductions but a lot of people don't really use like

Randomness in real life they use Fiat chamir and I think that's also something that Anna you mentioned you discussed recently on an episode with nethermind yeah so the episode right before this one was with some of the folks from mind and they were telling me about some work they had done about proving fry but proving the security of fry kind in the context of with with f Shamir there's like something related to that I had wanted to bring that up almost to understand if is their work and your work similar is it complimentary are they dealing with a different part of this of the stack I know what we talked a lot about was like fries assume to be secure once you put it through Fiat Shamir it changes its properties like

that was kind of of the the area that that we were talking about primarily but yeah maybe we can just talk a little bit about those papers and how they they interface so I guess to to start is the the interesting part about this framework is that actually we don't touch the security of f Shamir at all in fact we take great we go through great pain to avoid ever touching any cryptographic principle that can be otherwise included in a model so we simply say look there's a black box that you can query that has these properties uh of course practical protocols will Implement these black boxes as

cryptographic protocols but we will simply take them as given so the the work is certainly extremely complimentary in the sense that the security of fry under F Shamir you know puristic Transformations is an important question but it's it's in a sense from the perspective of this paper at least an important question about how one implements fry practically the framework that we put actually attempts to much as possible to alide the question of how do you implement this protocol practically and simply aims to give understanding of why the protocol works at the very highest level and give some stion of security around it um I'm sure Alex has more thoughts on this yeah and every paper that tries to do this has a number

of dirty secrets and ours we're not necessarily super shy about this we talk about in the paper in our description of models which is we sweep under the rug a lot of very very important things and say look you can look under here but here be dragons right this is the type of thing that can really shoot you in the foot in practice and you should go talk to the cryptographers about that they know all about it right for for now so when we say we prove the security of fry we don't mean it in the sense of all right now it's bulletproof and you could just take a randomized reduction that's not close to True right there's some intuitions about randomized reductions why they work how they work what types of tools you have at your

disposal how you can compose those tools and we talk about that and then there's a separate and Incredibly valuable line of work that's important to practitioners and is interesting theoretically which reasons about how these things are instantiated in practice because these Notions are very mathematical right and magical right we talk about Randomness we could have a whole separate podcast about the philosophy of what Randomness even is does it even exist in practice right we have these like crap in the real world when you come back home to implement a real protocol right you have to deal with real objects right hash functions how those hash functions are implemented how many times you repeat this protocol in order to get certain properties out of it um and it turns out those things

can be pretty counterintuitive um and this is why a lot of practitioners shoot themselves in the foot with things like f Shamir all the time um and I've heard actually Kobe and the folks over at geometry have been doing a lot of work specifically on this part of how do we reason about the true real world security of protocols like fry so while you're the co-host I'd be curious for your perspective on how these things interact no yeah I definitely think it's an important question and there are many things that can go wrong right like even just on the implementation part you can forget to to do things in a certain order or you can forget to put things inside the hashes but also it sometimes changes the probabilities that you get

from from some of these reductions so it does require get care but I think you are being very fair in the sense that most of the papers go through this route right like most of the papers don't really go through analyzing how it looks like after you f chamir it they they St top at the randomness part so I think it's already pretty good to do it on that level so another question I had in mind is that a lot of the the framing that you have in the paper is that it's kind of about Pro and verifier right but we also use Randomness when we want to speed up

things locally like when we have batches of pairing checks and we want to to do this faster as a verifier locally they feel like that this framework could be useful for these kind of things as well I mean I think the answer is yes I think in that case you probably have to deal with again the generalizations to things like modules uh over rings as opposed to the current linear algebraic Notions but a lot of the stuff that we talk about pretty much here actually pretty much everything except the specific cases of vector space checks should carry over pretty directly to the case of modules so I assume that the answer is yes but but we have not no I can't I I shouldn't claim that without having done all the leg

work of actually going through and and making this uh making this generalization yeah you'll notice just at a higher level that I don't think we discuss the notion of aover and a verifier that's right right so the idea of a local check and a check that you do between sort of approver and a verifier and the conventional say and Alice and Bob thing doesn't really exist like we sort of merge because we don't have cryptographic tools this notion of you don't you don't trust the prover and the prover might be giving you malicious like we Allied all of that right and so this is why our impression when putting this out was that be several people fuming on their keyboards or maybe

there's a couple people fuming while they're listening to this going about their day um is that we don't do that so the notion of a local check and the notion of something that you need to do by interacting with someone else are sort of abstracted like the difference between these two things is is isn't there isn't a distinction while you know a finer version of this that's actually useful in the real world would make that distinction very clear because it matters a lot right so we we say look there's there's cryptographic Tools around this and then there's communication protocols that could achieve similar things so you could say I can prescribe a specific order to how a communication Network should work between aover and a verifier in other words theover sends the first message the verifier gets another message Pro send something back blah blah blah and

and if you mess up that order right like your your proofs no longer work you need to be very very prescriptive in order to ensure the pro can't behave adaptively and maliciously in order to mess you up somewhere in your checks right but this notion is abstracted by just imagining this idea of a hard drive that is just giving you answers and that's right as a black box those answers are good you can secure them using a communication protocol to force non- adaptivity right and this is what people use in the traditional proof system interactive proofs and then it could be non-interactive um and you could use a lot of cryptographic tools VI Shamir is important in this context a lot of the polinomial commitment schemes and the cryptographic assumptions therein

utilize these things and of course a full understanding of these protocols is not complete with without understanding we just very intentionally wanted to pull out this idea that's ubiquitous which is random reductions why they work and how they work no that that's that's actually really good Framing and now that you say that I'm wondering would you want to see existing papers that do include all of these other parts Rewritten to rip out their analysis of that part and replace it with your tools I mean if it makes them more legible that would be great it's unclear

if it will I mean we obviously suspect that they it might but but in some sense they are like the the way to think about it is that they they are separate abstractions right like we should be consistently thinking of them as two separate things right one is the high level crazy things that happen in a protocol via these randomized reductions which are themselves not trivial already and then there's a second part that comes from okay how do we make this real how do we you know what are The cryptographic Primitives that we need to do it what are the communication you know channels that we actually need to ensure you know happen in this whatever causal way or this to ensure non- adaptivity or things like that so that's the the high level structuring of

this is is very much to kind of like take the things that are currently mashed together all in one and separate them out into its constituent parts and its constituent parts are should be in some sense quite logically independent and that's one of the other aims that we aim to show in this particular paper is that in many cases it seems like the meat of a paper is not for example in some of the deep cryptographic techniques use but indeed in the randomized reductions and those two things should be kind of intellectually distinguished as their own categories and they don't they they actually don't seem to overlap they're important and there are ways in which their overlap is important but they don't seem to overlap

as much as one would expect given the framework that papers put up for understanding improving the security of their protocols MH I would say this is a broader Trend in the field that we've noticed especially as good educational material has finally come online with the mukes and the failor book and the Whiteboard sessions and all this awesome stuff we we've gotten better at explaining these protocols and the way that we do it often times is by breaking up the components now totally gr 16 maybe a little bit hard to do that but for most of the things that people use you know are building new systems on there's these clean separations of arithmetization and iops and functional commitment schemes and within that

polinomial commitment schemes of different types and the more we're able to rip out specific abstractions and think about them as their own things then the EAS it sort of accomplishes two things the easier it is to then take those things and Stitch them together in ways that maybe are more interesting than the constituent Parts but secondly and this is maybe referring to something I don't want to be repetitive but it allows entrance into the field to have very well scoped out problems and have a very clear understanding of how their small contribution and expertise can contribute to the global state-ofthe-art so if you can break out this type of error correcting code based quote

unquote random reduction and somebody that has no idea about all the other parts can contribute something meaningful and important to that everybody else can benefit if they need to understand the entire system end to end in order to figure out where they can make any kind of contribution I think that stunts the development of the field and so a lot of what we've seen over the last two years as the field has just gone through this Renaissance and all these papers are coming out is in some ways we would think a consequence of the fact that now you can figure out you don't have to build a whole protocol end to end you can figure out where your unique contribution could be valuable yeah um and that opens up the field to many more people to come into it that have

expse so they could be you know how to optimize the particular hash function on hardw well awesome here's a very well scoped out problem for you to go off and do that you don't we'll deal with the cryptography we'll deal with the random reductions we'll deal with everybody everything else you go off and do this one thing and we can all benefit from it uh the more we can do that as a field we think the faster the progress will accelerate that's right that's awesome I so agree I actually as you're telling me this I just remember the first time I heard the breakdown of the IOP polinomial commitment scheme and maybe it had been presented a little bit before this but it was Dave OA oh writing it out I think Alexandre kza had I mean I don't know who first came up with it but I it's it's one of two

groups it's either Dan bones or it's or it's Alice Alexander KES but yeah just seeing that framing was the first time like someone could draw something that kind of described a snark other than like what it had been before is like the proving back and forth interactive it was like again Pro or verify here all of a sudden it was like here's components Y and then you you see subsequent breakdowns and then you see new techniques that are sort of introduced as well like lookups like folding so maybe you can tell me where like in that framing is randomize reductions in a different dimension completely or is it on top of this is it throughout in in some ways it's kind of throughout right

the the notion of randomized reductions and these probalistic implications are kind of embedded in a lot of cases so for example the polinomial commitment scheme of fry is you know as we show in this paper is particularly endowed with these randomized reductions in fact the entire thing is is about them um one could imagine that there are these other kind of you know interactive Oracle proofs that also similarly have these randomized reductions it is in some way kind of an in between but they should be separate components right like it it's simply another framework to think about kind of how the individual components play together the same thing then it's almost like it almost feels like a different dimension that you're looking at it through or like you're you've sort

of flipped the model sideways and you're just giving like a new characteristic that sort of is a is a through line you missed a great opportunity gearmo as a linear algebraist to use the word orthogonal such it was an alleyoop and you missed it and I miss it the problem friends have ruined this for us Alex oh the problem with orthogonal so Alex the problem with orthogonal is that if we found in you know finite Fields is that orthogonality doesn't make sense in finite fields which sucks because things can be orthogonal to themselves which is really dumb and I hate that and that pains me as someone who has done normal linear

algebra in normal places not this finite field crap so um but anyways if we're touching about weird final field stuff does the introduction of all of these popular extension Fields like Goldilocks and like the extension Fields over Goldilocks and M31 does it change anything from like in your analysis nope not one thing gets changed that's perfect uh the reason why mostly is is because it's we we just deal with a general field at no point do we ever make any assumptions about um how how the field interacts with the proofs or anything of like the only way that the field actually ever accidentally ends up coming into the proofs is via the

distance of the code that you are using yeah to produce the randomness but otherwise it is independent which is kind of an interesting fact right it's it's not obvious you would expect the field to have some deep connection to the actual randomized reduction but the only way we have See It Go in into any of these tools is actually purely through the distance of the matrix it's also an interesting fact that I I feel like there's something deeper there but it's not clear to me what it is yeah there's very basic properties about the size of the field and things like that that you use uh the fact that it's an extension field other I mean it's extremely important in practice right which Fields you sample from and what type of randoms you can see like when

you pull something random out from that field like how it should affect your soundness and all this all all that should work pretty clearly out of the box but the mere fact of it being this extension field that you construct doesn't change the substance of the analysis so I think we're close to the end of this interview um it leaves me with two questions one is when is the expansion pack coming so you talked about these building blocks and how they're working you know they work on this one case of fry but that you could potentially use them towards something else but you'd have to reformat them a little reskin them maybe yeah what's what's the expansion when's the expansion pack coming I don't know Alex you have any idea you're the one that

actually knows this stuff I'm just here writing uh math and what's next what would you do next is actually the other part of that question this is this is interesting there's a lot of different directions that this could go from here we discuss a couple of the generalizations actually some of them have come up in the discussion today out of your questions on could you generalize this to modules over and the answer is probably You' have to be a little bit careful about what you're doing and maybe we'll sit down and do that um could you then do a mapping from very specific protocols that we talk about these checks and these tools and they roughly correspond to what you see in these protocols you can be very very specific about rewriting them almost as educational

material of okay here's these tools now here's real protocols and here's how they would work there's a couple other ones including the conjecture that we hope that is uh something that somebody at least identifies either this work or whatever other means you find at figuring out that this question exists out there and that it's something you can solve we ECT it's true um but would love to see somebody prove it true um there's a couple others like that uh GMA I think you undersell the Bold ideas you have for subsequent work from us and from others on this particular line yeah one of them is is weird and it's uh actually I don't know if this is my idea

I'm pretty sure this is Alex's idea which is a weird merger a loving merger between a lot of these these lattice uh style kind of cryptographic questions um and so it turns out if if there's if you have certain for example hash functions that are very structured you can say very interesting things specifically under this framework more broadly uh and the structure of those hash functions essentially something that it almost looks linear it doesn't need to be quite linear it just needs to look linear enough and it seems to be close to possible using some of these these kind of um like Lattis cryptographic methods so that's that's one of them so the

second question before we sign off and actually Kobe this was actually your question I was about to steal it you want to ask it you go ahead no no take it take it okay okay so uh it was when ZK hack study group about this paper oh possibility I don't know if you guys know that we do this over on the Zack Discord folks get together and they pick pieces of content content and they set up sessions where they'll meet you know once a week and like go through it in detail I don't know how many weeks your paper would need but it might be something fun like a miniseries Study Club for people um I mean if anyone's interested in it I'm sure we could be happy to do it I for the near future

I'll be kind of mostly chilling so I'm happy to but but you know I don't want to be like oh we should do this paper I I I don't know if anyone's actually I mean Kobe is I know because he's read it so carefully that I have like 150 messages from him just about this paper and they're great by the way because like 90% of the comments we've implemented it we added in some few little extra proofs and stuff like that so bless Kobe so my point is uh happy to do it but I don't want to force Vaper upon anyone because it's it's cool but it's like you know it's it's like fine it's kind of interesting but well if anyone's interested in doing something like this as we release the episode uh I'll try to put a poll out on the Zeki heck Discord and we'll add a link to

that in the show notes where we could potentially do a minseries study group around this paper I think it would be really fun but yeah we need to hear from you if you're into it if you want to do it with us sounds like fun I don't know Alex can do it too love to yeah nice yeah so thank you guys both for being on this episode and for sharing with us like the the thinking around this work how you wanted to frame it why you structured it the way you did what the intention is what you found what people can do with it what could come next yeah thank you so much for going over it with us I don't know thank you for having us thank you and thanks for the awesome questions yeah those are awesome it was really fun thanks Kobe for being the

co-host on this one and I want to say a big thank you to the ZK podcast team Rachel Henrik and Tanya and to our listeners thanks for [Music] listening