ZKPodcast: Intro to zkSNARKs with Howard Wu

Transcript

[Music] welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik [Music] today we'll sit down with Howard Wu to talk about ZK snarks lip snark and how you distribute proof generation using Disick hi Fredrik hi how's it going pretty good

so today we're gonna be talking about ZK snarks this is the second episode in the zero-knowledge series that we started I guess like two months ago yeah I don't know it's it's been a while it always feels hard to measure time and blockchain space but yeah I mean we did the intro to zero knowledge proof episode kind of covering the basics what does zero knowledge proof is kind of how to think about it but it wasn't very practical it wasn't in an episode like talked about any particular implementation or anything and so we want to dig in now with Howard Wu on like some real practical stuff so

yeah we're really lucky to be sitting here with Howard Wu Howard was one of the kind of original guys at blockchain at Berkeley he's the live snark co-author and he's now acting as a managing director of decrypt capital Howard thank you so much for joining us to talk about CK snarks yeah it's my pleasure to be here I thinks they're having me to kick it off I think it would be really cool for us to hear a little bit more about you sure tell us about your story yeah I think that'd be great so my background is in computer science and applied math from Berkeley I first got into the blockchain space in 2011 through pic point mining at the time and around 2013-2014 when all of the different all coins started popping up I got really

fascinated by the technology itself and understanding you know the trust models like what is decentralization mean what kind of features does this enable what's the use cases and that's when I really started to go down the rabbit hole in research and I worked under two professors so one is Professor Alessandra Casas who is a Rishikesh and also professor dawn song who is a director for ic3 and now a founder for Asus labs and my work has primarily been around things like consensus mechanisms and generally in cryptography and one particular area of interest for me has been zero knowledge proof this is a area where you can do so many fascinating things and that's where

I've helped with different initiatives such as Lib snark which is a C++ library for ZK snarks as well as other libraries like the FK 50 and the FF these are kind of those arithmetic and mathematical basis for live snark recently released a library actually called the physic which we can also cover very soon but during my time at Berkeley I also helped with getting blocked in at Berkeley started and that's been a fun fun endeavor for me after after I finished my undergrad I went to to work at Google and it was fascinating to kind of learn how to think about distributed systems from their perspective but it was very clear

they didn't have that same notion of decentralization and so I came back to Berkeley to do my masters in cryptography and and ever since it's been a it's been a very fruitful endeavor and you know and now also with my partners are starting to creep capital and for us this is really meant to be one of those building blocks for getting this technology out to mainstream adoption we really look at it from a pain point perspective and so that's where things like privacy and scalability and interoperability are most poignant to us and we really try to work with founders to one educate them but also to support them on their journeys as well well I don't think we could have a better guest to go into zeroes marks then and I'm so glad that

you're here with us to explore this this part of the space I appreciate it maybe we could start with the basics what is a zk snark so I think to really get into what a ZK snark is it's probably good to start by saying like what is a zero knowledge proof and just to kind of remind the audience members No zero knowledge proof is what I would call a privacy preserving cryptographic proof of computational integrity that's a lot of jargon to basically say I can't tell you the secret but I can prove to you that I know the secret so for example perhaps I'm looking at like a Sudoku puzzle and it's one where you

know the the function itself is going to be the puzzle but the claimed output would be you know all rows and columns in some ordering of 1 through 9 and you will have two parties and in this scenario you have a proven and a verifier both of them know this particular function f and they also know this expected output in a 1 through 9 but anyone can basically come and say hey I know the actual solution and that is your private input X and so someone who claims to know this will be the prover and say all right let me generate some type of proof and they fill in you know their answers into some type of a circuit in this case and it will output a proof and the verifier then looks at the proof and runs it on that public

function f and also the expected output and will at some point very clearly believe that this person really knows the answer one of the great great features about this is that you can then convince someone else that you know how to solve a Sudoku puzzle without actually showing them the answer key and that's kind of the beauty around it I love that you've just explained that we actually used that example in the earlier episode but it took us so much longer to say what you just said very concise level so thanks for that yeah so in this context it's this is actually a notion that was first introduced in 1985

by a goldwasser McCauley and Rockoff this was one of those first papers that really started to introduce this notion of a zero knowledge proof and the early constructions were actually quite costly they were one not succinct meaning the proofs themselves were just massive like massive especially for that day and age when computers were also quite quite primitive so to speak um it just wasn't something that was very computationally feasible but additionally for approver to convince a verifier it was an interactive protocol meaning they would talk back and forth back and forth with each other a plane is kind of a challenge of verification game to actually convince each other or convince the verifier that the prover

really knew the answer and these are some of the trade-offs that were in the early constructions very clearly a bottleneck for adoption and what was really nice was you know in the past decade we've seen some huge advances by kind of taking a different route and a different approach to looking at zero knowledge proof sand that's where the ZK snarks really were born these are proofs themselves that are extremely succinct they're very shortened size we're talking about like you know a hundred or 200 kilobytes size proofs now and they were also non interactive meaning the prover could come up with a proof and then give it to the verifier and really any verifier could come and check this fact for themselves that for at any

point in time from then on it's a very nice notion and you know additionally these are proofs themselves that are publicly verifiable and have all these nice properties that can be associated with them especially in the case of blockchains and ZK snarks therefore our you know it's a it's a jargon but ZK snark stands for zero knowledge succinct non interactive argument of knowledge what that means is I'm basically you know I can I can convince you of some fact without having to tell you the underlying fact itself and I can do this very very concisely without having to interact with you continuously I just kind of generate some type of a proof

based on this problem and give it to you and I think that this is a very beautiful notion and also a very powerful one when you're talking about ZK snarks and zero knowledge proves I mean they're not the same right like ZK snarks is a technique or a zero knowledge proof system it's not a particular proof it's not a proof of any particular program or aspect it's a way to generate a proof right so how does ZK snark like set itself apart from these other solutions basically if you take the Sudoku problem you could could you express that as a ZK snark yeah absolutely so ZK snark is one type of zero knowledge proof and easy case

snark it basically is a a collection of these properties so you know zero knowledge is certainly one of them and you have these other properties as well that are intrinsic to the particular protocol that's being outlined here this protocol itself is formalized as part of this an approver verifier system that we discussed and in general like ZK snark certainly are just one branch of zero knowledge proof systems there are also other forms like as you've probably seen recently there's been a lot of interest around starts and starts themselves are another form of a proof system where you can also have zero knowledge as a property this is a very fascinating you know endeavor right now because of these

concerns especially in the blockchain space around a trusted set up which is intrinsic to ZK snarks and you know those are areas that certainly I'm happy to also talk about it maybe we can go into a little bit of this trusted set up because I think it's something when you you know quickly just kind of Google ZK snarks or Z cache or what have you it's it's one of those things that's often brought up as a negative or like as a problem with this space what is the trusted set up and why is it necessary yeah so in a ZK snark construction you have three components that you're reasoning about first is a set up a second is a proofer and third is a

verifier a set up basically is a process to establish the game that you're playing here so it is what generates a set of publicly viewable keys for example proving key and a verification key and what that does is basically set the stage for all of the provers and verifiers for the remainder of time to come on this particular problem that is a huge notion that in the academic world is not so much of a concern because in in the world of theory you just say oh I will have you know someone run a secure set up and all the provers and verifiers can continue to interact no problem you know what we see now in practice in the real world is there's

very clearly a notion that hey like who is going to run this setup then you know someone has to run it and that's where there has been recently some some concerns around basically what what is a setup and who runs this setup and how do we ensure that this is a secure setup and I I would say that there are multiple ways to address this problem you know the first is we've seen how Z Cash has done this originally there was a handful of people I believe six that had come together and said you know let's let's make this setup happen and they were geographically distributed they all went through their due diligence on buying computers in what I would call a random fashion and finding a random place to kind of operate and

spend a few days to generate these types of of keys that they would then use to combine and actually generate the proving and verification keys I think that that's a that's certainly one way to do it and the fact that there was just six individuals involved at the time has raised some concerns from folks in the community and that's where Z cash has said you know now we are transitioning to a new type of ZK snark and in the process we are also going to do a multi-party computation on our trusted set up so what this what this means is well a multi-party computation is when you have like a group of individuals that are each running some piece of a computation what Z cash has now done is say okay we have this powers

of tau it's a it's a it's what they're calling it and it's a component that's inside of this set up we're gonna have that be a process where anybody can run this and if you run it so long as you're honest to yourself you will believe that the rest of the process is also secure the reason for that is in a multi-party computation so long as one person in this case is honest then this then the system itself will generate an output that is also honest so actually so out of the six say you did six again you don't need one one of the six to actually be honest in the in the original trusted setup of Z cash the six the six people I mean there's some really great stories

about what the lengths that people went to to make sure that these that this computer was unique that there was no way for them to be hacked or found or followed or anything in that original trusted set up if did they all have to be honest or was that also one of those examples were only one needed to be honest for it to 100 percent yeah consider so legit so in that context you know as long as one person assured themselves that they were not going to keep any remnants of this computational process then the system itself would be would be sound and I think that that is a very powerful notion and certainly

there was some some footage if I remember right of people like burning you know machines and that's crazy I would say what this pretty funny yeah with this current with this current around where people or anyone can participate by the way there's also been some really really awesome photos I've seen like there was one guy who had you know had their computer lined with a tinfoil and like was running this whole thing in like a basement and it's just really really like guy saw someone yeah take their computer on a plane and buy a bunch of SIM cards to upload that data into Canada actually have what I have a friend who participated in the power so tell thing it was it's pretty funny I mean so whatever negative things you can say about this it is kind of cool to

have this like trusted set up thing like yeah if it's six people I can understand the arguments of like yeah you could like bribe these six people and whatever now I think I think they have over a hundred participants and powers of tau and like you don't know before and who these participants are so you can necessarily bribe them etc that are like you can be pretty damn sure that one out of a hundred is going to do this thing correctly and the nice thing about it though is it's like a community building effort you kind of get together and like you run this process and kind of build up this little community around ISM I mean it does sound awesome but I guess the downside is just imagine the

organization that this takes every time you want to do one of these things I know and I wonder is that sort of the reason that they're thinking of moving away from it like what like if it is so cool and fun and and now very trusted why why not do it I I would say as cool as it is and as community building as it is it is still also a probabilistic right like from their point of view because that you know these are like cryptographers who are looking at it and you know the cryptographers view of the world is very different from just a conventional notion of the world and it's like everyone is guilty until proven innocent and that's where that's where you know for a cryptographer like having a hundred or 200 or even a thousand

participants in one round means that you still have you know a you still have a probably you still have a probability that there is some collusion happening and it's much better if you can just remove that problem altogether so this is more on like the perspectives so to speak then the actual kind of practice this is kind of cool to hear a little bit more about like that mindset and like what what's driving this push towards less of the ceremony and entrusted set up and more of these like what you're about to say that though or maybe you did it was what is replacing the trusted set up then like what is actually coming in its place yeah so there's been a lot of efforts on the

research front to develop things like Starks Starks are basically succinct transparent arguments of knowledge these are it and and ZK Starks themselves enable the exact same game to be played as before with approver in a verifier but this time the setup itself is very simple you you basically only have a dependency around some random coins that are and the definition around some hash function that you choose and everybody understands this notion and can use it without having to actually rely on a generation process for these these structured and very large keys that are

that are going to be passed around it's a it's a much more so it's not it's not only a more computationally and cryptographically lighter assumption that you're making but it's also a a more trustless way to do this especially in the case of blockchains but the trade-off right now right is that Starks are way harder to generate isn't that right the the technology certainly is very young it's really it really sits in the realm of academia today and I would say that this is a very similar case with any previous advancements that were made if you look at how ZK snarks came about in the early constructions they were also like costly um you know you have proofs that are

large and if they can take longer than maybe what would be ideal and over the years people refine this notion and come up with newer protocols that have either different cryptographic assumptions or lighter cryptographic assumptions and you basically massage the techniques down to something that is much more efficient and user-friendly and that's that's kind of the state of the art itself and here we see a very similar progression happening albeit I would say much faster as well let's go back to the ZK snarks and talk a little bit more about them and how they they look are there any other are there like some key properties of ZK snarks specifically that are different from all of these

other systems that we've been talking about the case snarks themselves enable all sorts of interesting features and the reason for that is because of these properties like I had mentioned you know succinct Ness and on interactivity and zero knowledge and what I'm really trying to get at here is that ZK snark is a very practical protocol it's one where because of the fact that proofs are very short and verification time is extremely fast you actually can come up with constructions that are usable in the real world remember that most systems in the real world if you even have like 100 seconds or 200 milliseconds of latency it can be potentially you know

unacceptable for a service to operate you know with any higher thresholds and that's where in this case execu Starks themselves are extremely fast extremely efficient and therefore you know for the verification component it's actually very much usable and and and able to be integrated into existing systems but with that said what are the really big challenges of ZK snart's if you look at the current state-of-the-art lip snark is the de facto library for generating ZK snarks and lip snark itself is designed to be a monolithic process that runs on a single machine we've seen in practice from our benchmarks that in essence you can generate proofs for problems that are on the size of ten to twenty million gates so what what is a

gate here basically all problems in this world are mapped and can be mapped as circuits you can think of circuits as you have like two input wires in some output wire so like if you have like a an addition gate you have like a and B come in your evaluate a plus B and you get some value C out or multiplication a times B equals some value C and it turns out that a construction in Lipson art can really only support up to ten to twenty million gates if you look at the existing applications that use lip snark things like the zero cache protocol which is manifested as G cache we're talking things currently that are on the order of a million gates granted the

newer construction that's happening later this year will bring this down by you know an order of magnitude but it's very clear that as we start to branch out into larger things things that are more than just payments we are going to start to hit that upper bound on what libsyn are could possibly support and that's intrinsically the challenge that we're facing here I have a question here because do you just said you said a million gates and it's bringing it down maybe I misunderstood that don't you want more gates to make it more efficient they've written their algorithm to use less gates so that it is more of see I see yeah gotcha like it's it's better if if you know a user doesn't have to wait like a minute you know to

generate a private transaction and merely just seconds like and so you know the team there has worked very hard to come up with a new construction that can in fact be much more efficient and we've seen that it's something on the order of like 90 percent less memory usage and eighty percent faster and that's very powerful and and it helps with driving a usability and at option it nothing's like that yeah I mean so to put some perspective on the the bounds of things we're talking about like using a million gates like in Z cache you need several gigs of RAM it takes minutes to generate a transaction so it's it's slow it requires a big computer it's like not

something that you could do in your phone so if they can rewrite their construction to be much more efficient you could run it on a phone or they could enable shielded transactions to be like this the defaults choice where that would be pretty hard otherwise but is this also like you're talking about these constraints and why you want to be able to push up to more gates is that just because of like a hardware bounds like because a normal computer doesn't have more than eight gigs of ram and therefore you kind of want to be able to distribute this or that that's what you why you're saying like it it maxes out at a couple of million gates or is there

like some software aspects that makes it max out a millions of gates great great question so if we look at the existing systems that are using lip snark what happens is as we start to grow and solve bigger problems it's very clear that we run out of memory like we will exceed memory bounds and additionally it's so time intensive to generate the proof in that case because you know you're swapping out to disk and also just the problem itself is so large that it becomes a very inefficient process it's not parallelized and it also doesn't scale so that's where if you take the notion of like smart contracts today and this is like generalizing just on payments like if you add in payment

logic on how and when and why you would make a payment it's very clear that smart contracts could take advantage of this type of system as well especially in the case of scaling and also for privacy but we just don't have the ability to do that today with our single machine implementation it's not quite fast enough yet it's it's it itself is not running fast enough for it to be a scaling solution yeah to be helpful in a scaling solution if you look on a theme today you know you can run smart contracts but with severe limitations for example it can run for 3.14 million microseconds and you also have a memory capacity of about 39 megabytes these are real limitations to enabling

much more interesting smart contract logic and ideally you know one way to resolve these problems is to say hey what if I made a circuit construction out of my smart contract like I as a developer you know you map the smart contract code down to some circuit form and I compute this off chain on my own computer I get some result out and I generate a proof and I submit these to the etherium they only have to pay the cost of verifying approve rather than actually running that logic and this can potentially be a way not only to scale the EVM but also to improve the privacy bounds of the EVM we're doing often compute so you don't leak any knowledge in this particular case and that would be really cool actually but only if the

if the zero always proves themselves or the zk snarks themselves are our efficient efficient and like you know because in this case you wouldn't need a trusted set-up for every contract and that's not really feasible so there indeed you need something like Starks maybe yeah but I wanted to dig into these circuits a little bit so you mentioned they're essentially like gates but what are they like logic gates is there and and NAND and not and and that's it or are there we mentioned there was like a post gates what's the most complex gate and like what's the variety of gates that exist yeah so there's a few different forms that represent

the most common ones are arithmetic circuits and boolean circuits you can think of for example in arithmetic circuits you have two operations you have addition and multiplication addition and multiplication will operate inside of some finite field ideally a prime finite field and this allows you to basically map any type of computational logic down into a set of additions and multiplications the gates themselves take as input some number of input wires and then they'll spit out one output wire and you can basically use this to compose and represent all sorts of typical computer language primitives like your for loops and your

your while loops and your if statements and your else statements there's actually been some papers in the past that map the entire assembly language instructions down to a set of these types of circuits and this is also past work done by you know alessandro and you can you can find these things online and what's nice about it is there's been a lot of optimizations that people have come up with for example like how do i you know optimize for like a for loop case or how do i construct ops and optimizations for a certain specific type of azor knowledge proof system and what's nice about that then is that you can use these and amalgamate them into something that is very practical so that you can try to scale these smart

contracts for examples into much larger problems it sounds very much to me like CPU design I mean it's logic gates and I mean in CPU we have millions of transistors I mean couldn't it sounds in essence like anything that you could map on to a set of transistors is something that you can map into a zero knowledge proof which I guess I mean it would be true because it's generally but we I mean there exists a whole branch of computer science around FPGAs whoo that name they have their own languages to develop and design these FPGA is is this something that could be applicable to like speed-up generation of Sarah knowledge produced yeah I would say the general field of speeding up a ZK snarks

is quite young there hasn't been much explorations as far as I know that I've gone into things like FPGAs or some type of like custom like a6 or certain types of GPU implementations that's where like for us what we did was we you know I spent the past two years looking at distributed CK snarks and how do we basically parallel eyes this computation rather than looking at some of these other verticals so I think it was very clear that with the rise of like cloud computing and the the commoditization of these clusters it becomes cheaper and cheaper to just spin up more machines rather than go down the route of getting dedicated hardware and so this naturally arises then you know how can I just add on like another machine and another

machine another machine to to distribute and generate as you guys start proof then so we've talked a little bit about lip snarks you've mentioned it a couple times but I was thinking it might be really helpful to define exactly what Lib snark is this is something you're the co-author of and so I'd love to hear from you how you define it so I would say that lip snark is a library a C++ library that implements ZK snark schemes so these are a cryptographic method for improving and verifying in zero knowledge the integrity of computations inside of lips mark we have a host of reference implementations of ZK snark protocols and this is a very standard and at least currently a most used

library by those in the academic field and also in industry developments for implementing our protocols for their application needs Lipson arc itself has been around for a few years came out of a body of academic research and academic work to this day we still say that this is a code that is not intended for production use but has gone through many audits and we've done a lot of work to update the library as bugs have popped up in different audits lips mark itself has been adopted by you know several different projects in the blockchain space I think most prominently it would be a Z cache and we've seen that there's also been a lot of contributions that an

interest from the traditional tech companies here Google's and your Facebook's and your apples and I would say that this is a library that is meant to provide this set of reference implementations so that people can test and benchmark and understand and study the trade-offs that they make with different types of constructions and schemes with without something like this what would a developer have to do would they have like is this this is basically making it a lot easier to start incorporating it I guess yeah I mean the whole point about adding all of these implementations and making an open-source is to basically democratize the case-knives is to make it easy for any developer who gets a general notion on what this is but maybe

doesn't have the time or the capacity to go and implement the schemes themselves there is always you know what motivated reasons why someone would would develop a protocol here and add it in and we see this from time and time again more and more contributions to the library if I understand you correctly like one part of it is I can take one of these reference implementations I can like it if there's a something that I want to be able to generate proofs for and it's already implemented I can just take that off the shelf and use it yeah what if I wanted like what if I knew it had a new problem that I wanted to generate proofs for what would I have to do there's a few ways you can do this first I have on my github repo and

github.com slash a library called live snark - tutorial and what lipstick tutorial gives you is just a very simple boilerplate setup where you have like the existing lips mark library imported and you can from there immediately start to write code where you take advantage of things like the gadgets and underlying primitives and you can call in to certains you can arc protocols and just run with it from there if you want something that is more application oriented we've seen also things like Socrates from Jacob uber heart and and friends and they basically have mapped the lips nog library into their rust construction and that also

generates out boilerplate solidity code for basically verifying verifying proofs on aetherium another route that has been taken has been to add different types of bindings and wrappers around lip snark so for example there's J snark from emedco's ba who basically used a Java implementations to map into lips narcan it provides a more developer-friendly way to write circuits and generate proofs then there's also been Isaac McClure's implementation on snarky which is a no camel library that also maps into lips narcan Oh camel provides a a more implicit constraint generation process that makes it easy and intuitive to write functions that get mapped down

into a circuit world and I think that that's these are all ways to basically drive usability and so for developers who come in with different backgrounds they have different reference implementations and also different libraries to work with to fit their needs do you would you say that like Lib snark provided some sort of standardization like since it's a really highly used library is that something that's kind of a standard or would you say standards don't exist in this place yet so lips Ark for the longest time was the primary and only library to use for ZK snark protocols however in the past two years we've seen the rise of more and more proof systems come out and that

in and of itself meant new libraries that were introduced I think one of the most exciting that's coming out today has been from zk Feldman this is from Sean Bo at Z cash and bellman is a rust implementation of ZK snark protocol namely it's Groth 16 so this is a protocol that was developed by yen Schroth from UCL and in 2016 and this is a a particular ZK snark that has been written in rust and has been developed and optimized for the rust environment and that's also what zeke ash is using currently to generate their MVC round for the set up so I guess the answer is there is no standardization at all right

it was for a while because it's sort of there was one and now there's many I mean maybe let's talk a bit about that like what about standardization in this space is there something like is that is that happening is that something it feels like there should be a standard way to write these circuits because then you could kind of transform them but more like transports them between different library implementations or something yeah I completely agree this was something that I had brought up last year that twenty and twenty seventeen at Def Con when some of the Z cash folks like I think I discussed Andrew Miller and also Jacob was there and I and a few other folks that are just a part of that community were discussing the fact that there's

these libraries popping up and from my point of view it seems like in a standardization was of order at some point you know if you if you think about the different libraries that are out there today they can't talk to each other if I generate a circuit in lip snark it doesn't necessarily run and operate and it's not compatible with bellman there are other implementations that are coming out today as well and none of them can implement an interface with each other so if I generate a proof you know in one library how do I verify it in another library and there just isn't a standard form and so that's where earlier this year in May of 2018 there was a ZK standards workshop that was set up out in Cambridge Massachusetts and this was basically

meant to kind of bring the different folks who work on CVA snarks together to not only look at it from a theory standpoint but also from a implementation standpoint and an application standpoint and these were three tracks that independently operated and their goals were to basically achieve the ideals on what does standardization look like how do you make sure you know terminology is is uniform across the board how do you make sure these libraries can interface with each other and how to make sure applications understand what to call and when to call and for what reasons and so there's um there's all sorts of work that's happening on this front now but as you can imagine there's there's not a lot of people that are in this space and so you can only move so quickly because

of that also I guess because it's changing so much like it you have to be careful not making things too standard because that could potentially stop other implementations from arising so I guess right now it's this funny space where it would be really helpful to have some standardization these it seems like you still want to keep it a little bit open absolutely so jumping from lib snark which is something you have worked on let's jump into something that we've been teasing this whole episode which is Disick you're your new work and distributing these zero knowledge proof systems so like you said there's a limit in what you can do on one machine you want to be able to break

it up on multiple machines what is Disick and like how does that work yeah so Disick is a distributed zero knowledge proof system that's implemented in Java and uses a cluster compute framework called Apache spark what Disick does is take an existing protocol in this case across 16 and as a monolithic process it breaks it apart and enables algorithms that can work in a distributed setting so what that allows you to say is you know instead of being bound to just one laptop here if I can spin up a cluster of ec2 instances or just a cluster of machines somewhere maybe I have a data center or maybe I have like a few a few computers at home

if I link them together I can run something that is much more scalable and also much more parallelizable these are two intrinsic properties to this architecture that I think are very fascinating so what this means is as I increase the amount of memory and compute resources I give the system we will scale nearly linearly in the throughput and the output of our snarks that means you can grow the problem size to something much larger just by you know doubling if you want to double the circuit size just double the amount of resources you give it additionally it's much more parallelizable so you have the performance speed ups and increases in speed for generating a proof and that's because as you throw more machines then

you have more cores you can actually process the ZK snark itself much faster than you could with a single machine so it turns out that as you you know if you fix a circuit size and you just double the amount of compute and memory resources your time will also have in a very linear fashion then that sounds like you're pretty groundbreaking piece of work actually because like once you like we have these constructs and we all kind of know that they're they're hard they're limiting like in what you can actually do like see cash is not that complicated of a proof to generate like you're proving that you've sent some like an integer

from person a to person B conceptually like in the real world it's not that complicated if we wanted to do something like prove a smart contract it would be so much larger and you know hundred times larger a thousand times larger it just would not be feasible at all on a computer but basically with this structure you could do that you could actually make something that is a hundred times larger Wow would this what this actually mean that you would do as your knowledge proof like on chain the whole thing so if you're talking about on chain the problem is if it's like how do you distribute things on chain like you still need this compute cluster this is an interesting question though

because like have you guys thought about like baking this into a decent like if they're in one could argue is a decentralized compute cluster it just computes useless things so have you thought about like putting a blockchain into this somehow to coordinate these machines yeah actually if you know my current work right now is around how do you use devious narcs in a decentralized setting and this is a very open question right now because we there's very little bodies of work that demonstrate how to do this properly and I think that that's certainly something that merits a time and energy and that's that's an effort that I'm currently working on then oh just on the note of like this this kind

of many fold increase in performance have you thought of or seen any applications already where this could be exploited where like this this thing was completely not possible before but now you can actually run it yeah so we actually implemented two applications for our paper and I guess to preface it I would say that if you look at lip snark today we can compute about 10 to 20 million gates in lip snark with physic we can now compute billions of logical gates and that's a hundred x factor increase in the size of a circuit that we can reason about so naturally you speaking it's well and so

and so in terms of this computation it naturally arises that we can just solve much larger problems all of a sudden and so we went through kind of the different applications and use cases that would be interesting and also practical for the time line of a research paper and we basically came up with two areas that we thought were cool to look at one was basically implementing a previous paper called photo proof and what this allows you to do is basically provably show the transformations on an image kind of like if I'm photoshopping of an image that's really a series of matrix operations where I'm translating this and transforming and rotating and scaling and those operations can easily map into a circuit world and into a snark in this

case and so that's one one use case but the other one is also just in the case of machine learning how do you have verifiable and integrable machine learning computations if you think about you know how the industry works today much of this is a very dynamic problem if you want to be an ml researcher on healthcare data you know Stanford Hospital may not be so inclined to share with you their patient records because of HIPAA and all these different compliant laws right but for a researcher in the medical field they may want to know like what percentage of you know patients who have a heart attack die within two years and that is a very serious problem and a very serious endeavor and there's very little ways to

do this effectively and efficiently today instead if you could have some type of privacy preserving model for computing this information and training it in a machine learning model it very clearly arises the use case to actually do this and you know one of the problems with this in the past was that there's so much data you can't even compute it on in live snark right but now you're saying I'm storing this data in use massive databases and now I have a compute cluster framework that I can use to run education are gone why don't I just run this problem in this database and compute the the prove out from it and so these are two areas that we looked at that we thought were quite interesting and that's that those are the two things that we actually evaluated and wrote about in the paper

so essentially like instead of the hospital giving all their data to the researcher the researcher can like query like how many patients had or like you would have to it would have to be a boolean query I suppose so it's like do patients who have a heart attack die within two years and they could pose that question to the hospital they could compute the zero knowledge proof and give the answer back without ever sharing their data and yet it be known to be accurate yeah yeah exactly like that's very cool you would input the data with like their ID and like you know their age and when they had a heart attack and maybe when they passed or if

they're still living and you just run this type of a circuit construction I'd just say here's the circuit guys you know can you run it on your data and the hospital be like okay let's run it and at the end all you get is an answer yes or no and you don't leak anything about your patients data but you can believe they really computed it and so that's a very fascinating approach and a very valuable one so going back a little bit to Disick you mentioned it's built on Apache spark I'm interested like on a conceptual level is it basically that you're taking this huge circuit and breaking it up into smaller pieces of circuit and each of those being computed on one machine or is it something much more complicated that's a really great

question so naturally I think what what comes to mind is to say let's take this operations and just you know move it on to a database and like move it on to like a cluster compute framework and just you know run it and see what happens we actually did that and it was very very slow the reason for this is the way that we represent these circuits is in the form of matrices as polynomials so your matrix has a bunch of vectors in them and each vector represents a polynomial because we're going to billion sighs circuits we're talking about billion degree polynomials these are massive things where even just doing like a multiplication of these two polynomials will result in like first

off you're storing these polynomials in terabit sized arrays but then you're trying to multiply these things and there's no efficient ways as far as you know just naively translating things over to do this and so that's where in our paper we implemented some distributed arithmetic schemes so for example FFT so fast Fourier transforms are a common operation and these we implemented a distributed version of that also multi scalar multiplication that it's basically like this you multiply a scalar in a base and you have a vector of these scalars and a vector of these bases and you're just trying to element-wise multiply them we also implement a distributed scheme for that and also for lagrangians we implemented a distributed scheme for that so we

really started from the building blocks on what a snark needs for computing its proof and then worked our way up the ladder to the point where we actually tie those pieces together into a a protocol for computing the za snark itself and that's where we then have these tricks that we use and these optimizations that we use in the distributed scheme to write a distributor in that's actually efficient and the paper basically goes through how those things work and the library implements that example well sounds like a very large body overall it ended up being a very educational task but also I you know banging my head on the computer

many many times it turns out in a compute frameworks in class to compute frameworks basically if you don't spread your data evenly in the in the cluster then you get what are called stragglers and those are guys who just lag behind everybody else and the way that a framework works is that everyone has to kind of be in synchronicity with each other so when everybody finishes this particular task then you can move on to the next step and because some guys are just taking so much longer than others then the everyone else is waiting on them and so you'll be waiting like hours or days depending you know on how inefficient that that protocol becomes and that's where we have to go through and say on the theory level where can we massage this problem into

something that's much more uniform and can be spread out across these machines in an even fashion so trying to round out the episode here where we've hit time for sure it's so much instant content in here but maybe we could just talk a little bit about like what's bringing it back to soar a blockchain what block chains and protocols do you see using zero knowledge proof DK snark specifically so there's a few different projects that are really looking at zero knowledge proof and specifically on things xzk snarks and ZK Starks I would say that from a very enterprise standpoint and from a company standpoint there have been a lot of academics that have gone through and helped the the

formation of many of these endeavors and somehow it for example are in Israel there is like a cadet QED - it and this is a company that is specifically looking at DK snarks and their applicability in the like enterprise landscape as far as I understand and there's also been a rise of a host of blockchain protocols that take advantage of za snarks and what they do for example a coda protocol from owen labs is one this is with you know isaac macular and and folks there who basically have developed an approach to scale blockchain storage using zk snarks so they have this notion of uh succinct blockchain where you have recursive

proofs and you know that's a whole nother rabbit hole to go down and it's a very interesting one yeah additionally you have a you have projects like Oracle Oh RI geo and what they're doing is basically providing a form of private transactions on their own blockchain they they're integrating and actually developing things like a Z case in our circuit compiler so you can take things like like rust or whatnot that compile down to LLVM and basically model that as a circuit representation optimize on that very interesting techniques that are being investigated and developed currently and also you know on fronts like Starks there's also

like a lissandra's company Starck where that's a it's a it's a new company that is looking at implementing you know a lipstick library and also providing this as a potential service for the collection community I think that right now there's just an amalgam of different initiatives that are happening formal and informal in the ecosystem and it's very clear that that's why you know there are these conversations on standardization on how do we scale these types of computations to these large sizes and where do we go next like do we look at hardware or things like that and I think it's an open question for everybody and that's that's why everyone's so excited about it maybe that's leaves us to the last question which is about just the future like I mean you mentioned a couple of really

interesting projects but what's the future for you and this topic like what are you looking at going forward my early work was very much being involved with lip snark and getting this into a very usable form for the community and and the development community at large you know I've spent the past two years looking at how do we distribute Z hasten Oregon how do we make that next iteration on it I found that to be extremely fascinating and also quite insightful this has really motivated me to look at it in the very decentralized landscape and say where are ZK snarks useful in the decentralized realm and I think that this gives rise to all sorts of new notions like that notion of like private smart contract that we briefly touched on earlier and also looking at

the use cases on like maybe generalizing Z cash into something that's more modular and more broad than just you know we make a payment and these are areas that I think would be very fruitful for other for the blockchain space and you know that's that's basically where it where my head is that currently where can someone find out a little bit about disick know hey how do I say Disick yeah help me help me a help me with the pronunciation and B help me find it sure so the way we came up with the name Disick was actually a play on words in the zero knowledge proof world there's this notion of a non-interactive zero knowledge proof music it can be pronounced music or misc

different academics pronounce it different ways and we basically modified it to call a distributed zero knowledge proof a a disk or a disk you know from my conventions because of working with Alessandro and academics in that area we all pronounced it music and so then I call this visit but it's equally valid to say misc and disk then it sounds pretty cool that's all I gotta say where where where where do you find more info on this disick yeah so you can learn more and also play with this library and read about the paper at a few different things so first is a digit org di ZK org this will then direct you to the github library that we have released it's open source and with an

MIT license additionally if you search for ePrint disick you will find the paper there the actual link is ePrint dot I ACR org slash 2018 slash six nine one and this will then link you to the paper that we published which is the paper on physic I think we'll also put this in the show notes sure we'll put all the links we can find in the show notes in fact cool Howard thank you so much for taking us on this journey with you this is amazing it's my pleasure and again thank you for having me this was fun it's totally fun and I really I I would love to have you come back you know in maybe three months when some sometime soon ish continue as we do

this your knowledge series seriously I think we I mean I've learned so much in this episode I'm super super excited to share it with everybody yeah I think that would be really fun like I'm happy to do this again and we can then do a follow on and see like in the interim all the people that come on and like you know what they bring up and like what are open questions and like you know this face move so yeah so I mean I despite as slow as it is it actually moves quite quickly in many regards like just because you know once you get this out into industry and have them run with it then all these different ideas come out and like I couldn't have come up with any of these you know like two three years ago so it's it's really nice yeah

I think a fall one would be really fun I think it's a super interesting topic it's certainly one of my interests like my favorite things in the whole blockchain industry and like in in the work and stuff I deal with normally like this is this is a really cool stuff so I would say thank you and to our listeners thanks for listening thanks for listening [Music]