Overview of Zero Knowledge Proofs

Transcript

okay I think we're ready to start more people okay so I'm going to talk today about the knowledge proofs this is going to be it's meant to be an overview probably good for our show of hands actually who is anybody here completely new to 0 noise proofs okay and then anybody working on projects involving so much Bruce okay that's good so yeah it's difficult to know exactly where how to pitch this because this could be a very deep subject so I probably make it fairly general rather than going to very much detail about any particular proof or project people see how it works so to introduce myself I am

the CEO of a company called extra P we're a blockchain and cryptography consultancy based in Oxford we do general blockchain developments but we also do a lot of proof developments as well and consults on that I have one of my developers here Carol we also do audits we do a lot of workshops and I'll come back to that later because we run workshops around zero knowledge proof so try to get more people into this area it's a very exciting area but if you need to contact us please less contact details we are hiring I guess you can hear that a lot today and over the next few days so if you're interested in working in this area please come and talk to me afterwards or

I'll get in touch what I will talk about today I'll start off with an intuitive introduction to zero most proofs for those of you who are new to it I'll talk a little bit about proof systems and the cryptography behind so noise proofs I'll go through a timeline a little history of how they've they've come about and then look at some current research and the areas and look at some use cases because one question I often get from from clients or people who are interesting this technology is that yes it's really interesting but how is this used so it's useful to look at some use cases and if you want these slides I don't know if they'll be available elsewhere but you there's a URL there you can

all of them okay so to introduce so noise proofs typically we have three actors involved there may be a creator of the proof or that could be the prover as well but then usually we have approver who's typically called Peggy and a verifier called him Victor and the the idea behind this is that Peggy has some secrets and she wants to show chance to prove to Victor that she knows this secret but she doesn't want to Victor to know what the secret is in fact all she wants to do is to show that she has knowledge of the secret and give

away no other information at all and that really is in essence what a zero knowledge proof is about an intuitive example well I particularly like I missed the Where's Wally books or Where's Waldo if you're from the US so in these there's a character Wally who is very distinctively dressed he's in a picture surrounded by lots of other people who are similarly dressed and you have to find him but if you imagine that Peggy has indeed seen this picture and she has found War II and the picture and she wants to prove to Victor that she has found him but she knows that if she says if he points out the wall he is in the picture the victor will also claim oh yes I found him too she doesn't want that so to prevent Victor cheating what

she can do is take a large piece of paper and cut out a hole in the paper the size of Wally in the picture she can take the book put this underneath this large sheet of paper and so show to Victor through this hole in the paper that she has indeed found Wally though because the piece of paper is very large what a victor cannot see where the book is in relation to the rest of the paper and so he gains no information about where Wally is in the picture and so she has proven to him that she has found Wally she knows the secrets which is not given away information about where exactly is so a very physical example of a zero knowledge proof another one you tend to gain well I prefer when did

trying to introduce a zoo most proofs is the idea with having colored billiard balls the idea behind this is imagine that you want to prove that so the prover wants to prove that they can tell the difference between two colored billiard balls so they're red and green but the person that proving it to is colorblind and thinks these balls are identical and so they don't believe there's any difference and the way they can prove this is that the verifier victor can take these balls which he thinks are identical show them to the prover and then put them behind his back and swap them over or not swap them over bring them out again and ask the prover whether he has swapped them over and the idea is that if there is indeed a

difference between these balls that the prove can see that she will be able to say whether she is that Victor swapped them over or not and if you do this once you just have one round of this then the first time you could say the the obviously Peggy will get this correct she can see you difference tween these two things and she would give the correct answer but for the verifier they may think well of course this was just a good guess there's a 50-50 guess so I'm not going to believe that there really is a difference but if you go through a round of repeating this and go through an iteration repeating this again and again the chance of guessing is correctly each time drops off exponentially and so eventually the the Faro file will become convinced that there is indeed a difference between

these billiard balls that the that the proven owes in doing that that prove the verify has not gained any other information so they've not found out what this difference is they don't know how the prover has worked out all the differences but they just know that there is some difference that they can detect so those two are they some of these of simplest intuitive ideas behind a zero knowledge proof some of the easiest ways to explain them and I think it's interesting to think that I mean we go into the cryptography now and look at cryptographic means of doing zero noise proofs but it's interesting to think oh that you know here here are some examples it's very physical and it

strikes me there is something quite fundamental going on here the around maybe information theory I'd love to have chance to investigate this we were using it we use this because it's useful and we're using the results of this but I think there is something there's potential for a lot of research in this area to try to work out how come there is this idea of zero noise and we can do this in many many different ways okay so when we talk about doing those proofs there are really two aspects so we are often talking about a proof system we're trying to prove something that's beyond the doubt of the verifier and there's also a zero knowledge aspect in the proof system they mean we've just been

research about this for a very long time but we were there are two parts that we really require we want completeness and what this means is that if the prover is honest and gives a correct proof that the verifier will believe this the very far is not just going to deny this again and again that there's a high probability that the correct proof will be accepted by the verifier and on the converse there's the idea of soundness so that if you have a dishonest prover now somebody gives a false proof then the very file will be able to detect this so those are the that's they cannot the proof side then in addition we need the sort of zero knowledge Ness of this

and so this is I mean we've seen the examples in those first two examples you you you've got your proof and then the verifier has some means of checking this but whatever they do to check this whatever protocol they've used they should just come up with a an answer of whether the proof is true or false and gain no other information okay so I've done the examples I gave did not rely on cryptography in any way but in the the work we're probably doing and if for those who are involved in projects I'm sure it's the same with you you're going to use cryptography and there are some cryptographic primitives and

cryptographic ideas that really underline a lot of the work that has been done in Syria noise proofs a lot of research so some of them they are very straightforward and they are things that you also used very much in blockchain as well so a discrete log problem and collision resistant hash --is these are I'm sure you all know about these typical thing you know the idea is this dual functions the idea is that you can do a function one way and it's very difficult to to brute force it very difficult to go to go the opposite way also we particularly in a lot of proofs where there some primitive people have used or some ideas people have used our knowledge of exponents and groups of unknown order I'm not gonna go through

this in detail there's a good Vitalik did a good blog post about this to explain it's not series but the the idea is for the knowledge of exponents we often when we're doing so much proofs were often looking at polynomials and proving that we have these in fact match now that we can we can match pull numbers together and so looking at a pair of points we're trying to prove that if if there's some some value K that is unknown that this this cannot be doesn't ask or the leak between the prover the verifier another zero knowledge earnest of as the case knocks comes down to to this fact I then groups have unknown order again is

the the idea this is an example from cryptic accumulators but the the idea behind these again is that there is some information in this case it's this the order of the group that is that is kept secret and so you cannot then brute force back information and gain more information and by the system if for example you are a dishonest verifier okay now this is just a little diagram to show typically what a soon much proof of my protocol system might consist of the steps involved in it particular this is so seek a snark you would have some some algorithm that defines the proof that you're trying to represent this

going to be they're trying to give to the to the very far in the very far and approver obviously have to have some common understanding of this and then there will be some some trusted set up or some ceremony involved in in creating this or defining this and then with this in particular in snarks this then ghosting becomes maskull representation and goes through a series of transformations that take something that's potentially you could write this maybe it's a high level language you've written this this algorithm n or some definition of the algorithm and you turn this into some mathematical representation that can then be used in a proof that is so that the proof is still going to be succinct

and it's going to be able to be used in reasonable time and in reasonable memory this will produce a particular proving key so this is the some data that the the approver needs to produce the proof and also a very fine key that the verify needs to be able to check the proof and then the prover aggie she can put her take her secret often called witness and with the proving key she can produce a succinct proof of whatever it is she's trying to prove proof knowledge of this secret and then this sub sink proof will be given to the the verifier victor and then he can use his verifying key or to

then verify that that is a indeed a correct proof and if it's zero knowledge then they will gain he'll gain the other information on the way if you look at this in terms of some of the projects such as say Socrates which is doing this on aetherium you could start off here they have their own DSL to create a the algorithm for the proof which is then turned into a mathematical representation of chain you get you can create the the succinct proof and the verifying key effectively and the thing that does the check is a small contract so it was very far so that anybody can then verify it and the proof is I'm giving it to small contracts which the

function the contract would come back with a shorter force to see whether that proof is true okay another way to look at this is to say actually the same kind of process but if you if you imagine this is if we're talking about say a cryptocurrency you take you start off with the the idea of you know you know that the you have some keys for this from that you turn this into some polynomials and then that you have them inside a particular relationship so that's kind of one part this is a mathematical representation part of this this process and then we to stop the the prover or the verifier cheating we then

have the the compliance idea that we can we're picking points on these polynomials and that are chosen randomly for the verification so I said in just another way of thinking about they are in the previous slide okay so sooo much proofs I mean they've become very popular particularly since block chains become popular but they have been around for a long long time and the they've kind of history I think has been shaped by a couple of improvements or changes and that there have been improvements to the cryptographic primitives and people have done research on better curves and

better hash functions etc and this has really pushed the the research forward all those also been people making fundamental changes to the way that we think about zero knowledge and those those approaches have made quite big changes and brought us brought us to where we are there's a great blog post the Cambrian explosion which is it's all about this I really recommend people read that there's a link there to go through the history very quickly so it's back in the 1980s that really the the first paper started to be published about this and suddenly the the initial papers they were rejected by conferences when they first came out so they were a

couple of years these were these were being rejected and not not really seen as then you saw I think people were very much focused as this this quote from Matthew Green comes in they're very much focused on how you can about proving things and how you can check that a proof is valid and what the people doing the rottenness papers really did was to turn this on its head and saying well what about what about the verifier in this situation in this in this process as well how what if we can't trust them and they started to think about in a very different way and that was I think maybe that was one of the reasons why these things took a while to be accepted and starts to be seen but anyway during the eighties they started out and particularly you know

very powerful bits of research in the early nineties where they started looking and they problems in NP improving that you know any problem in NP could be represented by a zero knowledge proof so it really made this a very powerful area of technology and then during the during the nineties etcetera and the early part of this century these people carried on incremental adding ideas and improving the way things were going and doing adding things like you know effective set membership range proofs and then particularly the you know yes growth paper in 2016 really made a great change because it

made allow people to produce succinct proofs and produce proofs that could then be used and that we could run and you know we can see them now running on the blockchain and be used very had sufficient performance that they could be reduced widely and that was really a really a sea change in the whole thing so current areas of research and I do apologize if I've missed your project or your area so please do tell me connected to the slides but I try to think of it in in four areas so there are snarks really are they perhaps ibly the leading or the most popular way of looking at 0 at the moment and there have been some improvements to the way they are being

used some projects that improve those also I think recursive stalks are starting to be looked at and that's a quite a fundamental area of research but snarks not the whole thing then there are alternatives to them and then also we have to think about post quantum cryptography as well and in going through the projects I tried to get them to fit into this kind of scheme but it's not perfect they some of them kind of rely on a number of these aspects as well she'll say it's I find it generally very difficult when I'm trying to talk about it first together get a framework for this because people really do borrow from different areas of cryptography and mix-and-match so widely they're very very people are very creative in this area which is great but it's very

difficult thing to represent to this in a simple framework but this is the this is the approach I'm gonna take for this anyway okay so improvements of snarks we have some there have been improvements to do with the crypts of rhetoric primitives so you've got improvements on hashing functions MEMC Poseidon star CAD because one of the most expensive parts in terms of computation can be hash functions particularly you know dinosaur 256 hashes and like that and so these projects have really reduced the amount of computation needed to do that I'm MC really looking at the fact that we are when we are doing so much proofs and

we're doing cryptography we're using you know large finite fields and that the the the computation really needs to be expect that and so they've tried to minimize the amount of modification needed rather than doing you know some bitwise and working on small small fields very important thing about zeroes proofs and one that really occupies people's attention is the idea of a trusted set up so generally for a ZK snark tradition these have required a trusted set up so ashtec recently did their ignition ceremony to anybody take part in this no only one but it was quite last for quite a few weeks he was

a multi-party computation and was there to create what's called a common reference frame so that the and is done as a multi-party computation so that people could be confident that there have been no cheating going on in creating particular some data that was needed for the rest of the process C cash had a similar thing they've done a couple of they've done it a couple of times people have been very inventive with Z cash and how they they Grandy the multiple computation and people have used that as an example of someone who you had some radioactive material from Chernobyl and then use that V they reproduce the source of randomness for

the computation etc so they are seen as perhaps a drawback as they case knocks because they are involved you know they do take a long time they do require a lot of setup they do require a lot of people to be involved I think also though perhaps you should think the fact that by doing these these ceremonies you are involving a lot of people in your project so I think they do have a plus side as well and they do provide get people interested in the idea and interested in your product but they they are an overhead and people generally do not like this kind of overhead and would have been looking for alternatives to these so the the first when stocks were freely first being used I guess they

recorded a unique setup and the idea was you know for you for a particular problem you were trying to solve particular algorithm the neutron a producer proof for you had to have this setup so this setup would then provide the information of the prover and a verifier would share and he would describe the the the project the the proof and this this had to be done we don't find some once you've done it then that was that if you then change your algorithm or change the the proof that you were trying to do then you would have to run a new setup so it was seen as quite a limitation and but the alternative and I will come into this later than the alternative these if you don't tell across the set up is then you tend to get larger proof sizes so the

actual proof itself is much larger or it may be take much longer to verify so there's there was a trade-off here that's you you're getting a succinct proof and reasonable times for verification but you have to go through this this process initially so what some of the work in the last year so there's been that's done this people have focused on this and tried to find a way of doing a universal set up so the idea and these are some of the projects the idea is that you you don't have to once you've done your across a set up you could then potentially chain what the the algorithm is doing and

update it make it more efficient and that's been one of the big breaks because I think in the last say 18 months with a sonic and plunk Marlin for example I'm not going to see much detail because there's AK Williamson from NASA tech is giving a talk this afternoon I think it is yeah about this and I think this is exactly what it's going to talk about so please go start talk instead but the idea behind these these projects really so it's about improving this this first step in this equation or improving this trust of setup so recursive stocks are a very interesting idea and when they rely on cycles of elliptic curves

which can't be difficult to to find can be difficult to process but the idea generally behind a recursive snark is if I have if I have some proof of knowledge of one thing it may be that I can then take a proof of that I have that proof initially and so you can you can continue doing this you continue recursively producing proofs of proofs of proofs and by by this way it reduces the really the amounts that you have proofs that you need to do and so the the sea cash TV I should point company with the halo project and which doesn't require it I trust a set up and yeah so

one of the the major ones Khoda doing this so they they would they did this with an eye to the to the blockchain so you know in a typical blockchain we're using we have this this idea we want to be able to verify blogs and verify transactions and you you know if you're involved in the blockchain you need to verify all of this it's quite an expensive process that you need to just keep doing and you you end up with you know huge block chains particular what coder have done is to say well rather than do that why didn't we just have a proof of a particular block height of the validity of this blockchain and then we

can give we can pass that prover and instead and then for the next block we can get a proof of that we can do just proofs of proofs and effectively need to write back down through the blocks and so their blockchain and is they say toss up at a constant size about twins kilobytes and it is fairly quick to to verify and they're just using yeah come recursive composition of ZK snogs to do that another idea so another perhaps way of approaching the basis to use distributed processing so disick have the idea that if you're if you're doing your your snark you need to you know this is a you have the

proven needs to be to be verified this could be a complex a costly computation and so they'd have the idea of distributive Asst you know just the traditional way they would distribute any computational task one of the things that will take time is the this idea of the amount of logic gates so in your initial algorithm this will be turned in a case knock into a number of logic gates and they there is typically an upper size dictated by the performance because of the the amount of presume you'll need to do so there's typical upper size of the amount of the size of

your algorithm that you're going to be able to prove and so Disick's so they can really up this because they can then farm out there a lot of the processing to to multiple machines and therefore make the whole thing more performant perhaps another way of looking at it is concurrently I don't know great deal about this project it's just when I come across Lee recently but the idea is that you have rather than sort of having you know one provable and verifier and even if you you ship this out to multiple machines the idea that you could have multiple proved ISM verifiers and they will still be safe even in a setting where yeah he says you could corrupt many of them ok so I spoke that trust is set up and how people see

this as a real potential disadvantage and there are alternative to this so the one that people will perhaps best NOAA stocks there's one of the papers there for Aurora and people have done yeah and all projects on these it's the the some of the background so this has been around for quite a while but was not seen as really feasible but the the instead of a trust is set up you can use a public randomness and this is the transparency that you you have in the name of these things and really all you need is to be an agreement on a hash function for between approver and the

verifier yeah the just quickly about the process they go through this intermediate representation of a program which it's really going through a set of steps and you're looking at the the traces of them they described as like being registers and you just go through the steps have the the functions to produce the next step the starting listen to me representation and then it's further defined and there are ghosts with the Freud protocol etc I won't go to that anymore again so there's better people to talk about for me this again this afternoon talk about that so yeah please check

that out if you're interested and this this results in some pretty good scalability so what you have here is the that we've got the time against the complexity so these these different levels were different kind of bands of number of gates and you see that for a snark if the this you know as the number of gates increases that will set up time increases massively but all the the verification time is not too bad but with stocks I mean you you have a you don't really need to set up so it's just everything is just really constant so

they're very very scalable from that point of view similarly the another take on this and with the idea of not having a trust set up is bulletproof from Stanford they rely quickly on the idea of arrange proof but also a supersonic they who also try to moving away from having a trusted set up spartan as well so there's not quite a lot of projects coming out in this area and trying to move away from the trust of set up and this justice a quick little diagram to shows some of the ideas of the performance for these things so you see

the typical snarks you know they are they're very succinct whereas with the stark they're much much larger and they yeah the verifier you know it's a constant complexity of time but they have disadvantages so we have some strong cryptographic assumptions underlying our snarks where is for a stock we just we just say we need to agree on some hashes and then stocks have the additional advantage because of this their underlying realized just on hashes that they are resistant so yeah so there's a lot of research going on in

that area also fractals so they're taking a similar approach to stocks to Aurora but they also you have this additional step that they apply an encoding so to reduce the amount of information that is needed in the the input and then Marlene plonkers over there doing stock projects they also do a similar idea of encodings but it's a different different process so all of these projects they're really kind of I say there's very creative they were very much borrowing from each other and using a lot of different types of ideas in cryptography to achieve succinct and performant proofs post quantum so interestingly I mean the the problems

you'd get post quantum for a sufficiently powerful post corner computer obviously this is you know for some value of sufficiently but this could weaken some of the the cryptography that we underlie some aspects of a large proofs but whenever I speak to people involved in this area they always tell me it's about ten years away pretty much local diffusion but is those printers are the ones that are will potentially be affected by photography not so the hash functions which is why stocks are seen as quanta proof and so it's been researching so coming out of lattice based cryptography

so this is a type of cryptography that is quantum resistant relying on problems such as the Nira specter problem to to produce similar ideas that you get with you know your elliptic curve cryptography but in a way that is quantum proof and then people have taken that and there's some projects where they've used that to start to build as soon as proofs based on those as well so links to some that if we go to use cases now obviously cryptocurrencies perhaps the one the people will know best z cash grin forming will Manero Manero are

using bullet proof but also knife or from as young as if they died all using some aspects of zero knowledge it's been a as a use case it's been a very successful one but there there are other ones though those use cases very much focusing on on the privacy aspect of 0 noise Bruce trying to protect the information of who has sent some token to who someone else and so make that keep that secret but that's just one aspect of obviously not proven if you look at the the proof side we have some use cases in blockchain scalability so for example very well known projects I

think is roll up so this can increase the the transactions per second on aetherium the idea being that transactions are abundant together and proofs are made the transactions which then gets put on the main note so you don't need to verify everything you can just you can accept except the proof similar projects is ek sync so all of these particularly yeah targeting the idea of being a proof system and having a succinct proof of some more expensive computation rather than being about the privacy side other use cases when I particularly like and I've got some slides here from Los

Alamos Laboratories is a nuclear verification so the it's very important that some countries can verify what's happening with nuclear weapons and if you're claiming that you are getting rid of them it needs to be you need to be able to prove this to the satisfaction of the other nations involved in this but in a secure way and in a way that does not give away your secrets I mean you want to keep your secrets about your your weapons and so nuclear so so much proofs have been used in this area the the project that this front came from Los Alamos ended up with this is this is the architecture they used just if I can

explain its they were trying to really give proofs of a lot of areas of their system so they had some neural network that was involved in showing that it's involved in the verification but they had then to have proofs that this network model had not been tampered with that the output from the model was what it should be but also the inputs were what the they should have been and all of this then had to be signed so they ended up with quite a few quite a few proofs proving all the different aspects of a system this is one of their slides have no idea what Darth Vader is doing all that but I guess he said an attacker or something I don't know but so yeah so they've got the system

where they've they've produced multiple proofs in zero knowledge around the whole the Hubble area so an important one and I do recommend this these slides actually because they do some very nice introductions to say your nose proofs as well they do they go through in a very nice way I'm very clearly so it's worth checking out another aspect that I see quite a bit is around identity there's a starts been billion called kills who are working on this but also there's a lab been set up at Napier University in Edinburgh looking at identity particularly on blockchain but a large part of that then is around zero knowledge proof how those can be used to

preserve your identity and preserve leakage of personal information resources if you are interested in this area I want to learn more we run some workshops so please come to our workshops we run these in London we're trying to do these roughly once a month they are free for developers free to anyone who wants to come along this these are some photos from a recent one we had and typically we have with it's a two day workshop so we have a day roughly talking through the theory of solenoids proofs and we try to get speakers from projects in the area such as e-cash I know we also have a mini

hackathon this is photo of the people who have won the mini hackathon there so yeah we run these in London and we've done them in Oxford but we really like to expand so if you have a venue that you could help us with hosting them then please let us know we'd love to do them elsewhere and get more people into this space we have a blog and resources from there about zero noise proofs doing an introduction to the to the field in general and also going through particularly around ZK snarks going through the theory and the math so involved so you can check that out also [Music] that's it thank you for for attending

and this first talking the privacy stack I have some laptop stickers if you want some weather excellent talks coming up going into more details around this space so please do go have a look zach is great speaker Aztec is a great team so yeah I really recommend going to see them there's a workshop so I'm sure you all enjoy those but thank you for [Applause] attending what time we have a very quick question if you want to come talk to me ask me questions afterwards that's fine

they're on all truths I am an organization that called for tirado we're basically just promoting technology and another lie in fact if we could maybe eventually bring you down or something maybe even on lines doing good workshop going I know there are a lot of ethnic all right babe so just reach out here yes yes okay my name's Sam by the way I would shake your hand but let's talk about [Music]

[Music] [Music] [Music]

[Music] [Music] [Music] in general [Music]