Parameter Generation

hey all right thank you all very much and it's really fun to see so many people really interested in a zero knowledge proof technology this is gonna be a talk that actually is um I was totally expecting around like 20 to 25 people to care about ZK snark so this was meant to be more of a sort of brainstorming or open-ended talk and it follows from what Shawn was talking about in the talk right before lunch so I'll give a little recap of that before going into this a little bit about myself and I'll mention about the Z cash foundation I'm Andrew I'm a professor at the University of Illinois at urbana-champaign I do research on crypto currencies and part of the initiative for crypto currencies and contracts I'm also a technical adviser for a bunch of other projects you probably care about relevant for this talk I'm also one of the directors of the Z cash foundation and what I wanted to tell you a bit about today is how the Z cash foundation or how I'm thinking that the Z cash foundation should view how we can contribute to parameters set up for zero knowledge snarks a little bit more of just background about the Z cash foundation because I don't get that many opportunities to present on behalf of the Z cash foundation so far we are the nonprofit independent nonprofit organization associated with Z cash so we're a separate organization from busy cash company we're independent we have a separate board of directors we recently got our 501c3 status which i think is really exciting a Peter Van Valkenburg one of our board members has a really nice blog post about that just the the significance of this I won't go into all of that but I think that we are the first 501 C 3 public charity that is a cryptocurrency foundation that has some of the goals of other cryptocurrency foundations we get our endowment from pledged donations of the Z cash founders reward to about 1% of all of the mined coins all right and we have basically a complimentary mission to the Z cash company so something that's a little bit different about the Z cash foundation which you'll see is relevant for how I approach this question of parameters set up like we're not the core developers the Z cash company has the team of engineers that's working really hard and with all of the vigor and efficiency and enthusiasm of a start-up we're aiming to play a complementary role especially for now while the Z cash company has explicit of incentives to keep going and upgrading the software we're focused on things that are for the public good because that's as a 501 C 3 what our mission has to be and our mission in a little more detail has these three pillars of building a diverse community so that the Z cash company isn't the only you know effective organization in the Z cash community and providing leadership in terms of improving and maintaining the protocol especially when needed and doing things like education and research again just I'm giving background on the Z cash foundation because I assume maybe not too many of you are familiar with what we do a couple of our recent activities that I think are really interesting we're just about to conclude a a grant program of giving about $130,000 of funding out to community led and proposed projects and we're starting now planning for what will be Zeke on 0 sometime next year let me steer this back towards on the question of Z K parameter set up so this is the recap of the same motivation from from Shawn's talk the Z cash parameter set up for the Z cap 1.0 the sprout system it was the the first of its kind in many ways it's the first pudding of using a multi-party parameter generation ceremony to put zero knowledge snarks into practice all right and this was the first ceremony of its kind I think it was really cool I was one of the six participants in this so I have a really fond association with it is the largest scale multi-party computation of any kind at its time other ones had been like three parties there's like a famous Danish famous Danish beets auction if you follow MPC literature and cryptography they're all like oh we did this Danish beet auction that it's useful in practice that was like people and it was also in the semi honest case cryptographers are way more interested in this malicious case security and this was the first one of those done over the Internet and it had this nice quality that if even one of the people successfully deleted all the toxic waste from their computers at the end of the ceremony then you'd be able to rely on the safety of this and it was so exciting alright it had me at my mom's house and Orlando going and getting a random computer from a Walmart it had Peter Todd in a desert bus somewhere like out of communication and the vast expanse of Canada something like that alright but it's not it's the the mother of all one-off ceremonies all right it's not something that's replicatable that easily it was a one-off design and it has limited into the scale so there were six of us doing this and we had to basically stand vigilant over our computers for this 24 hour period during which we had to make sure no one's you know snuck in and took a copy of our RAM while we weren't looking and we had to do this for this 24 hour period that would have gotten worse if we had more than 6 people doing it and even worse it's brittle in the sense that if like Peter Todd crashed his Desert Bus and they couldn't do his second round we'd have had to throw it all out and start over do it some other way or rely on some backup parameters we had generated earlier alright so this isn't like the right way that we should be setting up zero knowledge snark parameters into the future and for all of the interesting ZK apps that I think you all want to build and especially if you want to build and take advantage of um you know some kind of general platform like this like snark support and Byzantium so we really want to have a more sustainable this is the same motivation as what Shawn's talk was you called it democratizing it I'm saying that it's sustainable it's really the same kind of idea here and you know riffing on it this is why it's a brainstorm session that even though we already have these e-cash parameters there's at least a couple of reasons why we want a better system for setting them up you know not the least of which is that the sapling upgrade is the planned upgrade for Z cache coming sometime next year and that'll require doing the ceremony again so we want the ceremony to be you know even better designed if we can alright and I think I'm really excited about this kind of cryptography technology I can see by the you know standing-room-only that you all are - I'm anticipating that there's going to be an upcoming boo of ZK snark enabled apps I don't know whether these are called Z apps zaps Z caps if you all have liked a suggestion you just shout it out or something it's a brainstorming talk zaps you like zaps for this okay all right well tentatively go the zaps I'm not gonna do you know votes for all of those okay so every zap all right it's gonna need its own snark this isn't necessarily true there's a you know a project called tiny rim and there's a couple variations of this the ideas maybe we could do one snark circuit that ends them all because it has in it a you know a really powerful general-purpose virtual machine you won't be able to put a Turing machine inside a snark exactly at least not one that runs with unbounded time but you can come kind of close to that by putting like an instruction set inside a snark the downside is that this has a performance penalty like the approver for for this generic things gonna be a lot slower that's like the time it takes to make a transactions going to be a lot slower than if you have a customized solution so I'm expecting that the boom of upcoming zaps are going to rely on custom circuits that are each going to need their own trusted set up to be performed so where does the Z cache foundation come in well the Z cache foundation's remit in its goals and its mission are broader than just Z cache so if we can we'd like for you know any work we do supporting this to actually end up being useful for other people as well and again this is still overlapping motivation with Sean's talk alright that the the protocol which i'll you know mention again for a recap the idea is that part of its work this phase one out of phase two can be reused across many different applications alright so what role would a foundation play well I think that by on Sean said at the end of his talk that we want to host it I want to dig into that term a little bit but I think that we should play a role in encouraging lots of people to contribute to jointly participating in some of this work especially the parts that can be reused for many different applications because we care about transparency we would like to come up with a process that has us publishing as much information as we can as the process goes along so that it's as visible for rest of the world that's the thing with these trusted setups is you you need confidence that they're done correctly more transparency as much as possible will help that all right what else can we do well we have an endowment and we have you know a lot of technical you know people associated with us so something we could do is try to encourage more independent versions of it so so far Shawn built his rust implementation of this we would like for other people to go and build you know alternate implementations of the same protocol that should you know help us wage fears that there's an implementation level bug that makes the parameters bad we also need more independent reviews so this is a new protocol I think that this will have to undergo a whole lot more cryptanalysis and scrutiny from the cryptography community before we end up you know hard working to use it all right we could maybe start doing some of the development and preparing this process or even generating parameters ahead of time but there's gonna have to be a lot of krypton now cryptanalytic review done all right before all of this confidence is earned these are all things that I think the the Z cash foundation should play a role in to give a recap of how this new protocol works and why it has these opportunities for this amortization so again this is my interpretation of Shawn's work I got to see the paper only you know several days ago I think on the order of a week ago so if I say something wrong I'm gonna rely on Shawn to shout out and we can try to work through this together instead of the snark setup ceremony like it was in the Z cash sprout being one big process that has some fixed number of people this is now split up into two phases and phase one in each phase the the parties that participate don't even have to be determined ahead of time all right and if one of the parties bowels out or fails they only have like one step to do you can just replace them with someone else it's not that big of a problem it's not brittle and what's even more exciting is that this phase one the powers of tau part doesn't depend at all on the specific circuit it kind of looks like this you'll have several parties each taking a step and at each step they have this crypto term that's like these powers of tau and at each step when a new party comes along they build on the work of the previous person by reran demising these things and providing some kind of checksum that says that did it correctly they didn't introduce an inconsistency all right and um you can keep going like this it's really it scales nicely because the amount of work that each new party has to do is exactly the same it's not like he gets quadratically worse over time it's the same kind of computation that they do the the size of this computation and the amount of time it takes to do only depend on the size like a bound on the size of the circuit that you're going to do but not on the details so for example what Shawn has in mind is that we should have a circuit that has two to the twenty-one gates the significance of this is that that's roughly the amount of size that will mean that um the steps that you have to take would fit on one DVD so if you wanted to participate in this and you want it to have an air-gapped computer did in the sprout ceremony this would be DVD sized all right two to the twenty one's also the size of the original Z cache circuit the new Z cache circuit is down to two to the seventeen or it is with a site that the gate size of the sapling circuit would be the point of this is that if you build this phase one powers of tau step with the two to the twenty one parameter anyone who wants to build a snark using a circuit that's that size or smaller can make use of this the final output so the the trust model is that at least one of these participants who re randomizes this has to actually reran demise it and forget what their randomness is that's disposing of the toxic waste all right no matter how many you have you just have to assume you know your trust relies on at least one of them doing that it can be anyone you don't have to know which one it is but you have to have one of them actually delete their randomness all right every part other part of the protocol except that needs to be verified but that can be done in a publicly verifiable way and that verification step also is just like one of the same kind of computation for each party so it doesn't get worse the more parties that you have but the more that you have the more of these that you have to do so there will be some kind of trade-off in terms of do you know how many should we have should we have a hundred or a thousand like what's the stopping point just for the sake of having a concrete number and I don't think you should hold Shawn to this I feel like I dredged it out of him but um just to keep in mind if two to the twenty one is the size of a circuit that we would want again that's big enough to hold the current Z cache circuit let alone the next one this compute time might take something the order of like 13 minutes of compute time for one contributor to add to this and verification time might take around 30 minutes these are just ballpark estimates and the size of each step would be a bit of an extra gigabyte that's added so if you have 100 contributors then to check it would be 30 minutes times 150 hours so you'd have to run your verifier node from scratch over for two days I don't know that's kind of comparable to sinking a full Bitcoin node right so it scales linearly with that all right after this phase one what happens is that then you have to do the circuit specific step and then this is something that would have to be done again for every news app that wants to use a different snark and there's still parts that are publicly verifiable what you basically do is take like a snapshot like whatever is the last powers of towel that you got to when you're ready to go build your circuits Pacific snark now you need to like take the get head if you will of that whatever's this current you know aversion and then reran demise it once more with public randomness all right that could maybe come from you you want to make sure that this randomness that this value can't have depended on this randomness so you'd want this to be time-stamped earlier and then you'd want this random beacon to come from blocks that came much later than when this was time-stamped all right but that's still publicly verifiable and then to do the second part efficiently you have to do this really beastly fast Fourier transform all right you know just over that last piece of data this is a slow step I don't know how slow that would be what would you think that would be for the one gigabyte yeah for the FFT hours like okay so like maybe an hour if you have like a huge multi-core ec2 or something so it's not like everyone's gonna want to rerun that entirely even then there's options that we could try right so we might imagine publishing that one gigabyte file that's the latest power of tau that we got to and the output of that FFT which is still about a gigabyte and using one of them you know a handful of techniques I think there's a lot of you know open-ended possibilities here there may be like a random verification option we can do so that if this is public anyone can verify a portion of it and if they find something wrong they'd be able to make a really short fraud proof or you could use the interactive verification technique that's a general-purpose solution that's suitable for this all right that's the same as the technique used in true--but I know there's going to be a presentation on that later if there hasn't been already so you could imagine applying any one of these other verification techniques to that big beastly FFT all right and then there's the final step of doing an MPC so that does depend on the details of your circuit the main thing is that this is now even faster like it's even less than the 13 minutes of compute per person but this will actually be the only part that depends on the details of your circuit all right so that was my rehashing of what um what this new protocol is going to look like so there's basically two main ideas here where I think we can get this kind of benefit and it's going to be sustainable because it's going to be a process that's you know useful for a lot of different people so the first one is we would want to make a really good powers of tau that everyone wants to use because everyone who wants to builds apps in the next year has contributed to this one all right and here this is where it started yet I'm trying to approach how the foundation would do this because the reason why I gave all that background about the foundation is that the foundation isn't in charge of anything at all all right the Foundation's not like officially responsible for Z cache really no cryptocurrency foundation is like responsible for all of the nodes that are running it they only get to direct hard Forks to the extent of the community of nodes and miners follows along with them and it's even more of the case in the Z cache foundation because we don't even know in the codebase or are the core developers were to the side all we have is that endowment to direct so the most obvious thing that we could do is to say okay at some time this year like on new years we're gonna publish the official list by decree of who the foundation deems will be the participants in the set up and there isn't really anything wrong with that it could still be a broad list it could still obviously be you know a large set of participants that you think wouldn't collude I think that we could do better somehow I'm still rolling around whether it's worth this like extra process but I like the idea of sitting back and like lettin consensus emerge on its own in some public space about who wants to contribute because the amount of effort for each new person to add if it's only 13 minutes of can you time and only a gigabyte maybe we could do something like just let whoever shows up on this mailing list which we set up the saps working group mailing list this is like a ghost town right now I just have a test post but we set it up it's on the Z Cash Foundation a domain so maybe the right thing to do is just allow whoever shows up if you're in the audience and go there right now maybe you could like you know claim your spot to be first and if everyone agrees with that then the foundation should acknowledge the consensus that exists rather than trying to make consensus by decree another alternative that maybe makes sense maybe not we haven't thought it through yet brainstorming is to like let miners contribute so like if you mind a bunch of blocks then maybe you should contribute if we do that then we should call it a tower of power was it a tower of proof of work I like all forms of like power towers I don't know if you like zaps maybe you you like that there's a I said that like I like this idea of you know reaching consensus in some way about how this process should be done or about what the order you know if the participants should be I mean there are a bunch of questions if this is going to be like a public resource that many different projects all benefit from you know maybe we should try to reach some kind of public consensus with input from you all there from everyone who wants to do Zapp's and some you know medium-term future like how many participants should we have should we build one with a hundred or one with a thousand though the more participants you have the better the chances that one of them successfully deleted their randomness their toxic waste all right but then verification from Genesis you know from the beginning of this is going to be more expensive so I'm not sure what that trade-off is there's a lot of flexibility in this protocol so like we could go up to a hundred and then cap it there for sapling and if everyone else wants to go further for whatever reason they could keep building on the first hundred that we use for sapling just for example what else so I mentioned that there's the circuit science parameter I think this is a good motivation that Shawn came up with to recommend 2 to the 1 but we've talked with some folks who say they are planning on doing zaps but they might need a much larger circuit so I actually have no idea what's the appropriate circuit size it's kind of an optimization challenge so it's hard to make a really small circuit that does what you especially if it's like binding digital signatures to the cipher texts of you know to the plaintext underneath some encryption maybe you get bigger and bigger circuits and it's hard to optimize them so maybe if not everyone has time to optimize their circuits really well that's a reason why we should make an even bigger one but again that feeds into the verification time maybe we should do multiple ones maybe we should do one for like two to the twenty one and also for a larger size as we mentioned saplings going to be on this better curve VLS twelve 381 alright but beyond 120 it's the one that's going to be in Byzantium right now there's powers of tell protocol I think works on both so but you have to do one or the other so maybe what would make sense is that we should have a process where we're doing both at the same time there's like a parallel track of the powers of tau all right and that may be you know we can do some process that still provides some benefit to the folks who want to build onto the zantium one all right the mean you know benefit of this one is that it has better security parameters and you know is much faster yeah anything yes that's right right not exactly the verification time for applications seems like it's gonna be constant I don't have the slightest idea Ellie it's all your hundred it depends even even tinier am I think has to have embedded a like a bound on how many steps to run so I have no idea what would be appropriate for that that's a good question something cool about this is that the cost of your phase 2 only depends on what you use so if we build the two to the twenty one and you only need a two to the 15 size circuit like you want a small snark then you know you your set-up time can be proportionally smaller oh sure right right yeah so if you had a project you're like I got it down to two to the 27 that's too you know too big it doesn't fit in here there's almost always a way you can break it down into multiple smaller circuits that you link together with them commitments yeah you can ask me about that if you want clarification on you know what that means but it's it's a standard trick in the yeah yeah oh you're saying even better than just the general line oh okay whoa okay that sounds awesome I didn't know about that paper re oh by the way here's like actual cryptographer so it definitely knows these things okay what else I mentioned this a little bit and kind of almost be repeating some points right the fact that you still have to do an independent you know second part of the circuit does phase two means that first sapling maybe we'll just come up with something and there's going to be some you know set of people that do the phase two but even there there's an opportunity for batching like we could imagine having all the people who participate in phase one because they want to build zaps also contribute you know they publish what their circuit is that they want compiled all right in this process and maybe when we go set up a phase 2 for sapling we might include you know some of all of these participants even in the phase two and try to grind out all of our circuits that we want to use at the same time all right you don't get like the amortized benefit in terms of how you know fast that is you still have to like do this separate work for each one of these separate circuits but you might as well amortize the like coordination effort in some way I think that makes sense all right and I think that what we should look towards in the future is something that doesn't just end at sapling but is like a sustainable snark set up as a service right where there's some process where if you come with a news app and you want it built maybe you don't have to work out how to do all of this yourself maybe there's something that we would do I could imagine set up something that maybe like takes place at universities or has some kind of like coordination that occurs like three times a year and you if you get your circuit included in the batch then we'll go through this process somehow and grind out that circus that's those circuits I like that I don't have much more details on how that would go just a thought at this point the fact that I'm out that was the end those are all of my slides so yeah that was the end of the brainstorm dump so more questions this says we have a minute what do you all think yeah and even like the trust model like so what happens is that in each of these faves there's some number of parties and it's still the same thing where one of them has to successfully delete their randomness in each column like in each phase yeah would you raise your hand if you have a circuit in mind or like you are a member of a project that knows that you want to use a snark in something like raise your hand if you're as that person okay that feels like Athena killing me that's amazing okay oh well sew it gracefully degrades even if you confer that yeah got it just have to know yeah but no yeah yeah yeah Joe has a pretty impressive line of work about how to basically squeeze high entropy randomness out of a source like a blockchain ashes like a proof of sequential work or a proof of time elapsing that kind of thing okay I think I'm out of time so I should let it go I just want to say if you raised your hand and are interested in zaps if you can find the Z cash foundation or the zaps working group mailing list I'd love it if you sign up or just try to contact me because I'm trying to build you know a list of everyone who might want to contribute in this way so yeah thank you all [Applause] [Music]