DAPPCON 2019: How Zero-Knowledge Proofs can Help your Dapp - Alex Glochowski (Matter Labs)

Transcript

so we're gonna talk about what zero knowledge proof are what you can use them for and what are the limitations and just to give you some sense on how like what's what what was different to normal programming in blockchains okay oh it works nice yeah so what they are what are the use cases what are the limitations so let's start with the basics zero knowledge proof is probably a bad term the Shradha have been called something like proofs of honest computation because what we really do is we prove the this is a family of cryptographic protocols which allows you

to convince a counterparty they do you have to perform some computation correctly on partially private data a partially public data and then some predicates some publicly known function which we both know to understand this better let's take an example you can prove to somebody that you have a pre-image to certain hash now the protocols will allow you to do this the hash function like should sha-256 will be our predicate the preimage will be your secret data and the hash will be the public data so you present somebody the public data they pay the hash and

then you either prove that you have no the preimage or you prove that you can revert engineer the hash function which is probably which is very unlikely so like most likely that you actually know they they preimage and the computation which you prove can be fairly complex it has some peculiarities compared to normal computation it's not a phenomenon architecture but you can do anything as complex as proving that you perform the entire blockchain state-transition correctly so if you look at this function we take the cryptographic commitment of the old blockchain state represented let's say by a Merkel tree

so you take the old Merkel tree root you in this you make it public you make a new regulatory route public and you display the details of the transactions maybe and then the path to this miracle like to the miracle proof updates and the signatures which you collected from users you keep private but you can still prove that you performed the transition from previous state to the new state by applying all the transactions correctly that you verify the signature for each transaction that you subtract the amount which are sending from the from account added to the to account updated announces correctly and maybe perform

some other contractual logic which is in this state so there are different protocols which you can use for journalist proofs you might be familiar with them this is not a complete list but I want to argue that in blockchains we're only or mostly interested in zero knowledge rules which has extent such as Starks and snarks where S stands for succinctness what does it mean it means that the very fire which is an algorithm which checks the proof and makes sure that it's actually it's it's it's correct and you made the computations correctly it's strictly less in computational complexity than the amount

of steps of your computation and same applies to the communicational complexity in other terms to the proof size the proof size also must be much shorter than the the amount of witness for the original proof generation and why is that important we replicate all the theorem transactions to more like to tens of thousands of machines worldwide and this is really important to ensure decentralization now if you take computation and make some piece of data you process it somehow you send it to everybody else they have to do the same exactly the same operations everywhere if you increase the amount of

computational work you do everybody has to increase and eventually you will reach the limits of the customary hardware such as laptops and cell phones which people use and only big players will be able to verify blockchains and this way we're going to lose the decentralization property so this is not cool what's your knowledge proofs allow you to do is to have a lot more computations which can scale but the verifiers have to do still same small amount of work so the the processing of the blockchain the etherium transactions the etherium nodes have to do very little work but then you can increase it significantly of course it has a cost so you actually have to

perform a lot more computations to generate this process more than you would do to do to make the to just compute the function itself so to give you a sense of what it will cost you if we have a very simple let's say layer 2 solution where you just send make transfers and send some assets single transaction the proof of a single transaction will cost you about four seconds on a hardware comparable to MacBook Pro and the breakdown will be something like this so we measure the complexity of zero knowledge proof programs we call them circuits and the complexity is measured in what we call constraints which is the technical term

but the linear really correspond to the complexity so you have most of the constraints go for hashes which we need to to check the miracle proof inclusions some power partial sum some part goes for like complex hash functions not all hash functions are equally computable under zero knowledge proof conditions and some small very small amount of computational power goes for actual operations and updating the balances okay so yeah so you have just different trade-offs you have to take them into account when you construct your programs but essentially you can prove arbitrary computations and this is really cool and

this technology is getting more mature we'll talk about a bit later so yeah we have 16 zero knowledge proof families we have two which are mostly mostly no we actually only have two like everything else is not release extent the first family is called snarks succeed non-interactive arguments of knowledge they are fully six in so the verification actually only takes off one no matter how large your computation verification will always be short and fast and cheap and the proof size is going to be just 300 bytes which is amazing that you can compress the entire blockchain which is 300 bytes and use this as a proof Starks have poly

logarithmic complexity of verification and proof sizes so the comparable stark proof will be in order of hundred kilobytes which if you use it for block chains it will consume almost entirely the gas limit of a block which is not not so cool but they have an upside they are post quantum resistant which may or may not be important because if we have quantum computers we're screwed anyway but they don't require trust is set up which starts narcs require because they are based on the elliptic curve pairings and the tracer setup is a nuisance like we need to pretty needed conduct the ceremony with a lot of participants and all of them promised to delete certain data which they used as an entropy as

input for this setup procedure and if at least one of them is honest the entire procedure is okay if all of them collude to Gera we have a problem because they can fake proofs so which if we have to do just once it's gonna be okay the older version of snarks were requiring you to come like build the trust setup for every application which is probably very difficult logistically politically so we have a newer we have mmm sorry it's not working again nice we have research going on in this direction with

a lot of brainpower involved which gave us sonic and proof systems which will probably appear soon which is similar to sonic which require trust to be done only once which can be reused for any application so us developers will not have to bother about it you can just take the one which was produced by a large body of highly prominent participants maybe aetherium foundation maybe other block chains maybe some other organizations and you can reuse it for your debts without bothering about security office and if you don't trust the this consortium which produced it the the trust setup you can always add your entropy on top and then you can be

a hundred percent sure that there was not compromised so this is the updatable property so we are pretty confident that these the Sonics are currently less efficient and grow 16 than the previous generation of snarks but work is being done to make them more efficient and very soon it will be possible to use them for block chains for very broad variety of applications so just keep an eye on it and let's talk about the exact use cases so we have these two properties zero knowledge which allows you to hide part at least part of the inputs of your computation and succinctness and they can be translated into privacy and scaling corresponding

so let's talk about privacy the most obvious use case for privacy is anonymous and confidential payments or transactions or mixers that you can make you can transact with other people economically without disclosing this to the entire world what we have currently on blockchain and anonymous means that you hide the recipients and Sanders confidential is slightly different property you just hide the amounts you can have both properties or just one of them maybe it's going to be difficult from regulation standpoint to to defend anonymity maybe confidentiality is easier or maybe we need both it's gonna

be up to you to decide what you what you want to use for your data then we can just use your knowledge proofs for partial data disclosure which opens a row of very interesting possibilities you can build you can for example disclose your bank account information without you you can make statements about your your assets without disclosing them and you can say that I have enough solvency but I'm not gonna tell you how much exactly is in my account then you can use it to construct kyc checks where you can prove to the authorities that your users have done kyc but you're not gonna tell them who

these users are you just make sure that they are on the whitelist or that they are not on the blacklist which is really interesting and finally you can do things like voting or like anything else where you in voting for example you would say that all users have voted only once but you're not going to disclose what the inputs of the vote what do the words actually work at you can make it private finally you can we are going towards being able to construct smart contracts which are very generic which operate on partially private and partially public data and this will give you ultimate power to create any applications which you want and I just want to remind you

that current feminists of journal which proves allow you basically arbitrary computation which is going to be bounded in size but you can do anything any program and it's going to be very easy to do we're getting better tooling better languages but the frameworks and profiling tools and so on now scaling is super important because we all remember what happens when block chains run out of capacity if we if you want your debt to be successful then you probably expect a lot of users at some point of time in the future and you want to be prepared for this so you want to plan ahead of how you're gonna handle the

scaling situation and when it occurs and we have many different approaches on layer one on layer two most of them are making certain trade-offs in the blockchain trilemma right so they either sacrifice the decentralization and make centralized or consortium like reduce centralization of reduced decentralization of the services or they make certain trade offs on the security or they make users to do really hard work and it's going to be not very usable zero knowledge proof allow us to circumvent a lot of these limitations

and have systems that behave almost like layer one block chains so they maintain the security properties of layer ones if you put your money there they're going to be as safe as though they're on layer one without you do having to do anything now they keep your systems decentralized you can have multiple operators and keep it such that censorship resistance is ensured and yeah scalability is going to be achieved through the 16th property of your knowledge proofs on the computational side at least on the data side we can reduce the data which needs to be propagated from the network a lot

because we can emit parts of the data which are discarded after the transactions are processed for example signatures of your transactions you're not putting them on blockchain you just need to check them once and then you throw them away so they if use your knowledge proofs we don't have to propagate them at all and yeah there are a growing number of projects while using your knowledge proofs for the applications if you want to learn more about them I highly recommend this awesome sure knowledge proof list where you will find introduction you will find the list of tools frameworks

presentations like it's been constantly updated if you have some ideas if you're working on your project which uses your knowledge pros please do a pull request you can update it and let everybody learn about your project and this is it thank you very much happy to answer questions [Applause] hi there great talk thank you on one of your slides you gave some estimates on what a simple token transfer would look like and it appears that most of the constraints come from the merkel ization

does this mean that you could actually put this would be the same estimate for computation for multiple transfers as well for what sorry does this mean that you could also do multiple transfers in this same proof since a majority of the constraints come from the Merkel tree computation so to get the benefits of scaling with your knowledge proofs you need to batch many transactions together because at least if you if you use it for layer two but also for layer one you want a big block of many transactions you compute the proof of the entire block and then you propagate to everybody just this one short proof for

all of them so what you see here is a cost of a single one of many transactions which will be included in this block so if you have thousand transactions you have to you will have to pay this cost thousand times so you will need four thousand seconds of computational time on a similar machine which of course you're not gonna use macbook for this what you're gonna do is you have you're gonna have a big cluster in some cloud which will do this work all in parallel so your proofs are constructed quickly but you will actually have to spend all like all this work for each of the transactions included in this book can you use zero knowledge proof to

prove a certain computation for any Turing complete computation for a Turing complete computation like any computation any arbitrary computation can I use zero knowledge proof to prove that I did that certain computation oh yes you can use your knowledge proofs to prove that you have done arbitrary computation so the you will have to deal with certain limitations so I'm gonna I can give you a sense of what the limitations are or maybe you can view you want to formulate the question smart like you can prove without doing that computation right prover will have to do the computation you have to actually do more work than just the computation

itself order of making is more work like the prover needs to do the computation to prove it of course he need to do the yes you need the computation and you need all the inputs and all the intermediate values throughout the computation throughout the execution trace of your computation you cannot construct proofs for things which you would not be able to compute yourself hey there thanks it was a great talk really we note with the zk basically there are two major implementation

options we have we can store data on China or or off trade and trade offs are obvious and obviously we can do a lot more if the data is obtained but then that introduces the data availability problem I was just wondering here you touch upon that and maybe know do you have any favorite approach and just absolutely so will thanks if we put the data on chain and we use it for scaling then goodbye but what we have to define what does it mean to put data on chain or off chain so we can use the chain to propagate the data and then users can store it separately what's what's really important is that we make the data

available so we solve the data availability on chain we don't need to use the theorem storage we can use just a theorem called data to make it available to everybody who uses the application now it depends on the kind of transactions which you execute for transfers single transfer only requires twelve or fourteen bytes of data to be propagated if we exclude the signatures now this is very little in terms of gasp it's something like 700 gasp at the current price from ýstanbul there is an EAP 2028 which reduces the

guest cost for Kol data by a factor of four or five so it will be even less and it's actually very cheap but the benefits which you get from putting the data on chain are enormous you actually get the security properties of ethereal if you have to handle data availability off chain then you have to introduce either some complex games or data notaries which have to sign off the data and so on and so on and this there are just too many security assumptions which users have to take by putting them on chain you just completely eliminate the problem and this is this is awesome so I would argue that the current costs for in case of transfers and similar

operations are speaking in favor of Witten data on chain if you have something which is very data-intensive then it's a different story but we have to look at the exact use case but what's important is your knowledge proofs just give you the ability to use the own chain data availability because they compress the data you just omit so many of data points which are redundant which are not necessary to store that it's actually possible if we wanted to do data availability for plasma on chain this would not be possible because you need to show all the signatures so your data cost is 10 times more no not that

not 10 times but maybe like maybe 7 or 8 times it's still a lot was a great talk and one question can you elaborate elaborate a little bit on the smart contracts on private data or you said it's in research it is in research for smart contracts on private data you need some kind of recursive composition of proofs if you want to use them so of course you can you can just have smart contracts where users produce

the proofs that they perform certain operations and they publish them on chain but this is going to be pretty expensive the cost of a single verification of such a smart contract is gonna be expensive maybe it's okay for some use cases if we want to be available in in masses and be scalable then we probably want something like user generated the proof of their own computation and then we take all of his proofs and vege verify them together and produce the proof that we verified all of this proofs and this is something what we're in matter Labs are looking at this requires some changes in the theorem if you want to use it on theorem namely we need support for different

elliptic curves which will allow this recursive composition currently a theorem only supports the m256 which doesn't have embedding nice embedding curves we can use but BLS curves and MN tickers they do have this and this is why we sponsor the AP 1962 which also has been included into ýstanbul but the second part of Istanbul which is going to be released around January and then we can use arbitrary curve elliptic curve operations on different curves and then it will become possible but if this is a heavy research topic which will it will take some time to properly to

construct the languages and frameworks which allow you to easily manipulate this data so some challenges around the logistics of data have to be solved and so on but it's definitely coming in few years from now it's definitely going to be here here so I just come in maybe you have answer the question in the slides but I ask it anyway do you think like because right now I am not sure if he's totally

practical to use ckp for a lot of applications so you think like is there is it's better to use it on chill or you you use it in a sidechain in the current stage if I want to build applications to really use it for a lot of transactions if you want to use it for a lot of transactions you need a sidechain because otherwise you would have to change the core of where one protocol which is not happening anytime soon but we are working on a layer 2 sidechain solution where you can move funds from the main chain to the side chain and then quickly transact in high volumes for very low predictable cost ah so you mean that's you already have a

sub channel ready for us to use it we have a sidechain you can check our website and there is a link demo you can see the demo actually on the main Metron thanks and thank you everybody