Episode 304 - Exploring FRI, LogUp and using M31 for STARKs with Ulrich Haböck

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 UL Hab and applied cryptographer at polygon Labs we talk about his journey into applied ZK cryptography from teaching to becoming a full-time practitioner through this story we learn about the contributions he's made to the field in

the form of many write-ups and manuscripts like the ones on Fry and breakdown we also discuss how he found new breakthroughs with his work on multivariant lookups in the form of log up and on logarithmic derivative lookups using gkr we also talk about his work at polygon Labs on Starks over finite Fields now before we kick off I want to let you know about our upcoming multi-week virtual event ZK hack 4 starting on January 16th and running until February 6th 2024 we will be hosting weekly workshops with top teams in ZK showcasing the state-of-the-art in tooling for ZK Builders every week we also host a ZK puzzle hacking competition in it we share a ZK system

that has something wrong with it you are meant to find the bug and hack the protocol the fastest hacker will make their way to the top of the ZK hack leaderboard there you can find prizes and Glory now this is our fourth time running this event series The ZK hack online series is not a hackathon but rather it's a chance to learn the latest in ZK tools with members of the ZK hack Community as well as learn the intricacies of ZK security through the puzzle hacking competition and because it runs over a few weeks participants often make friends find Future colleagues or Co co-founders and we really get a chance to dive into the ZK world together the event is free and open to all I've added the link on our website please join the mailing list so

that we can let you know when we have more info to share about the event also be sure to join our Discord that's where all communication around this event will be happening so yeah hope to see you there now Tanya will share a little bit about this week's sponsor launching soon namada is a proof of stake L1 blockchain focused on multi-chain asset agnostic privacy via a unified set namada is natively interoperable with fast finality chains via IBC and with ethereum using a trust minimize Bridge any compatible assets from these ecosystems whether fungible or non-fungible can join nada's unified shielded set effectively erasing the fragmentation of privacy sets that has limited multi-chain privacy guarantees in the past by remaining within the

shielded set users can utilize shielded actions to engage privately with applications on various chains including ethereum osmosis and Celestia that are not natively private nada's unique incentivization is embodied in a shielded set rewards these rewards function as a bootstrapping tool rewarding multi-chain users who enhance the overall privacy of namada participants follow namada on Twitter @ namada for more information and join the community on Discord discord.gg NADA and now here's our episode today we're here with UL habak an applied cryptographer at polygon labs welcome to the show hi thanks for having me and Nico is the co-host for this one

hey Nico hey Anna hey rri so today's interview came about Paul from risk zero had suggested bringing you on and he wanted to talk about a few things so I'll just sort of list what his message had said but you should cover things like his manuscript on Fry his work on lookups log up and gkr log up as well as the work he's doing on Starks in finite fields that aren't NT friendly now I think we may get into more than just this but here's sort of a starting point and a bit of a summary about some of the things we're going to talk about but first before we do that tell us a little bit about what got you started how did you jump into all of this where did I start so that's a good point I mean by by study I never studied cryptography so

when I was at University so I took the chance to dive into cryptography actually by teaching so I held a teaching position at a applied University of tech technology it's called for quite a long time I think it was more than more than 8 years or maybe even 10 years can't remember and that actually did uh I had quite a lot of freedom because I'm not I was not under the pressure of doing research so I could reorient completely so and I ran into cryptography because there was a lack of people teaching math and cryptography related stuff so I really started with the classical wow Primitives like RSA uh discret logorithm problem all these things and in the end

I found myself uh thanks to a friend of mine Stefan K and I found myself in zero knowledge proofs the classical world of zero knowledge proofs the schnore MH so wait you started by teaching kind of like technical topics then discovered cryptography in teaching it so like you had to learn it to teach it you it wasn't like you had learned it in a class and you were reteaching it to someone exactly I actually what I studied was I mean a mixture of of many things but I would say it was a lot of probability Theory and dynamical systems that was back then when I did my PhD but to be frank I never felt at home in this realm so that that was probably also the

reason why I switched over to a teaching position oh okay you didn't like being a student in a way no it's it's not that it's just like a never found in dynamic system I this was not my math okay I don't know so just Happ happened that I found myself there uh and it happened that I stepped out of it so I'm a late starter I would say I probably needed the time to reorient when I was teaching to find cryptography and to find that I really love it cool and that brought me in the end to classical zero knowledge proofs what was it about cryptography that you liked I would say it's is it the right word in English versatility versatility yeah H it's so manifold from

the type of math you meet ah I mean you can start off with all the statistics that's needed for symmetric Crypt analysis you you can go further to all these number theoretic constructions behind public key crypto and even then you know all these different Primitives starting from elliptic curves or just ordinary cyclic groups with a hard discrete logarithm problem up to Lees to uh it's all the different math you meet in crypto it's a mixture of all different things you can position yourself where you feel comfortable and the second thing that I missed actually in my PhD studies and what I had to do previously is its

immediate usefulness in practice and that's actually also the thing that drove me in the end to Industry actually to your first point something funny that I've noticed in sort of the history of of cryptography is how once in a while you have ideas that aren't new to math at all but that get injected into cryptography and suddenly we have like a whole new field of cryptography that shows up what do you thinking like elliptic curve cryptography for example right yeah I think it was menes no in the '90s with the Crypt analysis actually oh I wouldn't know same thing with pairings you know later on ah sorry sorry yeah yeah yeah pairings came with Crypt analysis of the discrete logorithm

problem yeah and I think it was m at say is who who was one of the driving forces of using elliptic curves as the discrete logorithm structures let's say so what was your first like move into working in our industry where did you first find yourself after being a teacher uh actually quite randomly at the first position that I just found that was here in Milano where I'm still based it was at Horizon lups uh the engineering arm of the Foundation St cryptocurrency yeah I actually when I was looking into your background I saw that you had worked at Horizon I had Alberto on the show I

think a two years ago it's longer than two years ago but I remember that at the time I was already there what were you doing there what kind of focus did you have actually that was perfect perfect position for myself to learn snarks so what I did essentially is learning snarks first of all learning all the technical subties of proof recursion in the context of aggregation scheme not folding back then didn't exist but the mother of folding and besides that I made Marlin the proof system Marlin recursion friendly so to speak but it was just a it was just an exercise in the end with all the details you need in

recursion and besides that uh of course it was a lot of instructing and in the developers of our team I see so you did continue almost in that educational side of things you're still learning and teaching it had also educational aspect but let's say it was more about learning actually okay but actually you come separate never is teaching is learning exactly teaching is an incredibly good way to learn really forces you to know what you're talking about okay so after Horizon you or actually maybe yeah just tell me what kind of work were you working on there what led you to then switch over to polygon Labs so I worked on really the classical let's say

elliptic curve based aggregation scheme cach pushed off aggregation scheme like recursive proof system uh which we had in mind and I don't know if it ever came to it I didn't follow much when I left the company but the initial idea was to have a full decentralized system of provs even with an incentiv Market a market that drives certain intensiv for the proest S so the PCD scheme or let's say the recursive proof system itself was not just a linear one a treewise one dynamically arranged treewise one and yeah we we did take over actually everything that halan did to m in in

that tree like setting and that means you had to think about the subtleties of let's say a kind of having flexibility in in expressiveness that means so we considered like having different base proofs and you have to have a key ring with it and and what does that mean if you have a tree wise recursion with all the subtleties of accumulators or aggregators in the cycle of curve you know uh and non-p pairing friendly and deferred arithmetics and it was to be frank it was a masterpiece for learning a pain in the neck wouldn't recommend so I I don't envy anyone who has to do with both aggregation folding and deferred

arithmetics if that's still needed nowadays it's not needed anymore I suppose but it's still thing yeah yeah and having let's say a flexible topology a nonlinear topology of the PCD scheme itself it's a hell of work of engineering of defining the right data structures in the end it comes down to define the right strs and the right tra and it's highly complex much more complex than uh with Starks did you double into the engineering side well I was influencing a lot or let's say had a lot of exchange with our Engineers okay to to help them Define or what I thought is a good notion of uh are good structs and so on

MH at what point did you move over to polygon Labs like was there a research reason was there something that Drew you to working on something they were working on yeah how did you make the move I think one of the main reason was something that also in the learning process I completely underestimated back then and it was off my radar was the Stark Side of of life and that's in particular the feasibility of ckvm and that actually led me to an intermediate step which wasn't polygon I worked for like 2 months for Orbee before unfort fortunately due to the FDX they went bankrupt ah so and orbis was working on cardano uh I'm not sure I

hope I don't say anything wrong it was partially financed by ardana one of the co-founders of Adana founded orbis ardana Ryan I don't know if I know this it also it also went backuped a few weeks later after FDX so I think it was a a staple coin on cardano okay but don't ask me I I I never due to time you know just two months three months there I never sounds like you didn't get that get big overview of what's happening on cadano okay so actually that was the intermed because Orbit's Target was to do a ckvm based second layer or rollup like solution for kadano MH okay that's how I

found myself there all of a sudden you were kind of playing in the ZK VM land and then FTX happens and the company goes under like I guess at this point though you must have been very familiar with the polygon zero work actually I was familiar with polygon seros work because blony 2 was really uh hit the scene so that was like half year before I left Horizon LS yeah especially if you were already looking at recursion plunky 2 was a big deal right yeah it just to me it was like uh something that I completely underestimated when when watching just the papers know if you looked at Aurora or fractal you know to large proof sizes you can't take that's another

thing people will kill me for that probably but it's my honest opinion that you can't take any Benchmark you didn't to be yourself serious agreed so I just didn't pay much attention on that side on the Stark Side and then came plony too and uh that completely proved myself being being fully ignorant you know wow before huh yeah so I I knew the work of polygon zero beyond that I learned a lot since since is well us I learned a lot about from from Ben s's track of work the whole fry thing starting from fry deep fry and and the proximity gaps paper from what was it 22 the the last one the most important one for proof

sizes got it and you wrote a very comprehensive summary of exactly that that brought me that actually brought me to orbis right so that summary was just an outcome for learning because everybody I guess everybody who who went over that track of papers that start off with fry and end up with with this proximity Gap thing it's a hard uh it's not not easy read it's not it's a hell of a climb yeah are you talking about the fry paper right now the Ser the line of work that goes with it okay okay and rri did you create the summary of the try low degree test is that exactly that summary is just I just wrote for myself actually everything that I write is just

for myself okay to learn to clarify my own thoughts that's that's why I write ePrint is your Google drive right yes so Paul actually had suggested we talk about this he just described as the manuscript on Fry that a lot of people will actually use to learn fry instead of the original paper at least that's what he felt so yeah this is even before you joined the polygon team was this also though inspired by plony 2 was it like plony 2 comes out it was kicked off by proving my ignorance to the stock side okay when plony 2 came out got it okay so plony 2 sort of triggered your realization you needed to learn fry and then this is your learning fry yeah so I

don't know how useful is it is for others I just really did it only for myself to keep the things clear to be able in the end to propose concrete parameter setting with a good feeling that they're correct you know so so not just like picking out some result and two months later you don't know anymore what you did well I'm going to add the link to this in the show notes for anyone who wants to see it as well why don't we continue though with your story so at this point you've written this manuscript on Fry I guess you've gotten to know the polygon zero team as well like planky to had come out that's happen yep I mean personally I was in contact with uh Daniel from polygon zer during my time with orbis okay because I

was already working on on log up uh on the logarithmic derivative look up back then okay which was actually triggered it's always like you see something you hear something that was triggered by my first uh CK Summit I was passively as a listener it was the ck8 I think the one in Berlin okay did you come or did you just watch the I was there I was there in person but I didn't give a talk or so just in the audience it was the first time back then that I was confronted with multilinear provs uh and I saw Benedict's talk and not just Benedicts also from William the so there was there was a track in the big room there was a track of multivariate pro stuff ending with Hyper plon uh and just starting

thinking about how would I prove hyperplan because uh Benedict didn't provide all the details or maybe I didn't understand them back then you know so so I was just thinking myself how would I do it and and the main thing is about how would you do the permutation argument for plon actually in the first place and that brought me to an idea had even back then at Horizon LA's time which was just for fun working with logarithmic derivatives formal logarithmic derivatives and I call it just a salad or mixed collections of biop pce that I just was playing around with a S Check in a different manner the one that that's uh that is often

referred to just a plon way where you have running running sums instead of running products actually I want to clarify something so you're saying you kind of looked at lookup arguments based on the logarithmic derivatives but what were lookup arguments based on before that like I actually don't know the change here change is from encoding witness data elements to be looked up as seros of polom to enode them as poles as poll yeah and the funny thing is counting zeros of pols is much more difficult because it's more multiplicative things so it's like a linear factor to the power of something and it's hard to prove the powers whereas polls just add

up so multiplicities they're just other up okay and this simple structure is actually the benefit of log up or flup which just came out one week before we published The Log up thing which is the same idea the same underlying idea just a different Focus not saying that it's the same piece of work but the same underlying idea so I'm a little stuck cuz I don't know what a poll is and I'm so sorry if this is like something that I should know but the Zero's part I think I got but I actually don't know what that means poll is just the inverse of a linear factor with zero you can't divide by zero so if you remember from calculus school calculus one you take a point consider the linear factor that

has a zero at the point this x minus that point mm and then takes it its inverse okay this has exactly pole of order one because it behaves like one over the difference to that point okay seems like I need to revisit calculus High School level calculus here but I vaguely remember that maybe yeah I don't know if this is high school level but okay the idea is um yeah if you have x minus something equals z uh you take take one over that and that's it you now have a poll that the something now becomes your poll and so you were doing the lookup argument based on this poll instead of on over zeros where does the idea for this come

from like why had the earlier ones not done that well that's what I said before uh one week before fluk up which is kovic and gabison and I think some but I know it's just uh Ariel and and and Dimitri who did it I think that that did use the same underlying idea that's why it's called fluk up for fractural decomposition okay so it's like the analogon it's from in algebraic geometry a field that I was back then not very familiar with but algebraic geometry you can say A polom you have two type of composition let's say in calculus you take always composition of polinomial into its its linear factors into its

roots uh whereas in general you have functions that that are uniquely decomposable using their poles it's a fractional decomposition and actually I now prefer much more that view instead of the view that brought me to it which it was more the logarithmic derivative okay huh so you guys both like both groups basically came to a very similar like next step very similar it was like Ariel said oh he didn't realize that actually you could view it also as logarithmic derivative I now changed my mind my approach to see actually like a fractional decomposition because it's it's more nice to talk about you out po you know I guess this is also what I meant earlier with once in a while

someone comes up with an idea that we know from math but we have't used inphy yet and suddenly unlock new protocols yeah this this idea of logarithmic derivatives or fractional decomposition is one of those examples yeah and it's important to point out us so we were not the only one who were thinking in that direction Megan you know so he he actually I was just not aware of that piece and I think Ariel back then wasn't aware either there is something like is it called bulletproof plus plus or something uh a publication of his where he already was using logarithmic derivatives uh not fully formalized but he was using it I mean the rest uh yeah if you have the idea the formalization

step as for most ideas in cryptographic proper course is just formality and I know from one session I was participating was in the audience it was a theendum session then some other mathematician also pointed out an approach which is equivalent to the uh I think it was in a context of having a truly distributed Prov for plon and it was about how to do the permutation argument and somebody pointed out the same thing the logarithmic derivative approach so it was in the air as post you know I'm trying to draw the connection though between the work you were doing on Fry and recursion to lookups it seems like a bit of a leap

was it just like a new area that became interesting to you when you came up with that work just happened I was just lucky to run over over Benedict's talk on hyper that's okay to think I was just trying my own exercise and then I came with using these logarithmic derivative to prove the plon permutation in argument and then I thought I mean it's clear was just an exercise but it took me quite a few weeks to discover its usefulness for exactly the situation you often face in the context of ckvm and it is you have a lot of columns often it's just a range proof but

they're subject to one and the same table look up and exactly this situation is where summing poles is superior over having a grand product argument that needs to involve all these functions all these columns and the main reason for this is that Grant product arguments they don't scale easily down without increasing algebraic degree that's a deeper explanation whereas some check they they just batch without increasing the degree and that's the main reason so actually I was and and that's also the main difference between what fluk up was targeting and what my work was targeting I was exactly targeting this situation

back then as orbis I think I don't know how many columns 16 columns subject to one at the same range not even range proof it was more their ckvm was more along the lines of bootle and others the ARA paper mhm 2018 19 or something like it and they were using a sort of uh this filter like bit pattern like decomposition for doing bitwise operations efficiently over the prime field and these lookups we had a lot of columns subject to this exactly being of the form having a zero bit at every even position how does this work like if we look at the history of lookup tables or

lookup techniques and evolution of that like I know that culk comes out at some point does this is this like a predecessor to that or is it happening in parallel yeah I'm just curious if it's optimizing in the same direction at all as something like that it's it's a different track or let's say different application okay I mean the whole whole line of work triggered by caulk which in the end found its highlight with CQ CQ yeah this is something I wouldn't know outside the kcg regime how to do it it's so specific that you have a commit where commitment actually is already already evaluation at some hidden point and it's

so specific to kcg and pairings that it's a whole world on its own got it so that line of work is the pairing focused one kzg track which kind of polinomial commitment scheme then is the log up for for arbitrary actually but it therefore because it looks at the commitment scheme generically it doesn't make use of any specific specific properties huh and can it be used this is actually something I've always been curious about can it be used with fry yeah yeah exactly that's actually that actually what what the connection uh that's how I met Daniel from polygon zero because I was looking just for other ckvm

applications and was asking how many columns uh for the same range proof or lookup table do you have turn out that uh don't nail me down on the number but I think the ckvm of polygon zero I always have to ask a game but it's like it exceeds several dozens of columns let's say like this if it's 80 or even more depends on the chip design in the end and in like this work that you did so I I'm sort of seeing the thread here so like you were you had done the fry work kind of int or plunky 2 introduced you to fry Starks then you were introduced to this lookup stuff and you were like actually let's create a

lookup Improvement side product it was just a side product but that could be used with fry now my question is like planky 2 plony 3 is out is plony 3 incorporating something like this plony 2 already incorporates log up now pretend I know like to call this logarithmic derivative look up log up though I'm not a fan of all these protocol names oh really I find them useful but yeah yeah of course it's useful to certain kind but sometimes uh this name just happened also because I was tired always to saying logarithmic derivative L logarithmic derivative logs logarithm know so at a certain point it

just happened to be log up L up yeah and uh so plony 2 implemented already log up yeah and we going to have it in plony 3 as well I see are you still working like I guess you made the sort of big shift to the logarithmic derivative or the variation that you described that you know you you think about it now but is there any more improvements is there any other kind of techniques borrowed maybe from other works that you've been able to incorporate into this is that even still something you're working on that's actually maybe a first question currently I mean not right now okay but uh recently like this was in August I was happy to work together with shakini

from starware and uh he was essentially driving as very simple observation that that came out of our learnings from lasso and Justin talers work on let's say multilinear work uh he did a lot of Publications in that field and uh it's just something that also something that I was not aware of that these what I always considered as a pre snark protocol the gkr protocol the gold vacala wrote plume protocol that this is useful in practice and it just shows once again my ignorance here because consensus did already did some used gkr in a similar context uh so the thing is

just popped up okay just learn okay there was this hint I would rather say in one of the many protocol variants of lasso the lass of paper which will say uh you can also do this Grand product prod argument without committing to the running products using this and that from a quite old paper of of Justin tler right and and that immediately brought Shaka to the idea okay why don't we do that for log up too and I said yeah should should work actually you're right should work and and actually this Improvement is cool from the point of view that you can you can reduce the whole lookup arguments if you have hundreds of

columns subject to one at the same table say one column table single column table you can say the only thing you need to commit to as the approver is one additional column and this carries just the multiplicities of the table entries that's it so no additional thing here I mean I would need to dive into log up a bit so in in log up you not just commit to the multiplicities of the table entries you unfortunately you need some helper columns and these are these are needed to turn a fractional subject means a subject over fractional Expressions you sum up the poles into a polom one just a tech technical thing actually not nice you know you need

these helper columns you need as many as you have columns subject to the lookup it was already improvement over the grand product situation of plup but now we can say thanks to shakini and gkr we can completely remove the need of committing to this help of stuff because we have a protocol that's round by round it's multi-round protocol though but still you don't have to commit anything you you prove layer by layer the sum of the poles being overall zero you always normalize the lookup balance as to say that if you take the poles from the

table with the multiplicities and the one from the witnesses they all need to balance out do we pay for this somewhere else say like in the proof size you not where you pay essentially I mean let's first uh look at Prov a Time so you you get rid of the cost of committing but what it costs on the other hand the price you have to pay for it is to run the gkr protocol which is a multi-round protocol that in each step that means let's consider uh the computation we do is a tree wise so consider that the leaf of a binary tree carries all the poles to make it simple and you want to add them up so

fractional Expressions so with each in each layer of the tree you combine two children from the layer below and add them up and this is topology of the circuit you prove so what you do is you have a layered circuit and you prove given the inputs which are already determined from what you have committed you prove the output the overall pole balance will be zero and that's done layer by layer and for each layer you have a multi linear sub to be done I mean it's a tree so the layers get half yeah in size at each level that's still fine but still it's work because the Su check itself is a multi protocol and multi-round protocols uh I

mean it costs all this extrapolation effort you have to do in a su check it's not for free but our operation counts in that paper indicate that it's worth it the more costly the commitment scheme itself is measured as a reference in let's say to commit one field element what is the equivalent number of say field multiplications to oversimplify the thing here then more costly the commitment scheme is the higher effective is this change yeah just to clarify though what is the name of the work you just described so this is with Shahar papini from starkware was there other co-authors on this too not that was the two of us uh it's I don't know

what's the how how did we call the title it's uh uh it's improving logarithmic derivative lookups using gkr or something like it okay and short form for this like format would it be gkr log up I would say yes exactly gkr log up I think Shahar gave a talk on the topic at ZK Summit 10 yeah he did exactly exactly it was originally under a different title like pomal tricks for Starks or something and he rug pulled everyone I know I know I know it just I mean just happened you know we have a we we share a a telegram group it just happened that uh yeah it was I would say love on the first s nice Shaka will kill me for

this if you like I'm going to definitely dig up the zk8 talks that you just mentioned had influenced you you did a zk9 talk on log up and then uh this zk10 talk we'll try to also dig up so that we can add this to the show not if people want to dive a little bit more into these in detail I want to sort of shift a little bit to another topic that Paul had actually suggested we talk about which is the work on Starks in finite fields that are not entity friendly that are not NT friendly let's talk about this work it seems like again a little bit of a shift from lookups but maybe I'm wrong yeah how did this work happen and

actually I guess at this point in Your Story by the way you've joined polygon Labs right okay when did you join them uh this was almost one year ago I think two days it's one year ago okay okay so like end of 2022 exactly so okay uh yeah I mean the first first month uh I I was just finalizing the log up paper and this thing but yeah I think it was essentially Danel pushing we should understand uh the breakdown approach to the tens of PCS approach which was also I mean I I remember that Orion that was like 21 even no yeah I don't want to say anything stupid but I I think 21 or 22

yeah I think it was Autumn 21 or something like this this was the last publication on that track I had in mind or we had in mind we should take a closer look is this an option because I mean at that point in time polygon zero was uh still and still is putting a lot of effort in finalizing the type 1 ckv based on plony too but Daniel was already let's say trying to get an idea let's sort out what will be next Generation proof system what could be so this is you you mentioned the paper Orion MH um who is that by I've quickly looked it up because I always forget the names of the authors but it's Chang Yen xang and Don song okay uh but coming

back to the the predecessor breakdown you also wrote a summary of this one is it in the same line as your some your fry or does it do more than that one could say it's it's it's a similar character it was learning about expanded codes and their expander analysis filtering out the quite suckint chapter on the expander analysis from the breakdown paper and my learning process on it so so essentially and moreover it did some small exercise refinements uh that have some impact for the Target Field sizes of blony 3 which is a 31 bit in particular theen Prime that which is our love I would say so

that brings us nicely to another one of your works on this meren 31 prime and the the field that comes with it can you tell us more about that like what it is what are the advantages over other small fields that we've seen exactly so so so I mean the whole thing is about next Generation proof system from po on zero and the field choice is not an easy thing as field Choice goes often with what type of proof architecture let's say proof system you use and and so onely I mean as we talked before about breakdown and expander codes I mean this is highly promising track of work for certain situations I would say because

it's poorly suent that means uh it seems like that there is I would say a law in proof systems everything that that improves Prov speed goes on the cost of the verifier yeah and in a similar way breakdown or Orion or now the recent work the improvements that is done from the ulana team Benjamin diamond and uh and chos and vas vas exactly uh so this uh these type of proof systems there have comparable po suak sness compared to even fry though uh being IUS comes approaches fry comes gets closer down to and uh but compared to to elliptic world

uh case where niik is based uh this is like incredible huge proof sizes and uh but it's super fast so coming back to my point it depends on the application very much where you would choose a breakdown like expander code like or not even expander code T of PCI like proof system in the style of breakdown and if you combine it with more suent systems fry based or elliptic curve base whatever you like so for very large instances and this is also one thing where often you know when it comes to multilinear proof systems as well as expander code in

particular it's so often people use quite inconscious manner the word linear time and you think it's better in any situation it's not necessarily as in because we are paying in proof size saying linear time is not so not even practically this istically is linear time yeah if you use expander code base M linear time that's even even here quite difficult let's say even breakdown is linear time only under certain under the assumption that your field in the hor Sark needs to grow with the circuit size anyway because it does it look up argument or permutation argument right and for that you need

field need need to be large enough to encode to host the zeros or the poles whatever technique you use for that is this something that Bas addresses this idea of like towers of fields and you can keep making them bigger and bigger as you go that's a different thing with Bas so asymptotically also pus would need to the fields which surf soundness which is like at least a 1 to8 bit large field mhm these fields need to grow with circuit sizes okay I mean and maybe better to clarify here so the term linear time is often used in quite loose motion but actually besides that that's

often something that is said to be a linear time prover which in a stricter sense isn't linear time much more than that it's about practical performance and often at at least to to to my understanding depends very much over which field and which concrete setup of the expander code is linear time encoding we observed that if you use classical R Salomon encoding MH that the break even Point say with a breakdown like expander code is at a quite large message size don't nail me down but something like two to the 20 field elements for the mm 31 or something like

that we're saying our circuits need to be of size 2 to the 20 for it to be worth it the message sizes you en code so that's even again a different thing if you look at tensor code right so it's some multiple of the circuit size it's a fraction of it if the square root reduction so typically it's like uh depends on how you lay out your reduction step there is some Optimum ratio between width and hate of the trace say of the reduction step that is done or the the interlift encoder or the tens of Dimension uh so there's a sweet spot which I can't remember uh where it is it's not the square root the symmetric square root

case with square root in withd square root in he okay and maybe I would need to look double check here where the break even bound with r Solomon encoder was maybe it's 2 to the 18 or something like this but uh it was unexpected high so that actually brought us again back to to R Solomon with the M31 and and we were exploring Daniel Jackie and I we we did explore about uh what can we do maybe just even ordinary approaches using the smoothness of the multiplicative group of the M 31 which is not absolutely nons smooth it's not

Mt friendly in the best sense but there are small prime factors 3 5 7 I think even 11 I don't know it by heart but we were exploring trying to find out using with different radiuses in the fft and and certain improvements on how to treat large radiuses like we were looking into radar algorithm and likewise so a lot of fft stuff I still don't understand what Marson 31 is though is it something you made is it a paper is it a Technique No m is it's just a certain prime number which seems to be for standard CPU architectures extremely friendly or okay for particular number exactly it's 2 to

31 minus 1 okay this is prime not every like if you take 2 to 30 minus one that's Prim so some there are few there few few power of 2 - one which are Prime 2 the 17 - 1 2 to 31 - 1 and is this then the number of the field that you choose kind of and then you construct things around it exactly so if you look at entity friendly Fields like goldilock babyar or baby bear mhm wonderful name I love it they're always of the form I think it's sometimes

called Sudan so they're like two to the some high power which is the field size essentially like 2 to the 31 or 2 to the 64 in the sense of Goldilocks and these are entity friendly those are yeah there few bits set yeah in their binary representation which actually there's a whole classical track of work that comes uh exactly speeding up computations and even if you look at standard of primes for elliptic curves old standards they use typically use exactly primes that have such a similar structure either you have few bit set it's like two to the some power minus two to the another

power and so on and the just few bits set because that eases arithmetics that eases modular reduction and the most radical ease you can have here is having a prime that is just 2 to the 31 minus one and nothing in between okay but that that you just described that is not NTT friendly or it is not as Goldilocks not as baby bear not as friendly as these okay much less friendly yeah I know we've actually covered this on the show I think in like the hardware episodes I might have even done it on the episode we did last week with Bas like I don't know but the NT friendly I kind of don't remember what that is at all so can we actually Define we probably should have

done it before asking the question but like why do we want it to be entity friendly what does that do entity or F fft friendly I I prefer even to say ffd fast fore transform friendly that's extremely helpful for polom arithmetics I mean all the snarks Starks they use what I like to call the snark principle the have polinomial iops so you encode the witness data into polinomial mhm you rephrase your target which is to prove certain constraints on the witnesses you translate it into the language of their pols which carry the

information and the nice thing with pols and relation on pols called them polinomial identities is that you can test them probabilistically often just at a single point and that makes the proof suent because instead of checking something where you would need to compute on the on full length polom length 1 million or even Beyond yeah here you just you get a shortcut it sounds like you just test the one your target identity which is equivalent to the initial goal at okay one or few points MH and and and that brings us to polinomial iops as it's called because

all all the snarks and Starks are essentially built from polinomial iops this is just the underlying principle of the proof how do you encode into pols and how do rephrase your target goal into polinomial language like so why with Bas the like reduction of the field does it make it less NT friendly or more NT friendly I didn't get the connection with Bas can you repeat the question so they they take it down to a binary field right to like they make it a very small field so does that make the the system more or less NTT friendly binary Fields is a different world okay for other reasons I will return to that

question let me first say let us revisit why fft is useful it's for Pol fast polinomial arithmetics mhm and there are two options you either have a field that has a cyclic multiplicative Group which is large enough and this group is the one where you do fft or entity okay so either you have a field that has a a multiplicative subgroup which is smooth enough nice enough to do fft or you have a binary field okay ah the binary field uh since 2014 you have a quite efficient analog on of the fft there which is called the additive fft but you would do

something else then it's like you you're not trying to get the binary field NTT friendly you're you're just using a different kind fft exactly no so let's say binary Fields per se are entity friendly mhm it's a bit hidden so when you mention that pus went down to bit bits Fields that's not the field where they do the R50 I see okay there's two sides then there's the binary field the use one in between I think it's it's the 16bit field that which is for their application The Sweet Spot and they use this 16bit field and they do R Solomon en coding okay which is fft based or

additive fft based to be right that to be concrete here the problem with the M31 over baby bear or even gf2 to the 16 which is the pus with Solomon alphabet field is that it's not a binary field so can't use binary uh the additive FD but its multiplicative group is not as smooth as wished like with baby bear or Goldilocks so that was just an open question to us is it useful this Prime could we can we do something with this Prime so I guess the question is how do you get around that and is it useful the funny thing is yeah we can get around and this just happened you know when

we're to exploring all this classical fft stuff from starting with Raiders algorithm for the larger primes in our multiplicative subgroup and just happened that I was thinking about why not just going to the complex numbers to the complex extension what I mean just the degree to extension because M Prime minus one is not a square root in other words x^2 + 1 doesn't have a root over the manen field and therefore you can just invent your imaginary unit you can extend the massen like you do in calculus going from the real to the complex number you extend the M as 31 to its two extension the complex extension the funny thing is

that this behaves very much like yeah so does that behave like a fft friendly field the extension yes beautiful exactly thanks for for helping me out here so yeah yeah exactly so so this is in contrast to the base field M31 which is short for the MSN 31 its quadratic extension is highly smooth it allows multiplicative subgroup up to or 2 to the 31 mhm because p^ s what's the size of the field if p is the m Prime the size of the field is p s its multiplicative group is p^ s - 1 and that factors into P min-1 * p + 1 and P plus one is the

sweet Factor here wonderful I guess maybe taking a step back from these explorations of breakdown and multi-linear land and explorations of different fields what's the recipe for plunky 3 that you settled on that we settled on uh if there is a recipe that's settled on I'm not sure what the stage of the project is it's still not fully converged one thing as I understand also from Daniel it should be a repository that is more modular than plony 2 therefore it will support not just a single proof system and also not just a single field but with the M31 the

menen fft as we like to call it going to the complex extension is is one of the things we're working on very curious to see yeah benchmarks when when they're out yeah yeah so so the in the end it's exactly so maybe one thing that I didn't point out what's the usefulness because you can always go to extension fields to be fft friendly MH but the thing is with the M31 going to the complex extension there is a bulk of well-known optimization just from classical signal processing that makes the complex fft of real data of real valued data efficient and in the same way all these techniques apply to that case of M31 either that

means even though you go to an extension in this case only a degree to extension but still it's an extension in fft cost you don't pay much compared to as if you had a native ffd not much more it's the number of multiplications even equivalent so correct me if I'm wrong I say this in my own words I guess from my own understanding you have this Prime field that is not entity friendly you do your entities in the extension but luckily enough the cost is you don't really pay for extending exactly or you don't pay too much for extending just very few so so we expect if we have optimized

everything down and do a fair comparison with an equally sized fft friendly F like baby bear that we will be in fft of same speed when it comes to commit read Solomon en coding we can do also a trick and that's actually let's say the other WR of that massen fft paper over the Circle Group as we call it or over the unit circle I think is that you can also if you look closer and it's just a simple calcul using fft for Series in the end if you look at the the extrapolated values that they can be rectified in other it's a sort it's like

polar coordinates a complex number can be written just as radius times the angle if you know what's the angle is you can just uh say it's just the radius is the thing that counts and something similar happens to the extension of real valued data over the trace to another domain which is the fry domain or the rich Solomon evaluation domain I need to ask something so you mentioned this M31 paper is it a paper is there work this is this is a write up on uh I mean everything that a publisher would like rather call a write up a write up okay so this is another summary of is this in the summary of breakdown or is this a summary of this is a separate one

uh I think uh let me see what the name is codes over the Circle Group thanks s Sol mon codes over the Circle Group yeah well we'll try to add this as well I think we're near the end of our interview and I want to understand what you're working on now I'm almost curious like now what will you be presenting at potentially future ZK Summits but yeah what is the like we were sort of talking about plony 3 would you say that's the focus of your work is there other it's so has to do with M31 has to do it incorporates all this stuff I guess all these concrete things you meet yeah when thinking about fields and proves cool there's some ongoing work with starware

with again with Shaka and David I'm not afraid I'm not allowed to say what it is about but that will be a CK 10 uh CK 11 is it not next one that would be a CK 11 topic cool I guess from the hints you've given so far if we're looking at fft friend Fields you were still in univariate polinomial it's still univarate yeah okay interesting it's an improvement over over the work that we opened up with the M31 uh F the ccle group thing ni and should be ready soon cool yeah actually I can I can maybe

make a little announcement here this is like our potentially our last episode of the year or one of our last episodes of the year but ZK Summit 11 over I don't know if you know this but we're uh we have a date set for April 10th in Athens so this is our current plan love yeah so people should Mark their calendar we're going to open applications in the new year for talks um just so I don't know if people are familiar with how we do ZK Summits but we actually have a selection committee we get our talks through application so it's not sponsored talks like other conferences so yeah it's a it's a separation there so we're going to be opening that met up in January and we also do an application form to attend

so if people want to attend they should also fill out the application form it's often limited space so yeah maybe we should ask them to explain meren 31 to frame yeah we usually pick a question that seems really in the weeds I don't know um but yeah maybe something actually r i I have one more question I would I would choose a more more I all I am um but actually or when you saw the Bas work did that change in a way the direction you were going like is this a pivot moment for your work for the work

of your team not sure uh uh it definitely puts also binary provs again on the plate maybe even for classical CPU architectures mhm but it has to be understood the concrete performance on these architecture not talking about hardware for Hardware I think it's great but it's it's the way to go yeah uh for CPU architectures we'll see in the end which is more performant and in the end you know it's so extremely hard to make Fair comparisons between proof systems even different fields because it you mixture not just the proof system itself in its performance uh it depends on the

application on the way you artize and so on there are so many and what task is it you ask people to do like there's yeah benchmarks are hard yeah extremely hard extremely hard I remember benchmarks I think even back to my Marlin learning times benchmarks that I think in the Marlin paper which if you look at the code did The Benchmark was setting up an examp sample rank one CS circuit that did not capture what it should capture actually in terms of performance I think it even was very much in favor to growth 16 right to the very very specific Pro structure of that sampled circuit uh so

actually did picked Marlin in a much less in favor of marlin back then actually and so so it's long story story short it's extremely hard first of all to make meaningful benches that that capture really the the generic case and the second is to make fair comparison between different proof system with different construction different field sizes and so on it's super this is a challenge super hard I personally if I may say something here what what I would like to have just from the entire community that is working on I it's Super H vibrant field but in general what would make me much more

happy is less advertisement of benchmarks that are not either hard to reproduce I mean in any cases of It's Always a contribution that's not the thing but when it comes to Benchmark and advertising I don't know maybe it's just me who gets older no I agree with you we see too many papers that show a table which in which the columns you know of the table are chosen in a way that their performance is going to be better everywhere yeah and it's not always true there's always is most of the time there is a tradeoff and I I see more value in papers that show you those columns where they are worse because now I get to compare fairly I get to get a sense of the trade-off space yeah it seems there currently a culture of advertisement uh

yeah which I don't like too much actually I mean we're in a weird space where our research is partly academic partly marketing right yeah but it not just comes from uh from from industry also in Academia I I know there's there are a few groups that are kind of like chain agnostic project agnostic like academic groups that are just focused on benchmarks but don't actually have something they're trying to optimize or like at least like optically show as better so hopefully there's more work like that coming out where people are just observing actually doing benchmarks where potentially they could show these different sides reproducibility would be one thing but for for the field we're working in is

that's not the only thing it's it's really just it's so hard to compare yeah and for certain situation just look at breakdown TI proof system versus more Su it depends on the youth case yeah that's totally fair cool thank you so much for coming on the show and sharing with us all of the work you've been doing I think your journey from like teacher to you know one of the authors on many of these works and like kind of pushing the field this is very cool and hopefully inspirational to people yeah thanks for sharing G and thanks for all the explanations thanks for having me I want to say thank you to the podcast team Henrik Rachel