zkSummit - State of the SNARG-scape - Alessandro Chiesa (UC Berkeley, StarkWare, Zcash)

Transcript

[Music] many of you maybe when you hear about Zika snarks and more generally snarks you think oh man there's so so many different constructions if you have to learn about in math to kind of understand how they work maybe some of them actually literally use magic so I want to kind of push back on this narrative of any more or impression and say that really like anything complicated that we design and you need it all there is actually rather simple paradigms and design principles that sort of construct something complicated

or something simpler okay and I'm gonna try you know just very few slides just point out how even a day with many topics like today in reality you know can be understood as a small set of design principles okay just to remind you it's not exactly too graphic proofs for computation integrity that are super surance very fast to verify these are actually things that are not particularly new from a feasibility perspective already in the 1990s a we had powerful results from computational complexity and cryptography that

basically told us things like zika snarks we understand how to construct at least in principle and the reason why we're here is that in the last ten years there's been extraordinary progress in sort of linear cryptography foundations efficient constructions implementations and you know most notably applications that's why can when you must care about the kiss narcs in the area and kind of the view that maybe you know some of you that entered at the blockchain space maybe early in the day you thought okay this is all about a peer-to-peer protocols with strong consensus today the view that we have is more like that constructing peer-to-peer protocols with strong security and privacy guarantees really constantly also leans on the

stronger and T's of Zika snarks okay this is is a important pillar of this type of systems that he's gonna probably gonna stick around for a while eh so for today I want to maybe remind you just briefly the picture of a sake a snark is gonna helpful to have a mental or sort of a representation of what it looks like so with the prover in the very fire a the prover has a particular function that is applying to a public input and I private input so X is the public input W is the property input anyone's to convince the verifier indeed many other people that he knows the secret input so that f of X and W equals one and naturally the prover is going to run in time this is proportional to the

computation but crucially the proof that attests to the correctness of computation is gonna be much much smaller than the computation itself exponentially smaller and verification sometimes is linear in the computation itself so this is kind of lean on 16 clarification or it is very fast this is what we call 16 for vacation either of these things are some interesting objects the important point about succinctly no interactive argument is that the proof is small crucially these proofs can be verified by anybody so if you can write them down somewhere in a transaction then many of the nodes and actor can read them I also could have asked many times you know what's the difference between a snark and a snark so the key at the end simply denotes

that there is this technicality in the in the security guarantee of a snark that really you don't want to know just a secret input exists but whoever produced the proof actually knows it okay is the technical notion cryptography that we know that we call an argument of knowledge okay so that's what it means and the guy in front stands for zero knowledge and then obviously if you have as a case snarky means they satisfy both properties most applications that you are probably familiar with require both properties both 0 knowledge and argument of knowledge for today specifically it will be helpful to remember that every snark actually requires a setup so we sometimes say snarks without setup that actually is they don't exist one can

prove they don't exist it's really a matter of discussing what's that setup you're using the most type the most benign type of setup is something called a union from reference string it's just pure randomness okay so the setup consists of a string that is guaranteed to be random and everybody knows and this string is used for producing and validating proofs so this is kind of like the gold standard of a setup but really instead what we've been using in practice so far is this so-called circuit specific or function specific setup where you have to conduct a procedure of line that depends on the function you want to run to produce the so-called reference string it's like

some collection of cryptographic parameters that will work for validating and for producing writing proofs only for this function for these functions today we have a program in the morning that is a around the goal of so-called universal set up this means that this one-time trusted procedure will depend only on upper bound on the sort of sizes of computations we care about but then it would be able to support any function or any circuit up to a certain size okay anyway the punchline for this pretty slide just remember all stars must have a set up without them you can prove they do not exist okay it's only a matter about what kind of setup

all right the gold standard is uniform sometimes we can't get there and it's and then you have to have something some other thing the many deployed solutions are about specific setups today we're going to hear about constructions a universal set up okay is that you can run the cryptographic siren when you once and for all okay all right so this is about this is the mental picture I keep in my head when I think about snarks I find it rather helpful I hope you find it useful as well in terms of sort of syntactic sort of which boxes do what okay all right so today we have a you know many constructions I'm gonna click and you're going to see a table that comes up with

many constructions tabulated according to properties it now looks scary for a moment okay so click so here it is so I've tabulated most well so these are not all snark constructions that we might care about there are many recent ones what I've done if I've split across constructions that rely on a uniform setup this is you know pure randomness in the sky versus this structured set up either Universal or circuit specific okay in the other direction I am discriminating according to whether the verification procedure is fast or not okay so here you have linear ocation procedure so if even though the proof is

small it will take you a linear amount of time to check the proof or if it's fast you could ask is it fast for all circuits or just for circuits that have they're nice they have like nice structure for example repeated circuits okay okay why why did I put this table on the slide first you know I want to share I want to point out that you can always by definition tabulate constructions you know you just list the properties and you write them you know table for it there's nothing special about being able to tabulate things however what I want to highlight is that while this may look like you know a complex reverser landscape in reality

the way we achieve these constructions is from a small set of design principles so specifically there are three main compilers okay that the compilers these are transformations that combined simpler ingredients to construct each of these sort of families of constructions the one on the right for example a grad 16 what is currently used for example in sapling okay it's an example of a construction that is obtained by combining so-called linear proofs or linear PCPs doesn't matter right now and linear encodings this new encodings are obtained from pairings okay and pretty much all of these constructions you can explain them as different ways of like instantiating linear proofs and

veneer encodings okay so it's like they're all part of the same family so once you understand one you basically start all of them okay this other family of constructions relies on combining two things polynomial commitment schemes that we'll hear about later today and algebraic proofs is again these are holistic proofs that we're proving where the prover sort of puts down only let's say hello degree polynomials doesn't matter right now but they are the point is that it explains a whole lot of constructions here and whether you fall on the left or on the right or like up here or down there depends on what type of algebraic proofs you use and also what types of

polymer could mean polynomial convinced schemes you use for instance you can build polynomial climbing schemes also from bellanger groups or you can also use just generic groups you know use groups of unknown order and depending upon how you instantiate these things you will kind of following different parts of this picture okay and finally there's an re compiler that puts together algebraic proofs and logically tests again whatever those are and cryptographic hash functions and you get sort of this those constructions so this is a non-trivial part of putting the table down right yes you can always tabulate a bunch of constructions but my point here is that all these constructions have many things in common

okay so if you are interested to understand or implement you know some of the schemes my advice would be to be mindful of them of be aware of that under there is this underlying you know simple structure okay any questions or you're looking like all in rapt attention and like you can move your muscles if you want alright so that's pretty kind of the main point of my I also want to mention that as far as we know a really nice question is in general to also achieve post quantum constructions unfortunately right now

the only postponed construction aware of fall in this category mostly because we have good cryptographic hash functions that are post quantum it means a good a good problem to have more post quantum constructions yeah I want to make so this is maybe the only other slide that requires some thinking I want to try to get it across this issue about when is it possible to have a fast very fire or not it's not your saboteur I want to try to kind of a highlight at this point so a snark very fire that runs exponentially faster computation weather dies possible not depends on what

computations you're willing to consider and what you know what about Stark you have let me try to explain that so maybe many of you are familiar with you know program computations right so you have a machine or like you know some specification about programming you say hey here's an input here that number of cycles you run you know please run someone some amount of time and either accept or reject okay so these machine computations going to look like this the main point is that the specification of your your computation is much smaller in computation itself okay so for example you can say take this hash function repeat it a million times and see whether the output contains I don't know like five zeros when you construct snark for you know this machine computations

the verifier needs to at the very least read the statement that is checking in this case the statement that it's checking it's much smaller than computation therefore it is okay to ask the verifier would you mind running in time that is proportion to the description of the computation not the size of the computation okay this is to say one way you can achieve faster education for snark is you focus on the computations that they arise from machine computations the description is much smaller than a computation size this is in contrast to circuit computations that maybe many are much more familiar with because even programmed circuits or constraint systems or you say here's a circuit what is a circuit a list of

gates here they are one after the other okay such that once you evaluate the circuit you know on this input you get 0 the point here is that now the circuit description of the circuit in general is as large as the computation itself so therefore later when you when you have a snark for circuits you might wonder how could it ever be the case that we can expect the verification sir variation algorithm turning time sub linear in a circuit at the very least the very far should know about the circuit and there is no smaller description in the circuit itself so today you will hear about many snarks

for circuits or constraint systems where education is fast so what's going on the point is that all of these are so-called pre-processing snarks there is an offline procedure that produces a revocation key that depends on the circuit ok this is a small kind of summary of a circuit is a cryptographic summary that is done example ok and then you can use it many times to check many proofs relative to the same circuit ok so this is an important difference to keep in mind ok cuz at this point we have actually in production snarks in different projects that fall in different categories we have fast

revocation through pre-processing of circuits or fabrication because you have computations with structure ok all right I'll just conclude by pointing out that today also we have not only talks about backends which are kind of argument systems for different languages whether it is with circuits constraints or any of these sort of newer languages sometimes you are worried about reducing from high level languages to low level languages this is done through reductions like you know NP reductions some of you are familiar with projects like bellman or

Socrates or snarky and these are all like ways in which you can take represent specifications written in Simpson reasonably high level form right and you take them down this is in contrast with some more recent projects for example you hear about air script today that are targeting these other languages these are basically machine specifications okay they're algebraic machine specifications and the way you kind of do these so-called succinct reductions is rather distinct from the way you program circuits okay just be aware of the difference this difference is not subjective underneath there are complexity attic reasons for why this is the case here you're doing NP reductions

between np-complete problems here you're reducing you know whatever you have in mind is on either P space or next complete problems so these are really distinct types of reductions and again you hear about the earth script today okay that's all I really wanted to say if you want to learn about more about cryptography I always would like to sort of I think Don Pony has a great online course about this cryptography in general if you want to learn more about computational complexity it's a great book by Sanjeev Arora and was Barak if you want to learn about pure realistic proofs actually this past spring I taught a course in pcps and interactive proofs where I go over some of these things and if you go to this URL there

is you know 25 recorded lectures thank you you