Episode 321 - STIR with Gal Arnon & Giacomo Fenzi

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 g from The wisman Institute of Science and Jacko fenzi from epfl they are co-authors of the paper entitled stir read Solomon proximity testing with fewer queries we discuss how they came to work on these topics and how the work

came about we then dive into the history of fry we tease out some of the nuances of fry and then introduce stir as a replacement to fry that include multiple optimizations drawing on previous work that improve the performance now before we kick off I just want to let you know about an upcoming hackathon we are getting very excited about ZK hack krao is now set to happen from May 17th to 19th in kco in the spirit of ZK hack Lisbon and ZK hack Istanbul we will be hosting Hackers from all over the world to join us for a weekend of building and experimenting with ZK Tech we already have some amazing sponsors confirmed like Mina 01 Labs polygon alzero scroll Avil nethermind and more if you're

interested in partic participating apply as a hacker there will be prizes and bounties to be won new friends and collaborators to meet and great workshops to get you up toate on ZK tooling hope to see you there I've added the link in the show notes and you can also visit ZK Haack cow.com to learn more 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 for a truly secure internet Alo has interwoven zero knowledge proofs into every facet of their stack resulting in a vertically integrated layer one blockchain that's unparalleled in its approach 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 this is an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at al.org and now here's our [Music] episode today we're here with gar Nan from The wisman Institute of Science and Ja fenzy from EOL poly technique Federal de loan or epfl they are two of the co-authors on the new stir work stir read Solomon proximity testing with fewer queries welcome to the show both of you thanks for having us thank you for having us we have Kobe as the

co-host for this one hey Kobe hello so I think I think to start off we should get to know both of you what are you studying and why are you studying and working on the work you're doing okay maybe I can start on this so yeah I'm jao I'm a second year PhD student at epfl and I'm working with Alexandro K and my research is basically everything that your knowledge like um so interactive proof interactive Oracle proofs uh cryptography latices anything that hopefully ends up in making efficient proof systems at large uh maybe you know my kind of like background is that like I like cryptography I like having this kind of intersection between math and computer

science and then you know there's only very few places where you were able to do things which are mathematically interesting and also end up having some practical impact so I just kind of continued going this path and you know I ended up starting my PhD and I'm pretty happy with how things have been going interesting were you specifically interested in zero knowledge type things or would you say your general field is somewhat outside of that well so originally like I was like very much into like pure mathematics category Theory you know which kind of leads directly to elliptic C and kind of stuff so that kind of like was my overall introduction into cryptography and then originally I was introduced by to General proof during like my bachelor the same like a very

cool concept like very counterintuitive and so I kind of started looking into it and at the end it was a bit of a marriage of convenience a part of it was like the fact that was very cool I really enjoyed the math and a part was that a lot of the work that I had been doing during my master was on like isogen based cryptography which turned out to be like less than ideal so at the end I ended up like working on Journal proofs and you know those are not broken yet at the moment so is kind of like all tied in very well together nice what about you gal what are you studying and why so I'm a four PhD student at The vitman Institute with uh Mon and I'm also

co-advised by Alon atan I work on mostly proof systems my background is mostly in like theoretical computer science complexity Theory and uh you I tended towards the proof systems on on the theory side okay and that somehow led me towards more and more practical things to some degree at least uh yeah I I was interested in complexity and cryptography basically from my bachelors and I just kept going in that direction cool yeah like the the work we're going to talk about today stir is Stir specific to ZK or could it be used in other contexts as well so I

guess there are like different ways to answer this so you know one of them is like so we have like pet peeve between Like Us in the fury community that you know whatever ends up being called ZK in practice is not really ZK really like we you know we have there's is all like scal ZK for scalability versus ZK for real knowledge that is kind of like a pet peeve so you know we can kind of answer the question in a sense like yes it can be used for a lot of other things that are not Z knowledge in fact like the thing that we do is not really zero knowledge so that's one part H but you know I don't think that's the interesting direction to answer that so from like the more practical thing like we think so like uh there's like um so so for D proofs is

interesting is a key building block that you can like get good Improvement concretely and efficiency things there are other things that end up being very like friendly to richmon and codings and the like so for example there's is work by Mark sying and other people on data availability using fry which is very very interesting like I have not really like fully grasp it yet but like that's a way in which you can use this proximity test which like fry in order to actually get something which is not directly to the way of constructing the proofs or snarks in general so that's a very interesting like direction for me and then of course the theory side which

I think gal is much more qualified to like answer about yeah on the on the theory side I low degree tests like sir are been very influential and very important on in theory to achieve like PCP theorems uh IOP theorems things like that I would say that in some sense uh because stir is mostly for concrete efficiency it doesn't necessarily do anything it does improve on some things theoretically that we don't know how to achieve but these things are not necessarily the things that interest Theory people the most but this this entire field is very important for Theory people okay cool the authors of the work it's yourselves plus Alexandro

kza and Alon yev and actually you're both at different universities as well I'm kind of curious how work like this happens like is there one person has an idea had you been working on things before together that this this kind of idea came out of yeah where does it come from and why are you all working together uh Sandro and Deon have been working together for a while I see okay and at some point uh I I joined at started working them uh as well uh as as Al student so I think this specific project starts from a previous paper of ours of B Alon and sandros which uh achieves uh what we're

really interested in these things in these uh uh Protocols are is the query complexity so it achieves theoretically the best quer complexity that we know it's not practical at all and so the question was can we make this practical okay and first of all uh Alon and I have no real practical experience so we definitely needed someone who knew what they were doing so we added Jacko to the project try to bring that that project to make that uh practically viable uh and uh it turned out pretty difficult like we we tried to do a lot of things uh and and it didn't really work out but then somehow the

idea from there we sort of shift it to something that's not necessarily theoretically as good as that protocol had been yeah yeah practically yeah practically it was suddenly like we just took those ideas and put it in the a different protocol cool we tried to very hard to get like the previous protocol working especially because we had a very cool name for it we had work very hour we had the ACR name there and at then you know from like the as of the pro called St Rose which I still think we made like a very good job with the naming like I think still think that he came out quite nicely but the previous name was great and you know yeah I'm not

going to spoil it cuz we might eventually reuse it but yeah we were very happy with that you you're talking about stir like you you're excited about the name stir so the name stir is great I love the name stir okay this is actually I think it was your idea G right I I think so it might have been alon's but I I think it was mine we we had some uh we were throwing around like ideas for how to improve it and then we got bored so we started just throwing out random names and I think this one just stck oh which is by far the most wor file part of any resech project by the way but the previous protocol with an even better name incredibly belabored

acronym you know long complicated made no sense it was but yet flavor to it so I was very happy and then we ended up having to scrap it which I still lose leap over but it sounds like you might bring this back someday if you can look all I can say is like you know names like that were are to come by yeah and I'm not willing to give up without a fight okay that's nice jao correct me if I'm wrong but I think that's part of why you joined the project I think I I uh I said that name originally and uh yes yes like so it was kind of funny because we went during the summer we did like this um this summer school together on the

only Pro ATA and so we were both T of the course and you know I was familiar with the work and then G fled to me like the idea of trying to get in concretely efficient but the name was really what sold me like you know wow the ideas were cool everything was pretty but the name was the thing that really like got me going jaimo now I'm curious the kind of work you were doing before because G just kind of highlighted you you came in to make something practical what had you been doing just before this so it's kind of funny because I like uh I was watching this talk of me Bel like two days ago and he said this kind of thing like you know he feel like when he's with theoreticians he feel like a

practical person while he when he's with practitioners he feel like a theoretician he a bit of Mis fift in both camps and I kind of and in the same camp so during my master I was doing very applied like attacks on iogen based protocol this kind of stuff and during my PD I've been doing a little bit of like this kind of like work which I like to think sits between like the theoretical and the concrete so for example like some of the work that we've been doing is this line of work with Canen which essentially is on um efficient polinomial commitment from latis schemes and trying to get something which kind of like resemble a ltis based kg so trying to get both a theoretical and a concrete component so

you know a part of that is that I have like this kind of interest in like you know I don't like to just be completely Theory I like I really like to see like some sizes at the end of the of a project then I also you know have a bunch of programming experience I've been working a lot on these kind of things and I think I have a relatively good understanding of like you know what are the bottlenecks improving systems and the likes so I end up being like the concrete guys in this kind of project which is kind of funny because in my old lab I used to be the fury guy so that's is is very funny to me uh all right so we came here today to explore stir but as we know it comes as a replacement or

let's say an improvement to something that a lot of people use today which is fry so what I was thinking is that we can start with some background on how fry works and basically show the history of the the Evol the evolution of fry because the fry that is used today or at least the systems that deployed fry are not exactly what existed in the original paper so yeah could you tell us a bit about that kind of evolution okay yeah so maybe at an ey level is kind of like an interesting part to consider is like the anatomy of a stark or any is kind of like IOP based Nars so the overall goal is to try to build like U

efficient Nars on High level we want to build a snark and the snarks that we consider for which stir and Fry are important are Starks which in my mind morally they are just snar which are obtained by compiling an IOP using the BCS transformation so doing everything in the pure random Oracle model so what usually ends up happening is that this tarks are obtained by like um taking a polinomial IOP uh which may be tailor to some arithmetization or whatever and then compiling it from a polinomial IOP into an IOP and there are some different ways to do it like this like the we to describe is not Universal so for example

break down do different things but one way that people end up doing it is that like the polinomial in the polom IOP actually end up being encoded as Rich Solomon code words and then the soundness of the resulting IOP is the dependent on the verifier being able to correctly check the claim that the approver sent are actually really rich Solomon code wordss or close to them and this is where like fry and stir come in so read Solomon code word is is the evaluation of some low degree polinomial over some evaluation domain so the prover sends a function and it claims that it's a a some low degree polinomial and we want the verifier to be able to

test this test that at least that it's close to a Lo polinomial and uh do that with the aid of the the pr so both uh stir and Fry they're trying to solve this problem so because these these Protocols are are used later they're compiled using the BCS transformation into an actual snark or Stark so maybe a point to note about these Transformations is uh when we compile the uh IOP into a snark a lot of the parameters from the IOP like the quer complexity they affect the efficiency of the snark yeah so the the main parameter that we cared about for for stir was uh

improving the query complexity because that improves the overall the size of the resulting Stark and also uh the number of hashes that the verifier needs to do which is very important especially in uh recursive snarks and things like that okay cool so in terms of uh quer complexity we know we know already that today these proofs that are based on Fry are pretty large and that's why you you usually batch let's say a lot of transactions in a rollup before you verify them and you know the verifi time in the very practical sense it affects uh the gas cost you have on ethereum for example to verify proofs so those are

definitely very very important and my thinking is that in order to understand the Improvement that was made in stair we actually need to go much deeper into fry and understand its structure and how the BCS transformation works so it would be really great to try to make a somewhat very high level step by step of what are the different components in Fry and how they come together and then we can see you know how we improve them using St sure maybe I can start by talking a little bit about like how the IOP andb transformation translate to

concrete like efficiency H and then we can like talk about fry see like how the different components are the commit phase query phase and how they translate into the sizes so the BCS transformation basically is a very lightweight way to take an IOP and turn it into asnar the main idea is that these iops are interactive protocols in which the prover and the verifier interact for a certain number of rounds and each round the prover sends an oracle uh the verifier sends some random challenges some public coin Randomness the samples and then at the end of this interaction the verifier makes some queries to these oracles and depending on the result of these queries it will end up like

actually accepting or rejecting the claim the way that we end up translating this into like asnar is that instead of sending these oracles which we cannot really do in the real world the pr ends up committing to them using a Oracle tree later on when the verifier wants to query them then he will actually ask the prover for the authentification path Associated to the index of the proof that was quered and then verify those authentification path and use the value that was sent by this so in a certain sense the Merkle tree allow you to get this virtual Oracle access further you know to make things are interact active we also do a f CH transform and basically this combination of Merle

trees plus F transform are the core of the BCS transformation so if you think about the parameter of the IOP this is essentially how it translate into the resulting snark so the pro time of the resulting snark is basically the pro time of the IOP plus the cost of committing to these Merle oracles the verifier time is basically the verifier time of the IOP plus the cost of verification the path plus the fashes queries in the IOP translate to authentification path which the pr has to send and also of course if you have a identification path you also have to verify it so queries also translate in a higher um uh number of Ashes the verifier to compute so

basically the parameters of the IOP and in particular the queries really affect what the sies are because in Practical deployment this kind of Merle trees end up being what this authentification path end to be the majority of the proof side that eventually appears in the resulting snark so this is like BCS at an ey level and now like where you PID the costs and then with fry I think you know I can let G take lead on that yes fry is an IOP so the which will later be compiled into uh start using uh in the way that Jaa said so the way it works is you start off with this uh function that's claimed to be a resell and code word you start off with a an interaction phase you you go

for multiple iterations in one fry iteration you start off with a code word over some domain of some size and then you fold this code word or this function claimed to be a code word into a smaller domain so usually when fries is presented you think of a domain that's half the size it's actually going to be important for stir later but uh not really for fry so you fold it into something that's half the size but this somehow preserves the distance from the the code so you keep doing that over and over again uh logarithmic number of times until you get something that's supposed

to be basically a constant function and then this is supposed to be very easy to to to test uh but this is just interaction this folding doesn't actually verify that the functions are sort of uh connected in in any way so afterwards you have a query phase in which the verifier makes a bunch of queries and queries all of the oracles that were sent in this entire protocol in a correlated way and verifies some consistency between each one of the functions so it actually tests that the function that we had at the beginning uh and the folded function are consistent in some way and then this together this tells us that the the function is actually the original

function was actually close to low degree nice can I ask a very quick clarification because you're using the term folding and I just want to know if it's folding like we've been hearing about with like folding scheme folding or if it's a different kind of folding no no it's a different one like in this sense you can think this is kind of like a fast for folding so imagine you take your polinomial you split into even and half coefficient and then you like kind of like take a random linear combination of the two halfs I see and then you keep doing it is it's in a different part of the entire construction right like it's not in the same place it sounds like exactly exactly like yeah the like the folding that these accumulation based foldings you know they use the same

terms which is unfortun because denom clature is the same but uh yes it's a different kind of folding in this case got it yeah yeah unfortunately in this field things tend to fold so we just use that [Music] word yeah and now when when you talking about folding in Fry um you basically let's say do it on on the polinomial that you're working on and then you by folding it you reduce its degree but you also move from one evaluation domain to the other and if I remember correctly in Fry you basically do the same reduction in

size and for example like you said in in evolation domain you go for to be the half to side and the degree goes to be half the degree and and so on and that probably also relates to the concept of rate that might be useful to to introduce yeah so maybe I'll just say first of all what what is the rate of a code uh so the rate of a code is it's the inverse of the amount of redundancy in the code word so at least in an intuitive level the more redundancy you have the more you with the more errors you can handle you can have and still be able to decode so it should in ly easier

to test proximity or or decode or things like that so the the smaller your rate the easier it is to test basically so with the read Solon code words the rate is going to be the degree over the size of the evaluation domain in this case yeah maybe to like give some numbers like think of this rate or something like one half one quarter one8 or 116 usually yeah so there's a trade-off on how you choose it but you can basically think that you taking your polinomial of say degree 2 to the 20 and then you write it down is EV valuation over a domain which is twice or four times or eight times as big and basically this you know if you think about it like the

the size of the polinomial related to The Domain kind of encodes like is the rate and it is like the amount of and so the the rest is just redundant information that allows you to then do like testing easier in normal coding Theory you really want this rate to be as close to one as possible because you know that means that you have to send less information to the code but in our case we this is like you know this is also important for practical efficiency because it relates to the size of the initial fft that you need to do to encode the the Oracle so you know you don't want to have a rate which is absoltely large especially at the start because then that means you have to do a very large fft but the main idea of St is that the added redundancy really

helps you a lot in order to test things in a more efficient way um so as far as I remember the original papers uh for fry and Starks they use this kind of two wise folding where they reduce the degree by by half each time and the result that they got is that because you fold it by the same manner both evaluation domain and the polinomial you somehow get to keep the same rate is that right yeah yeah so with uh with fry whenever you do folding whether it's uh folding with factor of two which is the original paper or some general uh Factor K uh which is what's actually used in

practice the uh evaluation domain becomes smaller in a factor of K uh and also the degree so if you have a domain of size n you get n over K and you have the degree the degree is D to D over k for the the next level of fry so in then in the next level this uh this ratio between the evaluation domain and the degree always stays the same and so the rate which is the ratio between these two always Remains the Same in fry no matter what iteration you're in cool thanks and so I think that again what we're describing is what is the original fry construction I guess and a lot of happen sense and I think in order to

understand steer we probably want to understand these new additions that came to fry in the recent years like the Deep papers and other recent papers because as you mentioned in your paper the version that is used is not the original one there are there have been many many different editions that people are using today so what what has been added besides the original folding construction and so on and what do they optimize as well right yeah maybe like so there are like two main like so and pardon me because my you know I've come into still kind of late so maybe my historical knowledge is not as good but so there was the original like um fried

paper then it was followed by the deep fry paper and then after that the proximity gaps paper came out which is possibly the most important line of work so the deep fry paper essentially introduced as far as I know this the idea of outo domain sampling which was used as a way to boost the soundness of fry and this is something that we actually use in this works and effectively it U it relates so like finding like using quents in order to like amplify distance in like the iteration of fry so this was one way to boost the fry soundness then this proximity Gap paper came out and this is also a very important Workhorse in our paper and it relates to like this kind

of notional proximity gaps which at a certain sense allow you to like U conduct a much sharper analysis of the original fry protocol so the proximity gaps paper basically improved the analysis of pry protocol by enabling it to essentially getting much tighter bounds so as far as I understand like the Fry that is actually used in this in practice is mainly the normal fry protocol but with analysis from the proximity gaps Paper Plus possibly stuff about extension fields while the contribution of like the Deep paper kind of ends up at an higher level of the stack so for example in Starks there's this concept of deali which I

think stands for deep algee linking or something like this which uses techniques from like this deep fry paper but this is kind of like at an higher level of the stack the test that is actually run is just fry okay cool right and correct me if I wrong like uh this is my understanding of what's the kind of like state of things yeah the original the pry was was just like you said uh was uh made to improve the soundness analysis but with the proximity gaps paper they managed to analyze fry the original protocol to have better soundness than deep fry and also deep fry doesn't seem to at least the protocol they gave there doesn't

seem to give anything with this new analysis so they both just have the same soundness but the de has extra STS so it's not needed cool I'm curious there's also this like deep Al work is that not related to any of this is that sort of like its own track yeah so it's kind of funny so this is at an higher level of the stack so from my understanding what happens is that like when you do this compilation of to an IOP something that you from a polom IOP to an IOP what you need to do is effectively like be able to quer these polinomial outside of the evaluation domain in order to get better soundness and test things so what you end up doing is instead of testing the

the the code word that you've been sent you test some appropriate quotient of it and this essentially is a trick that we also use in this work enabl you to basically ensure the valuation of the committed code word on things which are outside of the domain and this is where the Deep Aly line of work from my understanding which might be incorrect cor comes in so this is kind of like if you remember the kind of like road map which I talked about this kind of goes in the in the compilation from an IOP to let's call it a rich solmon encoded from Pol IOP to a rich Solon encoded IOP in which to like do this compilation you

end up doing this kind of like quotient out domain sampling kind of things while the lree test which is you know Fry at the moment and hopefully store in the future is kind of like in from the deepali step that's kind of my understanding but again it's you know take it with a grain of salt Okay cool so in in terms of uh let's say what we try to get to like what is our Target when we we use fry we try to get to something that is sound enough for us to to be confident in so let's say we're aiming that our eventual totally compiled protocol has let's say something like 128bit security so what what would be the parameter that we

would play with so for example if we do many more queries and we increase the query complexity that's one way but what what would be the different parameters that we could use like what we could increase and then decrease the other and so on uh so you basically have uh for fry I guess there's two parameters it's either the rate or the uh the query complexity so if you have a really really good rate right at the beginning so very very small rate so a lot of redundancy MH uh then uh you can get you get a lot of security by even making one one or two queries I mean obviously not one or two in the real world but you get a lot of security for every query that you do but the problem with having a

large rate is that the approver is going to have to work very hard for this so the smaller the rate the more the improver has to compute and the more memory it needs and uh this just collapses for a very small rate so uh or not not so small like you go to rate one over 32 it already starts for large enough degrees this already starts to like blow up your RAM completely yeah and this is just unmanageable so you you get stuck at some point yeah at Le for if you want to work with reasonable parameters yeah and so you'd have to increase the quer complexity so once you have a fixed rate so this is you know how much I will let the approver uh work I'll just uh I just need to do enough

queries in order to get this uh amount of security this 128 bits of Securities for example once I have the rate fixed I sort of have to there's only one little other thing that you can like kind of like play around to get some extra soundness and this is like what is also done in practice and it is like by doing some proof of work at the end of like the the proof so that is also a way that you can actually end up by like boosting the soundness of course this is also a trade-off between like the prover like cost and the sound so you can think about like for example to add 20 bits of security to like your proof the pro have to do an additional work of uh that order basically so there's also there a trade-off between Pro time and sound

that you get so yeah and and we do know in practice that that ffts over these large domains is going to be really heavy on RAM like you said and that's a real problem in practice especially when we're talking about these huge circuits that that are used in rollups let's say so yeah definitely you want to be very conservative with rate and yeah I guess this is a probably good time to talk about stair and what you you guys introduced right so let's see how you affected all of these parameters yeah so maybe let's start so the so yeah the main thing that kind of the inherent in Fry is that like you end up like

actually recursively reducing between codes of the same rate so if you start with like a you know a large rate then all the code word that you test like uh end up being of the same rate so what we notice is that like if you can actually like change rates during like the various stages of uh the recursion and like move between codes of different rate your your steps of testing of the lat code wordss actually become like easier so you can think about it like in store you the family of codes that you test end up having a smaller and smaller race and so they are like easier and easier to test so this is kind of like

the main intuition between store of course like when you try to do these kind of things some issues arise it's not like it's not all like you know roses otherwise people would have done it already yeah so the way I like to think it it is this you start with a fry or deep fry for example and then you decorrelate the queries so now instead of like testing them all at the end you test them at each round and now when you do this folding step instead of like writing down just the fold you write down the evaluation of the fold over some larger domain so imagine if you have like a folding Factor like 16 so what fry would do is like write down the

valuation of like uh the the function uh the fold of the function over a degree of if the original domain was of size n the new domain would be of size n/ 16 what we instead do is we write down this on like a domain uh which is much larger like n / two for example and now the kind of like CR of like what St does and the way that we are able to make this work is that now you have to kind of like test consistency between like what the pro wrote down and what the f should do and the way that we do this is by like a combination of like quotient as in in deep fry and out to domain sampling again as in deep fry so this is kind of like the main ey level like idea

of stir the code word that you write down is a rich Solomon code word where the degree is now D over K while the size of the evaluation domain is n / two so basically the new rate of this code is 2 over K time the original rate so if K is bigger than uh than two as it you know tends to be indicated in practice so think of K like 8 or 16 or 32 then the the rate goes smaller and smaller at each like folding step and that's kind of like where you really get the magic of like being able to then do less queries later on uh cool and from my understanding from you know reading this steer paper and you in order to do

that you actually need to move from one domain to the other right like you you me like you mentioned and that's a technique that you've taken from another paper that's called domain shifting right yeah so this technique is basically from uh the previous paper that I mentioned that was the starting point of this entire project we also developed these uh ideas of potions and out of domain samples that were I think originally shown in and deep fry but we uh sort of used them in a way that's bit different from what they did there which is also what we do in uh in stir and there we sort of saw there was this nice La that we had like oh you could if you have a code word over some domain and

you only have a test over some other domain then you can sort of shift the domains and we we just thought it was quite nice in that paper we didn't really realize uh what we could do with it it's actually like a simple byproduct of other stuff we did there can I just ask you though that query complexity paper that you keep talking about is that published is that something we could actually link to yeah yeah okay perfect another thing that I've seen you spend quite a bit of time on uh is your new method of degree correction so what happens there uh so the problem with using quotients in general in these kinds of protocols is that your degree

changes yeah so if you quotient by a point or by some amount of points your degree is lowered by that amount of points and the problem is that are low degre tests tend to work only with degrees that are like really nice that are like powers of two the math doesn't work out if they're not powers of two you're now a power of two minus four so what do you do you have to somehow correct the degree either down or up but up makes more sense because this is going to be the closer power of two and uh the previous techniques did this with uh basically worse error than than we have so you you used to basically pay

per so if you want to correct four in the degree you pay some factor of four somewhere for four is not that bad but if you have to do correct from you know D over two to all the way to D then you pay a factor of like d over two which is terrible yeah uh so we we have this technique that you you pay sort of like as if you were correcting only one instead of D over two okay cool and does the new technique that you you developed can it be applied to existing constructions as well would it be competitive or useful there I'm not I'm not sure okay do you mean stir or do you mean this particular part uh I mean just specifically the the gree correction ah

okay okay a lot of different systems they try to get around it in other ways like uh deep fry had potions but they got around it by assuming the degree is not a power of two but like some other function that sort of worked with their specific way of doing quotienting some projects that use quotienting they don't really need this ah I see it's inad of quotienting uh no well they they get around the degree issues in other ways usually okay I see uh but if they can't get around it then they can use this there's also other ways to to get around it that don't have they're not this technique but you could for example do quotienting uh Pair by pair instead of like we we do sort of like a monolithic quotient and

this lowers the degree by a lot you could do uh quotient Pair by pair and then you have a lot of functions that you have to test instead of one you have to merge those so there's a lot of different options there it sounds like I mean just going back on the story we've just told there was all of these lines of work you kind of picked great things from a number of them and the domain shift was coming from your previous work is there any other techniques or anything in this work that's also kind of new to folks you know so one part yeah this work combines like a lot of like pre-existing tools which is kind of very nice it also gives you a bit more confident that what we're doing is correct another thing that we have which is also kind of like present

is is present in like the previous work by allegal and Alon is this compiler for poom iops that was made for the I sound regime so it actually has some improved guarantees compared to uh previous compiler of the of the sort so in this work we kind of like extended it we made sure it was concretely efficient we gave around around knowledge soundness analysis which is also very important for actually like uh compiling to a non-interactive argument we think that if you have like a poal IOP that you are trying to like turn into a Stark in this sense you should try to see whether our compiler is a good fit for you so I think this is also something that I

think people yeah should be interested in because like the you know we don't we haven't highlighted it as much as we wanted to there's still some code that I need to write and I eventually we'll get to that we show but we really think that this compiler is also a very important like uh tool for like people who are trying to build uh Starks in this setting should also give some nice boost to soundness and to argument side and quer complexity in our in my opinion cool and I I'll maybe say that uh while I think a lot of the tools have existed like in especially were developed in this previous paper of ours this paper is very theoretical and uh I think that using them in practice is uh

also New like the yeah more practical researchers haven't seen these because they were just in this paper yeah that that makes a lot of sense and if you look at the at the paper then you look at the benchmarks and you see that it's pretty compelling right like you see the verifier time being reduced in all situations proof size as well but you do notice another thing which is that the proof time is larger and why why does that happen yeah so the kind of like uh main difference in the proof size is like so if you look at fry basically what happens when you do this kind of folding so you take like your like polinomial that you split in

two for example and then you combine it into a new one and if you do this with the same domain what ends up happening is that basically the constructing the new evaluation from the old one can be basically done in a linear pass so in fact the F in Fry stand for fast for this reason because it is like once you have the initial evaluations which would anyways require an fft which will then be able to do in linear time in our case since you actually need to write down like the evaluation of the fold over like a different domain we cannot like combine the valuation in this way so what you end up doing is that at every round you have to do a small fft so especially if you're testing a single polinomial What's

happen is that like stir does a bit more work on the prover not that much more work but a bit more work the nice kind of thing is that in general like as you said at the start when you people use fry in practice they usually use it in an heavily batch context which you're trying to test like proximity of very many like code words that once so what ends up being like the dominant cost in like practice is like the cost of Performing this initial large fft and this cost is shared and is exactly the same between stir and Fry so you can think about it as like bottleneck is the same between fry ster then in the tail end you actually spend a little bit more Pro time but we haven't done like The Benchmark for like the batch case but we

do believe that like this should be a negligible amount of time compared to like the cost of the initial fft in this deely batch contest mhm so we think little additional Pro time should really be worth it you just mentioned that like this needs to be implemented before we completely know how it gets used in all these different ways but for the developers who are working with things like fry should they be kind of trying to use it as a dropin replacement or there's certain ways in which it should never be used in some constructions like I'm just kind of curious if there's like ideal cases where you'd switch to something like this so for me like you know let me put my marketing ad on I believe that like you should wherever you're using fry okay you should put

stir in like bold like you know I'll make this very hard and bold statement like stir was meant to be a drop in replacement as fry it does the same job as fry it has improveed like uh astics it has better parameters in like both argument size verifier query complexity you know verifier time so unless you really really really care about Pro time in the sense that like a very like like I think I don't have the number on top of my head but imagine maybe a 15% slowdown in the non-bottleneck part of your Prov computation is really a deal breaker then I think you should use S nice especially in a recursive context

like you know for me it's not like there are some places where you should ideally use S but uh instead of fry so it's not a choice of like you know we should figure out whether where it's makes sense to to switch from stir to fry so from fry to stir but I think that there are some places which it is more ideal and other places in which is still you know better but not as ideal so that's bold That's my kind of like you know very like hard message that uh unapologetically and like very strongly make nice okay what about the security and battle tested of this system you guys just released it does this need to go through more of a process do you think before people are actually using it in the wild so sure I think there are some rough edges to like uh iron out so

people should implement it make sure they do not fall into Pitfall but the cool thing is is that as you mentioned before all of the tools that we see in stir were in one way or another like being seen before so the proximity gaps paper has been battle tested it's been deployed this what star we uses cautions you know they are like they were seeing in deep fry they're still they're using deep alley so this is also something that we know about like the Rec correction you know this is new but is also similar to other techniques that were seen before so all the components there are batttle tested they come from Legacy it sounds like like they have some precedence from previous works but it isn't a new construction yes like

when you add all these things together yeah I'm actually just curious the paper just came out but like what would you do next to kind of get it into a more battle hardened state would you write it again again would you see people implement it and then take their feedback yeah how do you even kind of like move it into that state yeah for me it's just like I want to see people implement it and try it break it you know like also yeah that would be great like you know I think that that's the most worthwhile feedback you can get like if people can break your protocol that's amazing but you know I I really believe that like while there's a lot of rough testing like the tools that we use

there are all battle tested the way in which they're composed might be like uh you know might be novel but for me at the moment you know maybe you know g a different opinion to him maybe a bit more cautious you know I'm I'm not really I believe that it would be very surprising if things went wrong so of course you know it's a new protocol so when people implement it it is easy to make mistakes you know we have seen many time like construction that were theoretically being broken by bad implementation or by other things but my impression is that like the tools that we use are battle tested the analysis was complex but we think this sound and we think it's uh you know it's not like

the proximity Gap paper which was uh you know beautiful but very hard to like actually par and understand so we think that if you sit down with a cup of coffee for maybe a two or three days you can really read the paper end to end so and I really hope that like the transition time from fry to is not too long and that there hopefully you know if things go wrong I would be very surprised not pleasantly surprised but like you know I would uh you know I would make a strong statement that I would be surprised okay I I will maybe add uh I mean I'm I'm more on the the theory side so so you're cautious cautiously optimistic I I well I don't know about uh breaking implementations

but uh the so we work quite hard to make the proof of soundness uh be I think relatively simple uh relatively easy to read um and also uh I think jao mentioned this earlier that we did an analysis for round by round soundness uh which is really important in practice and people sort of tend to forget about it and they just do regular soundness and we tried to also work relatively like generically so I think in in my a very biased opinion I think this is an easier paper to read and understand than fry so this this is

also I guess a plus for for stir and also why I'm quite positive about it that I think that the analysis uh is is relatively easy to understand I mean of course you need to the background you need to read it carefully but I think we we did quite a good job on on the theory side on on making sure that everything is easy to verify cool hopefully I mean I don't know how many people have actually read it well that story of the fry paper like I know that there's been work since the original fry paper and Fry papers trying to do what you just describe too like simplifying it making sure that the security analysis is a little bit more clear I did an episode

with the folks from nethermind who had written exactly that I know some other folks have also done kind of an attempt to just like break it down but you're starting from that place you've written it for people to already get that sense that's really cool yeah so I just want to remind the listeners that what we did in ZK hack 4 was exactly combining battle tested sub protocols in a way that when you combine them they're broken but yeah in ziki haak for the different thing was that they didn't write the proofs but you you guys did so you guys are good uh but yeah like like when you combine

stuff it might break after you combine it so that's uh that's interesting to see um yeah and I I think I have a couple of questions that actually came up from Nico which is from my team of geometry research but also a frequent co-host of the podcast and we were wondering is it compatible with the recent Works around Circle Stark and the M31 Prime which is is nons smooth how does that get affected here yeah so I've been in touch with ulri a lot and and I think either yugal or Alon I can't remember we're also in touch with SH yeah I I think like the belief that me andri share is that all the things from

Circle stir sry from Circle Stars can be brought to stir so it should be possible to get a circle stir or stle there's a we're working on that like that's the part so wow like the way like stay fast three times yeah exactly circle circle circle like um like my only research goal is to have terrible paper names uh yeah or great one depending on your thing but yes so the bottom line is that like you should be able to do stir over M31 in the same way that you're doing a fry over the circle and so the performance benefits from that should

also translate nice I think one of you just highlighted for me in a group the Bas fry work that just got released I mean it got released today as we're recording it it sounds like you could also be if you feel it's like a a drop in replacement I guess you could also do Ben stir yes so okay in that we actually I was speaking with Ben and Jim when I was in New York some time back so we talked a little bit about it okay there's a difference so that work like let's let's call it binary fry for the moment really like relates to the base fold paper that was released last year I believe mhm which basically show that you can think of fry as like a more General like IPP for foldable codes that means that instead of just testing Rich

Solomon you can do it in like for for a different family of codes and it got some benefits like the number of field you can choose and stuff like this crucially this really relates about the fact that fry doesn't use too much of the polinomial structure instead while we're using in store so we're using a lot more we using the AO domain samples we're using the quotients so when we started like working out at the board me Jim and Ben got stuck we couldn't really like get binary stir so that's something that true but that's for like the inner like structure of uh fry so you know store is a drop in replacement in terms of interface but what it does like inside is slightly different so like you know I haven't

stop I'm still thinking about this but uh yes we so it's harder than you thought harder than we thought yes okay is there additional kind of combinations or works that you're looking at past that so the sterle Stark God I really like that the B stir not yet but is there anything else that you're currently working on in that regard so I maybe mention like at the start of like the the podcast this Freeda work for like data availability oh yeah and we do also believe uh I mean I I do believe I haven't like double checked yet that St can also be use that for with all the benefits that they bring so I need still to figure that a little bit out but this

has been some of the things that we looked at there hasn't been much time we had to write the paper get the presentation and all of these kind of things I'm not sure if you know we have some ideas and some other like terrible names I think you know I don't think G wants to share them for now but yes the there there's like I think my like again marketing tag line is that we think that there's a bright future ahe for IOP based snarks nice okay so before we sign off the question about da it sort of made me realize something like because I always understood fry as sort of like sampling is it doing something like sampling or error correcting codes or something like is that where you see it being used for da or no I might be

completely off it is kind of art for me to like I you know I've schemed that paper I don't really understand it too much but basically the kind of idea of the data availability schemes that like you want to have like you you basically want to make sure that there is some data availability and you want like kind of like clients to be able to interact with like some Pro Data provider and then from the transcript of the interaction you should be able to then reconstruct the data that was available that's kind of like the high level understanding that I have and from what I've understood the way that you can do this is is through like actually error correcting the code and then committing to it in a Merle tree and then using things like fry to test actually

proximity to the code so you end up kind of like showing that the data that you committed to was actually encoded in the right way and then the error correcting like properties of the of Rich Solomon end up like carrying you some of the way to the data availability goal interesting that's kind of like my ey level intuition but you know you should get mark on the podcast can probably explain much better than me who yeah my my understanding is that they basically encode their message the data that you want to have available and then they somehow prove to every one of the the many like light nodes like these weak verifiers that there's actually a code word in there and then uh they will each

sort of test some random location and see that it's sort of consistent with this thing that's underneath and this consist and this is uh used they used fry for this consistency basically yeah yeah that's that's kind of what I meant mean I used the term sampling but maybe that's like wrong but sort of that testing at different places but not looking at the entire picture that's the part that fry can do and I guess stir can do as well all right well thank you so much G and jackamo thank you so much for coming on the show and sharing with us the history of fry a lot of the developments along the way what you used in constructing stir how it can be used instead of fry potentially and yeah and what you're working on now thanks so

much yeah I'm really looking forward to see if stir is in production yeah so are we thank you so much for having us thank you for having us cool I want to say thank you to the podcast team Rachel Henrik yonas and Tanya and to our listeners thanks for listening [Music]