ZKPodcast: Ariel Gabizon on his work with zkSNARKs and the beauty of math

Transcript

[Music] 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] in this episode would sit down with ariel Gabi's on to talk about some of his working from photography his path through Zeke Ashe and some of his latest work on the violin protocol before we start we want to say thank you to this

week's sponsor stark where stark where we'll be putting on the stark wear sessions in Tel Aviv on September 16th the event will be bringing together the brightest minds in the field of zero knowledge proves from both the academic and application arenas topics include self custodial Trading starts for layer one stark friendly hash functions and other cool things you can do with stark proofs fun fact I will actually be hosting one of the stages so if you're interested in this exciting cutting-edge tech do join the starter sessions or come a day early for the stark 101 workshop where you can actually build a stark prover from scratch use the code Zeke a podcast to get 20% off any ticket we have about 50 of these available

so get a fast as always info will be in the show notes so again thank you Starck we're for supporting this podcast and now here's our interview with Arielle Gabi's on so this week we're sitting down with REO Cabazon and it's pretty awesome to have you on the show you have an interesting background you've worked across a lot of this zero knowledge space and have done a lot of interesting work in this so I mean you're you're with the Z Cash company from the beginning and migrated to other projects now super excited to take in some of this welcome to the show thanks nice to be here given that you are cartographer I think what would be

really interesting to hear is those early days of what you were doing maybe in your studies or where have you where you started to get excited about this initially I didn't like cryptography it seemed like a really negative view of the world to me like why is everybody an adversary it's it's very depressing I think and I think I've actually become more paranoid because of that since I'm doing cryptography but sort of like if you're deeply in love with someone you'll go you know to a nightclub with them even though you don't like to go out at night so I I fell in love with Bitcoin when i when i read the bitcoin white paper and i saw that yeah that's where bitcoin wants to

go so if i want to be with bitcoin i have to be there too especially since I tried to see you know with my skills in my background how can I best get into this world so this is I'm talking at 2014 I have to give credit to a friend of mine IDO bento of that already told me about Bitcoin in 2012 but I was too stupid to understand it's a really cool thing and only when I looked at the white paper in 2014 also credit to another friend of mine Matan field which is in the field then after I read the white paper I'm like okay I got a my life has to intersect with this thing

and since I had a pretty heavy math background for from doing many years of theoretical computer science the best way for me to contribute or get into this world seemed to be with these zero knowledge proof sore these these Snorks as we call them today and practically the the way I did that I was then a postdoc at at Technion University in Israel and L events a son which a few years before that I did pure Theory stuff with him was getting into implementing stuff so I approached him and then we worked together for two years on what are now called Starks and the the early early versions a nice

anecdote was when we when I started working on this it would take 10 hours to make a proof about a program that does I plus plus 3 times and of course we've we and after that they have made in stark where incredible progress on that that's interesting so you come from very academic background did you have any sort of developer a programmer job in between there before like digging into Bitcoin world or did you compare away from the academic purely from the academic space I like to program as a child but I had a really long break from programming at least until I joined Elly's Start project and

then I was getting back to it a little so you'd said you were excited about the Bitcoin white paper but were there any other papers or concepts along the way that got you really excited sort of the paper that got me into theoretical computer science in general of which I would say cryptography is a subfield because before that I was more into the direction of AI and you know brain research maybe even this was a classical paper that in a sense I would view it as the paper that started this whole field of snarks from 1990 a paper of lund Fort know Carl Orff Nissan this was the first paper with an example of how we can get

what we can call an exponential speed-up in verification so what this paper did is I like suppose I want to prove to you there that some Sudoku puzzle doesn't have a solution the natural way to do that is you try all solutions and see that none of them work so this paper gave an efficient method where a verifier can quickly without going over all possibilities be convinced that a certain problem generally speaking a certain Co NP problem is like unsatisfiable it would be maybe a bit of a stretch but not much of a stretch that everything we're seeing up to this point the snarks of today you know after that paper how much can we leverage these how

much can we milk out of these ideas and that milking has brought I think all the beautiful developments we've seen since then the Starks the snarks the use of pairings so you joined you fell in love with Bitcoin then you joined Ellie in his quest of Starks how did you go from there into Lexie cash and and these other projects well so we were working on this Starks for about two years I was working also with Alessandro chiesa who works with Ellie and I was visiting Berkeley and then he arranged a meeting with Nathan the the CTO of Z cash now electric coin company I think

on the one hand I felt at that point I may have been wrong that the Starks are it's gonna take time for them to get into practice it may be happening faster than I thought at the time exactly after talking to Nathan I thought okay they have this maybe little hole they need to fill of someone with some a certain math background to help with this MPC for the parameters a little after that they contacted me about a part-time job and it seemed a good point for me to try something a little outside of academia what year is that so this was I joined Z cash part-time in 2016 June or July what was that like it was

it was really really good so the first few months I was basically only working with Sean bo on how to do this MPC so this is the original trusted set up ceremony where there were like six parties involved or something like that and like the initial parameter setting were set up this is not the powers of tau thing that came later yeah this is the original set up so basically what we had to do there was a paper by five for the Z Cash scientist elements of saw no sign of yes mother's fears around throw a mirror in Matt green about how to do how to do a set up for first knock

parameters I guess a lot of the work of those few months was how to I guess translate the ideas of that paper with a seat a few simplifications into code I think what I did most effectively was sort of being a translator between math papers that are written in some slightly more abstract general setting to getting the exact code you need in a certain in a certain case that's a pattern that I see in a lot of our guests and people we talk to him people I talk to in this base in general the most valuable people are those that can read a paper and translate it hence the code it's apparently a very rare

talent I wonder if it's rare or it's that at least till a few years ago the people with that skill were just not you know communicating with engineers and I wonder if that's still like today you look here at Z Khan you have a lot of people who can also implement things and understand the papers though perhaps another side of it is now I think academics are very much aware that their paper might be implemented the day after they publish it so they're more careful to actually make it implementable yeah

or maybe they they try to write it in a way that's yeah it's clear how to implement I'm curious I don't actually know this what was the initial set up written in was it C++ or was rust already on the table back then it was all written in rest that's cool so where did you go within the company after that you said you sort of started like almost as a part-timer on this and then kind of got fully into the company I guess how was that transition and working on the protocol itself and not just these outlying things I found when I moved to full-time I found it a pretty good balance of being able to alternate

according to you know what I felt like at the moment from doing a more just pure math thing prove like prove that this thing is secure or understand this complicated algebra algorithm to writing code understanding you know things with get better and in cherry-picking like there was a period where I was focusing on writing this snarky explainer serious periods where I was writing papers or understanding papers and then you know a period where I was just trying to port things from from Bitcoin doing that for for a month month and a half I think

sometimes then what would happen is a better you know engineer would redo what I did in a day but so it was a nice variation from the more programming side to the theory side did you beforehand did you have like a very strong interest in privacy was that part of the reason why you joined the project or was it purely the the math and the engineering no I I don't care about privacy I just do zero knowledge for fun I I never cared about privacy and I still don't I always found the more interesting thing in snarks to be the the compression aspect and actually the

specific the specific thing that one specific thing that got me into these zk snarks is the the compression problem you know like how do you you know this data on these block joint chains keeps aggregating and snarks seems to be the the perfect solution for this so when given your own background coming from an academic background we had Shawn on the episode before he comes from like dropping out of high school do you still think an academic background is needed or is it helpful we should like what would your recommendation be to someone who wants to get involved with this just like sit down and read papers or actually get an education it's

definitely not needed I think it's good to have people with different backgrounds to give different points of view I mean also in academia there's this sort of sliding scale and how formally people are are doing doing things I think people yeah whatever interests you most you should you should try to directly get into that and fill the holes going backward I think it's much even I heard this interview with this fields medalists you know mathematician that you know there was this problem who that

interested him this big math problem so he read the super advanced paper as an undergrad and of course he couldn't understand 90% of it so he kept have to had to go go back to you know but I think you know the way the brain what keeps the brain engaged and therefore efficient is always go to what interests you most and fill the holes because if you say to yourself oh ok I need now like 4 years of basic background before I get into what interests me or your brain won't be as engaged if there's nothing specific that you want to do at this moment I think getting a good math background in academia is a great great way to

spend time I think that helped me a lot looking back over your time as the cash you know what what kind of work did you see yourself doing there that you like would highlight a really nice thing we we did at Z cash was well there were a few things so there was this huge problem in in the first MPC that the participants need to be defined in advance and protect their secrets throughout the protocol which limited the number of participants to a very small number and then in this paper with Shawn and Ian Myers we showed that you know this odd thing that if you I guess

this is the oddities of what you need for a security proof even though it sometimes seems ridiculous and in real life so what we showed and in that paper I think the paper is called if you look for it on github reprint a scalable ZK snark parameter generation and the random beacon model so right in this ceremony everybody contributes their secret randomness to create some elements we showed that if in the end you you take another contribution from just a public source of randomness than even though the secret of that contribution is totally exposed that creates a

situation where you can do the security proof without everybody having to pre commit to the randomness and then that led to this powers of Tao ceremony where just you want to participate and hopefully you're the honest person so you you know you dynamically can say I want to participate now do your the computation for 20 minutes and that's it so one of the things that you might be most well known for hopefully not but it's certainly known for is discovering the bug in the Z cache protocol how did how was that discovered and like what happened after that yeah so the the snark the Z cache the

sprout z cache system originally used was from a paper of four authors also from the Z cache scientists that was a small variant of a previous snark and I guess because it was a really small variant that was maybe one reason why there wasn't a security proof in that paper so in the paper about the sprout NPC I wrote in an appendix of proof of for the first time perhaps a proof of security for this for the snark and this paper got accepted to this Bitcoin workshop in financial cryptography 218 so I came there to give a talk and the

night before the talk just sort of is nostalgically going over the paper that we've written I went through this appendix because I was really proud that I wrote this proof and then I suddenly saw that there was this one you know lying in the proof that that didn't make sense like that I was saying something like oh and because of this algebra thing then the only solution must be with these things in the beginning of the solution and then I was like no that doesn't really follow from the algebra and then I thought well so what does that mean it seems that means that if in the Z cash context if you have like a Z cash transaction where you're spending a

tenth of a sec you can change it to a Z cash transaction or you're spending a billion Zak by just you know adding some group element to your proof and it's all fine so so then I it would happen often that you know something wouldn't make sense to me and I you know since today you know the internet everything is so handy you know and II you know instead of sorting out in my head for 15 minutes I would immediately ask Shawn or someone so I wrote Shawn hey I don't think this you know this doesn't seem to make sense like it seems like the system is completely broken and usually he would you know immediately tell me why it's

not broken and he wrote oh well you know this this mitigates it but I said no because you know you can use this this thing to pass this check and then he stopped using slack he he wrote me an uncivil I'm coming to meet you we were by chance me Shawn and zuko all in Chris now in this hotel of the conference yeah I won't I think Shawn told a lot of the story from here he met me in person we verified it's a it's a bug we had some disagreement on how to patch it but it worked out that's actually a

really good clarification that you say here so the paper that you're referencing but that was actually an older paper and the implementation and everything happened after that and this was you at a conference looking over an older paper looking closer at an older paper oh sorry I so the paper with the broken protocol was there a few years before the the paper with the attempted proof was something I wrote with Sean and Matt Green and that was pretty new and and that was what I was present in that so oh I see so it was like looking at this newer paper finding the kind of inconsistency in the newer paper that made you go back to that older

paper and then you found out that through as I had understood it through the implementation sort of part of it had been ignored so there's a technicality of of how to exploit that relates to the implementation but the error in my proof yeah made me go back to the this protocol from this older paper and see that the the protocol is is broken so the problem yeah actually existed in the original paper and the problem was always there and the proof just sort of highlighted that problem in some sense exactly so you already mentioned that you know there are ways

to patch this and we've seen what actually happened I mean it was a patch was delayed and then they kind of rewrote on like the whole snark from scratch and then it was fixed at the same time but what other ways are would there have been to fix this and like it was a nine-month period or something like that between discovering it and patching it why was that wait so long so the wait was long because the idea was to fix it covertly as part of a big efficiency upgrade the sapling upgrade and this sapling upgrade was a big

change requiring a lot of time the the fix I suggested was I called it the re randomization fix so that wouldn't require would require only changing the what's called the proving and verifying key like the parameters but would not require changing the proving system or so it wouldn't really wouldn't require really changing any of the code but if you're changing the parameter so you need another trusted set up to change those parameters so you would need

another yeah more participants that would rear and Amaya's but while their rear and amaizing they would not do the rear and Amaya's ation on the what Shawn and zuko call the bypass elements the elements that let you carry out the attack and so you're left with new parameters where the DS element that where you can't carry out the attack anymore and then the question is what security do you get well you get that for someone who doesn't know the

vulnerability he cannot exploit unless he's corrupted all the original six sprout participant ceremony participants and whom whomever has done this reorganization and you get that even someone that knows the exploit to to now attack the system needs needs to know the secrets of everybody who participated in this reran demise ation so kind of my logic was even if we just do one round of this rear-end room ization it it wouldn't hurt the trust model anymore because in any case since

we knew about the exploit there was a period in time where you needed to trust us and the idea that this could still be presented a semi lame update you know covert update yeah I mean that that's a question to me because how you know in this world where there is an export you have to do correctly you don't want to tell anyone that there is a problem if you suddenly just go oh by the way we're gonna you know redo all the parameters it's there's no big deal how do you do that covertly so so my I agree like semi lame cover-up story was that so this thing

that we call the toxic waste in the original sprout it could it consists of eight filled elements and the advantage of this rare free randomization is that without redoing a whole ceremony with rounds with just one person doing one round five out of these eight toxic elements you can reran demise such that now you need all of this the six original people and the new person to discover one of these five now I think what maybe Sean said which is a good argument is that if so you could say alright we're doing this parameter

change that maybe doesn't really increase security but there's a chance it does and it doesn't hurt security so we're just doing it you know for extra safety yeah I think the argument against that that perhaps Sean said that if you do an update where you're increasing the security of five out of the eight toxic elements it could be a hint of people maybe there's an attack relating to using one of these five and then looking with a magnifying glass at this old old paper relative a few years be two thousand thirteen or fourteen paper and discovering the attack themselves and there's a window for attack there

between when you announce we're going to do this we randomized ation and when it's actually done in live on the network that someone could dig into this and try to my ass yeah I guess it's a question of how much details you have to give about why you're changing the parameters yeah right you could just not say anything and then suddenly you know next week there's there's an upgrade and this is new parameters and like everything and then detail afterwards yeah I think it could because there was this over winter upgrade that was much nearer in the future than sapling so yeah you could have said maybe a week

before oh by the way we're doing this parameter change it only increases to at least it doesn't hurt security maybe it increases it so we're just doing it for like why not there was I think an argument of the other yeah that I think the other three that were in on this Zucco Nathan and Shawn you know that something like this would make people really raise their eyebrows and you know what's going on and maybe that would have evolved to some drama or problem or who knows let's say you did and I was it a week before and like how likely is it that anyone would actually be able to find it in a week even with a magnifying glass and knowing you know there's

probably something here and big answer do you think anyone would be able to find the bug I don't I don't think it's likely I yeah I still think this was the the the better route you know given that it would would have reduced the exposure time from I think it was nine months to two months and also that this nine months you were putting the sapling upgrade in a pressure cooker to you know roll it out fast which increases the chance of introducing a bug you know in this new upgrade I mean it's really not

that okay we've just got to take care of this bug and then we can breathe and these things are so sensitive I mean you're writing write this thing we call our one CS you're writing but you know the logic of a valid transaction in like in sprout it was two million in sapling it's like seventy thousand degree two equations and it's enough to get one equation wrong for you know potentially unlimited counterfeiting yeah basically it wasn't only about someone finding an attack that week it was maybe about some PR and media yeah basically I still like that route better personally do you think that

there was anything that could have been done beforehand to catch this thing other than just like getting more eyes on it like would something like formal verification have helped would that have just been too crazy to do on something like this oh yeah that's a great question so actually I mean I did I discovered got to the bug through a relative relatively subtle process of going over this proof but simple sanity checks would have mitigated it the simplest check that every compiler does of do we have unused variables so in a sense in this 2014 paper there were unused variables in this in this in

these parameters that made everything look like more symmetric and the all the indices were you know in in the same range so but just that simple check for example would have found this bug and another thing there's this thing called the generic group model which in a sense is a stronger cryptography assumption than the snark used in sprout the Pinocchio /bc tv1 but I think you know proofs person in the generic group model it's totally possible they can be mechanized and even if you want to later prove your system secure with a weaker assumption you if someone will write such a computer program that could be a

great sanity check before we segue into talking about some of the stuff that you're working on now just looking back at this work what's your take away in designing and building these systems to make them secure because like you said it's obviously extremely tricky to get all of this right like how do you what's the best way to design these systems I don't really know to be completely blunt and honest I'm less worried about it because the crypto space is so volatile anyway that individual user I speculate is not gonna

lose more from these exploits than they do from the crashes of price so yeah it's not a problem we have to sell today this is more general but now that time has passed and you've since left the Z cache company right now the electric coin company looking back what's your feeling I think the these years in the Z cache company it was a really unique and special time I sometimes describe it used to describe it as taking a cartoon comics character and bringing him into

real life he's the Z case narcs were really just living in theory papers and and suddenly seeing them at all in the real world when Z cash launched and then seeing that it's not an incredibly small niche there's suddenly so many people interested in it it really felt like a taking part in a pioneering revolution yeah the landscape has changed and there's a lot of good projects who who were influenced and maybe will someone else will take it to the you know next

level I think that segues us well into the next thing I want to talk about which is you're now working for protocol labs on the file claim project which is interesting because earlier you said you don't actually care all that much about privacy and you're much more excited about that compression effects of a snark which is kind of what you're doing in file klein right right in file coin we need to do these proofs of replication which is this problem of I want to prove to you not only that I'm storing your file but that I'm storing several independent copies of your file which is a very tricky problem because

the natural way for you to check if I'm storing your file is to have some say merkel route commitment to it and ask random indices but that will not separate between me storing one copy and five copies so it turns out you can still do these proofs of replications using something called slow in codings but it translates to incredibly long these proofs of replication that you've really done a slow encoding of a file and this is its merkel route these proofs are extremely long so it's basically a merkel proof which includes like paths to the leaves in this Merkel

tree and like one piece of data and I guess the Merkel trees in this case are massive so the leaf the paths are really long it's massive Merkle trees and it's eleven of them because to get this security in this proof of replication you have to start with your original file which in the file coin context can be a one gigabyte or even 64 gigabyte file and you have to do ten layers of slow encoding on this file so so you do the slow encoding of the file the slow encoding of the slow encoding and each time when you're doing this you have the

Merkel route of the current thing and the more encoded thing and you have to check with a bunch of merkel paths that really the index here and the new thing is the right combination of like three two or three things in the old thing so you end up with a lot a lot of deep merkel paths and i think a circuit of about a billion gates well so this missus circuit then goes to prove that the Merkel proof is correct that's what yeah so maybe I I skipped so so first right you could say so it's not about

privacy so you could you could the proof that everything is correct is just a ton of deep merkel puffs and there's no need no nobody cares about hiding them it's just that you don't want to write hundreds of deep depth I think if it's maybe thirty miracle puffs on your vlog chain every time say a minor is is proving he's storing a certain file because the the file coin has the idea is to combine two things at once one is like incentivize people to store clients files and get paid for that and at the same time get mining power according to the amount of space they're allocating for the for the network so yeah you

don't want each miner to like put all these huge miracle paths on the chain so you have to compress them in a snark alright like in a normal box chain your proof of work is just a hash it's 256 bits and this is the proof that this buck is correct but in the file coin world do you need this massive merkel proof to say i am storing this file here's my proof so instead you compress all of this with us narcs and i are just storing this much smaller snark on chain to say that proves that my merkel proof is correct exactly in some conversations earlier this week we also started talking about this recursive level one is there anything like is is that related at all to what you're talking

about oh yeah this is very much related so like I said I think we end up with a circuit of about a billion gates and the prover computation and memory well mainly here the thing is the prover memory is linearly related to the circuit size so it's very hard unless I think you rent a special machine on AWS and paste significant money to even run this proof so the natural thing to do is since really this big huge circuit is just a lot of copies of the same thing a lot of these miracle paths so the natural thing is you know just split the big circuit into twenty smaller circuits and then the the memory requirements go

down by twenty but then you've lost in scalability because now you're going to post 20 snark proofs on the chain instead of one so you can solve this by one layer of snark recursion meaning that except these 20 now slightly somewhat smaller circuits you'll have another circuit where what's going on inside this this circuit is a verification of 20 proofs it's kind of similar to the sexy structure that in in their construction you have these you have the UT EXO model you have inputs and outputs an arbitrary amount of them in transaction and then you have one snark for each input and output but then

one like overlaying snark over all of them to prove that all of those are correct it's it's similar and and it's not a coincidence that we're using some of the sexy code base to get this done which is proven really useful also for this and also in another project I'm involved in called sello for building an ultra-light client for blockchain verification how long would it take to compute like on like you said on a beefy Amazon machine or something how long would it take to compute this proof that if you were to make one mega proof of everything I may have been getting this totally wrong I don't

remember the times I think I remember the the money they paid for the AWS machine that made one of these proofs was around $1,000 well I hope I'm not getting this wrong but I mean significance and I assume most of that then is RAM and RAM machines are super expensive on Amazon yeah I think it was it was clearly not good enough when it was just 1 billion gate circuit know how what's the speed up and doing this recursive level thing that the speed-up is not large unfortunately it's mainly about saving memory yeah so you can do it on a home computer and you don't need

the massive run machine yeah exactly I'm curious I mean we've had howard wand before to talk about Disick and distributing all of this it sounds like this can still be applied because like you say privacy is not an issue here like I can send this massive Merkel tree around to a bunch of machines even to other service providers off chain and say construct this schmuck for me and then just submit that on chain so so I know protocol labs made some investigation on using Disick and came to a conclusion that it wasn't practical in this case and I I don't know the details well I don't understand is equal

there might be a future file client business model is computer proofs for you and take a small cut of the mining rewards yeah could you could could you recurse another level if you wanted to like when we talked about that recursive level one it's the we had had quota on and they talked a little bit about what recursion was but could you not just kind of do two in order to make that the thing is more efficient yeah great question so the thing is our elliptic curve knowledge is very limited and in this sense and who knows maybe it will improve a lot and maybe we should get more encouraged some elliptic curve

experts to look into this but with the current thing we know which is this thing called the Cox pinch method basically in this method every time you add enough like one more layer of recursion you need to double the field size over which the curve is over which means doubling your everything you're putting on the chain and increasing computation time by I don't know if it'll be just doubling or maybe a bigger factor four or five did you look into any other proving systems initially when like exploring this space of because you you want some things to sink but you don't necessarily care

about like when we talk to Zack see there's a very you know particular requirements that the proof doesn't depend on input size because then you leak privacy details and things like you don't have those concerns here really so actually what I'm most excited about in the file coin context is even don't look at general-purpose proving systems like when you think about what you need sort of in this file coinage context it's it's this thing we can call a vector commitment that you you have this vector of values and you have a short

commitment to it and then you can just I ask you what is the 40th proved to me you know the 40th ENDEX and you can give me a short proof that this is the the 40th index so Merkle Merkle trees are the traditional way to do this but there's a really exciting developments on alternatives that protocol labs is looking into one really nice direction is these his vector commitments based on RSA accumulators that have gotten a lot of attention lately in the in the space I think because of scalability work of Benedict

bones and Don bone and others another direction I like a lot that I learned about when I learned initially from Mary malar about the the sonic paper is this thing called the kata it's all polynomial scheme polynomial commitment scheme that has actually been used in the race in recent years in many places for example in giving us the first practical universal snarks and I would love to do a whole episode on accumulators at some point because it's a fascinating topic it's also like the core problem in a lot of blockchains when it comes to implementation like

what's really challenging like in etherium there's a Merkel tree for all of the global states and it's getting to be really really big and it's one of these like it's one of the hardest things about implementing and that theorem note is managing this Merkel tree and if we could have something other than a Merkel tree that isn't so complicated to manage then it would be like in my point of view from like in a block chain implementers perspective not having to deal with Merkel trees would be a revolutionary yeah I think one an interesting thing if you look at the Z cash circuit you know which is you know snarks give you general circuits it oh well almost cheating a bit it boils down

to you need something with the proof of membership like that really this note you're spending its commitment is in this commitment tree and you need a proof of non membership that the serial number of this thing you're spending is not in this list of serial numbers of spent coins so I think this is an exciting sort of direction of instead of doing things with generic snarks maybe even things like like Z cash you can do with some variant of RSA accumulators or other accumulators so we're getting really close to the end here but is there anything else that you'd like to talk about before we wrap up so there's

a story I really like to tell about pairings so elliptic curve pairings really gave us an order of magnitude jump on how efficient is your knowledge proofs and snarks can be and really had a huge part in bringing them to into practice and I like to tell the story of how mathematicians who didn't care at all about cryptography and invented them totally by accident and it all starts with Riemann who was the question he was interested in which was is made the most fundamental question math at least a number theory is say I'm at some number you know 17 how many numbers do I

have to to go forward from 17 to hit another prime you know so so we know about the density of primes but the Holy Grail is giving an exact formula for when the next prime will appear and what I think not everybody knows is that Riemann in fact found an exact formula which is one of the most amazing things in math ever well with the slight caveat that there are infinitely many unknowns in this formula as part of this formula and these unknowns are the zeros of the what's called the Riemann zeta function this made you know finding what these zeros are perhaps the most interesting

question in mathematics and what mathematicians noticed after I guess trying to work on this is that well we don't know how to solve this problem but this Riemann zeta function you can actually think about it as the Riemann zeta function of the rational numbers and actually you can take a lot of other fields and also define as a de function for them and then maybe this question about where the zeros are of these Zeta functions is easier so in this kind of direction people started looking at

what's called function fields which are these weird fields where your elements are they're not exactly numbers they're like say rational functions in just the variable X like X divided by 1 plus X cubed will be an element of this field and then you have this very weird thing that like you can take the real numbers and add like the square root of -1 you can take this field of rational functions and add a square root of this variable X which sounds really really weird but just formally it's something you can do

so these fields are what's called algebraic function fields and people thought maybe if I look at the zeta function of these algebraic function fields it's easier to to say where the zeros are and that will be like a nice start so so ha say this mathematician showed that oh well for elliptic function fields you know these are exactly the the values of the zeros and on the way totally incidentally he you know this gave us a fact that all of elliptic curve cryptography is based on that say I want an elliptic curve with a certain number of bits what do I do

well you just define an elliptic curve over a certain field of size P and then you're guaranteed by HAases theorem that the the size of the curve will also be roughly P up to a 2 square root P factor in either direction and then well elliptic function fields were a special case of algebraic function fields so then this big question of these mathematicians I think mainly in Germany in the 20s and 30s was can we prove what's called the Riemann hypothesis for all algebraic function fields over finite fields like can we say where these zeros are or at least bound their

range for any algebraic function field for the zeta function of any algebraic function field and a famous French mathematician maybe one of the greatest mathematicians of the 20th century Andre V it's spelled with an L but I learned recently you don't pronounce the L in the end he solved this question and just as one step in in his proof he defined what's called the Veii pairing which has become really the basis of all all we can do today with with snarks and this cart a polynomial scheme and bila signatures and so I think that's just a nice story of how you know these things

do often math mathematics and gave us the tools we need for four totally unrelated reasons Wow well thanks for sharing that with us sure thanks do you think now you're part of like that story in a weird way in a very very small way of like standing on the shoulders of giants and peeking a millimeter millimeter above that's why I stay in school kids all right very cool thank you very much for being on the show it's been a pleasure yeah it's been fun thank you and to our listeners thanks for listening thanks for listening

[Music]