# Snarks for mixing, signaling and scaling by Barry Whitehat (Devcon4)

- Speakers: [Barry Whitehat](https://streameth.org/speakers/barry-whitehat)
- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2019-10-09
- Duration: 1:01:28
- Topics: blockchain, smart contracts, distributed ledger, Science & Technology
- Watch: https://streameth.org/watch/yt-lv6iK9qezBY
- YouTube: https://www.youtube.com/watch?v=lv6iK9qezBY

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on IPFS and more.
https://archive.devcon.org/archive/watch/4/snarks-for-mixing-signaling-and-scaling

There is general interest in the ethereum community to scale ethereum by moving dapps inside snarks. The key to do this is to make an efficient signature function available inside a snark. We present this signature function https://github.com/barryWhiteHat/baby_jubjub_ecc designed to work efficiently inside a snark. Furthermore we describe an architecture to scale ethereum using snarks. We discuss the trade offs required and compare them to building a dapp inside the evm.

Speaker(s): Barry Whitehat
Skill level: Intermediate
Track: Scalability
Keywords: scaling, dapps

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 4 was held in Prague, Czech Republic on Oct 30 - Nov 2, 2018.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

okay so last year around January no Iran December the year before yeah around December last year I started to work with snacks and thanks are applicable to two major things for privacy and for scalability so today I'm gonna talk about two applications to privacy and one application to scalability so the privacy projects are called Maximus in semaphore so makes a mess is uh is that is a generic either an e or C 20 token mixer where you can deposit money thir and later you can withdraw one either and there's no way to connect the deposit to the withdrawal and Saima four is if all it is very similar architecture and we use that to do to do general reputation mixing yeah so so you can you can become part of a group and you can signal things about your thoughts or beliefs or other things and no one can connect all people will know is that you're a member of that group and then we also have some rate limiting things there as well so that we can do like cooler public systems and then we'll talk about snacks with scalability it's okay you can come in and we'll talk about we'll talk about snacks with scalability so so basically we'll we'll build an elliptic curve inside the snark and we'll use that to make signatures and we'll use that also to Patterson commitments and then we then we sort of join that all together to make something called roll-up where and how what roll-up is is roll-up aggregates transactions together in order to it aggregates transaction validation so instead of having to verify 10,000 signatures inside the EVM you have to verify a single snag proof you can come in it's okay oh yeah who said that okay so yeah so then so that's that's what we use we use that's what roll up it's yeah it's just it's a scalability solution okay so first what is a snack okay so a snake is a snake is a way of proving that you did a computation without proving out proving that you did a computation correctly yeah so the verification of a snark is succinct oh wait I'll say that later so given given some inputs and some code that we predefined before we'll get some outputs yeah that's what that's what a snack proves yeah prove that we run the code with the inputs and got the outputs yeah but then we can do cool things right we can sort of hide some of the inputs and some of the outputs yeah and that's this is where we get our privacy properties right because we can start to hide things so or we can hide everything but that doesn't really make much that that kind of makes sense but not in not in a lot of applications okay so so for the rest of the talk we'll just talk about this code yeah so in the center box inside the snake we have this code that defines what we're verifying so we'd use that to verify that yeah so so that's the central problem that we're trying to solve yeah that it's difficult to make this code that verifies that yeah so it's difficult to define the computation that you're verifying you did correctly so so that's what we're gonna talk about later or that's like that's like the main theme of this talk yeah that will go through that and we'll see how it applies to three different solutions okay oh yeah okay so how does this relate to aetherium so so we can validate thanks inside the EBM although it's a little bit expensive it costs about five hundred thousand gasp at optimal to do that right now but there's the there is scope to reduce those costs so and this means we can have privacy and scalability yeah we can have privacy by just hiding the inputs that we have and we can add scalability because the the ballot the verification of a proof is succinct it takes the same amount of time no matter how complicated the the code that you are verifying is yeah so for the rest of the talk we're gonna define the code that we saw in the previous figure here yeah we're just going to define the code that defines the snack okay so a lot of the time in boxing we talk about a lot of the time in boxing we talk about Merkle trees right because Merkle trees are a good aggregator of information so this is how a Merkle tree works so basically you have ABC and D and those are the members of our group and we want to aggregate those together to a single root yeah so what we do is we hash A and B together we have C and D together and then we hash a and B C and D together and that gives us the root yeah so so sorry so we hash the hash of a and B and the hash of C and D together and we get the root so and then we can make something called mirco proof and prove that we remember and we can prove that we're a member of that set okay but so let's go forward okay so let's let's think about this now so so we can move we can move that Merkle proof inside a snack yeah and this lets us do some really cool things okay yeah okay so but but in order in order to so we can do cool things here but but it's there's nobody has any permissions here right because ABC and D are all public and that means anyone can prove that a B and C in the ABC or D are a member of our group but that doesn't really that doesn't really help us we want to we want to have a way that that people have some private information and they can use that private information to signal about to we want it we want to limit what people are able to do inside our system so the way that we do that is this that we come up with this really kind of naive we come up with this really naive kind of public key private key scheme yeah and the public key is defined as the hash of of two inputs one called it's not a fire one called a secret and another fire in the secret I just random numbers we just regenerate these random numbers and we hash them together to create our public key and we and we give our public and then we do something else with the public key so anyone who knows the private key of the public key is able to make a C but this is a little bit naive because if if people are able to make the signatures then they can always then as soon as you make a signature someone else can copy your signature because when you make the signature you reveal your private key so it doesn't really work but what we can do is we can put this inside the snack yes and if we put it inside the snack we can hide the notifier in the secret and that means that our signature scheme becomes kind of yeah that I signature seam now makes sense okay people can make signatures and it doesn't reveal what their private key so we can do this repeatedly yeah okay so but but now this doesn't really make sense as I said before right because we have we just people can prove that they're a member of this group the miracle that's defined by the root people can people can prove that they're a member but that doesn't really make sense because we don't reveal anything and if you give that proof to somebody else they don't even know what itwhat is talking about I mean they just know that you don't they just know that you're a member of song Merkle root and that doesn't that doesn't really make sense so what so what we need to do is reveal the merkel root yeah and now it starts to make sense yeah and that now the Merkel root is public to the verifier and when they verify it they can see that oh this person must know the private key of a member of this of this group okay oh wait what does it say is there some way for me to know the time okay I can I can see okay okay so so now we can use it okay so this is already enough to do some cool things okay this is already enough to do to make a mixer okay so this is what it makes me smart contractors first of all a user deposit and either into the contract and I and then the contract will allow them to add a leaf to our group yeah then a user can use a snack to prove that they know the secret information of a leaf in our in our group and users who prove this can withdraw coin and this this work and because the only thing that we reveal in the previous because the only thing we reveal is the merkel root there is no way for anyone to know which leaf LED to which withdrawal but there's a problem with this so does anybody know what the problem is yes sorry okay yeah that's also a problem but that's not the one that's not the one that I contrived to talk about next so yeah that's definitely a problem but the way that we solve that is that we limit it to one ether per deposit and one ether Patrol and yeah so it is a problem and there's wasted six atom and we can talk about those in a while but has anyone another a problem yes yes exactly you can do a double spend right because nobody because you just proved you're part of the Merkel route yeah and people can people and just take out coins again and again as long as you're a single member you can repeatedly take money out because there's no there's no sort of there's nothing to prevent you from from double spending yeah it's the double spend problem because you just don't have information about about who was withdrawn previously so okay how do we fix this problem does anyone have any ideas yes sorry I didn't hear what he said yeah that would kind that would kind of work but if people because everyone uses the same balance it doesn't really it doesn't I could just deposit the same balance as somebody else and just take I could take all let's say one either is a popular amount I could just take one either is out a bunch of times but yeah probably to nullify exactly so so we kind of contrived to have this nullifier here previously as part of the public key and that's why I didn't just call a private key so so what we do is we we publish the nullifier yeah we make that public and then in our smart contract we remember that whenever someone uses a certain nullifier we remember it and then we prevent people from withdrawing with the same nullifier twice and so this actually introduces another problem that we need to think about but it's kind of outside the scope of the talk but but the problem is that that there's like a griefing attack here that's someone could someone could see that I'm trying to withdraw a nullifier X and quickly deposit deposit nullifier X again and then withdraw that and then my would role would fail but this is a griefing attack and it's like $1 for $1 I mean it's very expensive to hurt people with it but yeah it's definitely problem but but yeah there's ways to fix it but it's kind of outside the scope what we only talked about okay so now we can check yeah so now every time we withdraw we make sure that that coin hasn't been withdrawn already okay so that's how makes much worse I mean that's that's that's that's exactly what we have currently in the github okay so we have some problems with that and I'm one of the major problems is is who pays for the gas right so the thinking is that if I deposit one ether and then later I deposit another either I need to have gas in that account in order to pay for the transaction fee of the withdrawal and because I can't do that yeah because now you have a chicken and egg situation it's like I had this anonymous money but I need non-anonymous money to take it out so that becomes a problem so so there's a way to solve that I don't know if I talked about that in the next slide or not no so the way the way that we saw that is we do like layer two transaction abstraction which is oh it's actually called meta transactions that's the new name for it so what we do is a meta transaction where people get a fee for broadcasting these proofs and the fee is like a portion of the amount of money that you deposited okay so then problem number two is that people can analyze the inputs and the outputs to track the users yeah and so this is more like a temporal attack and you can use these heuristics to let's say that let's say that I deposit one either into the smart contract and then I would throw that one either in the next block I mean it's very obvious that it's kind of obvious who deposited yeah I mean you can't connect them cryptographically but you can come up with these sort of clever heuristics about about how much you can how much you can take in and take out and that's part of the reason why I prevented the having multiple amounts because because if you have multiple amounts the amount that you would draw is also an indicator of who deposited yeah and let's say that I've deposited one point one five six seven either and then someone later withdrew one point five six seven either it's a good bet that it was me it was my withdrawal I mean what we want to do is maximize our privacy set so yeah so that's that's know there's some thoughts on that so we have a proposal for the layer two transaction abstraction and hopefully we'll be able to sort of merge it with with someone else's but anyone that's kind of future work that needs to be known okay so can we allow multiple deposited sizes and that's kind of that's kind of whatever address and yeah it's also trivial to to allow here C 2012 in deposits and withdrawals but we need to be careful about the privacy set again if these tokens have sort of low volume then it's unlikely that people will be able to get these if these these transactions have low value but it'll be unlikely that people yeah I mean people might think that this is really super private annum and it might not be I mean it's just something to be aware of when when about these things because yeah okay and then there's like other kind of further research questions about how can we can we increase the size of our privacy set by being able to trade from one currency to another privately and that would that would be kind of cool I mean that would that would sort of marriage are separated here see 20 tokens into a way that that we could into something that makes a little bit that has stronger anonymity properties but that that seems that seems to be a difficult thing to do but we can see that that sort of future future work okay so so basically so that's the end of mix Emes okay so so that's that's that's all I really have to say about mix mix for now so it's a general token mixer that you can use to mix your ether or your tokens so this is this is this is like cool it's nice work but it's a little bit it's not really very it's very similar to see caches work and I mean it's similar to things that already exist I mean they don't exist in material but it's like work that's been done before and it's cool but I would sort of search for other ways to use snacks to do other things so the thing that I'm actually more interested in is is something called semaphore which is which is very very similar to to mix mess so so instead of instead of depositing one either and being allowed to join the tree we come up with some other rule that lets people join the tree yeah we could have like a sign-in with github button and people who sign in with github are able to are able to join this Merkel tree and and then they can make proofs about things yeah and if they don't sign in with and we sort of limit the amount of members in the group so this this tree becomes like a proof of github yeah and anyone with github is able to is able to make signals about things so how do we do this how do we make like a generic signaling application and the way that we do it is so so basically we have a lot of what we need already yeah that's very similar to make suppose we have the same public keys and private key I should do the air quotes when I say public key private key we have the same setup and then we have a Merkel tree where we aggregate all of these together and then we put that inside the snark and we add you see here you see here in the we we've added the idea of a signal so this signal is just like 32 bytes and it says it's the hash of something that you want to say I mean it could be the hash of a tweet or it could be the hash of of a vote or it could be a hash of something else yeah so we include that yeah so yeah so we include the signal but we still have another problem and what is the problem does anybody know yeah anybody else so think think about the difference between what we do it makes it makes a mess like makes a mess is we only want to use maximus one time but this we want to use multiple times does anyone have any ideas so the problem is oh yeah sorry exactly yeah so the answer is that you you you you if you reuse you we force you to reuse the same nullifier here and when we force you to do that you can link different signals together yeah so if I say if I do one tweet and one vote the nullifier will be the same and I will I will be able to link those two things together and it still has like it's still anonymous ish but because you can connect them together it's it's not really great because I mean because we don't really want to do that I mean we to be able to tweet and vote and do a bunch of other things and have them disconnected from each other yeah so the another pilot so how can we fix this does anyone have any ideas sorry how should we the counter yeah that's right yeah so we are so we had this idea of an external nullifier yeah so we hashed the nola part with the external nullifier inside the snark and I mean this gets a little bit a little bit messy but but yeah that works so we have this external nullifier and we hash the two together so now our expert are our our new nullifier will be unique because as long as the external nullifier is different then each signal is unique and we can limit people from making multiple signals about the same thing but we can't connect to say two different signals about two different topics together okay okay so now I have two examples let me see what time it is okay so this is this is looking good so we can we can talk about at least this example it may be another so so like this is this is this starts to get a little bit complicated so let's do an example to make it to make it a little bit clearer so so let's do first-past-the-post voting yeah and let's just think about that so first-past-the-post voting is just where everybody votes and then you count the votes and whoever has the most votes at the end of the count wins uh maybe that's not exactly what yeah that's that's what that's what I'm talking about anyway I'm not sure if that's the technical definition of first-past-the-post voting but yeah okay so so let's say that everyone in this room comes up and we vote for some decision yeah weather weather zero or one weather weather people thought to have come was good or people thought that one was bad good okay so we have this binary decision and we and we come up with some framework so we say that okay we all agree on the same signal yeah and the signal is wait yeah so we all we all agree on the same signal and the signal is that DEFCON is bad we have another signal and that signal is DEFCON is boo good yeah and people can vote and we'll count up all of them together and at the end we'll we'll we'll see who thought how many people thought everything was good and how many people thought they was bad and then finally we need to think about their external nullifier so who thinks that we should use the same external nullifier four four four bolt signals okay and who thinks we shouldn't use the same external notify for both signals okay okay so if we don't use the same external nullifier for both signals then then people would be able to vote I think that one was good and I think that one was bad and we'll have no way to detect them so we need to vote we need to have the same nullifier external nullifier for bolt ok and this way you can you you can link the votes together which kind of sucks but you also limit people from voting twice which is definitely a good idea okay so now we can let's talk about something a little bit more complicated so we can also do like proportional representation and proportional representation is another form of voting where when instead of voting like having a binary choice you can you can choose among multiple multiple different choices so the idea so that's that's a spanner or a previous example where we had oh I think that program was good I think that wasn't bad and now we can add a third one I and say that I think that one was okay but I think I think we can do better next year so that people can people can choose oh actually that doesn't really make sense I think I think I think it makes more sense for like leadership elections so let's say that we vote between an elephant giraffe and a kangaroo to be our to be our leaders okay and we want it so okay so different people like different animals more yeah oh let's change one of them to a lion so an elephant a kangaroo and a lion yeah because this makes more sense okay okay so okay so we're voting between a elephant kangaroo no line right and we want to pick yeah so some people really some people really don't want to vote for the lion so oh wait I'm explaining the the benefits of proportional representation and I shouldn't do that because on topic okay okay so okay so yeah so so basically we can do the same thing but for the elephant the lion and the kangaroo they each have a different signal but the external no the fire always stays the same okay yeah so that really makes sense from it's very similar it's a previous example okay okay so let's just keep going I mean here's the current problems with with with some before so chemists so can we build a proportional representation where you can't link the votes together because I mean in the previous example it's clear that we have to use the same external nullifier I have for each signal and that kind of lets us that's us link that oh I voted first for the kangaroo and then for the giraffe and then for the lion and that's that and that will reveal information about the electorate in general and maybe we want to stop doing maybe we want we don't want to do that yeah so that's one thing but that's really complicated and can we do quadratic voting like this that's another interesting question there's like a bunch of application for some before that that haven't really been explored again how do we pay the gas that is if you do this if you do this on chain but I don't we change stuff with this but in general it makes more sense to have it as an option of chain scalability solution Ono obtained signaling solution I mean it just works a lot better because you have to pay five hundred thousand guys for every vote which is which it doesn't really work very well okay and then can we make deniable signatures so this is this is more to do with like anti coercion voting oh no bribery resistant folding or coercion resistant folding where where someone can force someone to either through physical force or through money to or they can pay them to vote a certain way and this is about dayum we all agree it's about thing and we should think about how to solve it and there's and there's some ways that we can do it but they're kind of outside the scope of what we're talking about here but if anyone's interested to talk about that we can talk about it later okay so now now some more limitations of the snark work that we've done so far so the proofing time is is is quite long for Maximus in semaphore it takes about I have some numbers here oh wait no I'll talk about that in a minute okay so then there's okay so this is so so now we've talked about makes a mess and we talked about semaphore and we see that we see that in that we have some cool some cool things that we can do with these so there's a point and there's a bunch of like open opportunities to continue this work and to do other cool stuff with it for example we could have a yeah so example we could have we could we could build this kind of group I mean we don't really have any groups in semaphore yet and it would be nice to have a group of people who could signal about something together and then we can expand it so one way to do that is to have a like we have to have a way to limit the amount of people who can join a group otherwise you can just join the group and and signal about whatever you want yeah I do sock puppet attacks and things like that which we know soft but it's a puppet attack is where it's where like you see this really interesting discourse on some social media platform but it turns out it's just one person with many accounts talking to themselves and it's a way to sort of propagate your ideas and force the discourse on the topic in a certain direction and in general I think this is bad and this is bad and we should we should find a way to stop it so one way the way to stop it is to limit the amount of people who can join the conversation but we also want everyone to be able to join the conversation we just don't we just want everyone to be able to join once so there's a bunch of ways to think about how we limit people from joining them and one of the and one of the ways is although it's really it's really it's not very strong it's very weak is to have like a github based Merkle tree joining and we have some other and then there's some other ways to do it and I can talk about those later okay so then the next idea is to is to build on top of some sort of membership requirement to build on top of that and to make some sort of social media platform so this would be a little bit different than the ones that were used to that instead of having like a person who tweets about something we could have a it's a very impersonal tweet about something we could have a group yeah you would join a group and your group would engage in discourse internally and externally so you could see a group of people discussing something and some of the people believe something and other people believe something else and I think that if we remove like the idea of the self from this I think we remove the idea of this self from this then we can I think it will lead to like more open discourse so so this is like sort of a philosophical tangent that I'm gonna go on but this is this is what I this is this is my sort of reasoning for this it's not like in general in life it's normally it's easy for people to coordinate inside a group it's easy for people to say oh listen I think this and I think this and people have this sort of healthy discourse and then they agree or disagree and this is this is very good for everybody but but sometimes this is not possible sometimes like for an example sometimes a minority inside a group can be oppressed by the majority and the majority can impose some sort of costs on the minority when they try to coordinate and it comes and and this will lead to a point where with the minority are unable to sort of even admit that they're part of the minority because they're afraid of oppression or something like that or they're afraid of some sort of consequence for this for this admission and there's been a bunch of rights movements that I've been around that have standard around people saying that oh I'm part of this group and and revealing that and paying this kind of high social costs but that's like not very good for everybody I mean there should be a way for people to coordinate without having to pay this high cost and one of the ways for people to coordinate and not pay this high cost is to make these like anonymous signalling groups yeah and people can say it can can anonymously say oh I'm part of this group without revealing which part of which member of the group they are so they they they can't be they can't be the victim of some kind of oppression because they didn't they or it's more difficult for them to be a victim of some kind of oppression and they're also free to sort of express this belief and this I think is a healthy thing for society in general because people should be free to sort of coordinate with each other and express their beliefs and I think that when yeah yeah okay so that's that's like the end of the philosophical tangent but that's that's that's that's why we need to have these sort of anonymity system or systems with strong anonymity properties so I'm very interested in people are in people who are interested in working on this in billing things with time before and please talk to me afterwards if you are there's a bunch of but there's a few people working on this and we're happy for other people to join and there's a lot of open opportunities so so then so then we can have anonymous credential systems and this is where you can just sign into something without revealing who you are and we can and that's a whole other use case that we can have then we can have reputation systems and it's in fact we found a way to build a reputation peace system where where you can kind of exclude someone from the group if they if they if they if they break some rules so let's say that I have like a VPN server and I'm like I let everybody use my PP on server who's in this it was in this room I at the end of the thing I just go around and I collect everyone's private key and I say ok everyone's allowed to join but then or some someone sites to use this VPN all the time and they use too much of the bandwidth and I have to remove them from the system so there's this kind of talks that this post here talks about how we can do that and what we can do yeah so this this post is each research post talks about how we can do that and and other things about that and yeah so it's sort of the limits and trade-offs and whether it is useful or not no this is definition that we can go in with some four seven four okay so there's a bunch more stuff we can build with some four and I kind of think that like not enough people are working on this so I'm happy to sort of talk with people afterwards or during the question answer session about this and yeah hopefully we can sort of do some work together okay okay so then also I want to promote this ethnics so as Eric said SMX is this theorem snark project that's funded by the ATM foundation that are moving forward with some of the the lower-level equip the graphic primitives that we need and they're doing a bunch of good stuff and if anyone has some C++ experience or wants to learn a little bit about snacks that this would be a good place to sort of contribute there's also Socrates and circum I I think I have circum later but I'm sorry Socrates it's also a cool project I maybe had them later so so we also use a or C 20 tokens oh yeah so this is other things we can fix with Maximus so we could make a pull request to include ear see 20 tokens ethics have re-implemented it being a much more efficient way and it'd be nice to sort of port their work to the original repository yeah and then it would be good to merge mix in seven four together because they're so similar it would just be good to have a single a single repository okay and then then this other work to do we can replace the hash function which I'll talk about in a while and then there's also a bunch more some before use cases that that'll be nice to explore and talk about okay so let's talk about some of some of the figures of what we have so so okay so so the hash function so we need in order to make a Merkle tree in order to make a Merkle tree we need to have a hash function and a hash function that we use right now is a a 256 and char 256 it's very expensive to do inside inside the snark because it's based upon binary operations and I'm gonna talk about that in a minute so improving time in seven four is about seven minutes and the Merkle tree the depth of the Markel tree is 29 which means there's like 29 hashes so that's yeah so it's quite expensive but that a the tree is very big it's enough for like 500 million people to join so on my laptop it takes about seven minutes and it needs a lot of problems it's impossible to run it on a smartphone and this is a problem so it's about 50 K constraints per hash which is which leads to 1.5 million constraints altogether and this makes the proof this is the reason why the proving time is so so so we want to minimize the we want to minimize the proving time so we want to meet early so we want to reduce the number of constraints so let's talk about how we can do this okay so inside of snark we can do a time we can we can do this we can sort of check these assertions yeah we can check to sight Chinese and sign kinds of assertions we can say that a multiplied by B equals C and we can check that we can check multiplications and additions so we can also replace a and B with a bunch of additions of something else yeah where it can be the sums of things yeah so then we can already do cool things with this I mean we can already implement every company computation with this right because we and the way that we the way that we end up the end of doing it is okay for example can can anyone think about how to do how to design an xor gate with this I mean maybe this is probably not a good interactive question but this is a good sort of learning experience to make an xor gate at the start and just see how you can make these constraints also I have a list of these problems that are kind of interesting to approach you at the start so if anyone's interested in that please let me know yeah so sha-256 is binary operator it has a bunch of binary operations one of them is an XOR and then there's like Sigma shifting yourself and a whole other bunch of stuff so what we do is or what other people have done well the lipsmack people have done it they've implemented sha-256 they've implemented it in in lipstick and and they've just built all the basic gadgets and plug them all together so we can we can we can already do this but it turns out it's really expensive because we just turn everything in a binary and inside the binary we use we can just do zero on one where we have we can actually do a lot more expressive things inside the snark so how can we can how can we improve this so let's talk about what we can do inside a snack so we can do this a times a times B equals C where a and B and C are all these items and we can also but we have to be careful because we have to we have an overflow so snacks work over this prime field and if we get to this number which is about 253 bits which is 253 bits we will overflow I mean if we add one more will overflow and so we wrap around at this other number down here which is about 200 to 250 bits so a turn so that means that we do all our arithmetic modulo P yeah where P is where P is a prime number so does anyone know how this can be how we can use this anyone have any ideas how we can use this to build like an interesting interesting things this is it this is a difficult question yeah okay so it turns out and we kind of use this to build elliptic curves yeah because okay so if we take a look if we take an example of psychic it's like P 256 K 1 which is about where P is to 256 bits all operations occur so it turns out that we could we could build a comparative elliptic curve inside the snark and do and have all our reason to take modulo P done for free so so we just do regular multiplications and additions inside this now I kind of would turn out that that would be that those those operations were done modulo P so so why don't we do this with Zack P 256 K 1 the reason that we don't do it with this curve is because they have edge cases that the when you when you try and double points okay so if people are like strolling to follow that's okay I mean this is this is this is kind of a little bit difficult stuff and it's gonna get easier in a little bit it's just I'm just talking about how to build these krypter krypter graphic primitives for like two more minutes and then we're gonna get back to the regular kind of okay now we put this here and now we put this here and how do we build things with this okay okay so so the reason why we don't use the reason why we pay so we use it twisted Edwards curve yeah we use it twisted Edwards curve down these are the formulas neither point additions Ouisa twisted Edwards curve because it doesn't have edge cases when you when you double the identity or you yeah when you double the identity or you are their identity to something else so in general in science we don't want to have it if we had an edge case we'd have to have if we had an edge case we'd have to have an if loop and if we have an if loop that's that's not very good inside the snark it's just really expensive to do in a loop because we have to do everything a times B equals C which which is really okay there's another example how do you make an if loop with a times B equals C it's totally possible but it's it turns out that it's it's prohibitively expensive when you do it a bunch of times okay so this is the curve due to these are the point multiple so then okay so inside the curve we need so we need to be able to do two things to do a little cryptography the first thing is to do point additions which is easy we can use these formulas here and we can implement implement those inside the snack easily the second is to do point a to point multiplicative multiplication and we can do that too it's just a little bit more complicated and we just do a bunch of doublets actually scalar multiplication just degrades to to just additions well yeah we can figure that out too and you yeah we can figure out a 2 and we can use window exponentiation we could switch to window exponentiation which will save us a lot of constraints and add snags have done that already there there now we come in the canonical implementation although circum have a competing one and Socrates are gonna make their own implementation soon so we're gonna have a bunch of these implementations that people can use to do electric art stuff I hope it's okay that I said that okay okay so then these are some links that will teach you about elliptic curve operations and how to do that and just a general background yeah because this is I mean the last couple of slides were generally difficult off and it's okay that if you didn't understand them I'm and now we're gonna get back to that oh yeah so I just had some future work about this so and then we're gonna get back to the regular stuff so I'm not sure that link is right but you guys you folks can find it okay so so future work so the first thing is that this this this work should be treated yeah this work hasn't been reviewed and I don't think that anybody should use this in production until it's been reviewed a lot this is like the rule in crypto waste or the rule in crypto currencies is don't roll your own crypto and I did okay so so please be very careful about this also if you have crypto cryptography expertise it would be I'd be very interested to talk to you about sort of reviewing some of this work and so more people can use it but at least we should say that it's possible to do this kind of cryptographic stuff inside a snark this is yeah this is at least an example of how that's possible so it's for pedestal hashes and signature scheme which I'll talk about in a second yeah so okay so we'll be good to get some review and here's where you can review it and then there's possibility that we could build bowler proofs in the same way and embed them inside the snack and that's a nice interesting that's interesting like a research problem and then there is also it would be cool if we could do like recursive snacks or at least requires one layer and then we can do something like the sea paper there was this paper recently about using recursive snacks to do like private smart contracts so that would that's an also an interesting sort of future future direction okay okay I know also I want to say thanks to Dario Hopwood and and for for help and advice about this as well as the Z cash team who had done who III who had done very similar work before me and really lit away from me when I was doing this it specifically this issue you can see it's so cool they just describe everything or every single step of their decision-making and then they also have a blog post about about how to do so and actually they're using it now in the wild so they just had a couple of days ago another they're using Patterson commitments oh yeah so I should have talked about that oh sorry okay so so what can we actually use this to do like what is the what is elliptic curve inside it's not useful for and the answer is as you said as you asked Patterson commitments and and signature scheme so on top of this on top of this we built a I built a Patterson commitments and signature scheme and ethnics have also implemented it so and zk are now using this in the world they've had a daughter did although their work is is a little bit different than ours because they use the different they do use a different curve and that means that they're yeah so their their work is not directly trans transferable but it's still like a proof of concept that this is possible okay so a big nice alignment congratulations that I'm on their recent hired Fork it's cool okay so next we're gonna talk about we're gonna talk about scalability so 20 minutes cool okay so next we're gonna talk about scalability so so far we've done so far yeah so so far we've just talked about using using snacks for privacy and now we're gonna talk about using snacks for scalability so we can so so the thing that we were missing was a signature scheme before before that we weren't able to really use it for for privacy but now we can or for scalability but now we can so here's here's what we do we take the we take we make this new form as opposed to before where we had we just had the private key be just this simple two images that are 2 2 this is just secret key that we hash together we got the public the public key we replaced this now with with this new construction this is for this is for a generic database yeah a permission database so in the tree we have a B and C and each a B and C has a public key associated with it as well as an object so the public key tells says it says who is allowed to update this object yeah and the object can be whatever you want it to be it can be like a list of tweets it can be your token balance it can be a bunch of other things as well so this is like a generic scalability solution where you can update these leaves in the Merkle tree in batches so myself yeah okay so the way that this works is that we have a single prover yeah and we have a bunch of users and what the users do is they aggregate signatures together and know what the users do is they make signatures and they pass it to the prover and the prover aggregates these signatures together and use and makes a ZK start to prove that they updated the Merkle tree correctly so let's see how that looks yeah so this is what they do they have the old Merkel route then they have a snark where they prove that everything was done correctly that they did where they validate a bunch of signatures and then they have the new Merkel route yeah and this proof is proof that they have possession of these but that's so so they so for example they can't update the tree they can update and take someone's money unless they have a signature to send it somewhere so what the user does if they want to send if they want to update the leaf is that they sign a E and B yeah and then I stack those the following things ok this Naik check that the signature match is the public key pop key here and B oh yeah yeah checks that this signature matches pop key generates the leaf B by hashing with the object that that's that's that the user probably also provided check start that leaf is in the tree and then replaces that leaf B with the new leaf e okay so you see what happens you see what happens you can go like this yeah okay and what we do is we have a snack that proves that before we had we had root and now we have updated root so the so we use a smart contract to verify each transition and now the operator now we now we know we have a smart contract that validates each transition and now and now we have a system where the we're sorry now yeah so this is just a general scalability system so we know and so now the operator isn't able to isn't able to update the tree on that's the users allow them to unless the user gives them a signature and says ok I'll take my Leafs a - a - yeah so that makes that make sense I mean but this is this really doesn't work as it is right because this really doesn't work as it is because it costs 500 thousand gasp to validate the snark right and it costs like less than ten thousand gasp to validate signature inside the snack inside the EBM so why would we use this does anyone have any ideas okay so so patch yes patch them up because the verification of a snack is succinct we can include as many as we want inside the snack yeah so basically instead of instead of using this for one signal transaction we use this for like ten thousand transactions yeah so we can aggregate together ten thousand transactions and we can and we can use this to update the merkel route so this is where we get our scalability benefit yeah so now it takes five to five hundred thousand got five hundred thousand guys to validate ten thousand transactions which is great I mean it's great we're moving things are getting cheaper okay so so now just to summarize to link the cryptographic so to cryptography stuff to here so what we did before when we define this twisted edwards curve that we were using is that we we wanted to make a signature scheme and we need to make a signature scheme so the users could sign something in the and and the operand the prover wasn't able to just sort of steal people's money and move things around so we made this signature scheme and now we just validate a bunch of signature schemes inside the snark and we update our route yeah old road new route perfect so we do that okay so we do that a bunch of times inside the snack we have like a for loop and we end up with just a single proof that we had transition a to be correctly new routes to new route correctly okay so what are some problems with this okay so some problems with this is is the proving time so the proving time is quite quite high I think you can prove on unlike regular hard way to 220 million constraints and that's about enough for maybe twelve twelve transactions but but that's not our limiting factor here so because it turns out that we can use the AWS Amazon Web Services to do two boxes or another cluster yeah just an e cluster to pass these transactions together and to make the proofs but this cost money but it doesn't cost a lot of money it costs like $1200 for a proof which is totally which is totally fine if you if you doing $1,200 for 10,000 transactions that works out really cheap yeah okay so and we can use Paris and commitments it's difficult to have a hash function that's efficient inside the snack inside the VM but I should talk about that in a while okay so now our only problem becomes this our only problem is now the data availability problem yeah that we know that the operator can't steal people's money but we thought the operator is able to be able to block people from getting their money and does anybody know how they do this yeah okay yeah they refuse to publish it yeah they refuse to put so so someone does a Merkle tree update yeah and then they refuse to update publish to people the merkel leaves that they need to make the proof yeah and when you refuse to do that nobody is able to move their money anymore so now let's talk about sort of solutions to this oh I'm almost done okay so so one of it one of the ideas is is is this thing called roll up and roll back yeah so with roll up what you do is the the prover continues to update the miracle tree they do these transitions and then Annie and then and then we have this we have what we what it's called yeah so it's similar it is similar to pass my exists and we can we cannot let merge and split leaves it's just like it's just like plasma or cache I think where you have like these independent leaves and you can't join them together but you can send them to other people [Music] okay so that's so one solution is roll up yeah which I'll talk about in the next slide and the other solution is to is to pass all the data from the EBM into the stack yeah and I suppose about this and I'll talk about this so so how this roll up roll back work and roll up roll up roll back is actually called nazma roll up roll back is the old name so so we have a priority queue okay so so listen we have so the operator aggregate severence transactions and they and they go block at a time block at a time moving forward with the chain and then at some point in the future let's imagine that our operator becomes malicious and they refuse to publish the the the Merkle path or the merkel leaves that you need in order to exit your coins so what do we do so we have this thing called a priority queue a priority exit queue and basically anyone who enters the priority execute is able to is anyone who enters that queue the operator must serve that key within a timeout that we define like a week two weeks something like that and if the operator doesn't it doesn't doesn't fulfill that request what we do is we slash the operator and we say that okay data is now unavailable yeah and what we do is we start to we do two things now yes and we start the world back mechanism so roll back okay so here's the current his let me set the stage so we have the operator has been running for a while for five states yeah we started at s1 where the one person deposited one coin yeah and we know that data is completely available then then we move then we we started to move forward the operator makes nag proofs and validated them on chain and we ended up at say five yeah and I'd stay five the operator refuses to share the data so I'd stay five we enter the priority queue and the operator refuses to refuse it to exit us so what we do is we stash the operator and we have this kind of option for a new operator yeah someone else to take over the chain um when you bid in this option what you have to do is you say you say the state that you want to begin from the state that you want to take over from so you don't have to continue from state five you can continue from any previous state so you say the state that you want to continue from and you say you say the state that you want to continue from and you say how much you want to put as your deposit yeah we have liked this idea of a limited deposit and something something like that that's fine so so we finish the auction and we select the the bidder who selected the newest state with the highest the highest bid yeah and then what we do let's say that the new operator yeah so the idea is that the new operator will never will never ask to continue from a state where they have all the data available to them from the state where they don't have all the data available because they will be trivially slashed immediately yeah and they'll lose all their their whole deposit so then let's say that their of the new operator comes and they say okay I'm gonna take over at say three so what we what we do we have this transition from state 5 to say 3 so what we do is we say that ok anyone who has an implied transaction between state in state 4 or state 5 is able to exit yeah and we have another period where we have this kind of plasmus dialogues that where people come forward and say ok I want to go I want to leave and that works out fine so so then we roll back to state 3 and the new opera continues yeah and if no so if no operator comes forward and says listen I want to continue we just go all the way back to state zero and that's just basically a plasma exit it's more ordered though yeah yeah ok that kind of works but it's it's there's a bunch of problems with that and one of the major problems is that you can enjoy and leave together for a reason that I can discuss afterwards that people have questions about it and another problem with that is another problem with that is like this idea of finality that you you don't know that you you're not guaranteed that your state is not gonna chain rule back but we can have this kind of weaker for now the assumptions and you can say that listen if I have all the data for a single for a single state I know that if there's a I know that someone will come forward to take over from another state or I can come forward and take over from that state so people will know that okay we only roll back a little bit okay so that's that's kind of that's kind of how roll up roll backs nazma that's how stance my works okay okay so now the other option is to do that availability inside the chain and what we do is we just pass all the variables from the EVM to the snark and we verify we bear and this way no one is able to no one is able to yeah this way the data is definitely available we rely on the theory availability guarantees yeah about this this is kind of this is not great for two reasons for some reasons it's it costs a lot of gas per transaction which sort of limits our scaling not at the amount of proofs that we can make or the size of proofs that we can make but at the cost per transaction so we limited by gas inside the VM because we have to pay gas every transaction that we include yeah yeah so I talked about compressing here but I all sort of leave out the new ones of that but yeah we have to compress the data to inside a bimbo compressing is just hash together so that works that works too and this is kind of the approach that we've sort of moving forward with at the moment so these comparisons with plasma which I already did okay and then I have two examples so this is like alright let's finish the I won't do the examples because because we only have like five minutes a minute left yeah okay so let's just talk about yeah these two exams quickly so one is you can if T and this this was done at a hackathon in Berlin by a bunch of people and I would say their names what I'm not sure they want me to say their name so I won't yeah okay so yeah so basically they did and not non-functional token with roll-up ana works pretty well and we also are me and a few people are working on making some sort of generic token with this we can just patch talking transpose together yeah and if we were gonna use that available in chain as I said before and each each leaf has a variable amount you can trade tokens for to each other but not spit oh oh no users can split two tokens that's not right that side and users connected leap what the leaf is no wait that's not this light is wrong okay so let's talk about roller problems really quickly and then then we'll have some questions okay so so one that one problem is that the proving time is quite big and we need to outsource this is quite long it takes okay so it takes about it takes one hour and a half to prove on AWS and it costs like $1500 a little bit less than that and we want to reduce this and we think that we can reduce it but it will get more expensive and then there's other way to reduce it to instead of using the cluster we can use GPUs FPGAs and Asics and those are all open open areas of research that or implementations that I'm interested in to talking to people about if people are interested in doing that that's cool come and we can talk about it can we add strong anonymity properties to this system that's another research question because everything ok everything is completely transparent here just because we used to start to aggregate the data it doesn't mean that doesn't mean that we still have the anonymity properties that we had before so is it possible to add those anonymity properties back that's another interesting question so we have optimizations yeah so it's it's interesting it's this add snarks project have done a lot of work with with these these optimizations this is move forward quite quite well also ID ID entry have another implementation at sites are working on implementation I need three are working on implementation two [Music] yeah and we're gonna replace you are 256 with pedals and commitments in some places good so future work yeah so we want to implement both approaches yeah so if so many if there's if someone who's implement interests in implementing the other approach the it's not as my approach would be interested in that too and so we're interested in hearing about generic other use cases other than just scaling and tokens or tokens and stuff like that I'd be interested to hear all the use cases that we can use it to aggregate transactions together and aggregated like bolts and things together I know that comes with a bunch of problems still oh yeah we could do that too non fundable token maybe we can make an exchange with this request so this is like a request so if we good to have the guards cost reduced in the EVM newarker for more security would be nice so we use I'll be I'm 128 right now would be nice to move to be LS the one that seeker uses and that means we could reuse a bunch of they're a bunch of their signature schemes and stuff like that and a bunch of their tools and we can all just be working on the same curve that would be great and it would be good to have a hash function pre-compile that that's efficient inside the snark something like Patterson commitments that'll be cool ok that's it ok [Applause] okay so um do we have time for questions yeah we have time for maybe one or two questions okay if people want to ask me more questions I'll just hang out outside for a little while and we can talk okay okay so who has any questions yeah you mentioned one possible use case is quadratic voting and I'm wondering if you have any like tight design ideas about how you can ensure that someone doesn't have create multiple identities in order to skew quadratic voting okay so there's like there's like some ideas about this one thing we could do is and it's a bit creepy as we could use like we could use biometrics in order to limit the amount of people who are able to join our group but this is this has problems too because people can just make fake biometrics yeah so we'd have to have some kind of real-world biometric testing station and that's not really very I don't know that has some problems it's game of all the other thing is that we can have a we can have this kind of these kind of parties where everyone comes and you everywhere every attendee is able to join the group but but that kind of limits us because every attendee you could just get your friends to come and take their take their keys or take their position in the group another thing that we could do is we could have this like really high barrier to entry and say that you have to have accomplished X Y inside in order to join but that's not very good either because I mean sort of limits the amount of people that can join and can be sort of commit to it so yeah I I mean it's sort of it's a difficult problem I think and it's but it's one that's important to sort of figure out and solve so I think a good approach would be to do like some sort of trusted Hardware with with some sort of biometric database or something like that I mean it's it's not very it's not very nice but if we need to do something like that we could do that yeah the white t-shirt he asked first and then is the stuff that stock wear is working on could that potentially improve the efficiency of this there's a completely different right so they would improve they would they're proving time but I they would prove improve the pooping time but currently the proves are a little bit big on it still I mean I'm totally interested in and seeing what they have when when they sort of when they're ready for that but it's still it's still moving forward I guess it would be good to talk to you who's here he sort of has some more more ideas about that yeah okay cool sorry that's my time if anyone wants to talk I'll be outside yeah pour like the next you