ZKPodcast: Eli Ben-Sasson on the latest from StarkWare and the origin of mathematical ideas

Transcript

welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik [Music] this week I speak with le Ben Sasse on about the latest starker industries the booming zero knowledge research space and the origin of new mathematical ideas [Music] before we start I want to let you know about an event that we are gonna be hosting next month on October 26th we're

hosting the fourth edition of the zero knowledge summit this is happening right before the San Francisco blockchain week and about two weeks after Def Con we're gonna be bringing together the latest research and ideas around zero knowledge proof ZK snarks Universal trusted set ups and all the new research that's coming out about how to make that more versatile and efficient we're gonna be talking about Starks bulletproof and way more in this edition we will be looking at zero knowledge for privacy zero knowledge for scalability as well as scratching the surface of an emerging use case that is zero knowledge proof for interoperability applications to attend are currently open so please apply today I will add the link in her show notes just note there are limited spots and the event is highly technical we will be

prioritizing the researchers and devs already working in the space but get your application in early for a better chance of getting a ticket if you don't get a spot don't worry we will be filming it and sharing it on our YouTube channel which is a thing which you may not know but yeah check out her YouTube channel all else add the link to that in our show notes you can keep an eye on our Twitter account at zero knowledge fm for more details about the event or join in the conversation with our community on telegram so very much looking forward to this edition hope to see you there so now here's our interview with Ellie Ben's a son from Stark where so today I'm sitting down with Ellie Benson from Stark we're welcome to the show again thank you thank you for having me again

so this is the second time that Ellie is on the show we did an episode in January where we actually talked about Stark where Starks and about Ellie's background and how he got into it so this is a bit of a catch-up I guess maybe just start off what's happened since we last spoke Wow so a lot has happened Stark where now has a product that we're very happy with which is going to be a scalability engine for trading and for settlement we'll be launching it hopefully early 2020 at the latest

we're also advancing on our stark friendly hash selection which is a project we promised the theorem foundation to lead and there is so much going on in our team in terms of sciences and engineering and so a lot of fun so this interview is coming off the back of the starquest sessions and the Starks 101 workshop here in Tel Aviv I want to talk like maybe just to kick off about that so what were those and what why did you decide to do an event like that yeah so we had two events the first one was stark 101 it was a hands-on

workshop where folks came in sat with a jupiter notebook that our team created led by one of our engineers a shield and they came out with a full blown stark prover for a very specific computation the reason we did this is we want to educate about the beauty of Starks and this was aimed at developers and programmers the following day we held stark war sessions where there were two main themes the first one was how do Z K Starks fit in the larger ecosystem of

proof systems and cryptography and blockchains and the second theme was applications how stark where and its products fit into the larger ecosystem of block chains and what is the value proposition of our system and others all right so let's talk about the updates from Starke where you mentioned a few of them but let's go a little deeper into them the first one as as I understand is the scalability the decks work that you've done have you actually released a decks of your own we have not released the decks of our own and we view ourselves more as technology providers for backend of of

existing exchanges both centralized exchanges and decentralized ones so we would like to provide engines that in the first stage do things like settlement at scale earlier this year around July we announced and released our alpha start X this was a joint project with 0x in which we displayed scaling up of settling thousand trades in each batch at a sustained rate of 10 TPS 10 transactions per second and now what we're doing and this will be released on

on main it by early 2020 is we are building settlement engines at scale for non-custodial trading that will be back-end engines used by custodial exchanges that want to enlarge their liquidity pool and offer it also to traders that don't want to hand custody over to them so this is a the next step along that project of stark exchange we're working already with multiple exchanges famously coinbase has announced already that they're working with us on this in allowing their liquidity pool also to non-custodial traders so that's the news on Stark

exchange ok let's talk then next about the a theorem grant and the hash function work that you're doing and it's interesting I we when we had you on before I know that we mentioned at the grant but I don't know that we actually went into what was in the grant right so that might be good to clarify ok yeah so the etherium foundation nted us a sizable grant at the time was the largest that they granted the the goal of this grant was to provide the etherion Foundation and its developer ecosystem with very efficient provers and verify restore starts for repeated invocations of a hash function and one

of the main goals of this grant was to recommend to the etherium foundation start friendly hash at first we thought that will just you know scan the list of existing hash functions and select one of them but quickly we realize that there's a better way that would be better for the community which is to actually solicit new constructions of hash functions that optimize the parameters needed for them to be start friendly and by now we have already two new suggestions that can be added to one pre-existing one which is Mimzy and we funded again with funds from the grant that we received we funded both of these efforts we also funded a cryptanalytic

effort to understand these new constructions from the point of view of algebraic ripped analysis and grab no basis algorithms which are very relevant and important to these new constructions and we're progressing along so the next main step is going to be we're convening a committee of expert in symmetric cryptanalysis led by Professor and canto it will be held in Paris mid November this committee will you know examine the various constructions and recommend by early 2020 the one start friendly hash and then we have starker has roughly half a year to code it up write an efficient prover and verifier run audits

on it and then release the code to the Assyrian foundation when when doing this kind of like finding a new hash would that automatically work within the current aetherium construction or would you need to do something to actually enable that some of the hash can structions would work pretty well already on the existing aetherium framework and for instance we actually are running now a start friendly hash challenge where there is a bunch of smart contracts that payout ether to those who find the collision in some of these candidates so by the way just as it was very funny that exactly as the

session on the stark friendly hash function selection was going on we were alerted that the very first collision and one of these challenges was found okay and one ether will be handed out to the solver to find the first finder of this collision so the smart contracts that we wrote for this competition are already existing as smart contracts on etherium now there are other constructions especially those that are based on binary fields that are much harder to implement over aetherium right now but I'm guessing that the etherium foundation once there is a selected start friendly hash the etherion

foundation probably will want to consider doing some consensus chain to allow you know pre-compile for it or add it to the existing hashes that it already allows like a check but this is really you know not part of our project this is up to the etherium foundation to decide afterwards how do you define what a good like what are you looking for is like well how do you choose between hash functions yeah that's a great question as always the the most important aspect would of course be security because if the hash function isn't really collision resistant or doesn't look pseudo-random enough then then it's no use but having said that there are some very specific algebraic parameters that you would like

to minimize if you're interested in making it stark friendly and those parameters if I had to you know summarize them they would be about making so suppose you want to implement your hash using an arithmetic circuit an arithmetic circuit is a sequence of operations the allows only things like additions multiplications divisions what you want to do is minimize the number of operations that take the input to the output write a hash takes an input and then produces an output so if you have two hash functions and one of them has a thousand operations and the other one has a hundred operations the second one would be more stark friendly than the first it's slightly more complicated

than that but this is roughly the idea of it the problem is that as you decrease the number of arithmetic operations you're also maybe compromising security because maybe it's just too simple a function for instance if you just take the two inputs and multiply them and that's not a good hash function you probably want to do a whole bunch of operations so that's the tension between maintaining security and minimizing the number of operations needed to compute it when you minimize the number of operations does it make it faster yes it makes it faster definitely it makes it it makes proving statements about it more efficient which is one of the main goals of being start friendly at the same time it makes it more

susceptible to all kinds of attacks and the most potent one seems to be the ones that are based on algebraic geometry and things called grab no basis and algebraic crypt analysis those are the ones that are new and most threatening to to this kind of minimization effort cheers where where is most of the hash function research happening like where is that is it in other fields is it in the field of cryptography and various universities that's a great question and and I learned a lot as I as I was going into this project because my upbringing is not as one of these experts I come from

a very different field of computer science so within cryptography so I learned there is a sub branch that would be described as symmetric cryptography as opposed to a symmetric cryptography you know public key cryptography RSA diffie-hellman that sort of stuff and which is very algebraic and number theoretic that lives in the asymmetric right that's the ace symmetric world a lot of number theory a lot of elliptic curves that kind of stuff now within the symmetric key cryptography where you have things like AES and you have the hashes and a bunch of digital signatures as well post quantum ones and so on there's a

very vibrant community I should say I realized that I learned that most of it is in Western Europe so Paris Belgium Germany Luxembourg those places it's a very uh it's a very hot topic and a lot of the experts reside there and these are in the cryptography departments of universities or are they in industry more so in in in academia okay but also you know some of them consult or go back and forth or also in industry is there like I'm just wondering like the sort of the call out to an open source community looking for hashes like what are you are

you also pinging the people in the university or are they already aware of this like are they already kind of participating in a lot of these ecosystems the the people we reached out to are the kinds that are already doing this for a living for a very long time so one of the first teams we guess the very first team we contracted is the cosec team at low even in belgium yeah that is led by vincent raymond who is actually one of the co-inventors of the aes symmetric cipher and his team is so in particular seem in the hygge and tama sure have led this effort of suggesting one of the constructions so and and this

whole community of researchers they engage often in a lot of competitions about selecting and building new hash functions and new ciphers I learned that that's a lot of what they do and so this is not new to them because I work hmm-what like who did they usually work with like they're not usually working they're not exclusively working with blockchain stuff I imagine what like what world is that I think and I may be wrong here so so I hope my you know friends symmetric cryptographers will forgive me if I'm making huge errors here but I think that often first of all a lot of industries often need you know various let's say

you know low consumption new hash functions or signature schemes or ciphers there are a lot of government solicitations coming out from NIST and various other international standardization bodies so I think a lot of those are routinely interacting with them and you could say that you know the theorem foundation is you know could be thought also as one such or it will be I mean any blockchain governance is also a standardization body for this particular blockchain so it's it's it's kind of in the same ballpark of the stuff that you've been doing already mmm cool yeah so going back to the actual project is

it a because this competition this is about finding like a collision so almost like breaking a hash but the other side is this like evaluation how far are you do you have a do you have a favorite no I don't have a favorite III want to be or we at starker want to be agnostic we hope that it will be secure that's very important the worst thing that could happen is if something is selected and then actually a lot of stuff is built using it and trusting its security and then a lot of economic value is already sort of hinged to it and then someone says oops you know here's a collision or here's a bug that would be very

unfortunate so it's very important that we remain you know agnostic as to who wins so like but will there be one hash function at the end of this that is the will be at least one definitely but there may be a basket of hash functions yeah I'm guessing that what will happen is that the experts when they convene in mid-november we're sort of you know sit and really try to kick the tires of these things and sort of pull and push and try all kinds of attacks and it's a bit of an art and understand like understanding what works or what makes you comfortable or less and it's an art I only observe from the outside it's not

something that I practice in or have intuition about which is why others are going to be selecting it so I think they'll end up by saying I mean there could be a few outcomes it could say they could come out and say look all of them look pretty safe to us so so then it's basically up to starker to define which one is the most efficient in terms of it's a start complexity could also be that they will come out and say look you know here's one or two that we think are far safer based on a whole variety of reasons and then we'll probably build those hmm so what's next for struck we're so stark or is a bit of a unique creature in blockchain space we are a

for-profit company nevertheless what we deal with is is can be viewed as part of something that could be infrastructure and they're not too many other companies like us so we're constantly thinking about what next so right now we're very very happy with our first business model which is prove er as a service which means we're releasing a verifier on chain that verifies the evolution of a very scalable system and we keep the prover super efficient provers closed sourced and run a service that we offer to exchanges that work with us we're

very happy with exploring this business model and we hope to get our customers using it early 2020 beyond that I mean immediate steps are gonna be - you know validate this business model to enlarge the capabilities of the stock exchange system to sign up more customers so those of you listening out there if you're running in exchange and you expect significant volume in non-custodial trading you know please reach out to us we also want to enlarge the same prove eraz a service mechanism to things like payment systems we can scale up to tens of thousands of payments being verified within a single aetherium block today and we'd very much

like to work with payment providers and payment processors to offer this functionality also under the prover as a service model later on were exploring how to engage the developer community a bit more and offer what we call b2d tools so business to developer tools so that we can have a more vibrant community of developers that use Starks and build their own statements and systems and I guess that's pretty much what's right now on our mind what kind of future like the company you just sort of mentioned it's a for-profit company

what do you imagine it evolving into like have you looked at a lot of those companies that work around open source do you see yourself becoming like a I don't know like a service provider for an open source protocol like how do you envision this company wow that's a really uh that's a really yeah making predictions is very hard especially concerning the future let's see what can can i you know comfortably say and not eat my hat you know in a few years we very much believe that Starks are gonna be used in a whole lot of places in blockchains first and then also in the financial ecosystem at large

in the end and we very much believe and we'll strive to be one of the main providers of this technology now the way we might end up let's in five years time or maybe ten years time we could be something like you know this is very long range we couldn't that we could end up being something like you know Nvidia or Intel where we sell hardware and we sort of release a whole lot of tools that that make working with this hardware very efficient that's one long-term option we could be the analog of some cloud provider or service provider that basically runs these big servers super-efficient proving and you know also releases and supports a vibrant

open-source community that develops other things and and you know those comfortable building their own proving systems and so on could could will work with without us that's a second option a third option and this sort of ties into what blockchain governance might might decide would be to partner somehow with with existing block chains to offer this infrastructure at a more lower level in return for some form of you know I'd say at least limited exclusivity or something so this model that is used in infrastructure building called the Bo T

model build operate transfer which is often used with when when governments and countries build you know bridges or other things comes to mind where and and here this is not only about Stark where this is in general about how the block chains want to foster a thriving private sector that builds infrastructures so think about wallets I would like to see block chains coming to wallet providers and saying let's now run an auction for we need three wallet providers that will be sort of open sourced over the next you know for the next five years and the winner is based on price and quality and

whatnot will be given sort of a license to offer their software and they will get maybe rewarded as part of the mining reward of the process and after this period the you know the governance will find a new system or run a new auction I think this this this you know would benefit the ecosystem so that's another option that maybe we become part of the infrastructure or layer in some place or other okay so now what I'd really like to touch on is something you brought up in your presentation at Starke where sessions and that was about sort of the xperia all noticing this but this explosion of new

papers new protocol ideas kind of new angles to solve some of the problems that zero knowledge of proofs are trying to solve what do you make of this so I think this is great news for for the whole space we called it the Cambrian explosion of ZK peas because the camp Cambrian explosion was this era in in geology or the history of the earth were all of a sudden from this primordial soup of microbes within a very short period of time a huge number of animals and plants emerged about half a billion years ago so ZK peas and and proof systems in general have been

around theoretically since the 80s mid 80s ever since this amazing discovery by goldwasser and McCauley a knock off in 1985 and they've been the playground of theoretical cryptographers for a very long time starting a few years ago about 5 or so they started being deployed and now there's this boom there's big explosion and it's like in the last month it's gotten pretty wild yeah a lot of papers are coming out and announcements and you know so it's it's terrific that's really great being somebody who comes from academia when

you see a new paper like is there is it such that you release a paper into the world and then there are dedicated researchers who really know the stuff who go into it or is it kind of like if it's popular enough you're gonna get some attention I'm just wondering how that works because obviously in universities it's really formalized things have changed even in university so when I started doing my research 25 years ago even though the internet was around you didn't have archives where you can just upload papers so the process was very structured maybe too structured meaning that the only way for your paper to be

known was for it to be published in in some journal or in a conference proceedings for that to happen you had to send it again there were no archives just uploaded say I'd to send it and then it went through a peer-review process which was far from perfect in both false positive and false negatives so sometimes it admitted papers that were later found to have you know bugs in them and the other way around sometimes really amazing papers were not accepted for instance a very famous example is that the very first paper on zero knowledge proof was rejected I think from three conferences that it was published is that the one in 1985 yeah why there's one in 1989 well no that's

the that's the sort of the journal version of it but but what happened I mean and this paper famously wrote one you know a bunch of awards including the curing award and the getter award again the peer review process always had and always will have some you know false positives and false negatives this was let's say up to 20 years ago now with the abundance of like online publishing venues what happens is that is that you just need you know to write something up and you can immediately post it an extreme case of this that everyone saw was clearly problematic is of course the notion of a white paper that comes along with an ICO of some coin right so

there might be even some mathematical formulas in it but you know this is clearly not something you want to do anything with so now with this abundance of immediate publishing venues there is of course this on the one side it's really really good because you can do you get your ideas out there friends more people I guess can get their ideas out there you don't have to be part of some instance right even this guy who no one heard about likes by the name of Satoshi Nakamoto can just publish a paper that yeah happens to be pretty important there's also of course the danger that comes with it that you know you might just very quickly associate a

lot of credibility to the paper that is in PDF format and you prynt and maybe even has formulas in it so I think it's a better way that we now can publish things immediately and peer review was never perfect but we should at the very least you know make sure that the T's are crossed and I's are dotted and have some experts look at that papers and sort of pine on them and and and ensure that I have another set of eyes on the ball so that things don't fall a break with so many new papers and ideas and acronyms coming at us like

what what is like the danger and maybe like how should we navigate this I would say that okay the abundance of new ideas and new acronyms is actually very good but we should proceed with caution so I think what I mean let's science move at its pace which should be as fast or as slow as as science and scientists move let the scientists have enough time to sort of cross the t's dot the i's feel comfortable with what they're publishing let the scientific community have its

time to look at things and peer review it and evaluate it and proceed with caution especially if you want to you know we're all eager to have like you know the latest and greatest technology at our disposal when it comes to things that are based on cryptography and advanced one at that you really have to sort of balance that with the desire to future-proof your system and not just be out there as quickly as possible but be sure that you are preserving your

customers or your users assets for the longest possible time in the safest possible way it sounds like it comes down to trust it's the long-term trust of the system that you should be aiming for a not first market yes the long-term trust the soundness of the foundations this we should always remember we're building an infrastructure that will have trillions of dollars of value flowing on it it's far more important to be sure that the foundations are solid then to make it as fast as possible or have it out there as fast as possible

cool so I'm really I'm really glad that we talked about that because we are experiencing right at this moment an explosion as mentioned so there's in the last month or two months it's just like it's awesome but there are new papers dropping from like really established teams and kind of introducing all these new ways to think about these problems in your presentation at the star core sessions event the other day you actually outlined you helped me at least map out what's going on like where do those different protocols live so how would you break down this landscape okay so the categories I was referring to are related to the basic cryptographic

assumptions that underlie the different Z KPS that we see emerging and there are three types of such assumptions the the newest than the one that was deployed for instance in Z cash comes from this family of knowledge of exponent assumptions and which is a cryptographic assumption that started being used in arts and and gets redefined and with with some new variants of it with almost every new paper the second family of constructions which relies on assumptions they're a bit older those are constructions based on

elliptic curve discrete log problem I guess the most famous one from this family is the bullet proof system that's deployed in Monell and these cryptographic assumptions go back to the 80s up to the aunt and the third family to which Starks belong along with other systems such as all Varley Givens ekabo to mention a few relies on the cryptographic assumption of a collision resistant hash and this assumption has been around since the mid 1970s and the reason I was talking about these three different categories of proof systems relates to their future proof nests because the more fundamental a

cryptographic assumption is used and the longer it's been around and the more other stuff that is tied to it the safer it is considered so knowledge of exponent assumptions have an economy of roughly half a billion dollars the Z care system what what else is in there what other kind of protocols are in the knowledge of exponent so systems that we know of by now that that require such assumptions are things like sonic and plunk those are very recent constructions they they require knowledge of exponent assumptions and snarks do they fall in there as well yeah the snarks used by Z cache yes snark has also a more general definition

that you can incorporate other things but usually when people talk about snarks they refer to the ones in Z cache and and that definitely so snark sonic and plunk come from this family okay so this is a rather recent family it has roughly half a billion dollar worth of an economy around it if you look at the elliptic curve discrete log problem it has in it things like bulletproof and possibly a halo and supersonic depending and when I say possibly it's because the exact cryptographic assumptions are not quite completely spelled out in all of these things but it looks like it requires only elliptic curve discrete log and and pairings as well and these

assumptions go back a little bit further to the again 20 years earlier or so and there's a bit more of an economy built on them things like certain forms of ssl key exchange and identity base cryptography and then the third family to which our Starke system so so just like snark Starks are a bigger definition but they're typically associated with a very particular implementation so I'm referring to that so it uses hashes which have been around since the very early days of cryptography the mid-70s and basically all of the e-commerce and you know all of the internet infrastructure security relies on at least such an assumption so that's why we at starker think this is

the safest and most future proof ready system did these distinctions have anything to do with being post quantum secure or is that a different category completely so it's known since the breakthrough of Peter Shaw that quantum computers can break the discrete log problem and if you can break the discrete log problem you can break things like Halo and bulletproof sand these systems and you can also break the knowledge of exponent assumptions used by the snarks and Sonic and plunk so if you have a quantum computer then the two newer families sort of fall down that's one of the aspects of having a system

that is more future proof as long as you have a hash function that is post quantum secure then there's at least hope for these other family of systems based on interactive Oracle proofs and similar things and very recently there's a very beautiful paper by Allison Lowe chiesa who's also one of her is my co-founder at Stark where and two colleagues on on actually proving that in certain model the quantum random or model these systems are actually safe even when you compose them into a non-interactive proof so there's there's

even some theoretical substantiation of having families based on collision resistant hash as being safe to quantum computers that's even but that's interesting so it's like the older cryptography can go further into the future yeah that seems snow so from uh sort of history of science point of view what happened was that it initially seemed to some that systems based on those older techniques are not as efficient and people looked for newer ways to get efficient systems so they looked also at newer cryptographic

assumptions I think the the work that started this was a beautiful paper by two of my colleagues from Technion Valley Cheyenne al Khushi Leavitt along with Raphael Ostrovsky from UCLA who basically said look if we use things known as additive homomorphic encryption we can sort of bypass the gnarly parts of the other kind of efficient systems and and because of that you have these newer systems that have more exotic and newer cryptographic assumptions that are also prone to quantum computers but what people have not noticed they're now noticing a bit more was that actually we've been making a lot of progress along the earlier kind of route and getting the most efficient systems there

that also happened to be post quantum secure there must be so much being shared between these systems to like as much as we're outlining them as three unique types of zero knowledge like just in terms of techniques they imagine there's a lot of sharing definitely all of these systems all of the efficient proof systems use this beautiful technique called arithmetic it was invented in the early 80s by the great Alexander oz Bob [Music] an amazing theoretical computer scientist and use to prove circuit lobe lower bounds and computational complexity and later were transitioned

into the area of proof systems in this beautiful paper by loon calif fault now and nissan ah I think Gabi's on mentioned this one yes yes definitely well a lot of people mention it right it's a very important paper that use the earth Mehta's ation in a new context of generating efficient proof systems so all of the systems and all of the three trees use some form of arithmetic in arithmetic is this process of converting a problem about computation into a problem about low degree polynomials and then the differences are how do you actually know that your prover is using low degree polynomials and here is where the three

trees grow and use different techniques I see is it do you do you force something into that format or is it more of a test as to whether or not it is already in that format that's a great question and I think the answer to that so do you force your prover to use a low degree polynomial or do you allow her to do anything but then sort of check whether it's right it is a low degree polynomial the answer to this is exactly what distinguishes the oldest tree from the two newer ones because in the oldest tree the one built on hash function the way the system works is you tell the prover look you can use whatever you want but be be aware that we will test

and check whether what you're using is really a low degree polynomial and that only requires hashes whereas in the two newer versions the one that use elliptic curves and knowledge of exponents what happens is that there is a bunch of parameters or keys that are used in order to force the prover to necessarily use only a low degree polynomial and and so it's really the difference between the different trees and ways you get zero knowledge is the difference between do you allow anything and then check it or force the prover to use only a very particular kind of representation that's an interesting way to think about it in

this so you mentioned like a you know new ideas from the 80s that then permeated all of these groups but are there other I think I asked you this on the last episode as well the last one we did together but I'm curious if maybe there's there's new info here since we're deeper in it but are there other places or are you seeing some kind of techniques coming from other worlds possibly you know outside of of the cryptography used for zero knowledge that are actually entering in and being used across these different types of zero knowledge well all the time you have new ideas coming in typically from from you know other fields of

mathematics so for instance one theme that we already explored in theoretical works but hasn't really made its way into into implementations yet is is the use of generalizations of low degree polynomials things known as algebraic geometry codes or Copa codes that have some advantages so there's a bunch of works that I and my co-authors have written about the advantages of these things but they're not yet deployed in any practical setting I think what we're currently starting to see in some of the talks we had at the start of our

sessions were already exploring this is for instance taking techniques from the collision-resistant hash world things like fry and deep fry that that allow you to check if something is a low degree polynomial and then importing them into the world of these other systems that use discrete log and so on and so anywhere ones yeah the newer ones so and I'm sure we'll see a lot more of this sort of moving between different areas and incorporating ideas from one area into the other I did I think it was through the Starck where 101 workshop or through conversations after where I learned that there is some technique that was taken from FFTs from fast Fourier transformations and that was

incorporated into Frey yes let's actually define Frey so Frey let's open the acronym before so EF is fast R is reed-solomon which is this family of codes that uses low degree polynomials and the I stands for IOP of proximity I appears this model in which you know the post quantum secure collision resistant hash based ZK peas live so Fri stands for fast reed-solomon IOP and it is in stark constructions yes what's its purpose in the construction it is exactly the way we answer your question about how do we know that some function

is low degree so it is the technique by which we let someone say here's a Merkle tree that its leaves if you open them up they will be an evaluation of a low degree polynomial which is all weak the only thing we need in order to get all of the zero knowledge proof systems that's all we need we need to know that the prover is using you know one low degree polynomial in his answers so Frey is a way to check efficiently if someone has actually done this or if they're cheating and it uses this this technique from FFTs so and that's like a I mean I

know fast Fourier transformations from music signal processing right so very different part of math yeah so I always say ok I had the fortune of teaching you know the FFT in many courses and the first thing I say about it is the following that there are these concepts in math that their power and beauty is in having so many different interpretations and ways of using them so one of them is things like a matrix or a linear transformation it is such a powerful thing another one is determinant we is you know it has so many interpretations and meanings and you can

generalize it in so many ways another one is derivative of a function you know at first you learn that it is this angle then you learn that it is this linear transformation with a whole bunch of properties and and it you know goes on and on so the Fourier transform is yet another one of those amazing and magical concepts that has so many different ways of viewing it in using it so it's definitely used in signal processing and it's taught as this way to move from one representation to the other from a time-based representation into a frequency based one but it also has huge generalizations to number theory and group theory and analytic

functional analysis and a whole bunch of things and in particular it is also a concept that is used essentially in all of these proof systems there will be an FFT somewhere that does something pretty efficiently and it's needed so in the snarks used in z cache and in Sonic and plunk and in other systems you will have a 50s lurking around what's new about Fry is that it sort of starts doing an FFT but then it sort of speeds it up and which actually makes the Fry protocol even faster than an FFT in terms of its asymptotic running time and it achieves a slightly different goal of knowing that a function is indeed low degree is

it is FRA something that came out of Starck where industry research or is that something from academia where it where's fry from so the fried paper has four co-authors so one of them is so myself IDO bento of you know in harsh and my captive it was published when we were all in academia okay and what has come out of Starck where by now is this improvement on it called deep fry is a great name by the way yeah I agree it credit goes to our two co-authors who are also scientific advisers

starke where professors shibungi Soloff and swastika polity I don't know which one of them came up with the name but but we agreed that it's a great name and also Leo gold built from from Starke where together with me were four co-authors of this new paper I just wanna I just want to say that I believe that someday someone will find an improvement and and I already know what the name will be it must be a stirfry because if I fry and deep-fried must be stir fry nice cool what what does what does deep-fried do exactly so I don't think we tell which said that I actually well it instead of frying something it does nothing puts it in a lot of oil

[Laughter] no but jokes aside what deep-fried does is it sort of the title of the paper talks about deep fry a sampling outside the box which what happens with let's say with fry as you start with a Merkel tree or a commitment to some function that just as sort of a table of evaluations let's say you know there's one entry for the functions value at the point zero at the point one at the point two let's say up to the point one thousand so we have this big table this

table might look big but you know they're way more entries in the world and just those thousand entries so previously and fry all the queries that we ever did when we were sort of checking whether this is a good low degree polynomial were always to this domain to this let's say 1,000 entries that the approver committed to with deep fry we sort of go outside the box and we suddenly start making queries about let's say what is the value of this function at the point 1 million which isn't inside the table oh wow and this is the main idea that goes into it and then we incorporate the answers in way that make the system far more efficient and have better security what would you call like what's

comparable that technique is there anything else that you could say does stuff like that like where does that idea come from even this idea of sampling outside I don't know I mean what comes from where all ideas come from right I don't know where they come from like yeah that's a really good question no I mean probably some is there a word for that technique well we call it deep that's domain extending so we okay so it's domain extending for eliminating pretenders but look we needed the word deep somehow yeah you

just need to open the acronym no we do extend the domain and it does eliminate pretenders in a way that I won't go into it has to do with things called list decoding or pruning a list of contenders no no but I think the question you're asking about is like where do mathematical we're doing new mathematical ideas come from so I I mean I confess I don't know of too many places where this kind of idea was seen before I'm sure there might be areas but but I'm not aware of them this particular idea and then um yeah I mean I always go back to this beautiful paper by Henri Poincare where he sort of muses on on you know the nature of mathematical creativity it's a must-read

everyone must read it what's the name of the paper I think it's called first of all it was written in French so but I know the English translation and the title is I think it is on the nature of mathematical creativity so in a pond color in addition to being this amazing mathematician and you know the founder of a gothic theory and other things also was you know not all mathematicians can sort of take a step back and talk about the process of mathematical creativity but he was this rare genius that was also very articulate about it and he has this beautiful paper that you know every time I read it I get goosebumps because

it resonates so much for instance he talks about this process where you know he comes to a problem and he sits for two weeks and thinks about it and he's working very diligently and very hard like sitting at his desk eight hours a day but he's making no progress and then he goes on some vacation or something and he's crossing a bridge and as he crosses the bridge like thinking about nothing suddenly he sees it right it said like this solution emerges and the minute it emerges he sort of he doesn't need to write it even he like sees it in its

entirety and like completely understands and then he says okay now I just need to write it down but he sees it completely and and then he asked you know what what happened here and he says well look the two weeks I spent on it were not a waste of time I would never have had this revelation had I not spent that time but what happened in between I don't know like the best description is I mean maybe you'd have this process where you're feeding your subconscious yeah with all of this work and then your subconscious sort of connects all kinds of things and then at some point sort of floats up back to your consciousness and then you suddenly see something that you

had no idea that you could see I almost imagine it like you walk down various paths and even though they might seem far away you're eventually defining a map I don't know if that's in any way uh it's all about exploring this there's this unknown space I mean that science right it's you know exploring this unknown space now in mathematics this unknown space is very abstract but it is you know this unknown world and you're sort of walking and exploring in your complete darkness and as you're doing so the amazing thing is that you're I guess your subconscious is some Faculty of your brain as doing stuff you're unaware of and then all of a sudden sometimes like you know you suddenly see stuff so that's I mean that's the best answer I

can give to like you know where do ideas come from I love it that's so good so I want to say thank you so much for coming back on the zero knowledge podcast and talking to me about all of this I wish Frederic had been here unfortunately this was a bit of a spontaneous interview please do come back again thank you I will gladly and thank you so much for tolerating me yet again and to our listeners thanks for listening