Episode 282 - Error Correcting Codes & Information Theory with Ron Rothblum

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 Nico and I chat with Ron rothblum professor in computer science at technion Ron is someone who's been working for a very long time on the theory of cryptography and ZK topics and in this conversation we chat about his work on error correcting codes read

Solomon encoding fry ffts Fiat Shamir and more this was a pretty cryptography heavy episode even for this show but I hope you enjoy before we start in I just want to let you know that the application to attend ZK Summit 10 is now open the event will be happening in London on September 20th and as always we aim to bring together the top researchers engineers and practitioners working on ZK to share their latest research and new findings so if you're interested in attending be sure to apply that is the only way you get access to tickets so I've added the link in the show notes and hope to see you there now Tanya will share a little bit about this week's sponsor Elio is a new layer 1 blockchain that

achieves the programmability of ethereum the privacy of zcash and the scalability of a roll-up if you're interested in building private applications then check out Elio's programming language called Leo Leo enables non-cryptographers to harness the power of zkps to deploy decentralized exchanges hidden information games regulated stable coins and more visit developer.alio.org to learn more for questions join their Discord at elio.org forward slash Discord so thanks again Elio and now here's our episode [Music] So today we're here with Ron rothblum a professor at technion and someone who's been working on the theory of cryptography and ZK topics for the last 15 years welcome to the show Ron thank

you for having me and we also have Nico here to help co-host this one hey Nico hi Anna hi Ron so this interview came about because I was having a conversation with Dev oja talking about potential guests and he he thought it would be really great to have you on Ron and his reasons were kind of like you do all these interviews about present day snark work but you might be missing some of the earlier stuff and so he thought it would be cool to have you on also potentially to talk a little bit more about information Theory and then he also thought maybe error correction codes so I know where you have a lot to cover and we're very excited to hear more about you maybe we can get to some of those as we go so Ron why don't you tell us just a little bit about yourself what

was it that got you excited about this field and yeah how did you get to the place that you are today um okay so a tiny bit of background so it's back about 15 years ago I had been working um in a company doing some uh crypto engineering actually worked with Kobe uh there for for a short time so I know Kobe Gerkin yeah wow nice so much other from a long time back um and I didn't like it was like really low level crypto engineering I didn't love it and I went off to do a masters and I thought I would do some sort of uh Theory mathy kind of thing thinking about algorithms or something I really didn't think I would do crypto because I did not love the crypto that I was doing

before um but I went anyway and I did a masters at the white swan Institute and I took this course on foundations of cryptography which was given by Odette godrej who is one of the sort of uh I would say main leaders of the foundations of cryptography in general and specifically zero knowledge is one of the inventors of you know the the famous three coloring protocol it's the first piece of the general feasibility results for zero knowledge and but that gave the the course it was is you know outstanding I really really loved it it actually shows the protocol using you know physical transparencies it's uh really something uh a sight to be seen what do you mean physical transparent what does that mean think

about the 80s um I don't know if people were alive then that um where you have like uh a projector and you have like a transparency yeah that you would put and project so when it's really perfectly suited for the three coloring protocol so you draw the graph without colors on it and then you put the colors on top and you put another piece of paper hiding the colors okay so it actually just like runs the protocol to the show oh neat yeah that's uh it's really nice anyway it was a it was uh fantastic and I started working with him I ended up doing also my PhD with him I did a postdoc at MIT and came back to the technion so what drew me to the field is a an amazing course given

by Odette yeah and I to be honest I just really love the math underlying it uh it's challenging it's interesting it covers a lot of different fields in particular error correcting codes that maybe we can talk about um so it's been a blast so far is it also because like the fact that it's very very Cutting Edge or I guess a lot of research is very very Cutting Edge would it be the fact that it's getting used or applied uh I think research by definition is sort of Cutting Edge um no it is not at all about it being applied to be honest I mean when I started working on this you know 10 15 years ago it was no one thought I think maybe except for at events on a few

others if you look back like 2008 2009 people did not think that any of this would be possible no fhg the first like idea basic idea of an fhg scheme was coming out and it looked like you know it became from like uh something totally you know we had no idea how to do it it just became went down to science fiction but still science fiction you know so yeah like a feasibility uh idea so that was not what drew me it is something that nowadays that it's happening I find it really exciting and it's sort of what I like to do is for it to motivate my still like Theory research so the fact that it's being used raises some fundamental questions and if I can frame these questions as something neat as a

clean Theory question for which we don't know solution that is the kind of thing that I really like to to work on I'm sort of curious like how much of the actual implementation and Engineering or like almost like the research that comes out of that does that filter back into what you're doing or would you say the theory side is just its own track and it and it just kind of plows on doesn't need to kind of get that input because I know like research on the industrial like the industry research and the implementation there's a big back and forth there but I don't know about just pure Theory uh definitely I mean especially so I'm getting sort of inspired for my questions question that I'm working on uh from practice and I

see the things that practitioners or from my endic uh sort of engineering research that's going on and improvements that are happening and it can be kind of concrete I've had some works on uh linear time proving that have come out of that and it was sort of understanding what currently can be done and can I frame a clean fear question for which we don't know an answer and then try to work on that so definitely it's been from my perspective back and forth which protocol or project like who was using that that kind of gave you that feedback loop I wonder if it's anyone we know um so so so I mean hard to trace exactly back but I mean I was certainly aware of so so Justin Taylor and and his

co-authors had this like CMT protocol which is an improvement of gkr uh are there is another rothblum which happens to be my brother guy um so so definitely it was uh on my mind and and I understood that it that it's uh something that people in practice are really interested in and maybe this is jumping ahead thinking about sort of error correcting codes what are the bottlenecks why people are are sort of only using specific types of air correcting codes nowadays um made me start to think of you know how do I bypass these barriers you just mentioned your brother who's also a cryptographer who got into it first he did he did okay uh it was actually gave

me motivation to sort of not join the field so we won't be like uh stepping on each other's toes it kept you away a little bit but then you know I did was just too charismatic so nice yeah so you said you started with an experience in practice and you disliked sort of the very low level practice and then you went into Theory yeah and now what's happening in the industry research like more practical world is feeding back into theory of it do you do you feel dragged to practice ever or you you really have a dislike for it then stay away I mean this like is too strong of a word it was just like not my forte uh okay fair um and it was it's also like was very

different from like relevant things that are happening now so I certainly find the fact that these things are becoming practical super exciting and if some of the ideas that I have end up you know through some papers uh I think this happened going into practical work that that's fantastic cool so a few episodes ago maybe a little over a month now um Arielle gabizone and I went through this sort of Trilogy of snarks that he had in mind and I know we spoke just before this episode you mentioned you had heard it that was one of the episodes I was hoping you'd listen to Because I Really wondered what someone from your perspective who's been working on it from where you have been working

on it for so long how you would interpret that if you agreed if you see things sort of differently or if you're kind of like Focus like if you look at big breakthroughs are you looking kind of at a different level of the stack so it's an interesting question um I think from a theory perspective if you look at the basic question of uh things like succinct arguments uh snarks and so on from a theory perspective you could say this problem was solved in 92. that's what people developed this 1992 1992. okay so so people developed this extremely strong tool called the PCP publicly checkable proof um they knew how to do Merkle trees on top of it you do that put on fiatrimir featuring from 86 and you have yourself a snark

um and that that was all well known in um 1992 and it was also considered something that has no chance of ever being feasible what I think happened in this development of the trilogy and so on is I think people sort of found ways to get improvements on speed by sort of Shifting to different ideas this idea of linear pcps um Iko and uh um you know growth and so on the building on top of that and these gradual improvements have more hope and more interest and from some of from my perspective the idea is that this eventually led to nowadays are really going back to some of the ideas from the

early 90s so some subjects-based things um but you have to go through all these steps in between sort of give you enough hope that this thing is indeed doable going back to that time though could you have just combined them and it would have worked fine or were there some other breakthroughs that needed to happen for these to be like reincorporated into the proving systems so it depends on your definition of the word fine um there's the theory definition and there is the practice definition okay um the theory they're fine in theory yeah so the the basic theory definition says the proof runs in polynomial time um but the practice definition says that you know cubic time is a No-No mm-hmm

um but this sort of from my perspective uh so when I said that it was soft problem in the early 90s I meant that it was fine in this like very uh broad Theory perspective but now that there's an understanding that there's a bottleneck of prover time and practice this raises a theory question of can you get the same result that we had in the 90s but with uh quasi-linear time proof or a linear time prover so that that is something that I've been working on I'm really interested in so when you're making this distinction between like the theory and the practice does theory consider things like pairing based cryptography or does that fall already too much in the realm of practice no absolutely absolutely absolutely does and I think uh a lot of these papers

some fall they're right on the edge of theory and practice a lot of these papers and and a lot of the people doing them especially if you look at some like uh aliquis's papers he often has a theory paper followed a little bit later by a practice paper that builds on the theoretical idea um he's someone who's really is very good at like sort of thinking of a conceptual idea and articulating it as a theory advancement but then also trying to build that into a system yeah the reason I was bringing up pairings is because so Ariel's Trilogy is very most based around pairings and sort of okay that was the pairing-based Stark Trilogy yeah I think here we have a chance of talking about everything else that's sort of

been excluded from the pairing land like Stark stuff like Starks and the work of Benson is sort of almost you know hidden away in Ariel's Trilogy and I think that's maybe closer to the stuff you've been working on absolutely yeah and I mean I I think you know when when Eddie Benson when he introduces himself or at least the way he used to it was as a complexity theorist not as a cartographer because that's what he did for you know like you know that's what his PhD is about and what he did as a researcher until he he did the cyclic shift and a lot of uh things like the basic you know fry and stuff that starkware is doing is based on um sort of deep Theory and deep theoretical advancements that happened in you know in the realm of pcps

should we take a bit of time for I guess definitions or making sure that we know what we mean when we're saying complexity Theory information theory that kind of thing sure so uh complexity theories uh sort of broad fields that is trying to understand computation so what tests can be computed and at what cost um and what has cannot be computed and you can vary the type of resources that are available whether it be uh time space uh depth if you're talking about circuits and a lot of uh the field actually has developed around proof systems so if you think of you know the most basic question I think in in computer science arguably also in math

is the P versus MP question this is clearly a question about the existence of of uh or what can proof systems do and what they cannot do and the advancement of the our understanding or suggestions for the notion of a proof have these have lots of Notions like interactive proofs pcps and zero knowledge which nowadays are having a big impact in practice but they've had an enormous impact throughout the years on this entire field of computational complexity Theory um generating entire subfields within um so I don't know if people are aware of this but this this tool called pcps it was in introduced in the early 90s for about 20 years almost all the research that went into it was about its

relation to a totally different field in complexity Theory called hardness of approximation hardness of approximation yeah yeah so this is a field that deals with showing that some problems are hard not just to solve but even to approximate so this is kind of using this sort of Machinery that we think of as very positive pcps it's a useful tool it was being used to show lower bounds to show that some tasks are hard so anyway that was uh me trying uh to articulate that field of complexity Theory can I ask can I ask one thing before you move on yeah uh people use the term pcps I've totally had this defined for me but what does it stand for okay so it is uh

probabilistically checkable proof okay and this and this is what you mean by probabilistic so you're trying to approximate the hardness no no not that okay coming from somewhere else let me actually okay uh maybe remind definition of a PCP and um I think maybe in retrospect it would have been a better name for this object would have been a locally checkable proof so the idea is um you have a proof that you want to check it's written down but you're only allowed to read a very small number of bits from this proof and based on the small number of proofs you should be convinced is the statement that you care about true or false it sounds paradoxical like how can you get any information from reading a small

number of bits but miraculously we can build this kind of thing and iops or interactive vocal proofs are generalization of this notion in which it's not just like one static proof from which you read a small number of bits but it's sort of this interactive thing where you send a proof read a few bits uh send another proof read a few bits and so on so going back to the why is it so the reason what is the hardness of I'm sorry I'm blanking on what you just said harness of approximation it's nothing to do with the word probability and oh it is it is it is but uh oh it is yes definitely but uh so first of all the the why is the word probabilistically there because the places that you choose to read from the proof are chosen at random

okay so there's some process that choose these points um and maybe to remind the readers why are we talking about pcps in this context so there's a way to take a PCP which is this long proof and turn it into a succinct argument basically you can do something like commercial tree um for the entire proof and then you want to read the points the the few relevant points you can open up the miracle paths and uh this basic idea is underlying all iops that are around why is this related to hardness of approximation it's it's a little bit technical but the point is that you're saying the fact that this PCP exists means that there's a reduction mapping any problem to a

problem in which there is sort of this Gap if you start off with something that is true you get this proof that kind of no matter where you check you'll see truth whereas if you started with something that is false you get some something in which in most places you see something that's false but in most places so you've sort of generated this kind of Gap and if you could solve this Gap problem you could solve the original problem as long as you believe that the original problem is hard it means that even solving this Gap problem is going to be hard okay and that is the connection to hardness approximation which is a huge field inside a complexity Theory and not related to cryptography related in this indirect way okay and the fact that the same technique could be used for that

and that's maybe where the boom of the 90s came from was it the 90s 80s 90s and interesting so it's very much borrowing from another field yes and and I mean there have been amazing developments Amazing Ideas in that field which I think could very well end up being used also in the context of our sort of use of pcbs cool so there's a lot more to bring from that field that we haven't been using yet oh that's very interesting that's very promising yeah let's move on to another Point Nico you just mentioned which was information Theory so I know those two words and I feel like people have mentioned this on the show before it's the mathematical theory

of communication I don't know if that that's where what I found on the internet I'm not actually clear on what that is so you find it beautifully you think um mathematical theory of communication is great it's a big field there's a lot going on there very deep and beautiful math I think the most relevant part to proof systems is uh error correcting codes which is sort of a subfield within information Theory and that again like underlies essentially all the sort of underlying interactive Oracle proofs pcps and non-cryptographic components that go into building uh stuff like snarks so this is where would you say that's the primary

within the information Theory field is the error correction or error correcting correction codes is that the primary link then to cryptography and ZK or is there a lot of I sort of picture information theories this big umbrella term like are there other things that we're already using in snarks that would fall under that yeah I mean there are definitely so information Theory gives a lot of tools so I'm sure people are using things like uh Notions of entropy and so on to argue about proof systems but as a sort of a big hammer that's being used I would say that error correct encodes are the number one thing okay so I think this is a really good moment to introduce error correcting codes uh tell us what this is okay so uh error correcting codes are this really

basic object in computer science the idea is the following so suppose that Alice wants to transmit a message uh to Bob but she wants to do it over this noisy Communication channel okay so Justin if you just send a message in the clear some of the bits could disappear could flip and you're unhappy so what you would like to do is to First encode the message in such a way that even if this encoded message gets partially corrupt Bob can still recover the message and this basic idea sort of comes from Shannon's amazing work in the late 40s introducing this problem and it's been extremely well studied since then so we have a fantastic understanding of error correcting codes

um maybe just to give an example so people have in mind so that maybe probably the most famous example of an error correcting code is what's known as the Reed Salomon code in which code words are basically just low degree univariate polynomials and because polynomials don't like each other so much that you don't like to agree on a lot of points if you take your message you encoded inside a polynomial if Alice does this and sends over this polynomial to Bob even if a few of the coordinates are flipped let's say we know mechanisms for covering the underlying polynomial and the underlying message and that is this error correcting code yes so this would be an example of an aircraft probably the most famous one interesting

yeah I think and this is to um territory that's often covered when you have like snark tutorials these days it's very much like oh here's a polynomial IOP and here's a polynomial commitment scheme and everything revolves around polynomials right so so but yeah we're sort of generalizing right so everything like stock market is is doing that's the best of my knowledge nowadays is based on this read settlement error correcting code and building this mechanism around it so that you can prove statements when you're encoding your witness or your computation using this type of code but there are a lot of other great codes around there and we have yet to understand how we can use them in this context but we have some new ideas so a lot of the linear time proving is coming

from from a better understanding of that so there's a lot of things that I would like to unpack and get to so one thing you mentioned the the Benson's homework like fry and Fry actually stands for fast read Solomon as you're saying read salmon could interactive Oracle proof of proximity so this thing that I interactive Oracle proof of proximity I'm curious to chat more about out sort of what its role is within the snar construction and how it interacts with the error correcting code and then the other thing is obviously uh talking about some more recent error correcting codes and some more recent works that use those so here's here's a basic template of how to build an IOP an effective Oracle proof you take your think of it as the witness or the entire

computation you encode it under an error correcting code and uh you send that as your first Oracle okay so you send over that entire thing and now you want is now you want a couple of mechanisms one mechanism that you would like is to check that what the the message that was sent was indeed a correct code word okay so that's one thing that you would like and once you have that guarantee that it's a correct code word then you want other mechanisms on top that allow you sort of to check the this codeword represents a correct computation okay fry is basically a protocol solving the first problem so you took your computation you encoded it under the read summon encoding now you would like a protocol that lets you check that

something is indeed a valid read sum and encoding so that is exactly what fry does okay so proximity there is proximity to a code word okay so I should correct the word exactly because it is approximately what so what fry guarantees to you is that the message that was sent is close okay to a valid code word but in this context close is sort of good enough I wonder if you'd if you'd allow me a little bit of a step back to the definition of error correcting codes because you say it's encoded with read Solomon so that means Solomon encoding but I I guess like I saw that more as like an action like like some sort of tool but when there's

an entire Paradigm that encodes it in that way I don't I don't actually understand where it's where the error correction happens like so let me try to be a bit more precise so okay think of you know Alice poor Alice has her messages and she wants to transmit it what she's looking for is a function it's a function mapping from a set of possible messages so we think of this as the message space intercept of possible code words this is the code word space okay we definitely want this function to be injective because given the code word you want to be able to recover the message but we wanted to be Beyond injected we want to have the property this property called distance that if you take any two code words in the codeword space so if you take any two messages and

encode them you want the resulting code words to be far apart from one another and the reason for that is that you know think of Alice taking a message and encoding it it's sending it if the number of uh bit flips say that happened is relatively small and you have this guarantee that around the so think we have this code word that Alice sent the message that is received by Bob is going to be close to it right because a number of flip of bit flips let's say is bounded and then as long as there are no other code words floating around near to the code word that Bob received then at least theoretically should be able to to recover the codeword then hence the message so here distance is a measure of

how many bits are different right yes this is called Hamming distance actually Shannon was looking at a situation in which each bit is flipped with some probability whereas here we're just bounding the absolute number of bit flips which is sort of more relevant to when using error correcting codes to build proof systems I'm sort of trying to go back to the initial definition though which which was like if it were if this message were to be somewhat corrupted it would still be recoverable I don't really know I don't understand why the proximity matters for that okay so imagine that you let's go by counter examples suppose that you have an error correcting code in which you have two messages which Mac to code words that differ only on one

bit okay not suppose that one of these messages else attempted to send one of these messages and uh a coder is received by uh by Bob but now Bob is uncertain you know did that bit flip happen or did it not and depending on whether it happened or not I say then the you know he's confused about what message Alice meant to send so this would be not very easy to recovering like a bad error correction correcting code yeah this would be a terrible correcting code okay so the property that we want to realize that for if you take any two messages and you look at their encoding they're going to be the encodings will be far from one another I see so so that is the basic definition of an error correcting code okay I'll give you a bit of a visual

example of how you can pick up on an error very quickly so if you're using read Solomon codes so polynomials you could very well have that your message gets encoded into like a straight line like if you're drawing it in a graph you'll have a straight line right or some graph of a polynomial some nice elegant polynomial exactly things are nicely aligned but then only one of the points is like slightly off from the Pretty line uh so in that case you do know like okay that point is where the bit flip happened this is the error and it should have been on the pretty Lane ah because it's complicated enough like the it would be almost exactly probabilistically impossible that you'd

have sort of like a wrong polynomial exactly if you were to draw a smooth line that went through all those points it would be very high degree so to have a lot of bounces and this is why we're talking uh read Solomon codes or you use low degree polynomials right so you don't allow too many bounces I see it has to be a nice smooth line okay I hope that makes sense Ron I see you nodding so I'm yeah I I like that explanation okay cool [Music] I always and this is a maybe a tangent here I always thought that fry was similar or something to like Fast Fourier Transformations is it it's so it's inspired but that is sort of how the protocol works but it's okay important

for us to understand what is the problem that this protocol is trying to solve and the problem that it's trying to solve is you know I I was sent the prover sent over uh codeword which it allegedly encoded as a low degree polynomial and I want to check that that's indeed the case or at least approximately the case that that's a problem that's trying to solve the way that it does it is inspired by how fft works but the purpose of ffts is something else yes I see okay the outcome I kind of forget what what are the what is the purpose of a fast Warrior transformation again I I learned it years ago in the context of like music technology so like yeah so I I I wouldn't say that's uh it's unrelated

but it's it's not sort of there's a way to frame it so that it is similar but anyway what it what is ffts okay so with polynomials there are two nice ways to view them one is via the sort of What's called the coefficient uh basis or perspective you know to describe a polymer I'll just tell you what its coefficients are so that is one way to view uh Paul Mojo a different way to view the polynomial is you can think of it as kind of the graph that Nico described so just the values that this polynomial obtains on some sufficiently large sets okay so these are two different bases or different two different views of how to uh to look at a polynomial depict them okay and the fft is a fast algorithm a very fast algorithm that lets you move from one to

the other oh okay okay and so what you're saying is fry uses that technique of moving from two views no it's so it has to do with uh I mean that is also true sort of more involved way but uh I'm saying that the way that so the again the golden F50 is what I described to move between these bases the way that fft works is somehow to try to decompose this polynomial uh into parts and work with the parts and so on and Fry's following this also the same basic things trying to decompose the polynomial uh work with the parts and recurse okay so they're both recursive one is a recursive algorithm fries or

recursive protocol both work by decomposing a degree D polynomial into let's say two degree D over two polynomials and sort of combining them or working with them and as you do that which direction are you going are you going from a number of points along a graph with the line thread are you going to the coefficients in in Fry so in Fry you're just working so you start off with uh so you're looking at the evaluation perspective and you're going from a problem with checking that you so you're given the evaluation of something that is claimed to be a degree D polynomial remember you're only allowed to look at very few points yeah and Fry's giving you a reduction of how to reduce that into checking a similar statement about a degree D over two

polynomial I'm sorry I think I was still talking about the ffts I was actually wondering which direction are you going with ffts do you go both directions the reason I was asking is I thought I thought what you were describing was One Direction and that fry was using the techniques of One Direction uh the directions are very related so there's fft which is going from the I guess coefficient perspective into the evaluation perspective or basis is the proper mathematical term okay I mean there's an inverse F50 that does the the reverse and is there one that fry is more similar to I think the forward one yeah I guess so usually people also

think of the forward one it's like a is that that's a 50 and it does look very similar to that say that one again what is the forward one yeah so it's going from coefficient from the coefficient perspective to the evaluation perspective I see so fft by the way is also kind of the reason why it's it's a big part of why people love the read salmon code because it allows for a very fast um encoding of messages so if you view your message as a bunch of uh coefficients and you want to encode them and get the polynomial voila that's exactly what fft does and it does it very very well interesting so why would we want to work with other codes than the read Solomon code if it's so efficient it's so great okay

so two reasons um one is that it's great but it is not the greatest at least asymptotically speaking so the running time of doing an fft if say you have um and coefficients or working of computation of size n then time that it takes to do it is something like order of n log n whereas we know other codes for which the encoding is O of M so you know n log n is pretty awesome but of n is even more awesome so why not so is this where the land of work on linear prover sort of starts coming yes okay another related thing which is sort of more directly related to some work of

mine is that reach Solomon works over a very large field so you need your field to be large enough sort of for your graph that you were drawing to make sense you need the number of points that you can talk about to be at least the message length what this means is that when using read sum and based techniques you need the field to be at least the circuit size the field size needs to be at least the circuit size and and this forces so that is what like a lot of people are doing so that's what stockware is doing but I feel like so it's true that read someone has this property but other codes don't so you have other efficient codes that work over small Fields can we use them and maybe try to support computations sort

of non-arithmetic computations Boolean computations much more efficiently you see and then is there a trade-off between I guess the speed at which you can encode with your um error correcting code and how you do your IOP of proximity um trade-off in terms of efficiency means that if you're using yeah efficiency I guess okay so maybe this is a good time to point out that so read someone has a lot of amazing properties one of them is this uh very fast encoding not not the best but but very good the other one which is really fundamental to all of the IOP constructions is what's known as the multiplicative property okay so so

actually maybe before that let me uh talk about the additive property which is more basic one so right if you take two degree D polynomials and you add them up the result is going to be a degree D polynomial and that is very useful for sort of we use this property when trying to handle think of a circuit that has addition Gates um that is something that's very useful the other very nice property that reads Solomon code as a code has is that if you take any two polynomials and you multiply them Point wise so each point of the polynomial is Multiplied the effect is like you are basically multiplying the entire polynomials and it means that the the degree doubles okay so if you take two degree D

polynomials you get a degree 2D polynomial and it means that if you take so in other words if you take two code words and you do this pointwise product between them the result is going to be a not too bad codeword in itself does that make sense so so it's not it doesn't live in the same code because the degree has doubled but as long as you make your field large enough um it is going to have error correction properties and this multiplicative property is really really key to all of the IOP constructions accept some very recent ones and it is very hard to come by so we have very few codes that have this magical property I see is it a

requirement no I'm sure we can work without it right so I view um it used to be a requirement in the sense that the only way that we knew how to do arithmetization involved multiplication codes so the reason that you hear about univari polynomials and multivariate polynomials uh throughout all of these Works to a large extent to a very large extent is due to this multiplicative property and until you know I would say that roughly speaking until a couple of years ago we didn't know any other way so when I was talking about sort of barriers that we would need in order to get better efficiency I viewed that as a big as a big barrier that we had to overcome right so we have we want this multiplicative property

we have read salmon that has it but read Solomon you know it has its features but it also has its disadvantages which we would like to avoid yeah as we as we talk about all of this and I think Nico you did say this very briefly you know a few beats ago but you know we always learn about the polynomial commitment schemes and Fry falls under that category does that mean that error correcting codes like are all of those polynomial commitment schemes that we've learned error correcting code schemes like is that what those are or is it sort of like some of the polynomial commitment

schemes that we are using use the technique of error correcting codes um so maybe it's worth clearing things up a little because I think there's some some confusion because so we have this uh we haven't let's say we have an IOP and in the IOP we we said that we want to send code words right so um so kind of the IOP site that's what happens you send over code words whether it be polynomial whether it be something else later on what would be interested in doing is compiling this into a succinct argument you don't want to actually send this huge code word you want to send something short that represents it okay that is exactly what sort of polynomial commitments do with respect to the read Solomon code or if you're talking about

unified polynomials or um sort of read mother what's known to read mother code if you talk about multivariate low degree polynomials in general you could think of you know given a particular error correcting code C do you have uh the analog of a polynomial commitment with respect to this specific code C does that make sense sort of so I think what you're saying is like the error correcting code part is sort of bridging between these two sections of a snark so so the air correcting code sort of lives in the IOP land okay and the polynomial commitment is what is allowing you to translate that from the IOP land into a snark land okay um but then why why is fry considered a

polynomial commitment scheme right so so fry the weight is phrase in the way that uh you know if you look at the paper the weights phrase is as a component inside an IOP however if you take fry and you compile it using Merkel trees basically what you will get is a poem on a commitment okay okay so so you can kind of sort of fries is part of this bridging between um let's see if between a polynomial IOP and the snarg and then you can sort of push fry to either side if you push it towards the snark side you view from the lens of polynomial Commitment if you push it to the polynomial IOP you can transform the polymer on the IOP into the honest about IOP okay I think I sort of get it I I it seems a little in the

weeds actually I'd like to share with my mental model there so we were saying earlier like okay read Solomon codes are evaluations of polynomials and you as a verifier you don't want to read the whole thing you just want to check a few values so when I give you like a short commitment to something you want to know was it a commitment to read Solomon code or not if I translate that into polynomial and I could reset it as was this a commitment to a polynomial so this is where like fry acts as a polynomial commitment scheme because it makes sure that some commitment the values behind that commitment are actually the evaluations of a polynomial or close enough does that make sense

kind of kind of okay I mean it sort of follows what I was trying to say there which is it sounds like it fry out of context of a stark it's just it's not necessarily doing all that its name pertained like it's acronym so you're translating the name right you're replacing read Solomon by polynomial you're yeah the infry stands for an IOP or more accurately an IOP proximity um you can the point is you can take any IOP in particular this one and compile it using Merkle trees and you get an argument a succinct argument so if you did that directly to fry rather than the entire protocol what you end up getting is a polynomial commitment I still don't

get I still don't understand if the Reed Solomon part of it is still in it yes is that always there it's always there yeah yeah you read someone whenever someone tells you read someone just delete replaced by the word polynomial in that context though in any context in all contexts oh okay okay is it just equal to univari polynomial think I almost get it I probably at some point need to see this on a whiteboard but thanks so much for explaining it of course I wanted to I think Circle black is something we're talking about just now so we're still in Reed Solomon land what what comes after what kind of codes have you been using in your work on the near time provers okay so going back to what I was saying before we we seem to be

having this barrier where we need this multiplicative property on the one hand but codes that have it are a tiny bit slow We would like to use faster codes that are available I slowly mean the encoding right then coding so fft is awesome but uh we have this annoying login Vector that we would like to get rid of and we know that in principle we have codes that are faster so I was working with uh according theorist noga Rons V also also in Haifa like me and we have this idea which we call code switching which is saying the following so instead of encoding the computation using the slow code will encoded using the the fast code grade so far the problem that we run into is that we were

we wanted to use this multiplicative property which we don't have anymore so what we proposed is to pretend as though we did have as though the message that we had sent was indeed the polynomial the read summon encoding you send a super fast encoding of whatever you want of the computation let's say The Proven verifier pretend as though what had been sent was actually um you know a polynomial polynomial coding around the protocol as if it were that at the end of the day now the verifier wants to access let's say a point in this polynomial and our observation was that you can now run a sub-protocol proving that if you took the the message that is encoded within the super

efficient code if you had encoded it as a polynomial and looked at that point you would have seen a particular value and we show that we can do this sort of using subject-based techniques well okay and does this come at a big cost for the verifier or in proof size um not not so much so well it adds more more interaction because you need to run a sub protocol but that you sort of can filter me away later on and this is uh so this basic idea so we had this paper uh with noga in which we did this in the context we had that we were constructing iops that are extremely short so the amount of communication in the IOP is

just barely barely more than just sending over the witness which is what you would do if you had like no locality constraints so it's say 1.1 times the length of the witness and the ideas there was to use a very efficient uh encoding in terms of like number of bits for the first message and then later on switch to to the polynomials but but later on this basic idea was used by a paper by John boodle alakiesa and and yes Groth and they were saying you know at least the way I view what they were saying is send construct the first encoding using a very very fast code one of these the linear time encodable codes pretend that you had sent the polynomial run the protocol and then verify

and then this work of Justin Taylor and others breakdown Builds on that and Orion a more recent one Builds on that so in all these papers the basic thing that you want to say what you want to have is a very fast linear time encodable code with this property that you can sort of after the fact at the end check properties related to you know if I had taken this message and encoded it as a polynomial would I have seen something it turns out that that property is relatively easy to get you can use it using basically you can transform any efficient code into a code that supports that with relatively small overheads an operation called tensoring and this is what uh all these linear time uh poor uh

Works do tensoring so so they start off with an efficient linear time and quotable code and then they do on top of that they do tensoring and I think there's now uh a lot of room to try to optimize the basic linear time recordable code that you're using is is tensoring a known phenomenon tensoring is uh it's a non-phenomenon it's an amazing thing I mean in a sense whenever we say sub check would be actually mean it's tensoring um it sounds complicated but it's actually really simple so tensoring is a way to take a code and build from it a new code that has some amazingly nice properties okay and the way that the construction works is really simple so suppose you already have a great code that you love

I'll tell you how to build a new code from it it's called The tensor the square tensor of it or whatever so right so we already have a code we're trying to build a new and better food the way that this new and better code works is you're going to look at your messages as matrices think for example of uh it's simplest if you think of a square Matrix and now you're going to go to each one of your rows and encode it encode the row using the code that we have right so we start off with some number of rows we got some extra columns kind of because we encoded these rows and now you go to each one of both original columns and these new columns and you encode them again using this code I I wanted to give like an example of why like uh sort of a concrete

example so if you take the Reed Solomon code and you tensor it and if you tensor it more than so if you transfer it once what do you end up seeing is a bivariate polynomial if you tensor it a lot of times what you end up seeing is a low degree multivariate polynomial and in fact if you take a Nico's example from before the read settlement code with the line that's a very that's a encoding for encoding sort of I want to say either one or two bit messages um if you take that very basic code and you transfer it enough times what you end up get getting is sort of multilinear polynomials and this tensor operation is what really underlies the subject protocol did that make sense it does yeah I'm just taking a second to absorb it because yeah it is what we're

doing when we're putting all our points into like the Boolean hypercube but then we're still like defining your polynomial in a way bigger thing yeah I I never thought of it this way yeah so in that sense when you do tensoring you have some kind of blow up yes of the original code okay yes so it kind of in terms of the parameters of the code um so you get a lot of magical properties from this so you get the subject protocol you get um something called local testing which is an analog of fry in this in a situation the cost comes in in two ways first of all in terms of the amount of redundancy that you've inserted so previously said you were encoding K bits into n Bits now

you're encoding K squared bits into N squared Bits And if you look at it as a ratio the ratio is kind of squared right so if you look at K Over N now it's K squared over N squared if you were say uh you have this this ratio was a half now it's a quarter so you've inserted sort of more redundancy your code is longer and you're a little bit sadder so that's one place where you pay a little bit the other place that you pay is in terms of this notion of distance that I was talking about so how far apart different code words are from one another so it turns out it's not a hard exercise to show that in terms of like the relative number of bits that are different between these messages is going to also Square

so if you started off with the code with usually we use Delta to indicate this parameter so it's the like the percent of bits that uh you have to flip in order to go from one code word to another the minimal number of such a bit flips and that percent is going to square which is a good thing right I know it's a bad thing oh bad thing yeah so you're you're paying both the squaring thing happens both in terms of the the redundancy so you're paying there and you're paying in terms of the distance but you're gaining a lot of uh amazing properties so if I then look at the IOP as a whole that we're starting to build here is that going to translate into like some soundness error yeah essentially okay yes so

um the the distance is closely related to to the soundness error and because we are taking uh some limited hit in terms of the distance this will you know will pay in terms of sounds error or rather we will need to compensate for that by doing some sort of repetition or amplification to to bypass that let's talk about some of your recent work because I feel like we've spent a lot of time talking about the error correcting codes which is useful but I feel like Yeah from what we when doing a little bit of research on you Ron there it sounded like there was quite a body of work and quite a few threads that you were excited about so yeah why don't you tell us about some of the other work that you're looking at sure so one body of work that I've done a lot a lot of

work on is related to the Future mu transform so maybe it's worth to quickly remind the the audience what that is so it's basically this magical method of taking any interactive protocol it needs to satisfy one thing that I will say in a second and take this interactive protocol make it non-interactive so instead of a ping pong back and forth between verifier and Hoover boom it's a single message of Hoover sends uh can put on the blockchain or run those where and that's it so so it's fantastic the only like uh star that I had to add there is that the original protocol has to be what's called public coin which means that throughout the protocol all the verifier does is just toss random coins and tell the results is approve her no like fancy messages that the

verifier needs to send and the basic idea of how to do this is that rather than the verifier actually sending out these coins the approver is going to compute them by herself by taking some very complicated hash function and applying it to basically everything that the prover saw so far throughout the the execution and the hope is that because so if you sort of follow this logic you apply you apply the hash function to everything that happened in the execution and only then you get the result then you can not sort of tailor your previous messages for this result because if you were to try to modify previous messages then the hash value would also change okay so so

that is the future mu transform uh we've known of uh not since uh this work of uh atmosphere and Andy Samir from 86 and in terms of security there's a lot to be said there so first of all we know that this thing is secure and the in the random Oracle model so that that has been has been shown and that is why it is incredibly popular in practice so people are using it all over whether it be in zero knowledge proofs or in signatures that we're all using so it's incredibly popular um in theory land we are somewhat unhappy with this random Oracle situation we would like to base things on you know standard model can we do it based on discrete log or factory or

something concrete why do you dislike the random Oracle model Okay so one of the reasons is that there exist examples of protocols that are interactive public coin protocols which are you know sound secure they're great but if you apply future mirror to them no matter what hash function you use the resulting the result is going to be insecure okay okay so there are specific protocols where if you apply future mirror no matter in what way the end result is going to be insecure are these protocols kind of built for that property like are they slightly pathological in the way they're made so yes and no um so the first protocol is uh so this start with the work of uh rankanetti of

the godrej and Levy and boss Brock had a related work which doesn't sort of more directly uh does this and if you look at those protocols they are extremely contrived you think you know these were exactly built in order to be insecure when you apply for me but nevertheless it shows you you know the reason why we think future mirror is secure is because it just looks like it should always be secure and not because of any special properties of the protocols what they were using that's what I think you know Common Sense tells us these counter examples are saying that the common sense does not suffice if this thing really is secure it has to do with some specific properties of the underlying protocols so one related thing that I wanted to mention is that

uh I had this uh work with with other co-authors a couple of years ago where we actually gave an example of so like going back to this template of how we build snarks we take something like an IOP we compile with Merkle trees and we get a we get a snark so we gave an example of an IOP for which you follow this Paradigm of compiling with the Merkle tree you apply fiatramir it's going to become insecure so it's a secure IOP but if you go through all this Machinery the end result and non-attractive feature mere thing is insecure in other words if when applying feature Mir you know you you take the IOP as a black box which you don't want to look

into and understand we have counter examples for When Future mirror when doing this is insecure when you say sort of secure and insecure is are these binaries like is it like it's extremely insecure like to be insecure it's broken unusable yes there is a false statement for which you can efficiently construct a proof that is going to be verified with probability one so strongest possible attack you can imagine very very insecure got it okay very very the most insecure I can I can imagine it's broken it breaks it absolutely not a little bit all the way okay um not a little bit yeah I just wanted to be sure yeah so one thing like I will

I will give some hope and then take it away so One Reason for Hope is even this like oh no um this IOP that we have constructed is itself it looks very weird there's a component there that if you look at other iops they don't have it and it's it's it's baked in there as a trapdoor to to kind of to ruin it and you'll say okay no good we usually don't have these in in iops the reason why I'm going to take the hook away sorry about that is that this component looks to me it looks very reminiscent of uh snark composition a recursive composition so there's something about some form of diagonalization of running a program on itself as input which is going on there which you know if you just look at an

IOP you don't see that but when you're starting to do recursive composition you do see this kind of thing which I find worrying um I've tried to think of attacks I haven't come up with any so far but it certainly would not uh I would not be shocked if there was an attack based on this and when you say you called it sort of recursive constructions of snarks but are you also talking about like accumulation and yeah bolting scheme type stuff like and I talked about recursive composition so you have a smoke okay um or IVC or whatever you have a a snark and then you start to prove statements about the verification of the snark itself okay after the snark is finished not you're not talking about this sort of like internal accumulation or I don't

know yeah everything is a little bit like too concrete I think to concrete in the sense that I don't it's hard for me to see how to frame things in to view them similarly okay okay is it about this issue of so we have our snorics in the random Oracle model and then we want to do a snark of a snark we actually need the circuit or a snark verifier so our random Oracle no longer is a random Oracle it's an actual circuit yes is that kind of the problem that's linked to it yes and this is all based on uh it's hypothetical just it feels to me okay similar to uh this contrived examples that we have I would have loved to to show an attack I mean maybe others

would have been sad but I would have been happy um I have yet to do that so far so that is you know it's all hypothetical I mean if we realize that it's insecure I think everyone's better off if you find the attack right right what was you sort of started to talk about like do you have an alternative you said you don't want the random Oracle model right I think you mentioned what you would prefer to have yeah so there's been a huge body of work on trying to make fiatrimir secure when we have a hash function right what if we use that the hash function based on one of our favorite hash functions like Peterson or uh something based on lattices or something like that can we use a concrete hash function in order to do future mirror and just

prove that it works and even in theory of land where we are a lot more flexible in terms of we don't have things thing to be completely efficient uh we didn't know how to do anything positively we had counter examples we have these like contrast counter examples and we didn't know how to do anything positively until 2016 I think okay and then we had this paper showing for the first time uh a concrete hash function based on a very strong but still concrete cryptographic assumption however this and all the follow-ups that I'll mention in a second they work only for particular nice protocols so they work as long as the interactive protocol they start off with is a proof rather than an argument so it

has Security even against an unbounded proof so for those type of protocols since that work and we've had amazing follow-ups since we basically at least in theory land we now know how to instantiate Future mirror securely but only for that limited set of protocols do you have any examples of those what were the nice ones the next one would be gkr so gkr is an interactive protocol for all bounded depth computations and it's an interactive proof with statistical soundness and so we know how to do feature mirror to gkr for example okay we even know how to go how to go beyond that um but it is so it's a very rich class but still limited and also in terms of efficiency the hash functions for which

we know how to do this are essentially based you could say that they're based on fhe so they're not going to be completely efficient what was the very strong cryptographic assumption you're referring to um so the that was in the earlier work it's still it's been improved since um in the early work we needed to assume that some sort of encryption scheme was optimally hard meaning that there is basically no attack better than Brute Force in some quantitative way and even stronger than that but it was a basic feasibility result it showed that in principle something that we did not know at all could be done based on some assumption nowadays we can based it on an assumption called learning with errors which is sort of the Cornerstone of all lattice based cryptography and a

very widely uh studied assumption so what other open problems or topics themes are you interested in these days are working on um so actually I'll go back to something we were talking about before with the fish improvers because there's a question that that's I'm really interested in and I think it's also very relevant to practice um so these works that I mentioned before breakdown Orion um bbcg or from before that which achieved linear time perverse they're all considering arithmetic circuits over large fields and they over this in the setting they indeed achieve a linear time prover the thing I was curious as you know an

innocent theoretician is what can we say about Boolean circus right so we have hash functions sha or whatnot that are natively described as Boolean circuits One Direction that I think that the industry and people are taking is you know these are not nice functions because they're not friendly to other studentization let's invent new hash functions and I'm saying you know let's try to work with these what can we do in terms of proving correctness of Boolean circuits and they're the the ideas underlying the linear time provers uh sort of uh break down I had a couple of works on this and the first work was just also with noga we managed to construct even in this harder

setting of Boolean circuits uh strictly linear time prover but the downside was that the soundness error was a constant rather than being some you know negligible function which is what we prefer so that that was unfortunate I mean we were very very happy to have the linear time prover in the setting but the soundness error was uh large I had a follow-up with uh Justin Holmgren in which we could show that you can get two to the mind so if you take this basic protocol with noga and you repeated Lambda times you're going to get 2 to the minus Lambda sounds error which is good but the running time now becomes you know size of circuit times Lambda I have a work with Justin holgren in which we managed to reduce this to something

like n Times log Lambda okay so that is sort of framed in the right way it's an exponential Improvement um in terms of the pencil right instead of taking if you think of concretely instead of multiplying n by 128 you're multiplying n by log of 128. so that is a big Improvement but the basic theoretical question for me is can you construct iops and succinct arguments where the prover is strictly linear time and the soundness error is negligible that is something that we do not know how to do and I think that has the potential to save another order of magnitude uh in terms of improvement potentially also for practical uh linear time proving so was this for Boolean

circuit specifically or for all circuits so it basically works for it kind of takes away the restriction on the field so it can work for any field that you like okay the hardest case being when the field is just 0 1 F2 that's the hardest case with the most challenging case but it works for any field that you like I I think you've mentioned a few times someone named noga can you maybe introduce who that person is yes it's a noga Rons V with a fantastic coding theorist at the University of Haifa um and I mean we cooperated on these things because there's this very intimate connection between error correcting codes and pcps and iops and I think this joint perspective of coding from her side proof systems uh for me is what sort of enabled uh these

developments and I think that nowadays if you look at like optimizing the proven time and constructing better error correcting codes I think a coding Theory perspective is really really important uh there well cool well thank you Ron for walking us through complexity Theory information Theory error correcting codes all the way to Fiat Shamir transformation security um yeah thank you so much for sharing with us all of this information and all of this Insight thank you so much for having me thanks yeah this was a pleasure likewise and I want to say a big thank you to the CK podcast team Henrik Rachel and Tanya and tour listeners thanks for listening foreign