zkSummit: Rise of the SNARKs with Howard Wu (SCIPR Lab, Blockchain at Berkeley, UC Berkeley)

Transcript

now we're gonna be going a little bit more technical and diving deeper with Howard wound from blockchain at Berkeley and screwed what's to be skipper lab sorry and yeah and we're really excited to see what you have to say but I think just so you guys know on this room we're gonna be getting like deeper and deeper and deeper into zero knowledge proof I think it's if you at some point fine this gets a little too technical there's some other things going on and we we have the plan cool [Music] [Music]

awesome so my name is Howard and today I'm gonna be talking about well first an introduction building on top of Jack's last talk on as your knowledge proofs and in particular will look into one one specific type it's called a it's a class of proofs called CK snarks and last you'll talk about a library lip snark that implements the zero knowledge proof systems and is used in a lot of deployment in industry today so from a very high level cryptography is powerful because it it's useful for building secure systems and historically speaking a lot of the cryptography you work is used to provide these security properties for data if you think about

information when you transmit it if you want confidentiality you you can encrypt your information and send it additionally if you want to have authentic about the information you receive it makes sense to have like a checks on a signature something that allows you to verify and validate that the information indeed is the correct one but what about security properties for computation this is an area that is that that is very useful because as machines become more powerful and everyone is is not living in this digital era being able to communicate and execute protocols together is extremely valuable and providing a security guarantees on the integrity of computations is extremely useful so cryptographic proofs offer these privacy

preserving integrity for computation and when it comes to cryptographic proofs it's it's a powerful defense mechanism that enforces that malicious actors can be caught and what makes that extremely useful is in the case of blockchain so you know in the case of decentralized protocols where there is a model that users are mutually distrusting it's a very ideal situation to have proofs about your claims about what you've done and etins and force the protocols correct execution cryptographic proofs bridge together multiple disciplines spans anywhere from mathematics to complexity theory to cryptography to security and these are all areas where

there's a notion this formalization of proofs you can think about from the mathematical standpoint that a lot of mathematics is reasoning on formal proofs and computer science has come to reinvent it with things like zero knowledge proof if we look back at some earlier models in earlier work of cryptographic proofs you can think about a lot of like multi-party computations where there is this notion of a private input from different users and these inputs designated in red x1 through xn could potentially be say bank account balances perhaps the problem the function f is to say who is the richest of or the wealthiest of all of the end

participants and certainly you know people don't want to disclose what what their net worth is but perhaps within this group it's desirable to figure out who is the wealthiest of that subset and in in this case but potentially the output could be the user who has like the most wealth but does not disclose the amount and in these types of situations where there is a notion of privacy it makes a lot of sense to have a computation where people can have integrity namely that in executing this protocol they aren't able to lie about their wealth they aren't able to lie about their statement and they also can compute this in a fair fashion but if you look at these early constructions these these systems were very different from what what some of the stuff we see

today they're closed networks we're talking about participants who have to a priori know what the sample set is going to be and they have to all be online and available to talk to each other because of the communication cost involved this results in a lot of scalability issues and so oftentimes these problems are a reason about in a small setting and a small domain but in these cases you know things like zero knowledge proves which we were formalized in a second allows you to ensure that every message is sent according to this protocol that no single user is trying to cheat their way out of that that function fast forward to today and you have things like block

chains where it's it's a very different world these are environments that are extremely open they are ones where anyone can join and the participants can be online they can be offline they could be on for one minute and then disappear and they come back on it's very hard to say and additionally this is at a planetary scale and so these environments are very well motivated for things like cryptographic proofs it ensures a few things some for one like if you have a proof that you wanted to make a claim about in this case one you'd want it to be succinct meaning that this is a proof that's very small it's very efficient to check and it's something that can actually live and be

posted on the ledger additionally non interactivity is a desirable property meaning that if if I'm to post a proof online then I don't actually have to enforce that the prover remains online and have this channel with them to do some type of interaction it's better that they can post a proof go away and for the rest of eternity anyone in the system can go and check this proof additionally you'd like it to be publicly verifiable this is especially desirable in things like block chains and lastly because of the public nature of these chains zero-knowledge is a valuable component to say that certain inputs may not want to be revealed so to start from the ground up there was

this notion of zero knowledge proof introduced by Goldwasser McCauley and Rakoff and in this setting these are privacy preserving cryptographic proofs of computational integrity you can think about this as two parties approver and a verifier and the prover says hey I know some X such that the acclaimed output Y is equal to this function applied on my private input and this notion is something that is a valuable information for the verifier to check the verifier wants to know hey do you really have knowledge about this claimed output do you have the private input that gets you to this claim to output and so the prover has this notion of knowing a function a claimed output and some

claimed input the verifier all he knows the function and the claimed output and is reasoning through this interactive protocol to determine whether the prover indeed knows some private input what this construction gives you for one is completeness which is to say loosely that a honest proved err will always be able to convince a verifier of the correctness soundness in this case says that a malicious proved err should not be able to convince a verifier of this claim and lastly zero knowledge which is to say that it should not reveal any information the

formalization here uses a simulator and this is to say that there should be some type of indistinguishability and that component is what's so valuable in saying that zero knowledge it means that I don't reveal any information about my original inputs so this is a very powerful cryptographic tool however it this early construction has a lot of downsides to it first off there it's an interactive protocol meaning that the proven the verifier have to be online and they have to go back and forth and chat with each other additionally it's not succinct what this means is that the verification the communication complexity is on the order of the time it takes to compute the function itself so if I'm in the setting

of saying you know I have maybe like a 1 petabyte database of health records and I would like to find any people who are you know over 50 and have heart disease that computation I could run on my local machine but you know one one valuable thing here is to say I want to outsource it to a cloud provider to go and make this computation and doing so would be something where you know I don't know if they really ran it on the whole petabyte maybe they just do the first terabyte find 20 results and say hey this is all I got well in that case it's there there's no way for me to check unless there is a proof involved and zero knowledge proof is a valuable way to demonstrate this however if it takes as long to run that computation as it does

to check the actual integrity then I have gained no advantages in this case and so succinct miss is a very desirable property lastly if there is pour concrete efficiency in this case so this early their knowledge proof construction uses these things called probabilistically checkable proofs or PCPs for short and the idea about this is that you can pick some points and basically get a very high probability bound on the actual correctness so you know cryptographers don't sit in their offices and do nothing all day they went straight to work on this and started looking at different ways to improve on the zero knowledge proof and one of the earliest works was in providing succinct Ness this was this was work where they basically took probabilistic checkable

proofs and lifted it to provide succinct as a part of the protocol what this enforces is well you have your original three properties completeness soundness and zero knowledge but now you also have succinct in so just to say that the verifier can actually check this proof in a time that's proportional to the size of the function plus the size of the claimed output not so much the runtime of the function itself and obviously this is a more powerful cryptographic primitive now it's something that becomes more useful it can it can be valuable in many domains but it still suffers from two main problems the first of which is interactivity we still have to communicate back and forth proven

verifier it's not the most scalable approach but additionally it still remains very slow so there was some work that was done by Sylvia McCauley this was in 1994 this works published and it provided the first quote/unquote ZK snark it was a privacy preserving cryptographic succinct non interactive proof of computational integrity and what what he used was a in essence a random Oracle you can think of this like a hash function where you give it some input and the output should be indistinguishable from a random string and using this to lift the construction allows you to actually create non interactivity this is a for formalities a Fiat ramier transform and this construction is in essence the first DK snark it is a zero knowledge succinct

non interactive argument of knowledge zero knowledge as before proofs should not reveal anything about the witness that is your private input and it should be succinct meaning that they should be short the proof itself should be short and the verification should be fast it should be a non interactive so there should not be a necessity for interaction between the PRU friend the verifier and lastly it is an argument so here in essence the difference between a proof and an argument is that your sound is holds only up to computational bounds but having a computationally bounded verify in this case provides you easy case snark so this is a much more powerful cryptographic primitive and as we have resolved the interactivity

problem but as you see this is still a a use case that is built on PC peas and has cost with respect to the concrete efficiency so for about a good 10 years there wasn't so much work that was done in this area and a lot of people had gone away and done other things and eventually there was a study into these strong assumptions that were made and there have been of multiple approaches in trying to tackle this construction that uses a PCPs so the UK snarks without random Oracle's is a desirable property in this case and early work has grown into a large bucket of work since the 2010s we've seen a lot of developments in the research side of things with this constructions that are

still based on PCPs but use much different assumptions than before and these remain rather impractical to this day but there's another class where the constructions are based on linear PCBs and these things are actually very very practical they use pre-processing so there is a cost involved and and the architecture is different but it is very practical for actual use cases actual deployments and and for this reason lips nark was born it was a library that includes the implementation of many different like zika snark protocols and these are all publicly available for anyone to use and test and benchmark and compare and study so let's describe what pre-processing means here pre-processing

means that there has to be some setup phase a setup phase is one where there is a delegated control to basically generate some common reference string in this case there are two pieces to it one is a proving key and the other is a verification cue this setup is ran by sampling some randomness and constructing these keys they're then broadcast out into the world it's a one-time thing that becomes available for anyone to use then for anyone who wants to try to make some claim about some statement relevant to this problem that's been set up they can act as approver provide their acclaimed input and put the claimed output out and run this to generate a proof this proof is broadcasted out to a network it can be to you know verify or

can be to a blockchain it can be it can be anywhere and to verify what will take this proof they'll query it and check very efficiently whether the the approver actually knows something in practice we see that these constructions are rather efficient now with approver costs at about 0.05 milliseconds per gate the proof is also very succinct it's a 128 bytes three group elements and it's very fast for a verifier to check we're talking about three pairings which cost about three milliseconds and a linear number of exponentiations at about 0.4 microseconds per byte this particular construction is one that we have in lip snark that can be accessed

at that URL but there are still open problems and open developments on this front for one no there's this notion of a trusted setup you know so in in cryptography having a setup phase is not so much of an issue that we are talking about theoretical constructions but in in the real world someone has to go and run this set up and this is a point of contention and a lot of the blockchain architectures that you see a snarks so having a trusted set up is is a potential issue and there has been active developments on this front on the second hand there is the prover is bounded because of a memory intensive computations and memory intensive computations is something that the prover only the prover has to reason

about but nevertheless must deal with and so there is also active work in this area that I'll talk about in a second on how to resolve these and the lastly malleability that if a verify were to receive a proof how can he or she believed that this proof is indeed the corresponding incorrect one and this is an area where it's like you can think about it from a man attack perspective that you want to believe that this proof is indeed the one that's been claimed so on each of these fronts we see multiple developments first there has been work BC GTV 15 and also bgm 17 them for multi-party computations these are scalable MPC protocols to actually distribute and delegate the deconstruction of this trusted set up and you see this with work from Z cache

for example where they're currently doing their powers of tau computations and it's something where any individual can participate in anyone who has a distrust of the actual common set up for everyone to use can proceed to participate in this embassy protocol and so long as they themselves are honest to themselves and generate a result that is included in this final output they can believe that that whole process has not been corrupted as so long as one person in the entire embassy protocol is honest the entire process has been fair and so this is one way for anyone who has doubts to basically believe because they must believe themselves in the process in the second hand there is distributed ZK snarks this is an area of research work that I spent the past year on and in essence what it

says is look computing these things is very memory intensive what if you could in essence distribute the computation process across a cluster of nodes so say you have like ec2 or you have like you know Google Cloud or Microsoft Azure you can spin up a large set of nodes and what we have done is basically distributed the algorithms such that they're not bound by a single person and they're not bound by single machines so that you can expand this and just throw more cores and throw more memory and therefore it's scale almost infinitely from our initial benchmarks we had seen that well first off lip snark is the state of the art implementation at around 30 million gates that's where it roughly caps off that and what we have been able

to demonstrate is that this scales to the billions of gates now so this becomes very practical for a lot of large problems so long as you're willing to pay the compute cost and the time to do it lastly in terms of address addressing the issue of malleability there was a work last year by Grothman malar GM 17 this protocol is a simulation extract wuzzy a snark and the cost to actually construct this proof is about 20 to 30 percent more than Groth 16 which was the efficient construction you saw before but in doing so you actually get this protection from Amanda nil attacks as part of the properties so we had just talked about this particular pre-processing ZK snark and if you look

at the details this is actually a specific type of pre-processing ZK snark is a pairing based pre-processing ZK snark the reason is that this is using pairings in order to do this check and to go into some details on this we can think about this as a prime order by linear map so a pairing in essence has three finite cyclic groups of prime order P call it G 1 G 2 and G T and the idea is that you will have some type of a mapping an efficient mapping that takes as input an element from G 1 an element from G 2 and it gets you an output that's an element in the group G T so given some element G 1 a gene G 1 some element H in G 2 a bilinear map

preserves by linearity which is to say that this function mapping of G to the a and H to the B should be equivalent to the mapping of G and H exponentiated to a B and for notation I will just use a bracket 1 B bracket 2 and C bracket T and that's to say a is some element that lies in G 1 B is some element that lies in G 2 and C is an element that lies in GT so going back we have this pairing based pre-processing ZK snark and this in particular is the growth 16 protocol if you want to study this there is a lot

of research and and literature out there to deep dive to give a very high-level overview to and to give you a notion about what a ZK snark really looks like underneath I will walk you through what the underlying equations are by no means is this something that you must digest immediately there is a lot of underneath that that form its construction and this is more for your knowledge to see and to get a reason about to get some intuition on how a snark works so initially in the setup phase on the set up generates some common reference string I'll call it Sigma 1 and Sigma 2 and you can think of these as like vectors of information it's just these generated random values that are valuable for actually constructing the system and for running

and playing this approver verifier game so in this case you have the proving key and their verification key you can see that the proving key is a contains much more information than a verification key and it's a much larger problem that in fact the proving key is typically on the order of the problem itself and the verification key is independent of that once you get these random values out they are this is a one-time operation that is put out in the public then participants who want to make some claim of knowing some private inputs can run an algorithm they're running this computation to demonstrate their knowledge so in this case you have three equations a B and C and these are used to construct what is called in essence a

Franklin constraint system that's mapped into these quadratic arithmetic polynomials and this use case allows you to generate three concise group elements namely a B and C so a and C lie in G 1 B lies and B lies in G 2 and that is the proof it is three group elements lastly the verifier upon receiving this proof looks at its common public knowledge the verification key and takes the proof in and says hey let me do this check if I have a and B and I do a bilinear map on this that expected output doesn't match the right hand side which is alpha beta times this this polynomial and C and Delta and that value is in essence the fundamental check to say look it

does this equation match does it make sense and does the prover really know what he or she is claiming so to give some discussions on efficiency this is a very efficient construction much more efficient than the earlier work that you saw in the 80s and the 90s we discussed the proof size every set of three group elements to two elements from g1 one element from g2 and the proofer is also relatively quick there is n plus 3 and exponentiations in g1 and there is an exponentiation Xin g2 and the verifier handles a linear number of exponentiation Xin g1 and also three pairings so this work has been

integrated into a library called Lib snark it's a c++ library that implements a lot of these zero knowledge proof systems and lip snark is quite a behemoth at its base we have this algebraic core which includes multiple things first off there is Lib FF which is a C++ library for finite fields and an elliptic curves this library implements finite field arithmetic by linear group arithmetic and fixed and variable based multi exponentiation this was something that is incorporated into a lot of projects independent of ZK snarks and it's very useful as a library for people to just develop and do algebraic constructions on next we have the second layer which is polynomial interpolation evaluation fast Fourier

transforms and finite fields and the grunge coefficient computations these things are all encapsulated into library called FFT FFT it's a C++ library for fast Fourier transforms infinite fuels I'll say this is an area that is a relatively understudied fast Fourier transforms have been well studied but in the domain of finite fields not so much we only have some so much knowledge about the constructions and you'll see a little discussion about them shortly so on top of that we have a back-end the backend is comprised of multiple components first off you can think about arithmetic circuits boolean circuits proof carrying data these are basically the models that say how do I represent a notion of a statement how do I represent a notion of a problem how do I actually reason about

something that I would like to prove and these are the representation of those statements on top of that there is a front-end interface which includes multiple things this is a small subset of it which is like there are things like zero cash there a tiny RAM there are things a general library in here that is for gadgets and proto boards and what that allows you to do and it is in essence create your own gadgets your own representations of these problems and provide a very easy interface to construct these circuits that allow you to actually a reason for a proof on and on the application layer well there are a whole a variety of different applications certainly zero cash has been extended out to a project called Z cash I'm sure

you're familiar with and there's also other areas where you know this privacy-preserving micropayments privacy-preserving computations and also from Jacob this library called Socrates it's a toolbox for ZK snarks on etherium and it allows anyone to in essence and make some claim for example like the crossword puzzle that Jack had mentioned where in essence if you know the answer you can construct a proof and potentially maybe if you know the answer but don't want to reveal it or in the case of a theorem it's it's not practical to reveal the answer because then anyone can game the system you can have a smart contract that runs a verify and checks your proof to say hey do you actually know the answer and if you do maybe it pays you out some reward this is a very useful construction and this

library I believe Jacob will be talking about soon so for anyone who is interested to develop on lib snark there are a lot of different choices that can be made and your construction at its core we have live ffs which provides these elliptic curve implications there is the Brayden Erik curve Edwards curve MN t4 and MN t6 and these are all at varying bits of security there are open fronts for us to explore an add-on u curves and for anyone that's interested you know please contribute these these things are very useful for a lot of the bilinear group arithmetic and the bilinear group constructions that i had discussed earlier additionally we have live fq FFT which provides a set of five evaluation domains so you have a

standard radix to an extended radix to step radix to a geometric sequence and arithmetic sequence so for these problems you know with most cases you can find a lot of roots of unity and that allows you to reason about things for FFTs very quickly but in the case of finite fields depending on your modulus and how your field looks and is constructed you may not have sufficient numbers of roots of unity for what you want and that's where we provide things like the geometric sequence in arithmetic sequence for computing those but the the performance costs on those is much much slower and if you go to the github page for the VFD 50 on the readme you can see the performances we've benchmarked the implementations of these across multiple

domains on all of these evaluation domains this stuff is useful for things like quantum interpolation and evaluation so going one there above we have the arithmetic circuits and at its core an arithmetic circuit looks something like this you have some inputs like a 1 and a 3 and perhaps in this case the quadratic equation is checking does a 1 plus a 3 multiplied by a 3 equal this value at a 2 and this in its most general form can be expressed as this combination of terms the summation of a sub I times U sub I multiplied by the summation of a sub I V sub I and you

check if this equals summation of a savai W sub I over the variables a from 1 through m and for convention we always keep a sub 0 to be the 1 1 value so an arithmetic circuit can define an NP language with statements that are encoded in a 1 through a l and the witnesses meaning your private inputs are stored in a l plus 1 through m so it took to build these arithmetic circuits you know if it's a very simple problem you can imagine that it's rather efficient rather quick and it's a small problem you can just kind of write it in one file and and do it and move on but in practice you know most people like to

reason about real real problems like that are much larger and in order to do that having it in one file just like with this constructions is quite a mess and so in lip snark we introduced this concept of a gadget a gadget in essence in essence is a is a collection of some arithmetic circuits some representation of a problem if you the sub-problem for example if i wanted to do the hash function of a hash function of a hash function like a hash some value three times it doesn't make sense for me to like writing arithmetic circuit that's like I put the inputs into that directly three times rather it makes sense for me to encode the hash function itself as a gadget and I call that gadget three times so that it becomes an independent and easily

debuggable form so in lips now if you provide to libraries gadget live one and gadget live two these are low level libraries that expose all the features of the pre-processing ZK snark and in our case we provide a lot of boilerplate gadgets for free there is finite fields elliptic curves parings multi exponentiation hash functions Merkle trees CPU checkers and even UK snark verifiers the sequence mark verifier is useful for some cases like recursive snark composition if you're familiar with it and these are all things that we provide immediately but the library also includes a these proto boards that are anyone to build at any type of gadgets that they would like as long as it can be expressed which it can be in arithmetic circuit form the underlying

constructions use different types of representations the most common being a rank one constraint system so that's an overview of Lib snark there are so many pieces involved in it and in our case this has been a very large engineering effort that has also been helped by a lot of developers that are building applications using ZK snarks and also by people who are interested in this field for any of you that are interested in developing on it I've set up a repo at github calm slash hard loose lips snark - tutorial and what this provides is an immediate developer environment for you to just get clone and start working on it in essence provides all the install scripts for you to install live snark on your

machine current support is mainly on the ubuntu side of things but once you get that up and running you can immediately start have importing gadgets constructing them to solve some very basic problems and it's meant to be a tutorial to make you comfortable on the developers side I get a lot of emails with respect to like a compilation and so this library is meant to resolve half of those things and and to make it easier for people to actually develop ZK snark applications for anyone who is very familiar or would like to get more involved on the development side of ellipse mark remains an open library that is out for anyone to help contribute to their we have a host of different things we would like to upgrade and update in here namely for example with respect to the curves that

we provide no pls 12 381 that the curve that Z cache is using is something that would be very desirable for us to include in lips snark and there are other areas where we'd like to refactor out certain libraries that have grown to be much larger than he had anticipated and there's a lot of areas that that you can get involved in if you if you'd like there's a Google Form at this link lips marked org slash get involved and please be in touch but other than that I want to say thanks and I hope this was informative I'm happy to answer any questions outside after this Thanks [Applause] all right any questions hey thanks for

the talk I was wondering if there's been any research done on how the implementations are resistant to trackside channels so for example if if an attacker could observe or infer the amount of time it takes for a prover to produce a proof that might reveal something about the inputs yeah side channel attacks are a very real problem and at least in this case I'm not so familiar on that that body of literature but it's an area that I think is much more lower level in terms of the actual CPU level of running these computations side-channel attacks are very prevalent any other questions I have one when I

talk to people about Z cache and ZK sparks and things in general you get all of the comments that you know that this is very new cryptography can we really trust it does it really work and like we're not really sure what would your response to that be yeah I would say first off I think a lot of this stuff like as people call it a spooky moon map and overall look like these are these are very formal academic works these are peer-reviewed papers that have very complex constructions but have been reasoned through by academics in this space and in terms of the actual proofs themselves they demonstrate a perfect completeness and perfect zero knowledge that means that if someone really knows

this information they can with high it with with complete assurance actually and force the correctness and convince a verifier of their claim and additionally they can ensure that they don't reveal any information about it so having that as like a principal is extremely valuable and I think that some of the concerns that are in this space have to do with the practicalities of it the engineering side of it were indeed you know that there is a notion of a trusted setup and this is an area that I think the current innovations that have been happening in the academic world are resolving these issues I'm providing some type of MPC protocol is useful but I would also say there's new developments on the area of Starks where there is no notion of us setup here and as those things become more practical and come online I think

that there will be much more choices for the community to reason about all right thank you very much awesome thank you