ZK HACK - How to Make SNARKs - Alessandro Chiesa

Transcript

you're now back for some basically the part of the program that's focused very much on an introduction to snarks and the languages that you can use and the tools that you can use to build snarks so the first person that i want to introduce to the stage is alessandro queza who's going to be helping us understand how to make snarks so let's have ali join hey ally hey hi everyone can you hear me sounds good wonderful okay so i'll get started thank you anna so in this talk uh titled how to make snarks i'll provide some high level introduction to what are snarks and what are the a high level um paradigms that we use to construct snarks this will lead into the follow-up

talks that will delve deeper into some of these paradigms so some of you may come to snarks with the opinion or expectation that they you know work because of magic or they involve a lot of moon mass or maybe they're just you know complicated creatures that they work but they're hard to understand but the reality is that a snarks are designed according to a rather simple and clear design principles and they're assembled by using simpler ingredients that are sort of easier to understand and so in this talk i will try to convince you that actually

designing snarks is actually not that hard once you understand uh sort of the main recipes for them okay so let's let's get started so um many of you are familiar with uh snarks nonetheless the way i like to think about them on high level is that there are cryptographic proofs for computational integrity okay so the correctness of computations that are super short and uh sometimes super sharp super fast to verify from a technical perspective they have their origins in the 1990s and they sit at the intersection of two areas in computer science one is a computational complexity specifically probabilistic proofs

and the other one is cryptography and specifically the area of efficient arguments so that's what snarks are and lastly ten years there's been extraordinary progress in the cryptographic foundations of snarks efficient constructions and of course implementations that's why we're all here and implement applications as many of the companies that you've seen in the sort of sponsor segment of today are working on and the context is of course that while maybe until a few years ago we understood peer-to-peer protocols like blockchains that's primarily founded on consensus protocols increasingly the ability for a node to

post to the blockchain a zika snark asserting to some private computation possibly an expensive computation conducted offline has become truly another pillar of modern blockchains and in the many ways that uh i won't get into like layer two protocols uh private computation that really show up everywhere and they're really becoming more and more fundamental in to the space so let's uh dig a little bit deeper so snarg stands for the acronym succinct non-interactive arguments okay so you have a prover and the verifier and the prover wishes to convince the verifier of some computational statement

that it knows a secret witness w such that some computation f okay applied to some public input x known as the instance and the private input w known as the witness accepts okay and the key property is that the proving process is say efficient relative to this computation so if it takes time t to conduct a computation you want this to be polynomial or ideally linear in t this will generate a certificate of correctness that is much smaller so logarithmic is exponentially smaller so polynomial in the logarithm of t and the verification is either okay for the application to be linear or you want this one also to be

super fast and of course you cannot just just literally depend on log t you're going to have to read at least the function description and the instance and so you have to pay for that as well and this proof can then be published online and be verified by many parties that's why sort of snark that goes on the blockchain the approver has to work once and then anybody can check the proof any number of times okay that's like a cheap operation uh now many people ask me so what is a snark then well snark denotes snark of knowledge it's a technical requirement that denotes some specific property of the verification procedure won't get into it right now and the zika in front denotes the zero

knowledge property namely the proof hides the witness w and of course a zika snark is when you combine both of these things now all snarks have a trusted setup it's actually impossible to construct snarks without a trusted setup but there are trusted steps that trust ups trust the setups of different types the most convenient is something that is known as a uniform reference string sometimes known as a public or transparent setup it just basically consists of public randomness okay so just some public randomness we agree that it is random or we know it is random and based on that the approver and verifier can generate and validate proofs sometimes however you have somewhat more

complicated types of setup these are known as structured reference strings also known as private setups and here you have some trusted party that together with some randomness and possibly some information about the statements you want to prove for example an upper bound on the the computations you want to prove it will generate the reference string okay and in the real world there's actually not going to be a trusted party but it's going to be a multi-party computation some cryptographic ceremony that simulates this uh sampling procedure securely sometimes you have specific setups where you actually need to bake into the setup the specific function that you want to prove things about okay and so this is just to remind you that all

snarks have setups but they may have different types of setups this is the most desirable why do we even talk about the less the desirable ones because well it's easier to construct snarks with these types of setups and sometimes it is worth to incur the inconvenience of the setup in exchange for other advantages of the snark for example like a very very short proof okay like the shortest snark proofs known today are known in this uh sort of let's say most inconvenient model okay so that is a snarg where does succinctness come from well it comes actually from computational complexity this area known as probabilistic proofs and um it's basically what a progressive proofs

it's a variety of different models all information theoretic that differ what kinds of powers and capabilities we grant to the verifier so here are the types of capabilities that are typically considered one is that you could call oracle access namely the verifier has the capability to query any location of the provers messages without actually receiving the entire message another one is randomness okay the verifier is probabilistic yet another capability of a verifier could be interaction namely the proven verifier are exchanging messages during some conversation at the end of which the verifier may accept or reject yet either one is having the verifier may have access to multiple approvers that are physically isolated they cannot

talk to one another and depending upon which of these powers you grant to the verifier you're going to obtain different types of prolistic proofs perhaps the most common and the most familiar of all is interactive proofs they consider verifiers that can talk to the approver and use randomness okay that's this is the ip a class of interactive groups yet another is pcp probabilistically checkable proofs so here there is no interaction there is randomness but the approver sends a proof that the verifier can then later query at specific locations without having to pay for reading the entire

proof because it's not interested in reading the entire proof a class another class that simultaneously generalize generalizes interactive proofs and pcps is interactive oracle proofs okay we'll get to these later on today there's also mip which considers multiple provers interaction and randomness and of course you can consider all resources for a class that hasn't really been studied much for miop so why am i putting down this diagram first i wanted to at least communicate at a very high level how do different probabilistic proof models differ it's really all about what powers does the verifier have in this

information therapy model and i would also like to mention that especially on the oracle access there is a number of different flavors you could consider the simplest is that you can query a location of the proof but also people have studied more rich let's say query access interfaces for example you may request a polynomial evaluation of the proof or a linear combination of the proof with some tensor vector or just any arbitrary linear combination with the proof okay so all of these have been studied and they give different types of pcps we'll come back to this later i won't get too much into sort of all of

these i'll just qualitatively say that interactive proofs the role they play inside the snark world is primarily a subroutines because on their own they're actually not that powerful but the subroutines they're extremely useful for example some check protocol is an interactive proof so they're mostly used as subroutines of other things okay still you should if you want to understand snarks it's something you should be familiar with pcps are for the most part pedagogy pedagogically extremely useful but they are as of today very inefficient and so uh we don't really use them in practice mips and their generalizations to mrp miops have very attractive features for example space efficiency but they're

actually hard to use we don't really have good compilers to turn these into snarks i'll get into compilers later i'll just say that i would love to see practical applications of mips or more a powerful compilers to use them today there have rather limited applicability the type of interactive proof that is mostly used today in practice is iops okay today they underline most efficient snarks there are some exceptions but uh they really show up like uh in very many places so this is a bird's eye overview of probabilistic proofs i'll uh briefly mention in more detail what is the pcp because it will be useful later

in the talk by nick so we said that it it is where the verifier has is probabilistic and has oracle access to just one program message so it looks like this the prover wants to prove some computational statement for that it outputs a very long proof but the verifier can query this long proof at a small number of locations as little as a constant number of locations gets back the answer and decides whether to accept or reject okay now crucially notice that this is not a succinct argument even though the verifier is sending a small number of requests to read the proof and get back a small number of answers you cannot trust the prover to give you the answers based on

the queries you have to first fix the proof and then query the proof after it has been fixed you cannot otherwise if the approver sees the queries then it can dream up some answers that will always make the very far accept okay so this is not something you can conduct basically as a succinct proof okay so as i mentioned pcps are rather inefficient we have amazing asymptotic results that however the constants involved are amazingly huge and they're not really relevant in the real world there's been a direct attack on pcps to try to make them concretely efficient this has led to turning them from galactic algorithms to merely expensive algorithms but still

the proofs involved for the resulting snarks are still pretty large and to this day there hasn't really been much of a progress on the concrete efficiency of pcps so today they remain concretely more efficient and also asymptotically suboptimal for example we do not have linear size pcbs and that's pretty annoying because pcps are actually really versatile you can use them in a number of snark constructions but they're quite inefficient i don't think a notable exception that has been used in practice is a is a relaxation of pcps which is known as linear pcps i alluded at this earlier it is a pcp where the verifier is allowed to make linear queries to the proof these are actually efficient

one exception in this area all right so what has happened is that people have studied the multi-round generalization iops interactive oracle proofs where the verifier can simultaneously leverage randomness interaction and oracle access okay and so they look like this again the prover wants to demonstrate some computational statement and rather than sending just one long proof it engages with a verifier in some interaction of some number of rounds where it sends a bunch of long proofs at the end of which the verifier can query some number of locations from these long proofs get back the answers and decide where to accept or reject the exciting thing that has happened

over the past few years is that there's been tons of research in iops and discovered that we know how to do a lot of much more efficient things with iops that we did not know how to do with pcps so the interaction really helped there's many techniques that have been used to achieve these strong efficiency properties and overall a sort of five years six years later after iops have been introduced is that we we know that we have much much better efficiency both asymptotically and concretely i won't say much i won't say more about iops i'll just say that ballistic proofs is a really beautiful but also technical area it requires understanding coding

theory algebra and computational complexity but fortunately there is a good resources out there there's an online course you can go to this link to learn about holistic proofs and there's also summer school um that i co-organized this past summer and there's like a bunch of problem sets that you can use to sort of learn the material in addition to the videos great okay so i'll just conclude with a couple of slides to mention how do you go from probabilistic proofs to snarks and that is cryptography okay so all snark recipes out there or almost all combine cryptography with some type of holistic proof and the subsequent talks

will dig into some of these some of the earliest practical ways of doing that was a linear pcp together with a linear encoding more recently people have studied a combining piece well theoretically pcps of course but practically iops with something called vector commitments or sort of hash functions and uh also a relaxation of uh and pcp is known as polynomial pcps in iops that combine them with polynomial commitments the key point of all these recipes is that the pluralistic proof is the one that determines the type of computation you support whether it's circuits or machine or whatnot and the cryptography is the thing that

determines the cryptographic costs improver time and verifier time whether the construction in the end is pre-quantum or post-quantum and what kind of setup do you have whether it's transparent private or it is specific or universal so it comes from the cryptography you preserve primarily the time and space efficiency of the snark comes from the time species efficiency of the underlying ingredients and you we can instantiate these ingredients using all kinds of different types of cryptography and you will learn more about this type of recipe nick's talk and this type of recipe from patricia's talk a notable crossover that doesn't have a clear split is actually something called cryptographic sum checks that for

example bulletproofs and follow-up work have studied it's actually some very curious exception to this state of affairs um all right just have a couple of uh more minutes that uh and that i would like to use to conclude so um in snarks not only we are interested in small proofs but sometimes we're interested in fast verification and how fast verification is achieved in a snark depends on the type of computation that you're checking so for example if you're trying to check some machine computation where you have some kind of small description of an algorithm that is computing for a long time

this is usually done by having a snark where the verifier doesn't actually unroll the computation in its head but somehow talks about the description of the computation directly and can you can think about it it arithmetizes the the computation directly without unrolling it into a circuit okay and thanks to that it uh sort of doesn't have to pay for the size of computation t okay many snarks however are based on circuit computations where kind of the description of the computation is the size of the computation itself so how can you have a sublima verification in this case in these cases you have a situation where you pre-process the circuit and

you generate a verification key that is short that depends on the circuit and in that case this is how you achieve a sublimitation this is just that high level partition will talk a little bit more about this the main point i want you to take away from this is that these are two incomparable approaches you can either achieve sublime verification for some computations mostly machine computations without pre-processing or you can achieve subliminification for all computations including ones that are sort of random looking but you must use preprocessing in that case okay and these are the two main paradigms for sublime replication and both have actually been deployed in practice i'll just point out there's a difference

between front ends and backhands this will come up in the last talk the back end is you have some argument system for a low level language usually this is some circuit language or some machine language and separately you need to have some high-level language to reduce you have a reduction from a high-level language low-level language and you've seen some of these names in some of them in sponsor talks there are explicit reductions to reduce the circuits and there are success reductions that are used to machines actually both circum and cairo are er er and snarky are sort of languages are used in the real world by some of the sponsor companies you will hear a lot more about this in

alex's talk so i'm just about done this was just a high level overview for in what are snarks what are the underlying probabilistic proofs and what are the main high-level recipes to make them and in the subsequent talks they will delve in more detail into some of these topics enjoy the rest of the day thank you so much ale for this talk i also want to ask you and we've had this question kind of while you're speaking a lot of people would love to have access to these slides would we be able to have them afterwards yeah i don't know if you have them saved somewhere we're going to collect them potentially and share with everyone

because i know that question has come up a few times um also if you have a chance alley there's been there have been actually a few questions in the comments in the public comments um so maybe you can have a peek in there and take a look i don't know that we i think we probably should go on i don't know if there's any question you want to take off hand or if we should just if it's okay if you answer them in the chat i don't know how you feel about that if someone can maybe if you can point me to if there is time and you can point me to a to uh uh to a question that would be okay let me pull up one i can i think i can pull it up on here actually oh yeah thanks susan you can actually read it here

all right so uh um yeah so the the way that snarks help with the symmetry is that you have the prover does the computation once okay and then you only have to send a to the blockchain this one proof that can then be communicated to everyone in the network and everybody else doesn't have to do the same computation it's not so much about network uh bandwidth because imagine a situation where everybody else already does the same computation then you wouldn't have had to send the proof right so in some sense you're paying more bandwidth but because the proof is so small then it doesn't matter too much okay what you're saving other nodes in the network is the computation cost okay now there are other situations where you're proving

a statement about data that you don't see and in that case you don't have to send that data okay so that happens as well okay but maybe the most obvious way in which the help is to save computation to everybody else thank you for the question how viable are interactive proofs so maybe the question is about snargs because the interactive proofs themselves are interactive right so you in order to run interactive proof on a blockchain you would have to interact with everybody in the network and that would be not feasible when you put something on a blockchain you want the thing to be non-interactive so that the person that made the proof

doesn't have to be online to interact with you right that's why it's important for the snarks to be non-interactive now snarks are viable in the sense that they are used on ethereum today so there are smart contracts on ethereum running today where there is a snark verifier and it receives proofs and these proofs are attesting to huge off-chain computations and because you the verification is much smaller and much cheaper than the original computation then overall you save gas fees compared to the naive re running actually all the computation that was done offline off chain thank you for the question oh let's do two more and then we okay so how do you know you can trust the

roundness in a structured setup does have to be proven in some way it's a great question well you don't that's why it's a trusted setup right so in the simplest even the simplest type of setup where all you really want is just a random string you have to kind of use real world methods to for example you could chop the first thousand digits of cha of pi and call that your random string you know presumably pi wasn't born to break your scheme right it's gonna exist long before we design the schemes right you could also have some coin flipping protocol between some number of parties to try to collect with some

cryptographic property where i don't know some majority if the majority are honest then the result of the coin flipping protocol is guaranteed to be random right so it is not a simple answer and all setups in the real world require some care and the more complicated the setup is the more complicated it might be to deploy in the real world with the most extreme situation being you have to run cryptographic ceremonies between large number of parties so that with the security property that if at least one of them is uh honest then the setup can be trusted okay but this is unavoidable because all snarks need set up there's just no snark without a setup it's just about the type of setup okay i'm actually getting the note that

we may not have time for another question i'm so sorry i thought we could sneak too in thanks so much ale and yeah there are a few more questions in here so maybe you can help answer those in the chat