zkSummit - Zk0x02 - DIZK: A Distributed Zero Knowledge Proof System - Howard Wu (UC Berkeley)

Transcript

[Music] I'm really excited to introduce Howard Wu who's going to be talking about Disick we actually got a chance to sit down with Howard I think three weeks ago or so and do an episode on we're talking about ZK snarks but we did get a chance to touch on this so I'm definitely excited about this talk cool take it away Thanks hi so I'm Howard and I'm a researcher at skipper lab in Berkeley and also a partner at the Crypt today I'm gonna be talking about Disick and physic is a distributed zero knowledge proof system this is joint work actually done with

wenting Alessandra Raluca and Yan to begin with you're probably asking and we've also had a lot of great discussions earlier today on what is a zero knowledge proof and I will give you my rendition on this zero knowledge proof involves two parties we have a proven a verifier and both the proven the verifier knows some public function f as well as a claimed output Y and the prover says hey I know X such that f of X is equal to Y you can think of X as your private input in this case and the verifier wants to be convinced of this

and so he or she will then challenge the prover they play this interactive game with each other after which time the prover will convince the verifier if indeed they know this secret now there's one particular type of zero knowledge proof that has recently gained a significant amount of attention and this is ZK snarks easy case snark is a zero knowledge proof with a few additional guarantees for one you have non interactivity so what this means is that the prover only needs to provide a proof to convince the verifier that they know the private input X secondly you have succinct Ness

and what this means is that the proof itself is small in size and the verification time here is fast now one particular type of ZK snark that we're going to talk about today and also is very commonly used in deployment today in industry is that of pre-processing ZK snarks and a pre-processing ZK snark has a function a set up sorry that it takes as input a public function f and it produces two outputs one is a proving key and the other is a verification key I try to use size here to show kind of the the differences in costs on memory and time and the proving key here is going to be significantly larger than

the verification key now ZK snarks in general have many interesting applications two of which we will discuss today so the first application that we're going to look at is peer to peer payments and suppose you have Alice and Bob Alice wants to pay Bob let's say $1 and she may use a blockchain to facilitate this payment as you will commonly think this would actually reveal a lot of information first off you learn about the addresses that are involved and so you learned that Alice is the sender that bob is the receiver and that the payment amount here is for

$1 instead what you could do is actually encrypt the contents of the payment and so if you do that then you could actually get anonymous peer-to-peer payments but to ensure the validity of the payment in this case you would use a zero knowledge proof as you case narc that would be attached for the transaction to ensure those encrypted contents indeed are valid and justify a proper payment this is a protocol called zero cash and it's manifested in industry as e cash let's look at a second application so suppose you want to use a smart contract to run a publicly verifiable computation we actually just saw in the previous talk

with Socrates a very nice demonstration of potential use cases and potential chants for UK starts in terms of aetherium and the issue is that today when you invoke a smart contract you have to require all the validators to rerun this computation so a more scalable approach is actually for the caller to run the computation off chain and instead send along the result along with the proof attesting to the validity of the result then the validators would only need to check the proof which we've established here is cheap now these are only two applications of zero knowledge

proof sand don't be offended if your favorite application was represented here these two applications were actually chosen very specifically to motivate our problem which I'm now going to address so we have some good news and some bad news the well if we plot the circuit sizes of the applications that we just discussed we'll see that the private payment application requires about a million gates and this is this is great it's actually very practical and this is why you see things like zacasha and deployment today now if we look at a typical smart contract execution and we try to map it into the circuit world we find that the actual cost of these

things is around a hundred million gates and for a larger smart contract execution we find ourselves using billions of gates so unfortunately current monolithic ZK snark implementations run out of memory at around 10 million gates and this makes this particular application smart contract executions just out of reach from current techniques so we so we asked ourselves you know what could be a stepping stone for enabling applications such as this and this is where you know I present here physic physic is a zero knowledge proof system that is one

distributed meaning it enables the execution of a ZK snarks set up and prove her across a compute cluster second it is scalable so heretofore unreachable circuit sizes up to billions of gates and the intuition that we have and the pattern that we see is that as we double the number of machines we effectively support twice the circuit size the third point is that this is parallel so it speeds up the time it takes to generate a proof and again the pattern that we see is that as we double the number of machines we the general computation itself is roughly twice as fast so how did we do it well the approach that we took was to take a

monolithic ZK snark namely one by N's growth from 2016 and distributed it on a cluster of machines now this approach seems quite simple however it turns out there were a lot of challenges to distributing the protocol we chose got 16 specifically because it is highly efficient and currently offers the smallest ZK snark proof size and in general we had to tailor our architecture at every level to ensure that our protocol could adequately demonstrate scalability and parallelism so let's talk about and let's let me walk you through some of these challenges that we face now so in terms of challenges like let's take this ZK

snark diagram and I want to point out that the verifier in this context is extremely small and really cheap to run therefore we turn our attention to the setup and the prover at first glance we probably want to spin up a cluster of machines and run the setup and prove our on it and next we probably want to use a distributed data structure to represent our public function f the proving key and our secret input this looks all right however it's not and there's several challenges that arise with this current setup the first is that we're multiplying polynomials of degree that are in the billions second we're

representing these polynomials as terabit sized arrays third were accessing large pools of shared memory and complex and forth were synchronizing shared state that incurs significant network delays all in all these fundamental challenges are things that we need to overcome and we do so in the following way so we start with the setup and it turns out it's not enough to keep the subcomponents of the setup itself monolithic and so we distribute the setup by implementing distributed algorithms for the subcomponents of this setup the distribute setup then outputs a proving key a distributed proving key

and a small verification key just as before we distribute the prover by distributing the monolithic subcomponents of the prover and lastly we will verify that the proof is valid and again we forego distributing this step as it's extremely cheap to run so for times sake I want to focus on one critical part of our system and that's the distributed prove err you will find details of all of this all of these distributed techniques in the paper for Disick and it's available online and I'll show you the link at the end but today I really want to go over one

critical component in this system and that's namely the witness reduction so the witness reduction I will show you some of the off-the-shelf approaches that you can use to compute this reduction and then I will show you the tailored approach that we use to make this witness reduction both scalable and parallel so to efficiently compute the ZK snark proof we need to the circuit we started with in polynomial form and namely the equation that we want to evaluate here is this one if you haven't seen this equation before this is an important equation introduced in GG PR 13 that defines a quadratic arithmetic

program which has to do with arithmetic for circuits and if we zoom in on this equation there are three terms that need to be efficiently represented and evaluated in order to perform the witness reduction also notice that these terms have summations from zero to n where n is in the billions so I'll focus on how we efficiently evaluate these summations note that the earth medic operations outside of these three terms will make use of distributed FFTs which again you can find it in the paper and zooming in on one of these terms we see that there are two components a matrix a and a vector Z the matrix a represents

one part of the input wires comprising our circuit and the vector Z is a satisfying assignment for the circuit you can think of it kind of like a combination of the public inputs and the private inputs that we discussed earlier so as a strawman for computing this we might start by representing our matrix a as follows and representing our vector Z as follows we'll represent these as matrices and vectors in the canonical form and to evaluate the summation we need to join the elements by their index I so as a straumann approach we may partition our matrix a row wise and our vector Z element wise next we'll join

our partitions row wise so a naught with Z naught a 1 with Z 1 dot a dot a down to a n with Z n and this generates a joint table that will look like this it appears quite uniform in cost with each entry now independent of all of the other entries but it turns out that this isn't the case and let's see why so here's an example of the data that that would be stored in this case and because of the nature of our circuit representation our matrix is what we call almost sparse and this means that most rows and columns are sparse however there will always be a handful that are

dense so in this case think of the red red entries as like your dense entries and the green ones as your for centuries if we partitioned our matrix column-wise to compute for the cluster to compute the second column would be slow and straggle causing all the other machines to wait on it to finish its task this is obviously a bad thing and so this is probably not the best way to look at it if we tried the other approach of partitioning this matrix row wise well again we'll actually run into the same problem with the first row as our straggler and causing all of the other machines to wait on it to finish its task we studied

all of the off-the-shelf approaches to address this problem currently and this is mainly trying to address a problem of data skew and we benchmark them across varying circuit sizes and also across varying numbers of machines to defer to determine their feasibility and the approach that we took with these was to basically say let's replicate and partition the data so that the computation is distribute evenly this is what all of the off-the-shelf approaches try to do from a it's like a systems level approach so the first one that we looked at was block join and block join is one of the common techniques to address data skew what it does is it will replicate each entry in one distributed data set across every machine so the hope is that when

you're joined but with the other distributed data set the partitions will be more or less evenly spread across the machines and what we end up with is a joint table that looks like this so at first glance this table looks quite large and indeed it is block join has performed n plus 1 times the number of partition replications and recall that n plus 1 here is again in the billions and so now every partition here is dense and therefore the computation is uniform well that's true however the table is also now huge and impractical to compute so this does not work for a system and

so we turn to other off-the-shelf approaches next we benchmarked another common technique to address data skew that's called skew joint and skew joint takes a more fine-grain approach by first computing usage statistics and it will replicate frequently used entries for every machine this sounds more reasonable and indeed in most cases it really is however for our system it turns out this provides us with minimal advantage and let's see why so if our matrix a is partitioned row wise and we perform a skew joint operation with vector Z we see that each partition only needs to access one unique element from

the vector Z and in this case skew join is actually functionally equivalent to the straumann approach we saw earlier now if our matrix a is partitioned column wise and we perform a skew join with vector Z we see that each partition now needs access to every unique element from the vector Z in this case we actually find that skew joint then is basically equivalent to block join and that was an approach that we saw earlier that we had deemed to be one that's dense and therefore impractical for our use cases so no matter how we organize the data here off-the-shelf approaches

will cause unnecessary replications that blow up our memory cost requirements and it makes it impossible to scale the system actually in fact I think the the approach this approach that we used at the time it turns out we wouldn't even scale beyond like 50 million constraints on 128 machines and so until then you know this is really a twice it's it actually really be twice as slow as our tailored approach and I'm going to describe that next so for the tailored approach we implemented one that basically can evaluate our witness reduction and preserve scalability and parallelism the approach that we took was to isolate and transform the data so that the computation is distributed

evenly and let me show you a high-level picture of how we do this so we start with the almost sparse matrix a from before and we perform now a pre-processing step this will get us our density counts and so this will get us density counts for each of the partitions that are in this matrix and these statistics will inform our system how to isolate the dense vectors from the sparse vectors which we do next so using this density count information our system will then split dense vectors into sparse partitions now to perform the joint operation between matrix a and vector Z we will perform what we call a

hybrid join a hybrid join will replicate only a handful of the unique elements from vector Z as we set our matrix a here is almost sparse and notice now that in our case each partition actually just has one dense computation to perform so our replication factor was minimal and as our approach is able to preserve the almost sparse structural representation of matrix a we find that this actually ends up being quite well this enables us to join our data and compute the summations from before without stragglers and in practice for the same number of machines we find that our tailored approach now enables us to

reach billions of gates were off-the-shelf approaches we had said kept us away from the Evo in the billions of gates and and so along with other distributes up components that were described in this paper were able to architect a zero knowledge proof system that is actually scalable and parallel so we implemented Disick and we used a cluster compute framework called Apache spark our system is written in Java with approximately 10,000 lines of code and we ran our experiments on ec2 using our 3/8 X large instances these each have 32 virtual CPUs and 244 gigabytes of memory our evaluations showed us some really interesting

patterns and properties so in terms of the largest supported circuit size what we first evaluated this and against lib snark lib snark is a C++ library 4zk snarks and we profile this in our environment and found that it would reach approximately four million gates when we profile physic across a different number of machines we found that we were able to reach approximately 2 billion gates with 256 machines and the pattern that we saw here is that as we double the number of machines we were able to support twice the circuit size so this then that is to ask you know could we compute up to these large

circuit sizes in a time efficient manner it's one thing to just be able to reach that it's another to be able to reach that in a practical manner and that's where we look at scalability so here we have two graphs on the left is the set up and on the right is the proofer note that this is a log-log scale graph and so if we follow the trend on one of these lines namely the one for 256 machines we find that the slope is approximately equal to 1 so this is a linear approximately linear and the pattern that we see is that as we double the circuit size we're able to support twice the what we're able to compute it takes roughly twice the time to compute and that's a very nice property to have here again we plot the same data now but

show the number of machines on the x-axis and plot the circuit size so this is trying to demonstrate parallelism and again on the Left we have the set up and on the right we have the prover if we follow this line at 2 to the 26 this green line the pattern that we see here is that as we double the number of machines those computations actually approximately twice as fast again this is a terrific property of this system and something that we find very that would be very necessary for computing large instances and so in conclusion we found that our that prior ZK snarks support Maxum circuit sizes in the millions of gates at an amortized cost per gate of one millisecond and we find with our techniques that physic is able to support Maxum circuit sizes in the

billions of gates at an amortized cost per gate of approximately 10 microseconds the full paper is available on crypto ePrint and I'm also proud to say that we've released Disick as an open-source library on github you can find it by going to digit org and we've put a lot of hard work into making this library available to the public with a convenient profiling infrastructure so that you can replicate these results but you can also use it to build new and interesting applications with disick and lastly I'd like to leave you with two open questions so the first question is with regards to even larger circuits what techniques will get us to trillions of gates if any and based on napkin math

if you look at the current techniques that we use we need approximately a hundred thousand machines in the best-case scenario which frankly is too many the second open question is with regards to others the scenes their knowledge proofs so how efficiently you can others things our knowledge crews be distributed and you can look at you know Starks or bullet proofs our techniques are likely an excellent starting point they share a lot of common primitives below and it seems to be an area that it would be very fruitful to study further and so with that I'd like to conclude and thanks for your attention hello cool so here's some questions hi

thank you have a great talk and what is the input for Disick so if I wanted to use that what would I have to get pass into it to compile or yeah so to use the system you basically need to have like a problem like some function that you're trying to compute and then you have to map that into a circuit world once you have that you'll have like your public inputs on your private infants that you need to provide all of this would then run on you know either your personal machine or on a cluster machine where you could it can really be be operated on any system that supports the Java like JVM in this case and in general like as long as you have all the dependencies that the library requires

you to do then that's kind of all the pieces that you need since this are one CS constraint system basically that's the input to the design yeah so the current library supports like penguin constraint systems and we use that and map it to a quadratic or reduce it to quadratic arithmetic programs if you'd like to try other approaches you're also welcome to contribute on that front but right now that's the empty language that we support thank you for the great talk looking at the performance graphs after after certain amount of executives it looks like the system reaches some kind of diminishing returns so after I see that for smaller instances and after 120

wait and you go to 256 and then yeah in this one second you know animations are slow they should have like a scroll feature okay in the next graph I believe yeah here I noticed that the set up and approvers in the in the lower part of the graphs they start taking longer yeah is there a - that is it that similar to other parallel how after while I think more CPUs does not make the parallelism better in just computational overhead

yeah absolutely that's a really good question I'm gonna move it to this previous graph and just kind of show you on the the red curve here it's the same it's the same property that you're pointing out there the the trade-off that's being made is that as you grow the number of machines you basically start to have this set-up cost overhead and not to be confused with the distributed setup it's like the actual cost of like no turning on and spinning up all of these machines there is a a cost of coordinating all of them getting them on the same page to solve a problem in this case to generate a proof and that cost itself will grow as you increase the number of machines on this graph we only plot it from two to the fifteen onwards but in practice because

I tried it from like two to the five and through two to the ten you actually see that it starts to really really cross over threshold so that to the point that like this will be actually the highest and this will be the lowest and that's a natural trade-off that you're making because as you increase number of machines the communication costs on network and also memory resources has to be shared and all those things grow and so the real value and this is actually kind of when you start to cross over that threshold and you're looking at large problems that it becomes useful to do a distributed technique thank you sorry the although this reduces the cost

of calculating a proof from a circuit is is it still preferred to be expensive to calculate the circuit from a virtual machine by code or whatever representation that you'd have that would be executable normally so are you saying like if I were to have some problem that I'm map into a circuit and then I want to compute this like that process before I get to computing which still be hard is that the question or I've been calculating the circuit diagram from some form that a human would write oh well so the actual computations here are happening in the clusters so it would be solved through this system which maybe I'm not I'm not sure phrase imma create I wrote my own

my question correctly so like if you for example you want to prove some kind of small contract mm-hm is it still relatively expensive to use in a real blockchain to have like a human readable language of some kind to compute the circuit diagram from that language or from a byte code is that step still very expensive because this this system starts with the circuit diagram yeah so this this system itself assumes that you you come to it with like a circuit right and the steps leading up to that are not being addressed in the system currently to make that practical I would say it it's really not too bad of a problem right now certainly you have optimizations

that would be helpful to basically reduce the circuit size but from my understanding and I don't have t-bo's here and wants to clarify but there there is basically some cost to constructing those circuits it's actually a lot less than the arithmetic of the circuits themselves and so in practice you can do that on a single machine and load it up onto this cluster just fine it's it may be you know and how or something I don't know but in practice like this still remains the bulk of the computations which it would not be restricted to its bottlenecks on that's a great answer thank you any more questions cool so this graphs are useful to come

calculate like times like if I have so many machines and so many circuit sides it will take me so much is there can you can you refer a quater reference where I can actually compare some actual use cases and try to figure out how many like what what's the circuit size for example I calculate the e theorem transactions at like so many million gasps like how much a circuit size would I need to come to to construct such a ticket yeah so we we didn't evaluate it for like the smart contract case but we did two applications that you can find in the paper one was actually implementing another previous paper called photo proof and what that's doing is think of like like Photoshop operations like

image transformations and each of these image transformations is a state transition and so if you could have like a proof that the state transition is valid and it only does no blah things and it comes from a logical like a a properly signed like a camera for example then you can maintain the certificates that ensure the integrity of the image so that was one that we did and we actually able to get it up to like I think it's like five or seven megapixel photos that on just on just like 32 or 64 machines and it would it would take like a minute or two it was like pretty quick if I remember correctly so you could use you could use that as a heuristic benchmark for like if I had a smart contract and I'm trying to apply some matrix operation you know it's a very similar type of context that

you could potentially try to map the the napkin map the cost to the second application that we did was really at mission luring use cases so there's a lot of demand for our interest really for having verifiably like Integra table machine learning computations like a lot of that is just linear algebra really underneath and so as long as we can represent this in this matrix form which we actually show it is then you can compute a lot of machine learning techniques like linear regression and whatnot very naturally in this system and we also highlight that in the paper as something that's in the realm of practical for small problems any more questions oh one all the way in the back hey hey can you use that

approach to do delegation of proofs to a third party and are there any ways to sell guarantee privacy of the private inputs that's a really good question and so that that's one of the fundamental trade-offs that are being made here like this is a distributed system not necessarily a decentralized system and inherently if you spin up a cluster the trust model is that I assume that I trust all of these machines to be in my control and to behave honestly with me so you know if I go on AWS and I spin up a cluster of ec2 instances then I'm assuming here that I own all of those ec2 instances and I'm not tampering that hardware in this case it's it's another model to say like hey like maybe there's

an some other party that is doing this they're spinning up and easy to instance and I give them my data in which case like you'd need to have like another layer another additional layer of protocols which you know how are in explored here but I would I would think that you could do some type of encryption approaches or homomorphic encryption approaches that while extremely costly may get you something ok for you know recently sized problems but that's an area that's certainly open for more exploration Thanks anyone else I don't know if you can tell but lunch is actually I think it's been served so thank you so much Howard thank you

[Applause]