'Introduction to Zero Knowledge Proofs' - Elena Nadolinski

cool um yeah hello everyone um my name is elena and i work in a project called iron fish um iron fish is an uh layer one privacy coin we just launched our test net actually earlier this month um and my entire journey actually began with an eighth global event um the wave and got into crypto is because i went to uh one of the first hackathons at eth waterloo uh and actually jumped to start my entire interest in crypto so i'm so glad to be still part of this community and to give back so thank you so much um cool so i'm going to post all these slides on my twitter afterwards um and this is kind of meant to give you an overview of what your launch proofs are but i also added a bunch of links so if you're interested you can actually go through them later at your own time so what is azure knowledge proof um or what is a zkp and really it's the ability to prove honest computation without revealing inputs so the example that i like to use um is a where's waldo example uh for people who are totally used to journalist proofs um so the story goes that there was a math professor who was trying to figure out a way to explain what their life proofs are in a very simplistic way and he was reading where's waldo with his five-year-old son and they're looking at where's waldo page where you're supposed to find waldo and the father goes i know where waldo is and the sun goes prove it so it's kind of a perfect setting for how does the father prove to the son in technically zero knowledge that he knows the answer and so what the father does is he takes a huge newspaper he covers the entire book with this newspaper with a small little hole that reveals where waldo is um and the paper is much larger than the book so it actually gives the sun known information about where waldo is but it does give the sun the proof that the father does know where waldo is so this is a very very simplistic kind of explanation of what your knowledge proofs are um but yeah but at the core uh zoom launch proofs are honest computation and they are used for scalability and privacy uh like and i mentioned and there's a ton of projects that kind of demonstrate that um the uh geology proves and i'll go over like so many variants of zero large proofs um but there's three main properties that they must uh satisfy its completeness so meaning that an honest verifier will be convinced by an honest proverb soundness meaning that the reverse is true so uh if someone's trying to cheat an honest verifier can figure that out um and zero knowledge so if the statement is true then other than the fact that the statement is true there's no other information that's being leaked okay so brief history because generalized proofs come from such a rich background um so zealous proofs were first coined as a term by this paper in 1985 by shafi goldwasser sylvia mccauley and charles rakoff um and tropical boston sawyer mccauley i believe both got the turing award um in 2000 something um for their work and zero knowledge proofs which is kind of like one of the highest awards you can get in in cryptography and mathematics um so this particular protocol was interactive protocol we knew that two parties kind of have to go back and forth um to make the proof actually work and zk snarks are um kind of the first widely used a form of a non-interactive uh protocol and um right now if we talk about zkp's most of the time people still refer to zkeps and zdk snarks and obviously there are a ton of different launch proofs um but zika snarks are i think it's still at this point probably the most popular form of ckp um and that the term of zika snarks was first coined in 2011. um some of these uh names and authors you might actually recognize today um in 2013 there was a famous paper that came out called the pinocchio paper um from researchers from microsoft and ibm and that was like the first like kind of general computing application for sneaky snarks um and only in 2016 with the paper grass 16 by jans groth was it made fairly efficient for us to actually use today so i'm not going to go over exactly how zika snarks work um because that's kind of a large topic however a ton of people have explained it extremely well so to break up zika snark there's fairly five steps so first is computation so how do we how do we break down the computation to arithmetic circuit then there's something called rank one constraint system then we transfer that to something called a quadratic arithmetic program and finally last step is a snark so if you are interested in learning more there is a great tutorial that actually explains the first four step first four steps fairly well and the last step um is explained by maxine petkas in his tutorial that goes very deeply and very thoroughly um into how the spark is constructed so if you're interested this tutorial is actually amazing and probably the most readable thing i've ever read on ziggy starks um and one there's another article for 3 12 301 curve if you ever heard of that one and wondered what is this curve why is it such a big deal there's actually a great article that explains why it's such a big deal and why it's being used in cross kind of long 16 short um there is a statement that gets transferred to a language of polynomials um and there's a prover and a verifier and a challenge um such that there's a kind of a hard-coded common reference string or structured reference string that is used as part of the challenge and together all these things kind of create this proof system such that approver can create the zero-knowledge proof that a verifier can then verify so this is a very kind of high level of what zika snarks are so i kind of mentioned this proof system called roth 16 or type of a as a case snark um and uh why is it so great because it's actually still used today and it's i think still probably um considered the standard today and zoo launch proofs are typically created on three things prover time so how long it takes to actually generate the proof proof size how physically large the proof is going to be and verification time and for gross 16 in particular the prover time is pretty good the proof size is constant and it's super small and the verification time is also constant really fast there's a lot going for gras 16 and by a lot of metrics it's still actually relatively unbeatable there are different proof systems for different like metrics that have beaten across 16 in the past but i think overall it's actually a very good system there's also a couple other uh kind of criteria that zqp's are graded on um that i kind of skipped over so uh ezekies arcs are great um except for one big downside that a lot of people talk about uh very frequently which is that they require this thing called trusted setup um so if you kind of learn more about how zika snarks work they do require that common reference string or a structured reference string that i mentioned earlier and to get that to be as part of the challenge there has to be a trusted setup meaning that some people you know have to come together and provide their randomness and if all of them collude then potentially the system could be flawed now i think practically the chance of that happening is actually pretty small um but people have been kind of questioning whether or not we can have a better proof system that doesn't require the step to be you know better for decentralized uh technology so in 2017 uh onward there's been an explosion of academic research in the zoologic proof space to figure out okay can we use something else uh to kind of get rid of the trusted setup or at least replace it with something better um and a lot of these new proof systems that i'm going to kind of mention really quickly um actually came out due to this paper of polynomial schemes and i found this amazing tutorial that actually explains them if you guys want to kind of dive deep into exactly how that works so 2017 we had a ton of research 2018 is when stars came out 2019 was an explosive year for new zealand launch proof systems um this is where sonic came out halo came out to kind of name some of the more famous ones plonk obviously um 2020 was a great year as well 2021 there's only one that i kind of paid attention to there are others please link me i can update the slides um so there's a ton of these new kind of replacements for graph 16 that either have no trusted setup or universal setup or some other alternative um and in terms of all these i guess the question is well which one should i pay attention to there's so many and so i would say probably these are the ones that i would pay attention to so bulletproofs um i believe they're used in monero um to uh to prove the range proof um starks there's an entire company behind it called starkware i think they're gonna be actually talking next um plonk um aztec is a company behind that and they're going to be talking next as well halo 2 was developed by zcash and i believe their next version of sapling that they want to do is going to be based on the halo 2. so these are kind of like the four that i would say like out of all of these um if you're curious i would kind of pay attention to these the most so still coming back to gross 16 um it is it probably has the biggest tool set currently and um i'll kind of brush on this on this tool set a little bit later on as well but there are a lot of what's called dsls or domain specific languages that are written for graph 16 that make it extremely easy for you today to actually write circuits in a fairly easy way so it's kind of like the huge power uh of of glass 16 is this tool set in this community around it of all these people that are doing so much research um plonk is another one they want to highlight um and once again i think aztec is going to be talking next i don't want to steal uh their fire but they're working on something called noir which is domain specific language for planck um so this is an entire kind of ecosystem that's still kind of earlier than graph 16 and so you're probably not going to have as much of a tool set but there's a ton of research happening here as well the thing about planck is that for the first time there's a proof system that um even though for some metrics it's still slower than cross 16 there's a ton of promise that with this research is going to be seeing a lot of improvements and then halo is the the other one that i mentioned are halo 2 in particular um this is the proof system that's being developed by c cash uh team currently um and not i think it's still like a work of progress i'm not entirely sure how much you can do today with it um but if you want to learn how plonk works um which is the thing that's actually uh related to how halo 2 works there's a great tutorial that i linked by vitalik uh if you want to kind of dig more into it okay so this entire talk so far has been kind of theoretical about all these like different proof systems um and i do want to highlight uh some examples of where xeon watch proofs are used in ethereum today to kind of give you inspiration of how achievable it is to actually use them today for different applications or smart contracts so first category is gaming so for ethereum everything's out in the open the state is public there are so many games out there where you might not want that uh you might want some privacy there's certain games where you know a player state should be hidden for whatever reason and currently it's really hard to do because everything's out in the open now with zero knowledge proofs there are ways they can do that so one obvious example is dark forest and brian green is going to be talking next about about this as well but what's amazing about this game is that a player has some hidden states primarily the coordinates of their planets and they're able to do this with zero knowledge proofs if you haven't tried it i highly highly recommend it everything is in the browser and so it kind of shows you the power of zero launch proofs um i think there's a misconception that the competition is super expensive which to be fair depending on the competition it is but there's a lot of these applications don't require really complex operations and so there's a lot you can do with a very good user experience so dark force happens entirely in the browser every time you make a move you actually make zero knowledge proof and it's a very good user experience so the other category obviously is private transactions which kind of animations as well so again same question ethereum has everything out in the public so if you did want to do a privacy layer how would you do it obviously it's doing all this proofs to the rescue so another notable example is tornado cache um and it's a privacy and topper theory and where you can in zero knowledge proof sort of like mix your your coins with with uh with some with somebody else and then obviously scalability which is kind of like the theme for for today um and there's a ton of zekirola projects some which are actually going to be speaking after me um there's stark where's darknet which uses starks not snarks um there's matalab ziki sync and i believe they're going to be talking today there's loop ring um i believe anna mentioned a lot more others so this is once again of how you do scalability scalability was your knowledge proofs so for things that i um so in terms of like okay you were you know ethereum developer trying to figure out a project you're inspired um what can i use today so socrates is probably one of the earlier projects uh for how to do a dsl with domain specific language for uh zeke snarks um so zovert is great because it provides really good documentation and kind of handles everything for you so it's a kind of pseudo language that does circuit construction for you in the background um and then it actually auto-generates this little verifier smart contract for you that you can very easily deploy um so that you can verify your proofs on ethereum and then create them you know somewhere else like let's say in your in your browser application the one that i think is probably most used today is circum and snark js so the two previous progress that i mentioned dark forest and tornado cache actually use um circum and circum is kind of amazing they've they've done everything in javascript and wasn't in fact most of their implementation is in javascript which i remember like when they first came out there was kind of doubt of whether or not it could work or it could work efficiently and so it's really cool to see that it's actually becoming like a very dominant choice for dsls for zika snarks on top of ethereum they have a great tutorial that i linked there and it's really easy to get started they also help you with the trusted setup as well um amazing project highly recommend if you're inspired to do something with zoom launchers day other notable languages that i kind of mentioned earlier there's something called zinc from matter labs and this is kind of a custom language that's a bit more similar to rust and this is this was designed by them primarily for zk sync then there's another language called war once again i think aztec is coming um it's going to be giving a talk after me and it's a domain specific language for plonk so this is naziki snark it's a different uh uh geological uh system cool and that's it hopefully the goal of this talk was to get you guys inspired um so i hope you have questions i don't know if we have time for questions or if that's a thing that's allowed here i think we have a little bit of time actually um i know there's at least one question uh and i'm waiting for a few others but one of the questions was actually about your project iron fish oh cool uh do you like are you iron fish is focused primarily on snarks correct like that's what you've decided to use that's correct yes would you cons like is is that sort of something you'd consider switching out if some of the other tech gets better like even some of that like tech we talked about that doesn't need trusted setups yeah totally i mean the way the reason why we went with it is because it has such a rich tooling um and because of the metrics like for a lot of use cases it's still fairly unbeatable if you're going to be using something um that's going to be saved on a blockchain uh proof site proof size of under 200 bytes is like a great metric to have because like you know whenever you see whenever you're saving something on the blockchain space is definitely something that is a huge huge concern um so kind of that combined with all the other metrics make it at least for us it made a pretty clear choice nice um why do you think you mentioned that there was this like you kind of listed all of these pro the the research that had come out year by year oh yeah 2019 is yeah boom and i know what you showed was like the the non-trusted setup kinds but the general research was huge so do you have do you have any sense for why that happened in that year um i'm not sure um i think like that year in particular was kind of experimental for different polynomials schemes and i kind of mentioned kate but i believe kate came out in 2010 and so the question is like why why hadn't all this happened earlier yeah um and i'm not not entirely sure i think like the ecosystem was kind of like what you were saying during your intro um was kind of like ripe for the taking like a lot of people care about privacy a lot of people care about scalability um and all of a sudden geological proofs which used to be like kind of a niche topic you know from the 80s just kind of gain more and more traction totally yeah i think that too i actually think it might be the scaling of the fact that scaling became such a clear need that just sort of pushed this a little faster i'm not sure because like uh zk roblox is using cros 16 uh which is like the very first for example by barry whitehat i believe was using graph 16 on a different curve on the ethereum curve um but actually you know relatively pretty well and i think like in terms of metrics i believe it's still probably the fastest one uh despite all this research so i don't know i think like i could like academia probably might have gotten excited that you know for the first time ever their research yeah has a much shorter life cycle like you know usually it takes like 30 years for you to like write a paper and then see it like live in action and here it's a matter of months um for that life cycle to actually happen yeah i one other thought is it may be like some there had been some proof that like it could exist in blockchain too like that connection point had been made a few years earlier by c cash at this point like it was clearly like it was there to stay i don't these are just some ideas um okay another question can someone how can someone get up to speed if they want to understand the tech and math behind snarks that's a great question yeah um so i'll post these slides um the other link that i'll add onto the slides somewhere um is a github link um i believe it actually was started by matter labs or somebody at better labs and it's called awesome zk snark links i believe and it's a compilation of a ton of tutorials and a ton of reading material for people who really want to dive in so add that to my slides before posting them on twitter for those who are interested cool so i'm i'm just gonna hold off a sec to see if there's any other questions oh i think we are i think we're good great okay so i'm going to [Music] so i'm going to invite alex uh osdemir up and thank you so much elena for the talk i'm excited to uh i'm excited you shared this with this audience