Scalability Solutions from zk SNARKs, with Mary Maller

hi everyone can you hear me okay good so I'm going to be talking about scalability solutions specifically from snacks today and hopefully I can say something interesting so when we're talking about yes okay sorry can you hear me now okay so when we're talking about trying to scale blockchains using snacks one of the classic ways you would do this is you would have lots of transactions which typically if you were to just use them normally every single person on the network would have to verify that every single transaction was correct they would need to have all of the data from those transactions in order to do so and this just makes things not scale very well if you have a proving system what you can do instead is you can have some third party who takes all of the transactions they do know all the data and they do have all of the information which they need to verify but rather than post all of this information to the blockchain what they are instead going to do is they're going to aggregate the information together and only provide a much smaller piece of information which you need in order to verify all of the state changes in one go you can't trust this person of course they might cheat but what the static lets you do is it lets you actually check that they haven't cheated you get to dis check a short proof that says if the aggregator has behaved honestly then this proof will pass and if they haven't then it will fail so there's no trust involved at all and definitely people have been already excited by the possibility this would have in terms of scaling Vitalik at some point wrote a blog post where he was saying that what you could get it down to 500 transactions a second might be a little bit of an over estimate but still and since then people have been working on something which is called zk roll up which is doing precisely this is saying if we have snacks are we able to compress down this data on the same okay this isn't so much related to aetherium but it is a project that I am really excited about it's called coda and what this one is doing is it's saying not only can we verify that the state change is correct but we can also at the same time verify that the previous state change was correct so you can have a snack of a snack from the previous state change and then the snack again with the next state change when the next sort of a validator comes along or aggregated sorry and what this means is you can get into a situation where in order to verify the whole block sorry the whole blockchain you can just verify one snack I mean you need to know what the current status so you you will have all of the addresses that you need to sort of check in the balances corresponding to them but actually checking the history is something you can do just like that UI is currently working on a scaling solution also luke Bringham aware has recently gone live with a solution and matter Labs is working on a solution as well and this isn't something which you can only do with snacks there are other solutions specifically Starks which have different trade-offs they are much bigger proofs and they don't scale so well for smaller statements but equally you get some quantum guarantees with them and you don't have any addressed setup issues have I missed any scalability solutions here so there's anyone in the audience that is really offended because I haven't mentioned their project so if putting this sort of more in a stark way it's not way rather than talking about blockchain and transaction and all of this what we instead have is we have a computation we have a description of a computation which is known to the verifiers and it's known to the prefer and the prover is going to compute the computation they're going to output the output of the computation and they're going to also output a proof that this is correct and this is worth doing if you have lots of verifiers because then every verifier can take that same proof and that same output and not have to compute it for themselves the property we need more than anything else in these proofs and the hardest thing in order to achieve is soundness we really need it to be the case that if the result is wrong then no prover is able to convince any verifier another thing that you can achieve as well as a property called zero knowledge this is actually much easier than the soundless property and for the zero knowledge what you would have is you would have that the verifier learns nothing about the input of the computation they just learned that the output is correct so this is very useful for privacy preserving solutions and yeah soundness is harder than zero knowledge because if you're working with very very small proofs it's only so much information you can really reveal okay the downsides of things that are making this quite actually hard to achieve at the moment is mostly proved a computation so we have a situation where if we're trying to compute the proof in order to give it to all the verifiers sometimes actually computing that proof would be more expensive than all of the verifiers checking the proof which is not great we want to get that much faster and this is more schematics talking about how you'd inserts nuts into the roll-up you have the state change you say this is what my state change is you still have to specify that but any information that you might need in order to check the state change typically things like signatures you don't actually include you just keep those in the stock and you verify the snack so the easiest way to do this uh Daan's the one that people are starting with is just with Schnoor signatures and these are the most commonly used signatures i would say anywhere for just sort of saying this transaction is correct so what we want to do is we want to make it so that rather than everybody checks there's no signature the the proof checks it but there is a challenge in this approach the main one being that the hash functions which were using inside tional typically sha-256 are really expensive to compute inside a snack like you're talking hundreds of thousands of gates which ends up making your pruvit just explode there are cheaper hashes such as MEMC and poseidon but the problem with these hashes is currently we have like asked people that work on hashes is that okay to use these and they've said no this might change maybe in a few years once they've had more time to look at them loading just say actually we haven't broken them maybe they're fine but for now the answer is it's a bit risky and there have actually been a couple of attacks already on MMC none over the prime ordered fields in which they're being used so they're more sort of breaking things that are over fields of size oh that's are described by something of two to the n rather than defined over a large prime we don't yet know whether the attacks might extend to prime fields but they might so one thing which is would be quite useful for rolling optional signatures would be to use a universal snack and in a universal snack what we mean is that the same set up so how many people in this room have heard of trusted set up lots of people not quite everyone and a trusted setup snack you have a situation where you have many participants who take part in something called a multi-party computation in order to produce the reference string the parameters which are needed to verify that your proofs are correct and if you have it that a single party who has taken part in this NPC is honest then the whole thing should be secured with a universal snack though sorry with a difficult trusted set up snack though the issue here is that you might have many different applications for which you want to be running your snacks over and if you have to have a different setup for every application then that becomes very difficult to coordinate it becomes difficult to check that the outputs are correct it becomes difficult to get people involved and just in general it is less flexible it's less easy to fix bugs if you have a universal snack you can use the same snack that's sorry the same setup across many different applications but you do still have that initial trusted set up layer where things could go wrong I would add here that if you're building any kind of implementation of any cryptography things can go wrong we're not perfect we're human mistakes get made so it is worth considering if a bug does happen if there is a mistake how are people going to tell you about it how are you going to respond to it is it something that you will be made aware of just in terms of best practice this is what you should be thinking there have already been a couple of setups for the sir on the online and which you can use as tech has done one and that's over bien 254 which is the curb that aetherium supports and its pre compiles so if you do want to use these setups and you don't need to do your own you can use a stencil I have recently been trying to implement Marlyn which is one of these universal snacks and solidity which I'm hoping that at some point people will be able to use I mean so far it's just toy coders no no in a production already and I have the solidity code and I can input a proof and it's verifying and it seems to be okay however I am running into some problems and my problem is that I'm trying to implement the prover in Python because I'm not somebody that wants to learn rest and in Python there's a library called pi acc which is very easy to use you just have simple operations add multiply powering but that multiply operation is taking me naught point naught 1 seconds and I didn't need to do something on the scale of a million of these which is really really not doable like I don't mind if it's slow because this is just a reference implementation I'm assuming somebody that does no rest will take it away and make it faster but if it's taking naught point naught 1 seconds I can't even run it in order to check that it works so if anyone knows how to maybe have a break have some sort of back-end C code which will make that one operation faster this would be really helpful okay the classic way to do this which I found out with some quick googling is to use siphon the thing that's unclear to me here is how do you represent you in two to five six types because these are happening all over when we're talking snacks and maybe you can represent them in siphon but there's not easy for them to figure out how for me maybe it's easy for you and if it is please tell me okay so we can not only roll up signatures we can also roll up snacks I mentioned earlier that coda was attempting to do this so many smart contracts especially ones that are privacy-preserving are not just using here's the state change here's my signature they're using some kind of snack in order to say I have done this computation correctly and please don't reveal my identity so in this situation you want to not only you you want to be able to approve a snack that mini start proofs have verified correctly and there are some great ways to do this which rely on curves within the curves the three that I'm mentioning well there's mt curves and these are good because you can have like limitless recursion you can have a snack of a snack or the snack of snack snack there is a recent paper called halo which was by the said cash team this doesn't work over pairings this works over just normal discrete log groups and it's quite exciting and there's also sexy which just allows you to do one layer of recursion but which is a bit faster than M&T curves the downside with these MNT curves really is that in order to get the same level of security you end up having to have much larger groups which means large approvers larger verify as large everything it's again unlimited recursion is really coolest so sometimes worth it like I said before hello doesn't use parent groups and one thing they've also motivated is this idea that you can have so two cycles so one parent group in one discrete log group and you can sort of switch between them that's not what they're doing they're just going from discrete log groups sexi was more designed around privacy so what they're trying to do is they're trying to hide specifically which our operation is being carried out hence why they only need one layer of recursion so this makes it more expensive than curves which require no recursion at all but certainly cheaper then curves with the M&T curves on ethereum we really can't use either of sexy or M&T curves because there's no pretty compiles and the fact that we don't have precompile just means that it would be far too expensive for the verifier to run yeah we can't do it but other downside to this even if we did have the curves working is that when we're trying to represent the snacks what we're doing is we are taking our snack verifier and we are converting it into a list of sort of constraints and this conversion process is actually really expensive you end up adding on I'm saying more than 10,000 overhead actually it's much much more than that that's a that's an under estimate and the result of this is the the thing I was saying before approvers are expensive enough that people are talking about or maybe if we have a massively parallel computer or maybe if we have an ASIC we can get this to work but currently it's just lagging behind the speed that we need one alternative solution which we've introduced recently is you can use something we're calling an inner product argument which works in the target group in order to represent snark verifiers so this over had it's not as good as six but it might be as good as ten it's really sort of the prover is fast it's not perfect in particular one thing that we cannot cover is we cannot cover snark approvers that are universal anymore because every Universal scheme that we have which is efficient enough has a random Oracle and random Oracle's are something which is just not supported by this scheme but we've a trusted set up such as snacks that are using glut 16 we can get it to work and save pruvit time and still get a pretty good verify time is logarithmic the downside to this one is that we need target group operations so target group operations are something which you can which I described how to implement and I go to paring based cryptography they're fairly standard but it's currently because other schemes haven't really been using them they're not included in the pre compiles so this means that if we can get a pre compile through which says here's some target group operations for any curve so it doesn't matter what kind of as long as there is one then we can use this technique but if we can't get that recompile through then we can't use that technique additional considerations that we should be considering if we're doing sort of roll-up style projects first one if there's only one aggregator how are you going to avoid censorship no matter there might be good answers to that but you know needs considering if there are many aggregators and your snack proofing is expensive and the aggregator has to pay the gas costs then you need to incentivize participation in some way and if you're going to incentivize participation then you might very well be having the aggregator being paid by the people that have taken given the aggregator transactions and then you have to think is this transaction also going to be privacy-preserving if that's what you're using your aggregator for or is it the case that by paying the aggregator you reveal your identity are there any more considerations that I haven't considered okay I realized that I've gone hugely under time here so I have lots of time for questions if there are questions yep but you might think like oh well this is simpler in some ways and it's simpler in the sense than it uses certain operations more versus less likely to see or decided but yeah they're like theoretical reasons why you would expect it to be hard I think possibly a bit of both the real answer is that we don't know yet but if you're thinking about doing things like sha-256 this is running largely over binary fields so every operation which your person that is computing the hash it's doing is really really cheap whereas if you're trying to do something over a prime ordered field which is you know suitable suitable for building snacks then every single operation that you're trying to do is going to be really expensive and this means that the number of operations that you can reasonably expect people to do is also much less so any hash function which is going to be secure in this setting for like similar computation costs you're going to have to argue that that prime ordered field is actually giving you some form of security and currently maybe that's true or maybe there's some subtle Grabner basis attack that people can use which would actually negate the benefits of having the large prime and that it was unfortunate that sha-256 didn't work well but maybe expected like you take the full space of going to hash functions I don't have a good reason for this but it feels like most of them probably aren't compatible just like chance but how much does this is like chance versus the end like you said the inherited there might be some inherent structural stuff there kind of like using time feel that actually fundamentally I'm not an expert here but yeah I mean with the char functions the reason they are so expensive inside the snacks is because inside a snack your binary operations cost exactly the same amount as a prime ordered operation which means that even though it's really cheap to compute negatively because there might be tons and tons of operations but they're all just binary operations you move that to snack world and that's not true anymore and that's where it's not surprising that the current ones weren't good but now we were optimizing for this new system naively you'd assume that once we have time we'll be able to figure it out and that's what I was wondering if it was more a factor of that lore there are these other inherent factors that make it harder also to say I would say we don't know yet yep you would be far better to answer than I am the general answer is just that be introducing examine the Jews consensus holes into clients so lots of the types of themselves the coordination to implement the school it's it's holiday wheelhouses so I think you have a sort of axles that are trusted and so there's a bit of nervousness like this and ultimately if we we implement a few different libraries and the libraries have affected them then we have potential small tip will have opposite determined that could be very interesting into video we have optimized for mining using different instead really scary things so I understand that there is AI people like every keen to move over to you too and all receptive to implement to these things it's sort of pottery equal great I think we can get the way that Raymond quickly is the threshold of confidence for introducing a pre-compiled should be extremely hot that's irrespective of the domain it turns out that this is a domain that it's not quite in line with the general expertise of the people you know we have the clients understandably and so that further compounds a challenge if there was an Oracle that gave you like perfect implementations that you were totally confident I would assume that it would happen pretty straightforwardly so it's just this practical security confidence consideration I seem to have a memory you got there was an intention to use like there was some meaning to us at some point but it's immigrated to that's not great that they asked oh thank you much for listening [Applause]