How can we use Zero-Knowledge Proofs in Ethereum?

Transcript

foreign I'm going to make a start this Workshop is going to be about how we can use zero knowledge proofs Within ethereum so I'm going to sort of follow this rough overview first I'm going to just set the scene and then I'm going to look into a case study I'm going to talk about pulling in your commitments a bit more case studies and then talk more specifically about zero knowledge specification I will ask questions as we go

and also if any of you have questions then please ask questions as we go I'm hoping to make it feel more like a workshop and less like a presentation so hopefully that will help with that so first questions which I'm going to want you to answer via a show of hands question one do you roughly know what a zero knowledge proof is okay so some of you do some if you don't how many researchers and Engineers do we have who are actively working on zero knowledge in the room a couple and how many of you have strong opinions about whether we should use zero knowledge proofs in the consensus layer of ethereum

one so to start off with what are zero knowledge proofs I'm going to own to something I actually hate telling people what zero knowledge proofs are but so many of you do already know what zero knowledge proofs are so can I quickly ask you to turn to the person next to them and give a quick quick explanation where you can use the where's Waldo example if you like laughs questions

[Music] 10 second warning okay I'm going to assume that that was the best explanation that's ever been given in terms of where Sarah knowledge proofs are currently being used in ethereum I would say that on the application layer they are being used almost everywhere you look and I gave a number of examples on the slides we've got the

decentralized identity private token transfer reducing bribery on on-chain game engines zero knowledge Bridges private defy scalability solution when it comes to the core layer however I would say that right now maybe arguably ecdsa second signatures are like a type of zero knowledge proof that's about it um and I would say that there are some fairly good reasons for this um by the core layer by the way I mean the layer which is deciding which transactions do and do not get included on the ethereum blockchain as opposed to what's going on inside a smart contract um the core layer because this is sort

of our key thing which is defining whether we're live whether the system is working at all people are relatively conservative there's some reasons for this probably the biggest one is that we can't really depreciate old code once you have code it has to be maintained forever um particularly with zero knowledge we've got a bit of a problem that bugs might require expert knowledge to fix so we can't just go up to some random developer and be there like we have a problem please fix like we would need a specialist on that case very very quickly um and a third reason is that there is a strong preference for Simplicity at the core layer and for all of the really

good things you can say about zero knowledge proofs they're not very simple however they are also they also really really useful and there are a number of situations where we are considering using zero knowledge proofs at the core layer uh absolutely including Roll-Ups uh private legal elections proof of validator inside the randomness Beacon there's um there's a bunch of different places one of these reasons is sort of I'm on the cryptography research team and when they come up to me and they're like do you have a solution I only have one solution it's use zero knowledge and if if that doesn't work then I'm kind of out of ideas so when they come back to me and they say but this is really complicated I've got I've got a real problem

so really the core question of this Workshop is going to be what can we do to mitigate the risks of implementing zero knowledge proofs and cryptography generally as a cryptographer I have some philosophy about this which is sort of rooted from well Academia and some of this philosophy is going to be good for philosophy which is really going to help with making sure that we get things right and some of it is maybe going to be less practical philosophy where inputs from developers and from people from other spaces might be very helpful but one thing which I'd say that cryptographers are very good at is answering the question what is my scheme

even trying to do it sounds like a simple question but actually this is something where you have to be very careful about the details because if you're even just slightly off it can affect things in ways that you wouldn't expect kind of related to this is what security properties do I want to achieve do I want to to be like private do I care about liveness do I care about authenticity do I want it to be composable so that would mean that I can use it as like a plug and play thing in other protocols do I care about adaptive security concurrent security lots of different questions along these lines and I'd say this is something where developers sometimes have a slightly better insight as to which properties

are genuinely important in their scheme and this is for good reason right they're very familiar with their scheme they know what they need they know what they want whereas if you're just sort of coming from the um from a different background being there like I think you want this sometimes you'll get it wrong uh the other question that they tend to ask is what is my theoretical model of computation and this is saying that if I'm going to abstract things away and sort of say here's how I'm going to analyze whether I think it's secure or not what do I consider to be a valid model of computation I'm not going to spend too much time on that the next step in the process is to

specify the scheme and this is an area where I would say cryptographers are in general a bit less precise than the general technical population don't get me wrong some specifications are better than others there are some very good quality ear ones out there but there are also less good quality ones out there typos are not that uncommon sometimes there's an implementation but it will typically be a proof of concept implementation done purely to give an idea of speed um also sometimes they will use black box subpracticals that are not fully specified this again is for quite good reason because it gives a developer some freedom in how they want to choose to instantiate it and it just sort of modularizes out some of the complexity when you're trying to analyze security

probably the biggest thing that most cryptographers would agree with is that security reductions are really important so the idea here is that you want to demonstrate that if my scheme doesn't satisfy my security requirements whatever those happen to be then I can break some hardness assumption I personally think of these as very high quality unit tests not to say that they're going to like catch all the problems or that if you have a security reduction everything is fine but more to say that if you don't have it then you probably haven't done your due diligence um some security reductions are better than others and one thing that I would note is that peer review is not the same as a thoroughly audited security

reduction there are many many layers between here's my research paper and what I would consider to be something ready for implementation so now a few couple of questions to you um can you think of any examples where there are one or more ethereum developers that have set out their design goals really really clearly and can we learn from them or alternatively is there a scheme specification written by a cryptographer that you wish other cryptographers would learn from and why feel free to answer either question can I have hands for anyone that wants to answer okay other questions too hard or too

easy we don't know so smart ah okay so I'm sort of saying do you know any of examples where people have done them well and the answer is no okay I'll take from that I'll take from that okay let me move on to a case study uh which is a case study that I have sort of personally been working on a bit which is a case of Shuffle arguments um specifically for leader elections so this is in my mind quite a fun application which is related to the core consensus layer of ethereum the aim here is to choose a validator to

update a future block the current way that we're doing this is that Randall is going to Output some Randomness which is just going to randomly determine the validator to run that update the problem with this approach is that the winning validator is like public everybody knows who they are and this makes them very susceptible both to bribery attacks and to DDOS attacks I've heard people argue that the bribery attacks are maybe more of concern than the DDOS for reasons to do with people being able to keep their their address private if they want to um but either way this is something where we kind of know how to solve it and the way that we can solve it is we

can run what's called a single secret leader election here every validator has a Tracker that they alone can identify and The Trackers which are kind of encrypted in a way are progressively shuffled by different parties um at the end of the shuffling process it will be secure as in like the winner of this Shuffle is going to be unknown provided a fraction of the parties to include where that fraction is something that you can is determined by the system the current proposal for doing this is called the Whisk proposal and I would say that there are three layers to this

proposal we have the consensus and permutation logic we have a random Beacon and we have a zero knowledge proof when it comes to the permutation logic there is a very nice paper by my colleague Mark simkin and his co-authors which is giving a formal argument as to why we would expect it to be the case that if enough people have shuffled nobody's going to know who the winning validator is possibly the thing that's more relevant to this talk though is the zero knowledge proof and there it says a special purpose there in our argument for uh Shuffle arguments which has some

very nice properties uh the probably the biggest one is it's quite a lot simpler and partic in particular you don't have to write out the constraints of what you're trying to prove because it's special purpose it's only proving this one thing so if any of you have ever sort of worked in circum or any things like that in order to say this is this is what I'm trying to do with this particular scheme you don't have to do that um the protocol which we're suggesting to use is a slight adaptation of a popular protocol by Bayern Gratz and it only uses group operations and hashes however even with this much simpler

scheme I'm going to say that there was still a lot of concern about the complexity being suggested I personally try to tackle some of the these concerns about the complexity and really with the only only trick that I knew how which is just more documentation goals more documentation and I had some specific documentation goals probably the biggest one is as much modularity as possible I wanted it to not only be the case that you can just plug in this zero knowledge proof and it doesn't affect the other parts of the system but I also wanted that the algorithms used within the zero knowledge proof itself were very much sort of plug and play and I don't mean

you see by this which cryptographers would mean something specific by I literally just mean that the inputs and the outputs are very clearly defined and if it's calling a subprotocol it's clear how it interacts with that subprotocol uh cryptography reductions are auditable I won't go as far as pretty but they could at least be audited by somebody who knows what they're doing and possibly one of the biggest ones optimizations are kept very very simple and are explained so in particular if there was an optimization which made things just a little bit better but came at the cost of making the protocol more complex then we didn't

include it okay so some more questions this didn't go that well last time but hopefully these should be a bit easier um I'm going to actually start with question two security reductions so you see my picture there it's not very pretty I would say that they're never pretty or easy to understand like if you have some documentation and you're there saying here's my security proof most people who are reading the documentation are going to look at that and go I don't want to read that but at the same time I do think they're very important to include for reasons of you know making sure that you've done your done your tests correctly so would you personally prefer that they

appear with the protocol or in separate documentation I would say Indiana the battery don't read usually in the appendix okay yeah I I think there's some good reasons for including it in an appendix there are some downsides being that when it's in an appendix people can sort of um what's the word assume that it's not going to be read and then things get even worse um but there are the upsides that developers then don't have to read that

part uh question one I think I'm going to do by show of hands does anyone think that it's possible to overdo modularity uh anyone willing to say why sometimes at um at each interface of modules you might be sort of compromising or making some oh yeah like compromises or or there's some extra conversions to to meet an interface so the more modular it is there's perhaps

more interfaces so there's just perhaps just more of that conversion rather than the core of what you're trying to do so like you'll be trying to introduce modularity and in doing so you'll make the scheme worse is that what you're saying in some places yeah yeah potentially like those sort of interface points between modules might add complexity it also makes it very hard to audit because there are so many modules and you have to like bounce back and forth so yeah so is that a sort of concern about it's harder to get a high level view of what's going on that makes sense um and the third question again I'm going to start with just a show of hands

um has anyone sort of come across a situation where security flaws have been introduced due to bad optimizations how many of you are Auditors by chance um again if you want to give some examples of that keep your hand up otherwise I'll move on uh easy classic one having a eraser modulus being picked back multiplying common command Prime just Computing a gcd you can break the factorization for instance there are so many of them where there's a classical one for the

optimizer for solidity uh they cache the check hash if you were using in line assembly and it was an optimization but they did a breaking up like it was a pretty obscure uh Edge case but you could be bricked by having a cached cache there so it's one of the examples okay so don't don't cash your hashes thank you so after the step of writing down sort of the what am I even trying to do what's the high level look of my protocol what's going on I would then say the next step into getting stuff productionizable is to have more

practical specifications um and proof of concept client implementations are sort of a big Next Step these are typically written by developers in the particular case of the single secret leader election with wisc we have three implementations at the moment one in Rust one in Python and one in go I've got the the links in the QRS codes to those there and some very good work went into all three of these I I don't know if any of anyone responsible for for writing these is in the room if so if so maybe make yourself name to me cool so when it came to these specifications

being written I would say that there were things that I was able to help with and I sort of interactive back and forth process and things that maybe I wasn't the correct person to help with and maybe there would be other people within the design space who would be better people to ask uh questions that I could help with uh absolutely includes is this a typo to which the answer is always yes if you've gone to enough effort to read the documentation to get to the point where they're like this doesn't look right this is a typo it probably is um if I optimize this passes it's still secure usually it's not usually there's a reason that optimization isn't included but not always can we not have the tracker uh this is like something that's quite

um specific to the ethereum consensus protocol I'm going to try and explain it from high level I apologize if it's not that simple to understand but basically this thing at your tracking which says have I won the election or not that is the one thing which is really interacting with the other consensus spec um parts of the parts of the algorithm like that's the only thing where we're there like you have to change the base consensus specs to allow for this like long-term tracker so people didn't really want that they would prefer to have it so that you can just use the your BLS public key and use that as your tracker

I kind of don't like this approach there's a couple of reasons but probably the biggest one is your BLS public key is like your validator key so this is the thing which all of your validator funds are tied to and I kind of like don't like the idea of that particular very high value public key being used Here There and Everywhere rather than just being tied to this one thing that it's trying to trying to keep secure um in terms of questions I was less able to help with but there were other very intelligent people that could help how should we Implement uh future Minnesota hash functions this is a very big question and which prng should I run so this is

again very much sort of saying there's all these different prngs out there which one is good for this use case again this is a getting to the to the level where I might not be the right person to ask okay so some more questions um the first question is a bit vague what do you believe is the ideal process to translator theoretical specification into a practical specification because this is a bit open-ended and vague I'm going to give people a brief second to sort of put their hand up if they want to answer but I won't Linger on that one got uh you could write very extensive tests

first so that you know any uh uh practical implementation could be tested against the theoretical specification that's quite a good idea I don't think that's currently done a lot practical specifications usually have tests but theoretical ones are usually quite quite short of them come on um oh sorry over there yes so what about formal specifications that you can reason about yes they're great [Laughter] hard to do take a lot of investment but when you talk about practical specification if it's in python or rest

or whatever it's an implementation rather than a specification um I would say it's more than that like there will be an implementation part but you would also have supporting documentation which would say all of the apis for example it would say the expected inputs and the expected outputs it would say what the scheme is trying to do this sort of thing you wouldn't you wouldn't just have the the code ideally um okay uh next question how can we educate the ethereum community about which projects have very high quality documentation and and are ready to use and which don't

what are you trying to achieve um so where we would be trying to say if you want to use this protocol then we have some faith that there has been a level of due diligence with the documentation or maybe we don't and it's just a research paper or something that's hot off the press I would say like getting an insight as to which projects are in which status is something which is quite hard so is there anything we can do to sort of help people help people identify gone yeah just sort of following on from the way I guess it's yeah who's coming to it and where so if it is on say

ethereum.org website somewhere um perhaps just an ordering or a simple like traffic like system to say it's like a band of quality in a sense like just make some um some projections for the user just to simplify it for them to say under the hood these things are well documented and others are not and just have it in that order so if someone's coming to use it they can very intuitively see where things are would you sort of be open to extending that to just labels where you can sort of say this is where the documentation is currently at and then it gets upgraded over time because I think that might be if nothing else less insulting yeah yeah definitely like that just to see where it is yeah yep sounds good um and the last question how do we

incentivize the production of high quality documentation because this takes time and effort and it's often not that rewarding so is there something we can do in order to sort of give people if nothing else some sense of status for having gone through this process quickly ad um yeah maybe in that place where people come to to see that they might just put like a like or a thumbs up and say hey I'm interested in this one and if it's lower in the list in terms of degree of documentation or quality of documentation then that might be an incentive as well or even bounties if you want to go further but yeah I'm gonna move on um polynomial commitment schemes uh I'm gonna guess that not everyone is

going to know whilst a polynomial commitment scheme is but again show of hands who does okay a good number about half I'd say um I would say as a general rule of thumb as to like how it's used why it's used it's kind of a data compression technique so it's typically used when we want to avoid sending sending very large amounts of data and we just want to sort of send a small small token which says the data exists I promise from a technical standpoint there are kind of like two phases there's a commit phase where you basically generate that sort of small token that says the data exists and there's also an evaluations phase which sort of says

this function outputs this value which can be computed by the person who knows the data knows a function and a decider is just going to take that and say do I believe you or do I not so that would be the evaluation phase um there are lots of different polynomial commitment schemes in that we are aware of and they have all of them have very different um trade-offs um so fries which are the ones that are used for example in stocks are typically a bit bigger but they are based on error correcting codes which have this very nice property for long-term security being that the only thing that you

really are depending on is Hash functions and if your hash function breaks you can always just replace it with a better hash function um another big and popular one is kcg these rely on pairings they are the smallest polynomial commitment scheme that we're aware of we can't make it get smaller than that can't really get a faster verifier than that either but they do come with the downside that you have to go through a trusted setup process which is like an initial multi-party computation which can be a can be it can be a bit of work bulletproofs is another big one these are going to have quite small

commitments but the verifier is quite slow as in the decider which can be can be an issue in in some places um two other ones which I'm going to briefly mention are lattices and darks the reason I'm only briefly mentioning these is because they're possibly a bit less explored and a bit less ready for implementation than the other three at this current moment in time this could change in terms of where we're thinking of using polynomial commitment schemes in ethereum zero knowledge proofs are something which sort of we're both hoping for at the core layer and the application layer and our a sort of big use case of them but there are actually quite a lot of other use

cases um certainly at the application layer we've got lots of things to do with secret sharing consensus algorithms distributed key Generations at the core layer though we have three situations where I know they're being suggested a Decay Roll-Ups that's related to serial knowledge proof so I'm not going to go into that one um we also have vehicle trees and data availability so vehicle trees are a suggested upgrade which are really being suggested as a scalability solution So currently we're using fan into Merkle trees um the idea here is that you want to replace them with finding n vectors if

you were to just do this replacement outright it would make the amount of data you're saying in order to say look this transaction exists on the blockchain therefore I can do this it would make it quite a lot slower because at each layer you'd be sending more data but if instead you have those vectors being committed to Via a vector commitment which is kind of a special case of polynomial commitments um then you end up with the amount of data that you're sending actually being very very small uh this is something which we do know how to do over the BLS curve which is quite important because BLS curve is already being implemented at the core

layer so we wouldn't sort of require additional curves and additional pairings um and uh one of the reasons we can do this is that there are inner curves so inside curves where we can do the vector commitments and in particular there's a curve called bandersnatch which is very very efficient for this sort of thing there are again good quality implementations of bandersnatch and there has been lots of lots of work to sort of guarantee it security for the application of zero knowledge proofs I will say more on this later because right now we're talking about uh

talking more about uh where where else polynomial commitment schemes are being seen on ethereum the big one I want to talk about is data availability and the reason I want to talk about this one is because polynomial commitment schemes which are core building block for zero knowledge proofs are going to be used on ethereum after the dencan upgrade probably so this moves me on to my second case study so data availability definitions and Design the basic idea of data availability is we want to Shard everything to make transactions very cheap the current

state of this is the eip4844 proto-dank sharding proposal but currently before the upgrade goes in things are unsharded and one block is seen by everyone can I just quickly before I get delve deep into this section give a couple of disclaimers the first being that this is not my own work so please forgive me if anything is inaccurate and the second is that 4844 is not yet a full gas solution so we have um so some of the stuff is like what we're aiming towards rather than what will be included in 4844 okay so rather than having one block which everyone everyone verifies instead we can Shard everything in order to try

and make um in order so that only subcommittees see each shard we're still going to have it such that there is some consistency checks and uh and the way that this is going to be done is that everybody is going to see small commitments to each of the shards but they won't see the full data itself and the hope is that if there is some data on for example Shard 2 and C3 that is that is typing C2 is inconsistent then um observers would be in a submission in a position to submit fraud proofs and say there's a problem here the trouble is observers can only sort

of say that there's a problem if they actually have access to the data and proving that you don't know something is uh not just practically but also theoretically impossible you cannot prove a lack of knowledge because you don't know what you're not proving but you can prove that you do know stuff and this it turns out is sufficient for us to say look we're going to prove that people do have the data available in order to do the checks that they need to do and the way this is done is actually kind of similar to lots of other cryptographic consensus and um cryptographic and consensus Concepts it's very related to verifiable secret sharing it's very relatable to broadcast

it's very relatable to the fry polynomial commitment scheme there's just a few tricks that I used everywhere I guess um I would say there's like four steps first you encode the data and you commit to it then you do something called a fast Fourier transform in order to find many more evaluations of the committed polynomials then you sort of distribute these evaluations and give different evaluations to different parties and then afterwards if you want to you can reconstruct where you can sort of say if enough honest parties have seen some of the data then we can reconstruct the full data actually defining what you want to do

with data availability sampling is something which is a bit non-trivial because even though it's very related to lots of Concepts in the literally in the literature it's not quite the same so there has been some work into sort of figuring out what we want um and if you sort of go for different requirements and different things that you're like aiming to achieve you will find that you end up with very different schemes so the the what the goal is is going to fundamentally impact what your final scheme ends up looking like um so back to sort of the uh some a couple more questions

because of data availability which is completely unrelated we are now in a position where polynomial commitment schemes are going to be used on layer one do you think that this will ease a transition to zero knowledge proofs considering they're like a fundamental building block or um or do you think there's still lots of barriers um maybe show of hands who thinks yes and who thinks no I would probably be more interested by the no answer I think um the other question what is the best place for cryptographers to learn about the design Girls behind

um candidate Improvement proposals because in this situation I'm sort of saying oh with the case of data availability if you do things differently then you're going to end up with different schemes actually knowing what the core design goals are is like really very important so do you think there's like a good place where these are are well documented foreign that's the case but isn't there the ethereum magician form sort of I don't know about that one actually what's the ethereum magician form

maybe I get the name wrong but with every eips oh most of them there is a link with to this forum where the author explains first in a post with the goal of the VIP is and then there is some discussion okay that sounds like a that sounds like the perfect place I'm going to move on to sort of the final part of the talk and this is going to be talking specifically about zero knowledge specification uh first I'm going to mention a movement called ZK proof and what this is is a global movement to try and sort of stand

standardize and mainstream Advanced cryptography by building a Community Driven trust ecosystem so what we want to do is we want to at this point just build practical specifications so not yet standards just specifications of at least one zero knowledge proving scheme it'd be good to have more but at the moment just one would be it would be already a big Improvement and we're kind of considering that there are like multiple different layers to what you would need in this documentation just because what we're trying to document is um well has lots of layers um the starting layer is probably the one where

um or where things are moving at a at a very fast place and is evolving quite quickly and that's just getting the constraint system so this is sort of saying what am I trying to prove if I want to prove that something's an encryption how am I going to tell that to the circuit if I want to prove that I've done this fully homomorphic operation correctly how am I going to encode that in such a way that my proving scheme knows that this is what I'm trying to trying to prove so our first step is really sort of trying to describe the constraint system and specify it with this sort of been mentioned that it would be a good idea maybe to do this in hacks back and do some basic checks uh to check with that valid assignments pass invalids fail things like that I would say that the

okay you've described your constraint system how are you then going to generate it is something that we're not tackling right now mostly because um we don't know how to tackle it I can't give a better answer than that the next sort of two steps are to describe the actual snark logic um and this first goes through an Optimizer many cryptographers are not aware of this step I certainly was not aware of it for a long time but it sort of says if you have these constraints you're not going to optimize by hand that would be a stupid idea we're going to do the optimizing as part of a back end for you um and um only after that do you move on to

sort of saying what's the actual proving system what does it look like what operations do I need to do how am I going to interact with these things the proving system by the way is the only step that was really required for the shuffling argument which we were just which I was describing earlier so when I say that the shuffle argument is simpler I really genuinely mean it after that you sort of take the proofing system and you compile it and this is the point where the polynomial commitment scheme comes in and which polynomial commitment scheme you use entirely affects what your ending scheme is going to look like in

some very fundamental ways so for example if you use a fry polynomial commitment scheme you get Starks if you um if you are going to use a kcg polynomial commitment scheme you're going to have something pairing based with a trusted setup if you use something discrete log based then you're going to have something that doesn't require pairing still requires group operations but maybe has quite a large verifier so really this is the step where you can choose choose what you want for your scheme [Music] so obviously we've got quite a lot of choices here does anyone have an opinion any opinions on which polynomial scheme they think it

would be important to write specifications for first do you think it would be better to have a for example something with a big proof but no trusted setup or do you think it would be better to have small proof and a trusted setup okay hi my name is Kenneth and I'm uh we knew in this blockchain industry and I've been looking on zero knowledge protocols because it's applicable outside of blockchain as well so um I I think that the trusted setup will be a good start because it is something

that is easily digest it is easily to be digested for my brain yeah okay the pairings are not the most simple thing in the world but thankfully we already have those so any other opinions and does anyone have sort of any any feelings on what they think the specifications should look like would you prefer something that's very easily digestible to somebody that's not necessarily that familiar with the space

or would you prefer something that's very in the detail about every single layer every single component that's being used gone I think the letter is better because that's why we can really understand what's going on in the background okay sometimes I when I don't have all the detail it's very hard for me to okay what but why we use this why why is that so you even think that it would be easier to understand if there were all of the technical details and it would be if it was abstracted away yes yes yeah the final layer is applying hash

functions this I would say is a very major area for implementation bugs for example it's very important to avoid the situation where you have overlapping inputs which is something that comes up quite quite frequently so this again is an area where we want to be very careful and very precise about what we tell developers to implement one current work on this is the safe API this is designed specifically for sponge hashes so that would include chart three and that would include Poseidon but that would not include chart 2.

um and yeah the aim here is to sort of say this is precisely what you can do if you don't deviate from this at all then you're probably not going to have too many implementation errors um I don't know if there's any other works within this area where people have been like trying to help people use hash functions in a good way but if there is do let me do let me know about it maybe a hand up if not then I've come to the end or come to the end of my slide so I think this would be a time to ask me any more questions if you have any okay I guess I've been asking Lots as

we've been going along so thank you very much [Applause] foreign [Music]