Pairing Based SNARKS by Mary Maller

[Applause] everyone today I'm going to be talking about snacks on this talk is going to be fairly high-level I'm going to start by just giving an execute of what they are and why you might want to use them and then I'm going to run them through a selection of options which are partly available which I think a school for various reasons Fuko support second can you hear me better now yeah such as a Serenata shock it says a subset of zero knowledge previous which have additional properties such as being very similar needs to verify and it stands close they're a nursing home interactive document of knowledge and I claim that they are useful for poaching applications what cell are you today the Syrian election proof allows you to demonstrate that you have run some protocol incorrectly and precisely what the protocol is it might be a way of saying that you have done your tax return correctly it might be a way of saying that you have encrypted a message correctly it doesn't really matter what's important is that there is a protocol and you have run the pentacle exactly as it is specified and then what's a verifiable will do is it will just take approve and say yes I agree or no I don't agree the other nice thing about them is that they allow the user to keep some of their inputs to the protocol confidential so for example with I have encrypted message example you could do that without revealing what the message actually was so the example we've just seen the role of example is classic thing what's not so good because the verification is cheaper than the natural computation itself so it was it essentially means is that we can have a I'm saying minor it probably wouldn't be my number let's say that it's a minor he receives lots and lots of transactions and all of these transactions have been signed the minor can then create a proof that it has run the verification algorithm for each of these signatures and these transactions and the verification has returned true and then when it broadcasts a transaction to all of the other nodes rather than having to complete this verification themselves they could just check the proof and this is much much cheaper for them to do this thing that's great the other nice thing that snacks about you to do is they allow you to achieve some more privacy so if you want them to hide the contents of a transaction for example suppose you have a fireplace you have urgent and goodbye abundance to room and buy some produce but they don't necessarily want you to know exactly what they're buying so the case I have given is for apples but actually if you're talking in the business situation if you have companies and the chances of them wanting to broadcast to you in 12 - the competitors precisely what they're buying and every single time you use a blockchain is quite small so this is quite realistic application so what happened you'd have a transaction which would say sends 10 Americans to buy an A and encrypt that transaction for W block chain but the thing is you now need to additionally prove that you actually do have 10 apples to send by a because otherwise this would be something which would completely break the integrity of the blockchain and that would be a problem so bread snack it's not pie is precisely what the Jim dice you're sending and all you can see is that yes I do actually have the merchandise that I'm sending in this so for developers if you wanted to use these things but you don't want to get into the details of how that work then a great tool you can use because Socrates and you will need to learn precisely how to encode the programs but is that firing to entry but you don't need to learn how that approving algorithm works for size you can listen to take that as given that one aside so just to summarize what these things are they are an interaction between approver and a verifier with a previous showing that they have followed a French go and a verifier is saying whether or not they believe you they need to be correct an honest prayer become always convinced - verified they need to be zero knowledge the verify events nothing from the prover apart from the fact that the statement is true and most important thing and actually most difficult to achieve zero knowledge is quite easy somnus it's not easy when 30 years trying to get somewhere sufficient and this is the idea that only a prefer who has actually followed the protocol can convince an honest verify [Music] so with all I ran through promo snacks which is sort of what I'm mostly focusing on I'm going to talk about some situations where you would perhaps not want to use apparent basemap where there would be better solutions in the literature that you could use the first one being if your only train intending to run your computation once so the thing with snacks is kind of the way they work and the way they get their efficiency is they have is the big pre-processing phase right at the start but the verifier is going to do a ton of work just to get a string of information which you can later refer to in order to massively speed up this verification and this means that if your mates they're verifying 100 proofs of thousand proofs it's really good but if you only need to make to use it once and that's a total waste of time you'd be better off using something else and in particular things that are good for this test be the Guru starts area Aurora and these are designed for one of the computations and another nice benefit of them is that they have typically quantum secure also they have very fast breeders another situation where you would not use schnapps if the program that you're trying to prove it's very very small so typical example of this would be range previous if you're trying to prove that something is between 0 & 2 to the 64 we can represent my program very efficiently it cost us a hundred twenty cakes or something like that so in this situation the stock is actually going to give you some concrete vapor head which we celebrate asymptotics and you were to be benefiting from a more large computation you wouldn't see the benefits of this in our situation got your fuses unapproved switch well practically it's so well asymptotically it's perhaps let's get the very small statements that actually take the head is so small that that's not going to come into effect and one last situation is when the thing that you're approving is a very specific computation for which we have a very specific solution okay so starts a quite powerful and they cover it here you can do general-purpose computations with them but sometimes you don't need that sometimes for example if not proofs if you're trying to say I know a secret key you could run the operation and that would be far better than running a snack the time when you do want to use a stock is when you are proving the same theorem same application the same set of constraints many many many many times okay because this is really the situation where the pre-processing stage that you can't start is going to benefit you you are going to reap the rewards so the permits it does have very similar sizes and by small I mean a couple of hundred bytes likewise a verification tends to be really fast but if you often eat rustic setup which is a downside also they rely on for some funky assumptions and my funky assumptions I do not mean wrong assumptions we can't break them what I mean is that we don't understand them very well and that makes us uncomfortable and finally and this is also a pretty important point the previous are not cheap the previous can be a big barrier to actually using these things in practice so now to run through a few schemes the first one if will you either speed grow 16 is the fastest snack in the literature which has the smallest criticize fastest verification time the fastest approval time is generally great this wasn't just as I've made a part of thinner it's actually the result of a huge line of Wax starting from Janeiro and others who found a really nice way to encode the programs that we're trying to prove which was later than people found where to turn us into rank on constraint systems which are the general standard people tend to use now for computing the constraints and then there was a line of papers that way each optimizing the rezidentura governments immediate gratification processes that were needed finishing them with broad scheme which is in the generic great model the downside here is that there is a trusted set up and I'm going to do a very very quick explanation of what they mean by that a secure don't understand me then Nagori because it would be quite bad promise so before the proven and the verify can grant I was saying that there's this expensive trust in such a process what sorry this expensive progressing step but impairing mistakes it's actually worse than that because the needs don't we do at the start some of the inputs to this pre-processing have to be secret in order for you to have a secure scheme at the end and worse than that the secrets are very structured and we actually don't know how to generate them without somebody knowing what they are so we can get around this but largely the way we get around this is we have many many participants all having a little bit of the secret and working together to output the parameters that the actual prefer and verify use and this is kind of nice in the sense that if all of the parties collude then sure you don't get any guarantees whatsoever but if a single one of those parties is honest then sure there could be other points of failure but you'll need that you're not going to have the point of failure being that the trusted stuffs I've had commuting parties okay and sometimes this is enough for example if you have a closed set of participants where you don't have people joining and leaving at any point in time but you just say have a hundred people that are always the same then they can just run the trust setup process themselves and because they have run it's been part of the process if they know that it's okay they know that they themselves are honest and that's great and the main thing they can use cross 16 which is the scheme in the literature likewise if you have a way to actually verify that that's any given computation that has been proven is wrong and at least you would know something bad has happened and this can can't be the case for example you these things put sharks which is where you have your prove being like a bulletproof thing which don't have try success up but then you also rather snap on top of it in order to get the verification costs down but you still have the original proof so you can still at least check that we originally proposed also very rare situation for decentralized technologies thus if you do have a central traffic passing and no problem [Music] one nice thing about science is that they are very highly paralyzed book and there's a work crew disick which explains exactly how to do there's not just for the great exponentiations but also for the fast Fourier transforms so if you're looking to paralyze snacks and I definitely recommend taking that one out another really cool thing you can do with starts you can have the snack of the staff it's not the snack that is not gives verifies and every single time you run a numbers expecting the recursion run another snack you get something which is smaller and cheaper to verify meaning about the full system would be really small and really fast a verify this isn't as simple as it sounds in particular the security assumptions which are based on yourself can blow up in size if you do throne so that happen works which have looked into precisely how you should lay out the fullness of your recursion such thing as security assumptions still hold also important in the least it's not so you have this specific way of representing with your program if you need to be able to represent your snack verifier and this is what Monsanto mothers did when they introduced something called MT curves which are basically a specific type of pairing which you are able to represent inside a snack which means that if you want to do layers of recursion you can another situation you might come across is if you cannot do a setup I mean this is you're still going to need to have some kind of setup process to be honest but you can have a situation where you have an updatable setup where at any point in time a new person can come along add some new randomness to the system and then be part of that setup process so it doesn't need to be a fixed thing with the face set of cutter point and this basically means that it's much easier to actually brand new trusted setup process which is secure much easier to audit much ease in how people taking part much easier to just generally manage but probably more importantly you can have a universal set up so typically when you're doing snack setups you would have one setup per application so if you're doing range proof you need a setup if you're doing that Z caching is set up it could encounter you need Assessor and also if you're set up you do your setup and then you happen to learn that something you didn't your protocol is actually wrong and maybe you missed a minus sign they have to do the whole process again whereas with an updatable setup you don't need to do that you have just a single setup fit so and this is quite nice because it means that you can coordinate sets you can make sure that there's lots of the companies lots of participants lots of governments lots of individual people taking part and just have one set up and that would be the only setup that you would need to audit so this is what sonic sonic briefs do they designed their knowledge briefs which are very nice if you want to the universal set up the catch with these is that they are actually only efficient if you're in a position where you can aggregate so if you have an aggregation party you can fit all the proofs together and help out other verifies than they're really efficient on the great and these the these levels have been improved by awesome if you cannot segregate then there have been a couple of works recently on completely of code Marlin which do not need any very aggregation but do have the downside that the proof sizes are a bit larger when I'm looking like a kilobyte rather than a couple hundred bytes but they don't need aggregator [Music] if you want to have your proofs being a bit bigger there's also quite a nice length lengths which is what which is also universal an updated book which is called Libra not the Facebook currency and the nice thing about this I mean what they were focusing on is getting moved down the creeper computation but what I think is really cool about it is that they do not need very large fast fourier transforms they can get away of just very little ones and this means that you're actually trying to represent the program and then you can use a field which doesn't need to have a large device repetier this gives us a lot more flexibility when were actually using it so to summarize Perry Mason axe can be small and pasta verify the can't be paralyzed apart they can be quickly they can be universal and updatable and they can be made on it to prove that slower to verify if that's what you want [Music] I say yeah this one has larger for even smaller premeditation that's regular troops you mentioned the shuffle arguments when you said Jets growth and the accumulators who wrote that paper I think an official actions by a jumbo resource research good [Music] say one recent one was love if you use the better person to protect documents than just another put in a new commitment scheme and this is how I behave data released by NC cash does they use a person in front of document which has a downside that have new clarification if you just run it as a run off but if you're aggregating then you have the situation where you can have the linear verification via one of the cost and then just have a lot of rhythmic factor on top of that for each individual proof which means that you can get something that's quite fast on saturation [Music] [Applause]